我们形容一个人国际象棋下得好，我们可能会说“他棋感优秀，扫一眼棋盘就知道哪一方机会更大”，也可能会说“他善于计算，能算到10步以后的局面”。棋感意味着我们清楚哪个局面是赢棋，哪个局面是优势，哪个局面是互有机会的动态平衡，哪个局面是我上我也行…换句话说棋感是对局面有估值判断，越可能赢，我们对它的估值便越高。棋感越高，估值越准确。
计算意味着我们清楚该考虑哪些走法。一般来说，每个局面下至少有30种符合规则的走法。如果我们把所有走法都探索一遍，那么计算10步以后的局面意味着要探索6*1e14种走法，这是不可能的！实际计算时，我们只会计算合理的局面，很少考虑明显送子的棋。因此计算能力越强，探索的合理局面越多。人类的思维方式，成功应用在很多棋类引擎中来。如果用人类做比喻，国际象棋引擎的大脑，就是估值和探索[1]。我们不会把新版本的Stockfish11看作是与Stockfish10不同的引擎，这是因为它们有着相似的大脑。但我们把Stockfish11和LCZero看作截然不同的两个引擎，完全是因为它们的大脑迥然不同。下面我们将从估值和探索两个方面入手，粗略的介绍各个国际象棋引擎的特点，并将其分门别类。
估值在国际象棋引擎中，指的是用一个启发式函数来估计局面的价值，或者是局面的得分期望。最简单的例子是，我们知道单后能杀王，那么（不考虑50步规则和重复局面）凡是逼和的局面得分期望均为0.5（和棋），其余局面得分期望均为1（赢棋）。
但是在实际操作中，我们无法得知局面是否必胜，因此往往用一个启发式函数来估计价值。对一个门外汉来说，利用双方的棋子个数差，就可以粗略地看出谁更有优势。棋子个数差便是一个估值。一个更加有名且复杂的估值函数，由Claude Shannon 在1949年给出[2]：f(p)=200∗(K−K′)+9∗(Q−Q′)+5∗(R−R′)+3∗(B−B′+N−N′)+1∗(P−P′)−0.5∗(D−D′+I−I′)+0.1∗(M−M′)D，I指我方叠兵(doubled pawn)，孤兵(isolated pawn)。M指我方行动力(mobility)，即符合规则的走法个数。传统的估值函数，是基于人类的知识的启发性估值函数。比如Stockfish，Komodo，Houdini，Fire这些CPU引擎，它们的估值函数均是人类提前给定的。
AlphaZero[3]的诞生，意味着估值函数家族迎来一位新成员——深度神经网络。深度神经网络与传统估值函数不同，它不完全基于人类的知识，甚至可以无需任何人类的智慧。它们只需要巧妙的神经网络架构和学习算法，并辅以充分的训练，就可以变得十分强大。LCZero[4]的学习算法是无监督学习，它只从自我博弈中学习。从t10到t30，t40再到如今的t60，每个发展阶段的神经网络架构都稍有不同（网络逐渐变大）。
LeelenStein[5]的学习算法是监督学习，它只从已有的引擎对局中学习。它的架构随着LCZero的架构变化而变化。
AntiFish的学习算法同样是监督学习，不过它更挑食，只学习Stockfish相关的对局。这就导致它训练的十分不充分，很快便从大家的视界消失了。ScorpioNN[6]的深度神经网络，其架构和训练方式均与Lc0不同。更重要的是，它的训练几乎是其作者一己之力完成的。因此我们称呼它为“氪金”。
传统的国际象棋引擎探索算法，都基于下面的MiniMax原则[7](博弈论纳什均衡点)。
图[8]中圆形的节点表示你面对的局面，而方块的节点表示对手面对的局面。节点里的数字表示局面的估值。这里是一个四层两个回合的决策树。
假设我们已经有了最后一层的局面估值。在第3层的方形节点，轮到你的对手走棋。你的对手为了取胜，一定会最小化你的估值。所以他当前局面的估值是：
现在我们来到了第2层圆形节点，轮到你走棋。你为了获胜，一定会最大化你的估值。所以你当前局面的估值是：
依此类推，在相邻的两层不断的做最小(Min)最大(Max)操作，最终可以得到当前局面的估值：若想应用Minimax原则，最大的难题在于我们需要探索每一个可能的局面。之前已经论述过，这是不可能的。为了解决这一问题，一个很简单的想法是只考虑合理的棋，不浪费时间探索明显送子的变化。基于这个想法应用Minimax原则，并加以改造、变形，人们得到了大量的算法。比如深度优先算法，IDA*，NegaC*，alpha-beta剪枝等等。传统CPU引擎的探索算法，均源于此。与传统确定性的探索算法不同的是，AlphaZero采用的探索算法是基于概率的蒙特卡洛树探索[9](Monte Carlo Tree Search MCTS)。这个算法的原理是先给定一个落子概率分布，再按照该概率落子，接着不断按照某种方式模拟对弈直到比赛结束，最后根据比赛结果修正落子概率分布。比如一共有4个位置可供选择，概率分别是0.1, 0.2, 0.3, 0.4。每个位置走到最后的得分与落子次数为80/97， 40/221， 70/310， 390/406。那么可以预见，下一次修正后，第一个和第四个位置的概率将大大提高，第二个和第三个位置的概率将大大降低。因为AlphaZero的老本行是围棋，所以它的探索算法是蒙特卡洛树探索，其复刻LCZero也是蒙特卡洛树探索。基于概率的MCTS，其劣势在于概率带来的不准确，而优势恰恰也是概率带来的可扩展性。在围棋里，每次可以选择的位置高达300个！如果使用Minimax，那么决策树将变得极为庞大，庞大到不可接受。但MCTS却不在乎有决策树的大小。无论有多少个可选位置，它总能不断迭代得到一个近似的概率分布。很多人认为国际象棋这么“小”的决策树，确定算法已经足够好用，无需使用概率算法。这群人开发出了适配于估值深度网络的传统探索算法，进而研发了Allie这款引擎（缝合怪一号）。另外，Komodo的开发者写了一个适配于传统估值算法的蒙特卡洛树探索算法，这也就是引擎KomodoMCTS[10]（缝合怪二号，菜modo）。在同样的估值算法下，究竟是Minimax好还是MCTS好，还需要进一步的实践来验证。验证的办法，就是让它们在TCEC上决一雌雄。可是TCEC认为Allie使用了LCZero的估值深度网络，LeelenStein使用了LCZero的蒙特卡洛树探索，“大脑”和LCZero高度重合，因此禁止它们参加比赛。Allie的开发者和LeelenStein的开发者一拍即合，决定使用Allie的探索算法和LeelenStein的估值深度网络，缝合得到新的引擎AllieStein[11]，并派其参加TCEC。
说了那么多，还是画个表格来的实在。
| 传统探索算法 | MCTS |
|---|
| 传统估值算法 | 传统引擎 | KomodoMCTS |
| 估值深度网络（监督学习） | AllieStein | LeelenStein |
| 估值深度网络（无监督学习） | Allie | LCZero |
参考资料
[1]https://www.chessprogramming.org/Getting_Started
[2]Claude Shannon (1949). Programming a Computer for Playing Chess.
[3]https://en.wikipedia.org/wiki/AlphaZero
[4]https://github.com/LeelaChessZero/lc0/wiki/What-is-Lc0%3F-(for-non-programmers)
[5]https://www.patreon.com/jjosh
[6]https://www.chessprogramming.org/ScorpioNN
[7]https://en.wikipedia.org/wiki/Minimax
[8]https://en.wikipedia.org/wiki/Minimax#/media/File:Minimax.svg
[9]https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
[10]https://www.chessprogramming.org/Komodo#MCTS
[11]https://www.chessprogramming.org/Allie#AllieStein