Как выиграть эту игру?

Question

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

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

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) тот, кто первым выигрывает.

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

P.S

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

Ответ

Благодаря sdcwc's link. Для таблиц размером больше 1 * 1 победит первый игрок. Доказательство следовать: (заимствовано из вики-страницы)

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

И Zermelo's theorem обеспечивает существование такой выигрышной стратегии.

Answer 1

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

Answer 2

Вещь, которая приходит на ум: если доска 2х2, первый игрок проигрывает: в самом деле, с этой платы:

O O 
O O 

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

A.1)

1 1 
O O 

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

1 1 
O 2 

или, стр.1)

1 O 
O O 

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

1 2 
O 2 

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

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

или

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

O O O 
O O O 
O O O 

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

Answer 3

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

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

Edit:

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

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

Answer 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!