第二章 计算机是如何学会下棋的

下棋一直被认为是人类的高智商游戏，从人工智能诞生的那一天开始，研究者就开始研究计算机如何下棋。著名人工智能学者、图灵奖获得者约翰·麦卡锡在 50 年代就开始从事计算机下棋方面的研究工作，并提出了著名的 α-β 剪枝算法。很长时间内，该算法成为了计算机下棋程序的核心算法，著名的国际象棋程序深蓝采用的就是该算法框架。

一、可以穷举吗？

1. 棋类人机大战简史

• 1996 年，正值人工智能诞生 40 周年之际，一场举世瞩目的国际象棋大战在深蓝与卡斯帕罗夫之间举行，可惜当时的深蓝功夫欠佳，以 2:4 的比分败下阵来。1997 年，经过改进的深蓝再战卡斯帕罗夫，这次深蓝不负众望，终于以 3.5:2.5 的比分战胜卡斯帕罗夫，可以说是人工智能发展史上的一个里程碑事件。

• 到了 2006 年，为了庆祝人工智能诞生 50 周年，中国人工智能学会主办了浪潮杯中国象棋人机大战，先期举行的机器博弈锦标赛获得前 5 名的中国象棋系统，分别与汪洋、柳大华、卜凤波、张强、徐天红 5 位中国象棋大师对弈，人机分别先行共战两轮 10 局比赛，双方互有胜负，最终机器以 11:9 的总成绩战胜人类大师队。

• 转眼到了 2016 年，又值人工智能诞生 60 周年，人工智能的发展已不可同日而语，呈现出蓬勃发展之势。沉默多年的计算机围棋界突然冒出个 AlphaGo，先是 4:1 战胜韩国棋手李世石，转年又战胜我国的柯洁。至此，在计算机下棋这个领域，机器已经完全碾压人类棋手，机器战胜人类最高水平棋手已无任何悬念。

• 三次重要事件均与人工智能提出的秩年有关，三大棋类机器战胜人类顶级棋手的时间顺序也刚好与三大棋类可能出现的状态数的多少一致，这也许只是一种巧合，在本章可以看到，状态数的多少并不是棋类难度的主要问题。

2. 分钱币游戏

• 分钱币游戏是这样的，桌上有若干堆钱币，每次对弈的一方选定一堆钱币，并将该堆钱币分成不等的两堆，这一过程称为行棋。甲乙双方轮流行棋，直到有一方不能行棋为止，则对方取胜。下图给出了初始状态为 8 个钱币的例子，图中给出了该问题所有可能的走法。

• 假设甲方先行行棋，甲方可以将 8 枚硬币分成（6，2）两堆，或者（5，3）两堆，或者（7，1）两堆，但不能分成（4,4），因为这是分成了相等的两堆，这是规则所不允许的。下一步轮到乙方行棋，“1”这堆不能选，因为无法分成两堆，“2”这堆也不能选，因为不能分成不相等的两堆，“6”、“5”、“7”都是可选的，但是要注意“6”只能分成（4，2）或者（5、1），而不能分成（3，3），因为（3，3）是相等的两堆。按照这样的原则，在图中给出了所有可能的行棋方法。
• 甲方如果按照红色箭头走成（7，1），则乙方只能选择“7”这堆，将“7”分成（6，1）或者（5，2）或者（4，3），也就是图中按照黄色箭头得到（6，1，1）、（5，2，1）、（4，3，1）。无论对于这三种情况的哪一种，甲方都可以按照红色箭头选择行棋到（4，2，1，1），比如乙方行棋到了（6，1，1），则甲方将“6”分成（4，2），如果乙方走的是（5，2，1），则甲方将“5”分成（4，1）即可。而一旦甲方走到了（4，2，1，1），则乙方只能行棋到（3，2，1，1，1），这时甲方只需将“3”分成（2，1），得到（2，2，1，1，1，1），则乙方无棋可走，必输无疑。也就是说，对于这样一个分钱币游戏，甲方是存在必胜策略的。
• 只要甲方走棋正确，乙方无论如何是不可能获胜的。
• 对于分钱币游戏这样的简单问题，或者再稍微复杂一点的游戏，依靠穷举所有可能的方法也许可以找到必胜策略，但是对于象棋、围棋这样的变化非常多的棋类，是不可能穷举其所有可能性的。这也是目前在一些人中存在的误解，认为现在计算机速度这么快，存储这么大，对于国际象棋、中国象棋这样的棋类，完全可以依靠穷举战胜人类。其实这是非常错误的看法。

