国际象棋引擎如何思考的

国际象棋引擎如何思考？这个问题还专门有人研究过，并且写了很大一篇的文章报告出现，国际象棋引擎如何思考想了解的小伙伴可以看看，很详细的介绍了里面的缘由

感谢、并致敬作者Horace，作为一个业余爱好者，他投入诸多心血、耗费很多个人时间才完成这篇大作。

原文来自chess24网站(chess24.com)，作者是西班牙特级大师Pepe Cuenca。他是格拉纳达大学(Granada
University)土木工程专业的本科毕业生，也拥有汉堡大学(University of Hamburg)的数学建模硕士学位和应用数学博士学位。

原文的网页链接为：

https://chess24.com/en/read/news/how-do-chess-engines-think

译文有删节。

不管是参加比赛还是在家训练，如果一位国际象棋棋手没有带着一台装着对弈引擎的电脑，那是很罕见的。

在过去，为了把一个复杂的局面分析透彻，多位特级大师需要聚集在一起研究几个小时甚至几天，尽管如此他们却常常以失败告终。那样的日子一去不复返了。

现在，只要几秒钟的时间，“机器”就能告诉我们任何局面下的最佳招法。而且这样得出的分析比棋王卡尔森更为可靠。

你知道这些引擎是如何工作的吗?他们是怎样在仅仅一瞬间就可靠地分析完无穷的变例呢?我自己参加了20年的比赛，却丝毫不懂这些怪兽们的工作原理。终于我忍不住好奇心，做了一些关于这个话题的搜索。在这篇文章里我们就尝试着理解一下引擎们的思考方式。也就是说探讨一些数学概念和主要的算法。

别害怕，我们不会走得太深，每个人都能理解。

他们如何工作：极小极大算法(Minimax algorithm)

国际象棋被称为“零和游戏”，简单说就是一方赢了什么另一方就得输掉什么。所以所赢总数减去所输总数就等于零，这就是“零和”的由来。

比如：下图的局面里白方刚刚吃了c6格的一只马。

白方所赢：一只马

黑方所输：一只马

所赢 – 所输 = 一只马 – 一只马 = 0

在这样一个零和游戏中该怎样量化双方的形势呢?这就需要用到极小极大算法(Minimax algorithm)。

这是一种找出失败的最大可能性中的最小值的算法(即最小化对手的最大收益)。

在这种算法中，我们假设双方都按照一个评分公式走出最佳招法。

在所谓的“1层搜索”中，我们只计算一步棋。走棋一方(极大方)仅需要计算每一步棋之后的结果，哪一步棋的结果最好，就走哪一步棋。但是在“2层搜索”中，对手一方(极小方)也要走棋，情形就变得复杂了。对手也会根据评分选择最好的一步招法。

简单说就是我们选择对自己最为有利的招法，同时假设对手也会选择对我方最为不利的招法。

让我们来看看下图中的例子：

如图白方先行，需要从a4，Rc7和Nc6三种走法中做出选择。对于白方的每一种招法黑方都要从三种应招中选择一种。每种变例下方的数字表示对于当前局面的评估(正数表示白方有利，负数表示黑方有利)。根据极小极大算法，黑方会走出对我们最为不利的招法，所以我们需要根据最差的情形来做出判断。于是在算法中的第一阶段，我们评价白方每种招法的结果就是下属分支的最小值，-8，0，3。然后我们再从这些值中选择最大值，最终3被选中，所以作为白方应该走Nc6。

由此可知，从计算机的角度来看有两条计算的线索，一条是极小方的线索，另一条是极大方的线索。这两条线索又可以通过极小极大算法的一种–负极大值算法(Negamax)而融合。其含义是：一方的评分等于另一方评分的负数。数学表达式如下：

max (a,b) = – min (-a, -b)

如果我们停下来审视极小极大算法，就会发现使用暴力破解的算法是很低效的。其中缘由可以用如下公式来解释：

