algorithm - 如何赢得这场比赛？

Question

支持我们有一个 n * m 的 table ，两个玩家玩这个游戏。它们依次排除细胞。玩家可以选择一个单元格 (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)种情况下，先下的一方获胜。

我的问题是，是否有任何策略可以让玩家在所有情况下都赢得比赛？他应该先上场吗？

附言

我认为它与动态规划或分而治之之类的策略有关，但还没有想到。所以我把它贴在这里。

答案

感谢sdcwc's link .对于大于 1*1 的 table ，第一个玩家获胜。证明如下:(从维基页面借来的)

It turns out that for any rectangular starting position bigger than 1 × 1 the 1st player can win. This can be shown using a strategy-stealing argument: assume that the 2nd player has a winning strategy against any initial 1st player move. Suppose then, that the 1st player takes only the bottom right hand square. By our assumption, the 2nd player has a response to this which will force victory. But if such a winning response exists, the 1st player could have played it as his first move and thus forced victory. The 2nd player therefore cannot have a winning strategy.

和Zermelo's theorem确保这种制胜战略的存在。

Answer 1

这个游戏被称为Chomp .第一个玩家获胜，查看他的策略链接(非建设性)。