• 以中国象棋为例分析一下。在考虑不同的走棋顺序的情况下，总的状态数大约为 $10^{150}$ ，假设 1 毫微秒可以产生一个状态，则产生出这些状态大约需要 $10^{134}$ 年。这是什么概念呢？从存储上考虑，地球上的原子总数约 $10^{50}$ 个，如果一个原子可以存储一个状态的话，则需要 $10^{100}$ 个地球才有可能存储得下这些状态。从时间上考虑，按照宇宙大爆炸的理论推算，宇宙年龄大概为 $1.38\times 10^{10}$ 年，假设从宇宙诞生那一刻起就有一台高速计算机以每毫微秒生成一个状态的速度在运算，到目前为止也只产生了其中的 $1.38\times 10^{-124}$ %，也就是 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000138%。

• 中国象棋的状态数特别大，依靠穷举所有可能的状态获得必胜策略的想法是行不通的。

• 国际象棋的状态数稍微少一些，但也没有质的差别，围棋状态数则更多。

• 所以结论就是不能靠穷举出所有可能状态的方法找到必胜的行棋策略。

3. 总结

• 棋类历史上有过三次著名的人机大战事件。大家对计算机围棋系统 AlphaGo 战胜李世石、柯洁，计算机国际象棋系统深蓝战胜卡斯帕罗夫比较熟悉，在这两次人机大战之间，我国的五套计算机中国象棋系统战胜了人类五位中国象棋大师，也是人工智能发展史上的一件大事。

• 在一些人中经常有这样的误解：认为现在计算机速度这么快，存储这么大，对于国际象棋、中国象棋这样的棋类，计算机完全可以依靠穷举出其所有可能状态的方法战胜人类，这是非常错误的看法。无论是国际象棋还是中国象棋，由于其可能出现的状态数过于庞大，是不可能通过穷举所有可能状态的方法找到必胜策略的。三次人机大战均与人工智能提出的秩年有关，三大棋类机器战胜人类顶级棋手的时间顺序也刚好与三大棋类可能出现的状态数的多少一致（按照可能的状态数多少从小到大排序依次为国际象棋、中国象棋和围棋），这也许只是一种巧合。

二、极大-极小模型

• 下象棋的人，在下棋时是如何考虑走哪步棋的？
• 在轮到自己行棋时，自己会考虑有哪几种下法，再考虑对于自己每种下法对方会如何考虑，自己再如何考虑……，然后看几步棋之后的局面如何，再选择一个自己认为好的走步。职业棋手能考虑到 7、8 步。
  

1. 极大-极小模型

• 这个思考过程可以用下图来示意。图中最上方的方框表示当前棋局，轮到甲方行棋，甲方考虑自己有 a 和 b 两种走法，下一步轮到乙方行棋，针对棋局 a，乙方可以有 c、d 两种走法，而对于 b，乙方可以有 e、f 两种走法。下一轮又该轮到甲方行棋……。假设甲方只思考了 4 步棋，则形成了下图的搜索图，最后一行就是双方四步后可能出现的棋局。从甲方的角度来说，他希望最后走到一个对自己有利的局面，而对乙方来说他也希望走到一个对乙方有利的局面。

