电脑是如何下五子棋的？

前言

我报名参加了科学声音组织的知识写作培训班，本文是第十讲的课后作业。作业题目是：找一本枯燥的教科书，从里面选取一段晦涩难懂的知识，用通俗易懂的文字重新讲述一遍。

注意本文是科普文，预期读者是没有编程和算法基础的普罗大众，不会涉及算法的具体实现。另外，考虑到五子棋在我国极为流行，很少有不会下五子棋的人，故假设本文的读者懂得五子棋的基本规则。

正文

婧婧是个很聪明的女孩子，和她下五子棋我老是输。于是便写了一个下五子棋的电脑程序，她果然下不过我写的程序。我指着屏幕上大大的提示文字“很遗憾，您输给了 Werner 写的电脑程序”，说：“这个程序注入了我的灵魂，你下不过它便相当于下不过我。”婧婧听了向我翻白眼：“哼，我又不是三岁的小孩，信你个鬼。”我尴尬地笑了笑。婧婧接着说：“确实很神奇哎，电脑又没有灵魂，是怎么下棋的？”我解释：”简单地讲，电脑会列出所有可能的走法，然后选出其中最好的走法。”“原来是这样呀”，婧婧说，“可我觉得自己没有真正理解。”看来婧婧不满足于空泛的解释，而是追求实质性地理解。于是我问：“详细解释得花些时间，还得认真思考，愿意听吗？”“当然愿意！”于是有了下面的对话。

我：请先思考一下，自己是如何下棋的。

婧婧：想落子到哪里，就用鼠标点一下。

我：别闹。我指的是如何决定下一颗棋子应该落在哪里。

婧婧：嗯，我一般会先观察对手的棋，如果对手已经有连在一起的三个子，或四个子，就堵掉。如果没有，就设法增加自己的“势”，同时试着减少对手的“势”。

我：啊，这就是高手的世界吗！你说的“势”是什么呀？

婧婧：是个比较玄乎的东西，应该是种感觉，就是看上去觉得形势大好，或形势不妙。

我：形势大好，形势不妙具体是什么意思？

婧婧：呃，大概是……觉得接下来自己有很多地方可以连成三个子，或四个子，这样我会觉得形势大好，而如果对手有很多地方可以连成三个子，或四个子，我就会觉得形势不妙。

我：其实电脑下棋也是差不多的。

婧婧：电脑也懂“势”吗？

我：电脑懂另一种“势”，不玄乎、可以计算的“势”，我把它叫做局势。

婧婧：局势？听着一样玄乎。

我：不是的，局势一点也不玄乎，甚至可以计算。

婧婧：怎么算的？

我：假设电脑执黑子，它要计算局势，就会数棋盘上黑子有多少个三，比方说，一个两头活的三加 700 分，一头活的三加 200 分，两头都堵死的三不加分。

婧婧：为何只数三？不数二或四？

我：别着急，我还没说完。当然要数二和四，一个活二，比方说加 120 分吧，两头活的四基本就意味着赢棋了，加个 4000 分好了。

婧婧：中间有间隔的三或四呢？算分吗？

我：有间隔？什么意思？

婧婧：不是三个子连在一起，而是两个子连在一起，空一个，又有一个子。和连三效果一样。

我：这种当然也算分了，和连三有一样的得分。

婧婧：那五呢？

我：五当然值更多分了，比方说就值 50000 分吧。

婧婧：可是出现连五意味着棋局已经结束了呀！

我：已经结束的棋局也可以计算局势嘛，为什么不可以呢？只不过没法再落下一子而已。

婧婧：好吧。

我：电脑会数棋盘上所有黑子的二、三、四、五，横着，竖着，斜着的都数，这样就能算出一个黑子的总分来。能理解吗？

婧婧：能。

我：接着电脑会用同样的方法算出一个白子的总分来。因为我们假设了电脑执黑子，所以局势最终得分便是黑子总分减去白子总分。

婧婧：哦，这样算的呀。

我：很简单吧。这样我们就量化地计算了局势。

婧婧：局势有可能是个负数？

我：没错，如果是负数就表示白子占优势，黑子不占优势。

婧婧：明白了。

我：总之呢，对于任意一盘棋，电脑总可以算出一个局势得分。请先确保自己理解这一点。

婧婧：我理解是怎么计算的。但有个疑问，什么情况加多少分是怎么确定的？

我：总体来说是由五子棋的规则确定的。比如五子连珠就赢了，所以连五有最高的得分，连四离胜利不远了，所以四的得分比三高，三比二得分高也是同样的道理。具体加多少分就由写程序的人自己决定了，所以我才说这个程序注入了我的灵魂。

婧婧：好的吧。

我：还有问题吗？

婧婧：没有了。

我：好，我们继续。仍假设电脑执黑子，婧婧在和电脑下棋，下了一半，现在该电脑走了，电脑该如何决定下一子落到哪里呢？

婧婧：啊，我好像明白了。电脑可以列出下一步所有可能的走法，棋盘就那么大，走法总是有限的，然后计算每种走法落子之后的局势得分，比较所有局势得分，选择局势得分最大的那种走法。

我：婧婧真聪明！就是这样的。

婧婧：就这么简单？

我：呃，实际情况比这再稍稍复杂一点点。

婧婧：好吧，果然没这么简单。

我：用你刚刚的描述，电脑是可以下棋的。但水平会很差，约等于刚学会下棋的小孩，毕竟只盯着眼前的利益。

婧婧：实际情况是怎样的呢？

