Как победить в этой игре?

Question

Как победить в этой игре?

Поддержка у нас есть n * m стол, и в эту игру играют два игрока. Они исключают клетки по очереди. Игрок может выбрать ячейку (i, j) и исключить все ячейки от (i, j) до (n, m), а тот, кто исключает последнюю ячейку, проигрывает игру.

Например, на доске 3*5 игрок 1 исключает ячейку (3,3) - (3,5), а игрок 2 исключает (2,5) - (3,5), текущая доска выглядит следующим образом: (O означает, что ячейка не исключена, а x означает, что она исключена)

3 O O x x x
2 O O O O x
1 O O O O O
  1 2 3 4 5

и после того, как игрок 1 исключает ячейки из (2,1) в (3,5), доска становится

3 x x x x x
2 x x x x x
1 O O O O O
  1 2 3 4 5

Теперь игрок 2 исключает ячейки из (1,2) в (3,5), что оставляет только (1,1) чистым:

3 x x x x x
2 x x x x x
1 O x x x x
  1 2 3 4 5

Таким образом, игрок 1 должен исключить единственную (1,1) ячейку, поскольку один игрок должен исключить хотя бы одну ячейку за ход, и он проигрывает игру.

Очевидно, что в случаях n*n, 1*n и 2*n (n >= 2) выигрывает тот, кто играет первым.

Моя проблема в том, есть ли какая-либо стратегия для игрока, чтобы выиграть игру во всех случаях? Должен ли он играть первым?

PS

Я думаю, что это связано со стратегиями, такими как динамическое программирование или "разделяй и властвуй", но пока не пришло к мысли. Поэтому я выкладываю это здесь.

Ответ

Благодаря ссылке sdcwc. За столами больше 1*1 выигрывает первый игрок. Доказательство следующее: (заимствовано из вики)

Оказывается, что для любой прямоугольной стартовой позиции, превышающей 1 × 1, 1-й игрок может выиграть. Это можно показать с помощью аргумента кражи стратегии: предположим, что у второго игрока есть выигрышная стратегия против любого начального хода первого игрока. Предположим, что 1-й игрок берет только нижний правый квадрат. По нашему предположению, у второго игрока есть ответ, который вызовет победу. Но если такой выигрышный ответ существует, 1-й игрок мог сыграть это как свой первый ход и таким образом принести победу. Поэтому у второго игрока не может быть выигрышной стратегии.

И теорема Цермело обеспечивает существование такой выигрышной стратегии.

7

algorithm game-theory

Источник

user111896 11 дек '09 в 08:34

4 ответа

Решение

Вот программа на Python, которая выиграет на досках размером более 1х1, если будет разрешено идти первыми (но она довольно медленная для досок размером более 10х10):