• 假设局面是否有利可以用一个分值表示，大于 0 的分值表示对甲方有利，而小于 0 的分值表示对乙方有利，等于 0 则表示双方势均力敌，是一个双方都可以接受的局面。我们从倒数第二行的圆圈开始考虑，这一行应该轮到乙方行棋。比如对于节点 g，乙方可以有两个选择，一个可以得到分值 0，一个可以得到分值 5。由于分值越小对乙方越有利，所以乙方肯定会选择走获得 0 分值的那一步，而不会选择走获得 5 分值的那一步。对于节点 h 也同样，乙方肯定会选择获得-3 分值的那一步。这一行的其他节点也一样，都是从其子节点中选择获得分值最小的那步棋。所以我们可以总结为，对于这一层来说，乙方总是选择具有极小值的节点作为自己的走步。图中倒数第二行节点边标的数字就是乙方所获得的分值。
• 我们再看倒数第三行的方框，这一行应该轮到甲方行棋。甲方刚好与乙方相反，他肯定会选择子节点中分值最大的那步棋。比如对于节点 c，甲方可以选择走到 g，可以获得 0 分值，也可以选择 h 获得-3 分值。由于分值越大对甲方越有利，甲方只会选择行棋到 g 获得 0 分值，而不会选择 h 获得-3 分值。这一行的其他节点也同样，图中标出了其他节点可以获得的分值。
• 最后我们再看 a、b 两个节点。这两个节点又轮到乙方行棋。乙方同样会从其子节点中选取分值小的节点作为走步，这样 a 可以获得 0 分值，b 可以获得 1 分值。而 a 和 b 是当前局面下可能的两个选择。如果选择 a，无论对方如何行棋，甲方都可以获得至少 0 分值，如果选择 b，无论对方如何行棋，甲方都可以至少获得 1 分值。虽然 0 分值对于甲方也是可以接受的，但是 1 分值结果会更好。所以经过这么一番思考后，甲方决定如图中红色箭头所示的，选择行棋到 b。这是一个模仿人类下棋的过程。
• 对于最后可能形成的局面人类只是大概估计一下是否对自己有利。这里之所以用数字表示，一方面是为了量化局面的有利程度，另一方面是为了以后用到计算机下棋上，计算机处理的话，必须表示为数字。
• 由于这种方法一层求最小值、一层求最大值交替进行，所以称作极小-极大模型，是通过模仿人类的下棋过程得到的一个模型。其中求最小值的节点称作极小节点，求最大值的节点称作极大节点。
• 上面说的这些内容，都是甲方为了走一步棋，而在他大脑内的思考过程，并不是甲乙双方真的在行棋。经过一番这样的思考后，甲方选择一步行棋，等待乙方下完一步棋后，甲方再根据乙方的行棋结果再次进行这样的思考。所以上述极小-极大模型只是描述了甲方走一步棋的过程。

2. 限定深度就可以穷举吗？

• 计算机就是采用这种办法下棋的吗？
• 还不是，因为这样做的话，对于实际的下棋过程计算量还是非常大的。以下国际象棋的深蓝为例，基本上要搜索 12 步，搜索树的节点数在 1018 量级，据估算，即便在深蓝这样的专用计算机上，完成一次搜索也需要大概 17 年的时间，所以这个极小-极大模型只是用来描述这样一种模拟人类下棋的过程，并不能真的用于计算机下棋，一些简单的棋类或许可能可以。

3. 总结

• 人类在下棋的过程中，一般是通过向前考虑若干步的方法找到自认为比较好的走法。受人类棋手下棋过程的启发，提出了计算机下棋的极小-极大模型。该模型是在有限搜索深度内穷举出所有可能的状态，从中找出一个在该搜索深度内的最好走法。
• 由于搜索深度越深计算机下棋的水平越高，极小-极大模型虽然限制了搜索的深度，但是对于真实的棋类问题，要达到与人类大师抗衡的水平，还是因为计算量过大，耗时过多而不能满足实际要求。以深蓝为例，搜索深度限制为 12 步，用极小-极大方法实现的话，完成一次搜索需要耗时 17 年时间。这显然是不现实的。