我：请在脑海中想象一棵树，一棵只有主干的树，把目前的棋局挂在这棵树的主干上。接下来轮到电脑走，假设总共有 n 种不同的走法，则这棵树干将向上长出 n 根树杈，每根树杈上都挂着一局棋，每局棋与主干上的棋局相比都只多落了一颗黑子，且每根树杈上的棋局各不相同。

婧婧：想好了。

我：目前这棵树只有主干和一级树杈。一级树杈代表的是黑子的不同走法，对吧？

婧婧：对的，有点啰嗦哦。

我：这里很重要，又很抽象，我怕自己说不清楚，就多说几句。

婧婧：我听懂了。

我：好。接着随便选一根树杈，也就是电脑随便选一种走法，电脑走后该婧婧走了。假设这时婧婧有 m 种不同的走法，则这根树杈将又向上长出 m 根二级树杈，每根二级树杈上都挂着一局棋……

婧婧：每局棋与那根一级树杈上的棋局相比都只多落了一颗白子，且每根二级树杈上的棋局各不相同，对吧？

我：对的对的，就是这样。每根一级树杈都会长出很多二级树杈，每根二级树杈又都会长出很多三级树杈，以此类推，除非某局棋有某方获胜了，或者棋盘被摆满了，才不会继续生长。

婧婧：这将是一棵好大好大的树。我好像又明白了，电脑只要计算出这棵树，选择最终自己会获得胜利的树杈就可以了。可是不对啊，这样就不需要计算局势得分了。

我：这棵树非常、非常、非常大，以至于就算是电脑也没办法一下子全部都计算出来。实际上电脑一般只用计算几级树杈，就足够下赢普通人了。

婧婧：哦，原来是这样。只计算几级树杈可能还没有到棋局结束，所以需要计算局势得分，选择得分最高的树杈。

我：就是这样的。

婧婧：这下我明白电脑是怎么下棋的了。

我：不，你还没有彻底明白。

婧婧：我彻底明白了。

我：不，你没有。还差最后一点。

婧婧：哪一点？

我：让我来举个例子。假设一级树杈只有两根，记作 A 和 B，A 得分 500 分，B 得分 800 分，如果只计算一级树杈，电脑该选择哪种走法呢？

婧婧：当然是 B 了，因为 B 得分高。

我：没错。但只计算一级树杈太蠢了，来计算两级。在刚刚例子的基础上，假设 A 和 B 又各自有两个分叉，记作 A1、A2 和 B1、B2，局势得分分别是 300 分、200 分、900 分和 -100 分。那么此时电脑该选择哪种走法呢？

婧婧：嗯，300 和 200 是走 A 之后的得分，900 和 -100 是走 B 之后的得分。应该还是选 B 吧，因为走了 B 就可以接着走 B1，走到局势得分为 900 分的棋局。

我：可是走了 B，接下来就该对手走了，对手才不会走 B1，一定会选择 B2 的呀。

婧婧：啊！是的哎，对手一定会选电脑局势得分最小的走法。

我：没错。当轮到我走的时候，会选局势得分最大的走法，而轮到对手走的时候，会选局势得分最小的走法。婧婧可以重新回答刚刚的问题吗？

婧婧：可以。二级树杈轮到对手走，A1 300 分，A2 200 分，对手一定会选 A2， B1 900 分、B2 -100 分，对手一定会选 B2。这样想的话，选 A 最终得分一定是 200 分，选 B 最终得分一定是 -100 分，和 A、B 这两根树杈上挂的棋局的局势得分完全不同！

我：当然不同，因为目光更长远了。

婧婧：所以目光长远些就应该选 A 而不是 B。

我：是的。你知道只计算一级和只计算二级树杈该怎么决定下一步选哪个，便也就学会了只计算三级、四级、五级树杈时怎么决定下一步选哪个。对吧？

婧婧：对的，最大值、最小值、最大值、最小值的顺序选。我想知道你的程序会计算几级树杈？

我：它计算了七级树杈。

婧婧：我下棋大概能看两三步吧，怪不得下不赢。这下我总算理解电脑是怎么下五子棋的了。

我：不是程序员能理解到这个程度已经很棒了。

婧婧：如果是程序员呢？

我：至少还得知道 Alpha-Beta 剪枝和 Zobrist 哈希吧。

婧婧：那是啥？AlphaGo？

我：不不不，和 AlphaGo 没关系，是编程实现的东西，你不用管。

婧婧：好吧。电脑是怎么下围棋的？和五子棋一样吗？AlphaGo 的原理是什么？

我：可以用和下五子棋一样的思路写下围棋的程序，但效果不好。因为围棋的局势很难评估，而且每一步的变化也很多。我不知道 AlphaGo 是什么原理，等我学会了再讲给你听。

婧婧：好的呀。

后记

为了通俗易懂地讲解电脑是如何下五子棋的，我虚构了两个人物和一次对话。对话体非常好用，从古希腊开始，柏拉图的《理想国》就采用了对话体，差不多同时代的《论语》也可以算作对话体，伽利略的著作书名直接是《关于托勒密和哥白尼两大世界体系的对话》，对法拉第产生了很大影响的科普书是《化学对话》¹，在信息安全领域，MIT 为了说明如何设计安全的认证系统 Kerberos，才采用了对话体²。

对话中体现的知识是局势评估和极大极小搜索，比较专业的资料可参考《对弈程序基本技术》中的《评价函数》和《最小-最大搜索》。

实际上我从没有写过五子棋 AI，倒是写过一种四子棋的 AI，和五子棋差不多。不过因为这种四子棋是某家公司的发明，为避免无意中侵犯专利，就没有公开。