O (b^d)

公式中的“b”又称为“分支因数(branching)”，“d”则表示“计算深度(depth)”。在中局局面中b的值约为35，也就是说在一个局面中每一方有35种可选招法。而d我们假设它为100，因为平均一局棋有50回合，双方共走100步。进而我们得出：35^100=2.5E154。也就是说一盘棋的所有招法比宇宙中原子的数量还要多很多。

我们必须要解决这个问题。最常见的手段就是限制搜索深度。当计算机算到一定深度时，我们就停止计算，根据已有数据来评估局面。如下图：

引擎怎样评估棋盘上的每一个局面呢?这是一个关键问题，因为如果评估不准的话，即使将深度算到了很多步之后也是没用的。

评估局面要靠评估方程，表达式如下：

f(x)= w1*f1(x) + w2*f2(x)+ w3*f3(x)+ …

一个评估方程式通常是不同棋子带有加权f(x)的线性组合。而加权则表示了每个棋子的重要性。最基本的评估方程式仅仅是计算棋盘上所剩棋子的数量：

f1(x)= 白后nº – 黑后nº

f2(x)= 白车nº – 黑车nº

f3(x)= 白象nº – 黑象nº

f4(x)= 白马nº – 黑马nº

f5(x)= 白兵nº – 黑兵nº

在这个公式中加权的数值就是我们在学校里学到的，如下：

w1=9

w2=5

w3=3

w4=3

w5=1

很明显这个简单的方程会导致错误，对于一个引擎来说它是不足的。如下图：

我们所给的方程会算出如下结果：

f(x)= 9*(1-0) + 5*(0-2) + 3*(1-1) + 3*(0-2) + 1*(1-4) = -10

从分数上来看黑棋有决定性的优势。可实际情况是白方将会走Qh6，下一步就威胁要杀王，黑棋无解只能认输。正是由于这样的原因，引擎使用不同技术的、更为先进的评估方法：

1.根据棋局的阶段来评估

根据棋局的不同阶段来评估局面是很有趣的。比如：我们在中局阶段希望王能远离中心。但我们也都知道王在残局阶段是一个关键棋子，此时它最好能待在中心。而引擎可以通过棋盘上所剩棋子的数量来判断当前局面处于棋局的什么阶段。

2.双象

如果一方拥有双象那就可以将评分略微上调(如果象的火力覆盖了棋盘上的很多格子，那就可以再将评分上调)。

3.根据棋子所在的格评分

特定棋子在特定格是可以加分的。比如在开局阶段，如果兵在中心格，那么它的评分就可以上调。

4.王的安全

这一点很重要。我们可以计算王周围兵的数量来判断王是否安全。或者我们可以看王的附近是否有车相伴。

5.局面的灵活性

我们通常都希望在一个局面下能有更多的行棋选择，比如象是否处于开放的斜线上。要评价局面的灵活性我们可以计算一方在某个局面下拥有多少种合规的应招，以此做为评估的参数。

6.兵形

叠兵可以稍微扣分，残局中的孤兵也可以稍微扣分，因为我们都知道这样的兵很容易受到攻击。

7.开放线上的车

我们都知道开放线上的车是一种优势，同样的还有第七横线上的车。

可以纳入考量的因素还有很多，而列出的这七种只是让你对更为先进的评估模式有一个印象。

地平线效应

现在我们来探讨一下地平线效应，当我们限制引擎的搜索深度时这种情况就会出现。

如上图：白车失陷，而引擎的搜索深度仅仅为2层。为了保住车白棋走了Bxf7+，从而在两步棋的范围内保住了白车，将问题解决在“地平线之上”。而结果是白车迟早都会被吃，为了延缓丢车，白棋又多丢了一个象。

