logo标签列表

如何赢得这个游戏？（关于IT技术方面的问题）

algorithmgame-theory
7

我们有一个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）的情况下，先手方获胜。
我的问题是，是否有一种策略可以让玩家在所有情况下赢得比赛？他应该先手吗？

P.S

我认为这与动态规划或分治等策略有关，但我还没有想到一个好的主意。所以我在这里发布了它。
感谢sdcwc's link提供的帮助。对于大于1×1的表格，第一位玩家将获胜。证明如下：（摘自维基百科页面）
事实证明，对于任何大于1×1的矩形起始位置，第一位玩家都可以获胜。这可以通过使用策略窃取论来证明：假设第二位玩家对任何初始第一位玩家的移动都有一个获胜策略。然后假设第一位玩家只拿右下角的方块。根据我们的假设，第二位玩家有一个响应，可以强制获胜。但是，如果存在这样的获胜响应，第一位玩家可以将其作为他的第一步，并因此强制获胜。因此，第二位玩家无法有获胜策略。
而策略游戏定理则保证了存在这样一种获胜策略。
1
虽然这是一个有趣的思维练习，但至少按照目前的写法，把它称为与编程相关似乎有些牵强。 - goldPseudo
1
一个二维的尼姆游戏？有趣。 - Jeffrey Hantin
2
参见：http://en.wikipedia.org/wiki/Chomp - sdcvvc
2
你应该将它作为答案返回。 - jk.
1
@Zellux 你应该在证明中加入 Zermelo 定理的信息。 - Andreas Brinck
显示剩余9条评论
4个回答
8
这个游戏被称为Chomp。第一个玩家获胜，查看链接以了解他的策略（非建设性）。
1
这是一个Python程序，如果允许先手，它将赢得大于1x1的棋盘（但对于大于10x10的棋盘来说速度相当慢）：
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!
0
一个想法是：如果棋盘是2x2，第一个玩家就输了：实际上，从这个棋盘开始：
O O 
O O

有两种变体（a和b）：

a.1)

1 1
O O

a.2) 第一个玩家输了

1 1
O 2

或者，b.1）

1 O
O O

b.2) 第一个玩家输了

1 2
O 2

在这一点上，策略归结为将棋盘变成2x2的正方形；然后，第一个进入该棋盘的人将会输掉比赛。这将引导你进入策略的第二步，主要是：

如何确保自己不是那个进入这种局面的人？

或者，

有多少种局面可以让我从一个更大的局面得到这样的局面呢？例如，从一个3x3的棋盘开始：

O O O
O O O
O O O

根据谁先开始和有多少个被无效的策略，有几种不同的策略；我建议在这个阶段使用遗传算法来探索最佳解决方案（很有趣！相信我）：)

你的棋盘编号似乎与问题不同？b.1 看起来像是一步非法的动作？ - jk.
@jk：哦，我的天，你说得对。我一直以为你只能取出行或列，从来没有想过可以取出一个正方形区域。糟糕。 - lorenzog
0

这很类似于经常使用火柴（我记不起名称）玩的游戏。

无论如何，我认为谁赢取决于棋盘的形状。2 * 2对于第二个玩家来说是明显的失败，而2 * N则通过将棋盘缩小到2 * 2并强迫另一个玩家参与游戏而明显地输给第一个玩家。 我认为所有正方形棋盘都是第二个玩家获胜，而长方形则是第一个玩家获胜，但尚未证明。

编辑：

好的，我想对于正方形棋盘，p1总是选择2,2然后平衡行和列，确保p2失败。

与sdcwc的评论一样，长方形棋盘也是第一位玩家的胜利。只有退化的1 * 1棋盘是第二位玩家的胜利。

1
为什么2*2是第二个玩家的胜利？第一个玩家拿走(2,2)，然后第二个玩家就会输。 - ZelluX
实际上，通过玩(2,N)，2*N是第一位玩家的胜利。第二个玩家无法避免第一个玩家始终使列的一对恰好比第二个大1。这意味着第二个玩家最终将被困在最后一列的最后一块棋子中。 - Paul Hsieh
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接