class State(object):
    """A state is a set of spaces that haven't yet been ruled out.
    Spaces are pairs of integers (x, y) where x and y >= 1."""

    # Only winnable states in this dictionary:
    _next_moves = {}
    # States where any play allows opponent to force a victory:
    _lose_states = set()

    def __init__(self, spaces):
        self._spaces = frozenset(spaces)

    @classmethod
    def create_board(cls, x, y):
        """Create a state with all spaces for the given board size."""
        return State([(r+1, c+1) for r in xrange(x) for c in xrange(y)])

    def __eq__(self, other):
        return self._spaces == other._spaces

    def __hash__(self):
        return hash(self._spaces)

    def play(self, move):
        """Returns a new state where the given move has been played."""
        if move not in self._spaces:
            raise ValueError('invalid move')
        new_spaces = set()
        for s in self._spaces:
            if s[0] < move[0] or s[1] < move[1]:
                new_spaces.add(s)
        return State(new_spaces)

    def winning_move(self):
        """If this state is winnable, return a move that guarantees victory."""
        if self.is_winnable() and not self.is_empty():
            return State._next_moves[self]
        return None

    def random_move(self):
        import random
        candidates = [m for m in self._spaces if m[0] > 1 and m[1] > 1]
        if candidates: return random.choice(candidates)
        candidates = [m for m in self._spaces if m[0] > 1 or m[1] > 1]
        if candidates: return random.choice(candidates)
        return (1,1)

    def minimal_move(self):
        """Return a move that removes as few pieces as possible."""
        return max(self._spaces, key=lambda s:len(self.play(s)._spaces))

    def is_winnable(self):
        """Return True if the current player can force a victory"""
        if not self._spaces or self in State._next_moves:
            return True
        if self in State._lose_states:
            return False

        # Try the moves that remove the most spaces from the board first
        plays = [(move, self.play(move)) for move in self._spaces]
        plays.sort(key=lambda play:len(play[1]._spaces))
        for move, result in plays:
            if not result.is_winnable():
                State._next_moves[self] = move
                return True
        # No moves can guarantee victory
        State._lose_states.add(self)
        return False

    def is_empty(self):
        return not self._spaces

    def draw_board(self, rows, cols):
        string = []
        for r in xrange(rows, 0, -1):
            row = ['.'] * cols
            for c in xrange(cols):
                if (r, c+1) in self._spaces:
                    row[c] = 'o'
            string.append(('%2d ' % r) + ' '.join(row))
        string.append('  ' + ''.join(('%2d' % c) for c in xrange(1, cols+1)))
        return '\n'.join(string)

    def __str__(self):
        if not self._spaces: return '.'
        rows = max(s[0] for s in self._spaces)
        cols = max(s[1] for s in self._spaces)
        return self.draw_board(rows, cols)

    def __repr__(self):
        return 'State(%r)' % sorted(self._spaces)

def run_game(x, y):
    turn = 1
    state = State.create_board(x, y)
    while True:
        if state.is_empty():
            print 'Player %s wins!' % turn
            return
        if state.is_winnable():
            move = state.winning_move()
        else:
            move = state.random_move()
        state = state.play(move)
        print 'Player %s plays %s:' % (turn, move)
        print state.draw_board(x, y)
        print
        turn = 3 - turn

def challenge_computer(x, y):
    state = State.create_board(x, y)
    print "Your turn:"
    print state.draw_board(x, y)
    while True:
        # Get valid user input
        while True:
            try:
                move = input('Enter move: ')
                if not (isinstance(move, tuple) and len(move) == 2):
                    raise SyntaxError
                state = state.play(move)
                break
            except SyntaxError, NameError:
                print 'Enter a pair of integers, for example: 1, 1'
            except ValueError:
                print 'Invalid move!'
            except (EOFError, KeyboardInterrupt):
                return
        print state.draw_board(x, y)
        if state.is_empty():
            print 'Computer wins!'
            return
        if state.is_winnable():
            move = state.winning_move()
        else:
            move = state.minimal_move()
        state = state.play(move)
        print
        print 'Computer plays %s:' % (move,)
        print state.draw_board(x, y)
        print
        if state.is_empty():
            print 'You win!'
            return

if __name__ == '__main__':
    challenge_computer(8, 9)

И вывод из примера запуска:

$ python -c 'import game; game.run_game(8, 9)'
Player 1 plays (6, 7):
 8 o o o o o o . . .
 7 o o o o o o . . .
 6 o o o o o o . . .
 5 o o o o o o o o o
 4 o o o o o o o o o
 3 o o o o o o o o o
 2 o o o o o o o o o
 1 o o o o o o o o o
   1 2 3 4 5 6 7 8 9

Player 2 plays (4, 8):
 8 o o o o o o . . .
 7 o o o o o o . . .
 6 o o o o o o . . .
 5 o o o o o o o . .
 4 o o o o o o o . .
 3 o o o o o o o o o
 2 o o o o o o o o o
 1 o o o o o o o o o
   1 2 3 4 5 6 7 8 9

Player 1 plays (5, 1):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 o o o o o o o . .
 3 o o o o o o o o o
 2 o o o o o o o o o
 1 o o o o o o o o o
   1 2 3 4 5 6 7 8 9

Player 2 plays (3, 7):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 o o o o o o . . .
 3 o o o o o o . . .
 2 o o o o o o o o o
 1 o o o o o o o o o
   1 2 3 4 5 6 7 8 9