解决这个问题的手段是“静止期搜索(quiescence
search)”。也就是说不去将引擎的搜索限制在某一个步数，而是让它搜索到局面“安静下来”为止。那怎样才算局面安静下来了呢?举个例子：安静局面的特性之一就是：在这个局面中双方都没有直接的吃子威胁。

剪枝算法(The Alpha-beta algorithm/Alpha-beta pruning)

剪枝算法是极小极大算法之后的一个重大进步。它是在1955年由John
McCarthy在达特茅斯学院(Dartmouth)的一个会议中提出的。它使用了修剪、界定计算分支的技术，能有效减少搜索树中需要计算的变例数量。当计算一步棋的所有应招时，只要能找到一个驳论，就可以将这步棋的所有分支彻底放弃。这样说起来很简单，可是当搜索局面很深的时候就会变得非常复杂。让我们举例说明。

假设白棋先行，搜索深度为2。也就是说我们考察白棋的每一步合规招法以及黑棋所有的对应招法。首先选择白棋的一步招法，并将之命名为“1号招法”，然后研究黑棋的所有应招并得出结论：1号招法的结果会导致局面均势。

然后我们考察白棋的第二种招法“2号招法”，并研究黑棋的可能回应。结果我们发现黑棋的第一种招法就会吃掉我们的一只象。于是我们就说2号招法已经被驳，无需计算余下的变例了。对于1号招法的详细分析使得我们得知至少白方有那么一步棋能导致均势。所以其他任何一步招法导致了明显不如均势的结果都可以被“驳”。

当计算深度达到了3或更深，情形就更为复杂了。对弈的双方都可以选择一步棋从而影响三步之后的局面。这时我们就要使用另一种策略，为计算设置一个下限和上限。所谓下限就是不去深入计算会导致己方局面太差的棋。而上限是不去计算三步棋或更多步棋之后己方局面太好的棋，因为对手不允许这样的局面出现，他会选择其他变例从而绕开这种对他不利的局面。在这种情形下，一方的上限/下限就是另一方的下限/上限。

减少运算成本

假设一个极小极大搜索树有X个节点，而相对应的剪枝算法的节点数是X的平方根。那我们到底节省了多少个搜索节点呢?那取决于搜索树的架构有多好。如果我们总是优先搜索最优招法，那么大多数的节点都会被删除。当然，我们并不总是知道哪一步招法是最优的。相反，如果我们总是从最差招法算起，那就没有任何节点会被保存。正因为如此，搜索顺序非常重要，这也是一款优秀的国际象棋软件很重要的一部分。

等招修剪

这种算法是在一个局面下，我们不去计算自己该怎么走，而是计算如果现在该对方走会怎样。换句话说我们假设己方走了一步“等招”，接下来由对方在相同局面下走棋。当引擎转而计算对手在该局面下走棋会有何结果时，我们可以把计算深度降为很低。

因为如果对手能通过战术进攻获取优势，那通常在很少几步棋中就会显现出来。如果算过几步棋的深度还没有发现对手有这样的战术威胁，那我们就可以假设对手无法在这样的局面下扩大优势。而计算获得的局面评估分数如果大于其他分支算出的“上限”，我们就可以把它作为我方行棋所获得的局面评估分数，然后停止继续在这个局面下花费计算资源。

这种算法背后的理论是：如果我方不走棋了都能获得这样的形势，那我方走棋的话形势很可能会更好。如此我们便“修剪”了搜索树，从而节省了计算资源。

不过这种算法不能用于“楚茨文克”局面，因为在“楚茨文克”局面中己方不走棋反而好过走任何一步棋，而国际象棋的规则是不允许一方不走棋的。

减少劣等招法的计算深度

通常引擎会将所有招法从优到劣排序。我们通常将排在前几名的招法进行最大深度的计算，而将排在后面的招法进行很浅的计算。这样便会节省计算时间，有时甚至会将下层子节点降低为2。

这趟计算机国际象棋世界的旅程就到此为止，希望我们上述的话题能让你对这个领域窥见一斑。