1.5　游戏的深奥程度与“先下手为强”定理

在本章的最后一节，将介绍一个案例，来说明游戏是无法用一根筋思路进行的。

我们来看看一种叫Chomp[1]的游戏（以下的内容基于文献[13]和[19]）。

Chomp的规则：

·在大小为m×n的长方形巧克力板上，两位玩家轮流啃下去。

·两位玩家轮流自选一块还剩下的巧克力，并把它右上边的所有巧克力啃走。

·最左下角的巧克力被涂了毒，所以谁啃到了就算输。

图1.2展示了4×6规格的Chomp游戏的前两步。

图1.2　Chomp游戏示意

这个游戏很简单，关键在于先下手为强。比如可以思考一下以下的必胜法。

·n×n的Chomp：先下手的玩家一开始不要去啃一大块正方形，而是在纵横向中正方形小块比较少的那一列或那一排，一列列或一排排地啃下去。

·2×n的Chomp：先下手的玩家直接啃右上角的一块就可以赢。

然而不管什么形状的Chomp，先下手为强的必胜法则可以归纳如下。

1）先手或后手，必然有一方会有必胜法则[2]。

2）假设后手会有必胜法则。

3）那么接下来，先手的第一步只啃下右上角一块，后手应该有相应的对应手段X。

4）在这种情况下，如果先手第一步就采取了手段X，那么先手会进入必胜状态，这是矛盾的。

5）那么，有必胜法则的是先手。

这种证明方法称为“战略盗用法”。有趣的是，这看起来证明了必胜法则的存在，但实际上根本不知道具体的取胜方法。

不管对于什么尺寸的Chomp游戏，大家都知道“想要取胜的第一步总是单一的”这样的猜想。这个猜想的确会在n为100以下的3×n的Chomp游戏中成立。但到后来还是找到了一个反例。反例中最小的情况出现在8×10的Chomp游戏中，如下所示。

·留下5列8行和5列4行。

·留下8列8行和2列3行。

关于这个内容，会在后面章节的关于利用AI的游戏搜索法的描述中得到确认。

我们在这里再思考一下另一个游戏例子——约数游戏。以下是这个游戏的简介。

约数游戏的规则：

·先固定一个正整数n。

·两位玩家轮流说出一个n的约数。

·已经说过的数的倍数是不可以说的。

·最后不得不说“1”的那一方算输。

根据战略盗用法，这个游戏也能体现出先下手的那一方必胜。

对于这样一个单纯的游戏，实际上也并非解开了所有的胜利方法。应当注意的是，如果在约数游戏中设为n=pa·qb，那么就会变成和Chomp一样的游戏（条件：p和q必须是不同的素数）。比如说图1.2的Chomp和n=p3·q5约数游戏是相同的。如果可以写成n=pa·qb的形式，玩家可以说的数字需要是pi·qj的形式，i和j至少有一个要比前面的数小（0≤i≤a或0≤j≤b）。这样就相当于（a+1）×（b+1）尺寸的Chomp游戏了。

两位玩家交替出手的游戏称为“交互式双人游戏”。国际象棋、黑白棋、井字棋就属于这一类游戏。对于交互式双人游戏，以下定理是成立的（参考文献[30]）。

策梅洛定理：对于交互式双人游戏来说，要么先手拥有必胜法则，要么后手拥有必胜法则，要么双方尽了最大的努力达成平局。

利用这个定理可以导出以下结果。

·先手在没有禁招的五子棋游戏中必胜。

·井字棋游戏中会平局。

·后手在6×6的黑白棋游戏中必胜。

·西洋跳棋游戏中会平局[73]。

然而，对于通常的8×8的黑白棋、国际象棋以及围棋，确认必胜法则至今还很困难。关于这一点请参考文献[30]。

接下来的章节会说明如何使用AI手法高效地解开这些游戏以及谜题。

[1] Chomp在英语中表示咀嚼的意思。

[2] 这可以用矛盾法证明，而不是用排除法［19］。