电脑是如何下五子棋的?

前言

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

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

正文

婧婧是个很聪明的女孩子,和她下五子棋我老是输。于是便写了一个下五子棋的电脑程序,她果然下不过我写的程序。我指着屏幕上大大的提示文字“很遗憾,您输给了 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 是什么原理,等我学会了再讲给你听。

婧婧:好的呀。

后记

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

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

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


  1. 《Conversations on Chemistry》,在 https://www.gutenberg.org/ebooks/26908 可以免费阅读电子版。 ↩︎
  2. Designing an Authentication System: a Dialogue in Four Scenes ↩︎

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

17 + 10 =