Player 1 plays (4, 1):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 . . . . . . . . .
 3 o o o o o o . . .
 2 o o o o o o o o o
 1 o o o o o o o o o
   1 2 3 4 5 6 7 8 9

Player 2 plays (2, 3):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 . . . . . . . . .
 3 o o . . . . . . .
 2 o o . . . . . . .
 1 o o o o o o o o o
   1 2 3 4 5 6 7 8 9

Player 1 plays (1, 5):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 . . . . . . . . .
 3 o o . . . . . . .
 2 o o . . . . . . .
 1 o o o o . . . . .
   1 2 3 4 5 6 7 8 9

Player 2 plays (2, 2):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 . . . . . . . . .
 3 o . . . . . . . .
 2 o . . . . . . . .
 1 o o o o . . . . .
   1 2 3 4 5 6 7 8 9

Player 1 plays (1, 4):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 . . . . . . . . .
 3 o . . . . . . . .
 2 o . . . . . . . .
 1 o o o . . . . . .
   1 2 3 4 5 6 7 8 9

Player 2 plays (2, 1):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 . . . . . . . . .
 3 . . . . . . . . .
 2 . . . . . . . . .
 1 o o o . . . . . .
   1 2 3 4 5 6 7 8 9

Player 1 plays (1, 2):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 . . . . . . . . .
 3 . . . . . . . . .
 2 . . . . . . . . .
 1 o . . . . . . . .
   1 2 3 4 5 6 7 8 9

Player 2 plays (1, 1):
 8 . . . . . . . . .
 7 . . . . . . . . .
 6 . . . . . . . . .
 5 . . . . . . . . .
 4 . . . . . . . . .
 3 . . . . . . . . .
 2 . . . . . . . . .
 1 . . . . . . . . .
   1 2 3 4 5 6 7 8 9

Player 1 wins!

1

Источник

user64474 11 дек '09 в 12:17

Что приходит на ум: если на доске 2х2, первый игрок проигрывает: фактически с этой доски:

O O 
O O

Есть два варианта (а и б):

A.1)

1 1
O O

а.2) первый игрок проигрывает

1 1
O 2

или б.1)

1 O
O O

б.2) первый игрок проигрывает

1 2
O 2

в этот момент стратегия сводится к тому, что доска становится 2х2 в квадрате; тогда первый, кто войдет в эту доску, потеряет ее. Это приведет вас ко второму шагу вашей стратегии, в основном:

как убедиться, что вы не тот, кто входит в такую конфигурацию?

или же,

сколько конфигураций приведет меня к получению такой конфигурации, начиная с более крупной? Например, начиная с доски 3х3:

O O O
O O O
O O O

Есть несколько стратегий, в зависимости от того, кто начинает первым и сколько аннулируется; На этом этапе я предлагаю использовать генетический алгоритм, чтобы найти лучшее решение (это весело! Поверьте мне):)

0

Источник

user204634 11 дек '09 в 08:58

Это похоже на игру, в которую часто играют со спичками (не могу вспомнить название)

Во всяком случае, я думаю, что это зависит от формы доски, которая выиграет. 2*2 - это тривиальный проигрыш для второго игрока, а 2 * N - тривиальный проигрыш для первого, уменьшив доску до 2 * 2 и заставив другого игрока играть. Я думаю, что все квадратные доски являются победами второго игрока, в то время как прямоугольные - победы первого игрока, но пока не доказано

Редактировать:

Хорошо, я думаю, что для квадратной доски p1 всегда выбирает 2,2, а затем выравнивает строку и столбец, гарантируя, что p2 проигрывает

как и в случае с комментариями sdcwc, доски прямоугольников также являются первой победой игрока. только вырожденная доска 1 * 1 является победой второго игрока

0

Источник

user207716 11 дек '09 в 09:01

Другие вопросы по тегам algorithm game-theory

user100020 11 дек '09 в 09:18 2009-12-11 09:18 · Accepted Answer · 2009-12-11 09:18

Эта игра называется Chomp. Первый игрок выигрывает, см. Ссылку для его стратегии (неконструктивно).

8

Источник

user100020 11 дек '09 в 09:18