完全信息对抗性博弈算法从入门到初识

· · 科技·工程

前言

说到博弈理论，大家作为 Oier 第一时间想到的一定是 OI 题目中最常涉及的公平组合游戏，或更为具体地，nim 游戏，sg 函数或纳什均衡等等。

然而现实中真正“有意思”的博弈情景，却甚少属于这些理想化的博弈论模型，而是独自拥有一类自己的理论框架。

与那些充满数学性的博弈结论截然不同的是，这些理论的“算法味”是相当浓厚的，同时，它又毫不缺乏在实践意义上的直观性，这两点可能便是它曾激发了我探索欲望的原因。

本文的目的正是向读者介绍这一研究领域的一些有趣的研究成果与理论方法。由于我自身水平的限制，大部分内容只能做到浅尝辄止，因此对本文的创作期望仅仅是一篇在部分内容处略有深入的科普短文。同时疏漏之处可能在所难免，欢迎读者在评论区指正。

概述

如上文所述，“对抗性博弈”最根本的研究动机就是实用。什么是实用？我们可以概括成，我们的研究对象就是日常生活中最常见的 棋牌，而非理想化后的数学模型。

在“棋牌“当中，牌一般是非对称信息的，比如打扑克就肯定互相看不到牌。这个其实是很难处理的，虽然近年来也有不少对这种非对称信息游戏的研究成果出现，但本文略过不谈。

因此我们的研究对象就再次缩小到了“棋”，而且是完全信息的棋。

对于这样的一类游戏，我们很容易发现，要求出某个局面的最优策略是没法取巧的，只能使用搜索 + 评估的方式。搜索不需要解释，评估指的是对一个局面的好坏程度进行估计，因为你没可能直接搜到游戏结束，所以评估方法的好坏显然也是极度重要的。

迄今为止的一切完全信息棋类引擎，都逃不过使用以下两类大的框架中的一种：要么是 AlphaBeta 框架，要么是 MCTS 框架。这里对它们的特点进行一个大致概括。

alpha-beta 就是我们所说的“爆搜”，当然我们会进行无穷多的剪枝与精细实现来将爆搜的效率提升得非常非常高。举一个例子，国际象棋每个局面可能都有个十几种走法，但采用这个框架的国际象棋最强引擎 Stockfish 最新版分支因子只有 1.6 不到，就是说每多搜索一步它的搜索树平均只会扩大 1.6 倍，而剩余的十几种着法则由于各种原因被剪枝，这是非常恐怖的。

alpha-beta 框架由于重心更偏向搜索与速度，相对没有那么看重评估函数的质量，因此适用于高效率，低精准度的评估函数。

MCTS 框架就截然不同，它是一种相对“离散”的搜索框架，你可以理解成它进行评估的位置实际上是很稀疏的。因此它适用于高精准度，但速度较慢的评估函数。

本文会对这两个方向的引擎算法都进行科普性质的讨论。两个方向相重叠的部分不多，你可以单独选择你感兴趣的部分进行阅读。

Alpha-Beta 方向

有关搜索优化

从最基础的想法开始 -- MiniMax

最基础的想法当然就是最简单的爆搜。不过这个爆搜应该如何实现，也许还是值得考虑一下的。

我们假设我们有一个给定的估值函数 Eval(GameState) 用来给出一个局面对先手方的评分，越高代表先手方越占优势，那么在先手方回合时我们当然想最大化这个值，后手方想最小化这个值，这也是其名字的由来。

一个最基础的 MiniMax 实现就是上述过程套上一个固定深度，如果深度已经为零则返回估值函数结果，否则枚举当前行棋方走法进行向下的迭代。当然在实际运用时，我们一般需要最优走法，所以你还需要记录一下它；同时正常的计算机博弈比赛都是限定时间而非层数，所以我们一般会在外面套一层迭代加深（每次把深度加一），考虑到搜索的指数性，就能发现其实这并不会增加多少时间开销。

这样的实现实际上是让双方都站在先手方的视角进行考虑；你可能已经敏锐地发现，如果将返回值变为“当前行棋方的最高分”，再加上要求 Eval 函数有对称性，即一个局面对先手的评分取相反数就可以得到局面对后手的评分（一般都会满足)，就可以有效地简化代码。这样的改动被称为 NegaMax 搜索。这个修改并非结构性的，所以基本只属于个人习惯问题（NegaMax 在实现多线程时会方便一些)。

利用一下搜索树的性质

读者们应该会有一种预感，即由于我们只要求当前局面的最优解而非整个搜索树，应当存在一种无损的，从搜索树本身性质出发的，因此是普适的剪枝方法来优化最朴素的 mini-max 搜索算法。

这个东西确实是存在的，一些熟读 oiwiki 或参加过 thuwc2024 的同学应该也知道这个东西，它就是 alpha-beta 剪枝。

我们从一个“显然可以进行剪枝”的例子来看看这个优化的动机。我们现在在搜索一个 max 层，已经搜索好了一些移动，那么现在就有了一个对该局面估值的下界 lb。此时我们如果进入一个新儿子进行搜索（这个儿子显然是 min 层），而这个儿子在搜索完一些移动后就会产生一个上界 ub。此时我们发现，如果 ub 已经小于等于 lb，那么该儿子已经不可能成为父亲的最优移动，也不可能更新父亲的估值，可以直接进行退出。

一些细致的读者也许会立刻意识到，其实如上的剪枝完全不只会出现在父亲儿子间，也有可能出现在跨越多层的节点间，所以我们应该尝试找到一个更一般性的剪枝理论。

alpha-beta 剪枝就是我们在寻觅的东西，而且它的原理其实很简单。

我们在搜索时额外传入两个值 alpha 与 beta，意义是“如果该儿子的搜索值已经小于等于 alpha 或大于等于 beta，则该儿子已经无用。

进行简单讨论，如果目前层为 max 层，我们会不断将 alpha 取 max，min 层则是不断将 beta 取 min，每次搜索儿子时传入该节点的最新 alpha 与 beta。剪枝在哪里呢？每次搜索好一个儿子，如果已经有 alpha \geq beta，则直接 break 即可。

alpha-beta 剪枝的形式是简洁优美的，且我们也不难验证它的正确性与无损性。它的效果非常强力，一般认为，它可以直接给分支因子开个根号（也就是将搜索深度乘二）。

alpha-beta 还我们带来了一份“小礼物”。这一点我们会在后续某个部分进行说明，容许我在此处先卖一下关子。

处理重复局面

在进入到下一个硬核算法之前，让我们先来一点点的幕间小菜。

这个东西是一个容易被想到的 "low-hanged fruit"。其动机很简单，我们应当有一个数据结构来处理搜索时遇到的相同局面情况（一般来说你的引擎水平越高遇到的这种情况就会越多）。

我们要处理的唯一工作就是找到一个易于增量，回撤，查询的哈希函数了。一般我们会使用 Zobrist-hash置换表。换成 oier 容易理解的语言，这就是一种异或哈希。

假设你的棋一共有 P 种棋子，盘面大小为 S，我们直接在一开始生成 P \cdot S 个 64 位权值，然后定义一个盘面哈希值为对于所有盘面位置，其上的棋子与该盘面位置权值的异或和即可。就如同寻常的异或哈希一般，移动撤销只需做 O(1) 次异或操作即可完成。

别急，还有一些细节要处理。首先是大家容易想到的一个细节，假如你现在必须再搜索 4 层，但哈希表里的结果是 2 层的，你就不能直接调用，所以得记录结果的层数。其次还有大家不容易想到的，假如你带着一个小窗口的 alpha-beta 参数搜了一个局面得到一个结果，那么换成大窗口后你这个结果还正确吗？显然是不一定的。因此当将局面计入哈希表时，你还必须保证该节点并未被从外面带进来的 alpha-beta 窗口影响。（即 alpha < result < beta）。

进行一点点的人类智慧

大家在思考“如何缩减搜索树大小”时，基本的第一印象肯定是，那些显然垃圾的着法就不应该被搜索。这个是对的，但是我们目前仍然在讨论无损的剪枝方法，所以表述应当被替换为：让显然垃圾的着法有着非常大的剪枝率。

考虑这个东西应该怎么实现。既然我们有显然垃圾的着法，那当然也会有显然更好的着法。如果我们在先前的“显然更好”的着法已经获得了一个很不错的评估分数，那此时再带着这个 alpha-beta 参数去搜索显然辣鸡的着法时的剪枝率就会非常高。

那么这个人类智慧就呼之欲出了。直接将所有着法按照（走这一步后的）评估函数进行排序即可（红方走就从大到小，反之亦然）。一般意义下，你的评估函数的质量越高，带来的剪枝力度就会越狠（实际上考量的是“当前的评估值”和“走一些步后的评估值”的接近程度），所以，如果你的评估函数巨烂无比，很可能这个玩意带来的甚至是负优化（因为要排序）。

以上方法被称为“静态着法启发”。其实我们还有各种妙妙小启发，基本原理和上面这个东西类似，都是试图把“可能有用”的着法先拎出来搜，这里再给出两个例子。

第一个是“置换表启发”。顾名思义，要用到我们上一章才讲了的置换表。如果现在表内有我的当前局面但是深度不够高，这个表就完全没用了吗？既然“静态着法启发”是根据走一步的评估值来排序，那么我们自然也可以根据置换表内的低深度评估值来进行排序，这样的效果显然会比静态着法启发更优秀。

第二个是“杀手着法启发”。这个略微复杂一点。如果在某个局面时搜了某个着法后直接触发了 alpha-beta 剪枝，那么它的兄弟们搜了该着法（如果存在）后也很可能会被直接剪掉。所以我们可以额外记录一个所谓的“杀手着法”，让后面的兄弟优先对它作搜索。

人类智慧是无穷的，所以“搜索启发”也是无穷的。但是对于每种棋类，一般都会有效果最好的“启发组合”，你甚至可以针对你正在开发 AI 的棋类做定制化的“启发”，这些就只有实战中才能学习得到了。

beyond alpha-beta

这个章节所阐述的算法被发明的动机是基于我们发现， alpha-beta 剪枝其实还有一些性质没有被完全利用，这也是之前我所说的它给我们留下的一些"小礼物"。

考虑执行一个带窗口的搜索 alphabeta(game,dep,alpha,beta) 和执行朴素的 minmax(game,dep) 的返回值差异。我们对 alpha-beta 自身的定义初衷（即小于等于 alpha 或大于等于 beta 可以直接剪掉）进行一个感性理解，能发现前者实际上就是对后者做了一个分段函数处理，也就是说，如果后者结果为 x，前者返回值实际就是：

\max(\text{alpha},\min(\text{beta},x))

那么此时我们会想，既然 alpha 和 beta 都是可以自己定义的，我们能不能利用一些特殊的 alpha-beta 值组来做一些事情呢？

考虑所谓的“零窗口搜索”，即如果我们令 beta = alpha + 1，那么根据这个东西的返回值我们就能知道其真实的结果与 alpha 的大小关系，且一次零窗口搜索一般是非常快的（基本都被剪掉了）。

对的，此时精通 OI 的你一定想到了，我们能不能利用这个玩意来做二分？恭喜你发明了 MTD-F 算法。

不过其实这个只是 MTD-F 的一个骨干思路，它还采取了一些额外优化，比如由浅一层的 MTD-F 先得出二分的大致界，对正负评分分别二分以减少在零附近的搜索开销之类，由它的全名 Memory-enhanced Test Driver 还能看出，这个算法的效率必须有高效的置换表作为支撑；此外该算法其实还有一堆细节要处理，因此虽然 MTD-F 可能比接下来要介绍的算法在性能上略高一筹（其实甚至都不一定），后一种算法细节更少，更便于实现，也是个不劣的选择。

这个算法就是 PVS(主变例搜索)。我们先进行一个静态搜索评估或者置换表评估，反正就是给着法从可能优到可能劣排个序，把第一个着法当作“主变例”做一个正常的 alpha-beta 搜索。

对于后面的着法，我们提出以下疑问：“这会比我们的主变例更优秀吗？”，即先以目前的最优估值为零窗口搜一遍，如果它已经被证明了不如主变例，就不用搜了，否则它成为新的主变例，再重新做一遍完整搜索即可。

很容易看出，使用 PVS 算法后，搜索的效率就更加依赖于启发性排序的效果优劣了。因此不管从什么意义上讲，估值函数的设计都是制作一个强力的 alpha-beta 引擎过程中相当重要的一环，我们会在更后面的章节对其进行讨论。

提速--增量化与位棋盘

这一章我们来讨论一点不那么算法性，但也同样重要的问题 -- 提速。

不难看出，搜索的一个比较大的性能开销在于对叶子节点计算估值函数（个别棋类还需要涉及到落子处理，比如黑白棋，但大部分棋这一方面是简单的），那么有一个朴实的想法就是将估值函数变得“可随单步移动快速更新”，比如一个五子棋引擎可能会统计棋盘上所有长度为五的连续段并对所有可能出现的模式给予不同评分，那么进行一步落子后，只需要更新与新落子点有交的连续段即可。

我们有可能仍然不满于更新的效率。但是很明显，使用普通的数据结构来维护更新的时间瓶颈已经摆在这里了，此时位棋盘堂堂登场。

这个东西可能同大家熟悉的 bitset 还是挺相似的。我们仍然以上述的五子棋评估函数来举例子，我们直接对于棋盘的每一行每一列每一个正反对角线记录代表它们的两个 16 位整数（分别代表黑子白子集合），然后如果我们要统计某一行有多少个连三的黑子，就可以直接用 x & (x>>1) & (x>>2) 状物来搞定了；如果你想要统计的是“活三”（即两头都没敌方子的），也可以通过再与代表敌方子的集合做一些位运算来搞定了，然后统计分数就是一个 popcount 的事情，优化了 棋盘边长 = 15 倍常数。

在你动手去实现一个位棋盘前，还有一件事情必须要阐明，就是位棋盘在带来强大的加速的同时，其实也是在给你的估值函数的形式施加限制。比如不用位棋盘时你可以对每种长度为 5 的 pattern 都给出评估，但如果用了位棋盘技术，每种 pattern 的统计都要付出棋盘边长次位运算的代价，可能就得不偿失了。极为适应位棋盘的五子棋尚且如此，像象棋这种看上去就一点不“位”的棋，要在保持评估函数质量的同时令其适应位棋盘，就需要高度精巧的位棋盘设计方法和丰富的经验了。

突破水平线 - 启发式延伸

固定深度的 alpha-beta 搜索，其本质劣势实际上是一个被称为“水平线效应”的东西，即以对应层数为水平线，在这一个线之后的东西引擎就无法看到了，这就会造成短视。

这个效应在实战中经常体现为：引擎可能会通过不断将劣势局面往后推，来回避在当前深度发现的不利局面。比如，它可能会不断将自己的子送到对方面前，逼迫对方吃子，这样就能把真正的劣势推到搜索深度之外。这就是为什么我们需要一种机制来突破这个"水平线"的限制。

而 启发式延伸 就是对此的一个很重要（根据 Stockfish 源代码，这个优化价值 200 elo) 的缓解方式。

我们之前已经讲过了一个“启发式”，所以大家应该已经知道“启发式 XX“这种命名就代表着这个优化是没有一个统一的最优定论的。比如我们刚才提到的 Stockfish，它所采取的延伸标准就比我们下面要介绍的版本要复杂很多，所以我们这里只是讲一个”动机性“的极简版本。

先以象棋为例子，比如我们仅仅以当前子力价值为评估标准，那么如果我们走好这一步刚好碰到了层数上限，但是我们此时走的这一步送了个子（对手下一步才能吃），引擎就不会看出我们这一步其实是送子的大劣着。又比如如果这一步是兑子，我们吃了对手子对手下一回合才能吃回来，引擎可能就会误以为我们直接赚了对手一子。这两种所述情况当然可以通过评估函数的优化来解决，但与这些类似的情况其实是无穷无尽的（比如将军，或者将军抽子之类）。

所以我们考虑一个更本质的解法，遇到这种所谓“比较复杂”的局面，不妨直接多搜一层（令 目前的 depth 升高 1），直到局面相对平静下来为止。当然对于我们的极简版本，我们可以把“比较复杂”的局面定义为有吃子或将军的局面。又比如换成五子棋的话，我们可以定义比较复杂的局面为有冲三或冲四的局面。

能够多延伸固然是一个好事，但是也需要有所平衡，如果延伸的时间开销足够你全部多搜一层了，那这时它就成为了累赘。

摆烂的智慧 - 空着裁减

这个东西被称为“无需结构性更改就能获得额外速度”的天上掉馅饼优化，我们来看看它是什么一个东西。

在很多局面下我们会发现，对手已经无可救药了，以至于我们这一步直接空着不走都能够获得一个比较好的结果。这便是空着裁减的动机 -- 如果 skip 这一步得到的结果都能触发 alpha-beta 剪枝了，我们就可以直接返回。

你可能发现，如果空着裁减时调用的是 alpha_beta(dep-1)，好像并没有明显的速度提升。但是我们这个时候其实完全可以激进一点 -- 我们都不走棋了，少搜两层怎么了？形式化来说，可以定义一个不小于 1 的裁减参数 d，空着裁减时直接调用 alpha_beta(dep-1-2*d) 。如果你对你的评估函数质量不是很自信，或者你搜索深度还不够深，d 可以取 1，否则取 2，3 甚至 4 都是可行的。

不过你先别急。敏锐的读者应该已经发现这个优化其实并不完全是“天上掉馅饼” -- 有些棋的某些局面中，不走反而成为了优势（比如中国象棋的困毙）。这个细节的处理可能是利用空着裁减过程中最为复杂的部分。专业引擎为了充分利用空着裁减的速度加成，一般会仔细设定“何时可以空着裁减”的决策表，但我建议你在编写时简单粗暴一些 -- 举中国象棋的例子的话，在残局前启用空着裁减，在残局时关闭空着裁减就是不错的想法。

提速的杂项

剪枝与优化是永无止境的话题，但碍于篇幅与本人水平，本文对 alpha-beta 路线提速方法的概述只能行至此处。这一章节会简单提及一些比较简短或不太好归类的搜索技巧。

期望窗口

不难发现在迭代加深过程中，对每个深度都进行完整窗口（即 (-inf,inf)) 的搜索是有一些浪费的。我们其实有充分的理由相信，提高一层后的搜索估值并不会比降低一层后的估值偏差多少，因此设上一层返回的评估值为 x，我们可以将该层的初始搜索窗口设定为 [x-\text{windows},x+\text{windows}]，其中 \text{windows} 为设定的某个不大的常量。

算杀

在部分棋类（最为典型的，五子棋）引擎的制作中格外有用的一个部分。

其实可以被理解成大号的 单步延伸。它出现的动机是，传统估值函数对于五子棋的“强制杀”（即连续冲三冲四），尤其是较长步数的强制杀的预见能力是相当差劲的。（甚至更优秀的估值方法，例如我们后面会提及的 NNUE 都摆脱不了这一点）。

同时我们发现，在对这些“强制杀”的计算中，其实可行的步数并不多（必须每步都形成冲三冲四），所以我们完全可以在不那么损耗计算性能的情况下计算到一个相当深的深度的杀（实现的好的话，四五十步），这可以用来纠正搜索过程中存在的这一短视。

算杀的实现中，也有很多很多的巧妙技巧，有兴趣的读者可以到 github 上寻找 wine 或 rapfi 的代码学习，这里就不过深涉及了。

有损剪枝

在前面的篇幅中，我们一直都在讨论无损或几乎无损（即希望达到无损，如空着裁剪）的搜索优化方法。这不是因为我是完美主义者，而是 这一类的有损剪枝 几乎都不是普适的，而是针对目标棋类而设计的。

不过可能必须要承认，这一类的剪枝应该是一个正常人类对着一个具象棋类看到“优化搜索”这一任务时得到的第一反应，比如只保留静态评估前 k 小的，或者五子棋选点只选在双方争夺中心几圈内之类；又或者你学会 alpha-beta 搜索后可能会立刻想到的，静态评估比 alpha 小多少或比 beta 大多少就立刻返回。

如果你要问这些东西有没有用，当然是有用的，不过我要强调的有两点。首先大部分的“朴素想法”必须经过精心的仔细考量与参数调整后加入你的引擎，才能起到提升棋力的作用，否则发生的情况几乎会是既没优化到速度，又让引擎漏算很多有用分支。其次，如果你真的认认真真把上述章节所提到的优化都加了进来的话，你会发现你想到的大部分有损优化实际上也不能提升多少速度 -- 事实上，Stockfish 搜索部分的所有有损剪枝加起来也占到 100 elo，而一个精心优化的启发式延伸就值了 200+ elo。

以下是一些个人理解。ab 系引擎的漏着主要来源于其天生拥有的难以根除的水平线效应（AlphaZero 可以从原理上缓解这一点）。此时若再过分地削弱自己在宽度上的无损性，导致的必然是得不偿失。

估值函数相关

虽然名字是 alpha-beta，但估值函数的设计有可能是 ab 系列引擎设计过程中最为重要困难的部分。正如上面的搜索部分所提及的，只有拥有一个优秀可靠的估值函数，你才能放心地去进行一些激进的剪枝。

必须承认，要找到设计估值函数过程的“共性”其实并不是容易的事。存在不少评估方法对于个别棋类有奇效，对于其它棋类则效果平平或无法实现，因此如果你对某种特定棋的估值函数设计有很浓厚兴趣，推荐你寻找针对该棋类撰写的领域论文进行更深入研究。

手工估值函数 -- 设计要求与常见内容

毫无疑问，我们希望估值函数尽可能精准。但是这不能以速度的无限牺牲为代价。也就是，我们应该在“知识量-速度”二维曲线上找到一个最大化引擎棋力的点。

不过让我们暂时看看一个朴素估值函数的“知识量”可能指的是哪些东西。

子力。毫无疑问。

空间。比如先给每个棋盘格赋权，然后某一方占据或控制该格子就获得对应权值等等。

机动性。最朴素的想法就是局面下某方的可走步数。虽然听起来有些扯淡，进行足够多比赛后一方的平均可走步数如果比对方多，就说明该方某种意义上地占据了更主动的位置。著名国际象棋引擎联赛 TCEC 就存在某些平局情况使用机动性作为判决依据的规定。不过事实上这个东西在国际象棋中还没那么显著，相关性最显著的应该是黑白棋及变种。

当然你把这个东西写进评估函数时肯定不能这么朴素。

特定数学特征。如果你使用 alpha-beta 方法写过 THUWC 那个四子棋 AI，你会发现它在残局就是下不过 MCTS。原因其实不复杂，一般人在设计四子棋的评估函数时大概只会像五子棋一样考虑连二连三个数这种事情，但事实上残局中这些因素作用反而很小，最重要的则是““控制”（剩余空格数为）奇数/偶数的列的个数”，而这些东西带来的优势同时又是很难被搜索所发现的（反而连三连二容易发现）。因此在此时加入人类研究的这种“棋理”就是很有必要的了。

威胁/牵制/保护 etc.. 这些东西都是象棋术语，并不普适。但是它们延拓的意思可以被理解为，己方子力与敌方子力的相互关系。

形状/图案 和“数学特征”其实可以被统称为“棋理”。比如中国象棋引擎 （曾经）普遍有以下两个盲点 -- 窝心马与空头炮。不太深的搜索难以发现其坏处，但长远来看它们会对运子产生严重的弊端，因此现在大多数引擎会直接对这一类“不好”的形状做罚分。

一个合格的估值函数大致就是根据速度需求对以上这些估值项目做取舍了。当然也许你还记得我们在前文提到的，如果你使用了位棋盘技术，那么还需要考虑到哪些项目是适应你的位棋盘形式的，哪一些是难以用位棋盘表示或会较大拖累速度的，那么这些就必须割舍了。

超参数优化方法？

这种东西其实就是纯纯的，盲人摸象，摸到什么有用就上什么。

靠人类经验手动调试 不用说了。

约束法缩小调整范围然后网格/随机搜索 类似于利用人类经验优化搜索。比如你认为一个车价值小于两个马，那么就约束马的价值大于车的价值的一半；或者你认为引擎宁愿亏一个兵也不应该形成某个糟糕棋型，这也是一个约束。

更大的超参数空间 + 遗传算法/其它最优化算法 有一点后面我们要提的 NNUE 算法的雏形了。你需要意识到人类的智慧终归是有极限的，我们总是要利用到一些黑盒的。不过此处暂时还只是黑盒，并没有丧失可解释性。也就是我们的“评估项目”仍然是具有可解释性的人工制定的产物，但是将具体细节大量交给可变的超参数。在 NNUE 出现前的较强引擎普遍使用的是这个算法。

其它神秘优化方法 盲人摸象可以摸出千奇百怪的结果。比如黑白棋有个很神秘的超参数设定法，你对于所有 只剩 3 个空格 的棋盘暴搜出必胜必败，然后再设置一些 pattern，你就拥有了一车 “双方各自拥有某个 pattern 集合情况下，这一方能够必胜” 的数据，对于这个东西做最优化的拟合即可。

最新成果 NNUE

看完以上这些乱七八糟的，你是不是会觉得这个玩意好像就是纯人类智慧，没有一点普适规律？

所以 NNUE 横空出世证伪了这个结论。光是原型版的国际象棋 NNUE 就把最人类智慧的朴素评估函数干掉了 200 个等级分，同时也使得 alpha-beta 系引擎仍然维持着对 alphazero 系引擎在个别棋类上的优势。

NNUE 是受 AlphaZero 对神经网络博弈算法的研究成果启发而生的。这个技术简单来说，就是我们抛弃传统的人造估值函数，同样求助于神经网络来进行估值；但是我们使用的神经网络与 Alphazero 的大网络有很大区别。它具有的特点，一个是很小，一个是具有“可快速更新”性（一般来说就是第一层很宽，后面很窄，这样可以直接对第一层打表，后面指令集之类的），还有一个就是需要进行高度人类智慧的特征工程（人为提取最可能有用的棋局特征，不能直接把整个棋盘扔过去让他自己找有用的用）。这样这个神经网络就适合我们 mini-max 宝宝体质了。不搜索单独使用训练出来的 NNUE 网络，能够发现它其实挺菜的，但是它高效的本钱在于它有着比起传统估值函数高得多的精准度与比起大型神经网络快得多的速度，这形成了一个平衡。

受限于篇幅与作者水平的双重限制，在此处并不能对这个算法做进一步深入。鳕鱼团队公开了其 NNUE 的开发文档，如果你感兴趣，可以进行进一步探究，然后来教我。

NNUE 是一个很厉害的成果。它改变了估值函数设计的"盲人摸象"状态。但是，这个改变是“如改”。因为此时网络的特征工程方法成为了新的一个需要人类智慧的地方。（虽然有一些经验可以借鉴，比如所有“杀王”棋都可以仿照国象 NNUE 的“棋子与王相对位置"进行设计)。同时由于 NNUE 的网络和平时使用的神经网络有较大区别，我们并不能通过现成的深度学习库来训练和加速 NNUE 网络，这无疑都提升了它的使用门槛。

那么什么是真正彻底的变革呢？我们马上要告别 alpha-beta，来到 MCTS-AlphZero 的章节。

AlphaZero 方向

如果你突发奇想，设计了一种全新的完全信息棋类游戏。你简单口胡了一下，觉得平衡性不差，且挺有意思，你现在很想知道该棋的最优解大致是什么，一个很强的 AI 会下成什么样，此时你的第一选择会是什么？对于大多数棋盘或决策空间不小，对“大战略”有需求的棋类，这个选择永远是 AlphaZero。

AlphaZero 最了不起的地方在于它兼顾了 延拓性 和 最大强度 ，这是十分令人诧异的。论延拓性，AlphaZero 一般不需要除了对弈规则实现以外的任何信息（针对特定棋类进行优化可能仍然有助于棋力提升，但这只是尖端棋力之间的微小差别罢了）。论最大强度，且不谈众所周知的围棋等 AlphaZero 拥有无可比拟优势的棋类，在 Alpha-beta 的传统阵地上 AlphaZero 同样能成为有力的挑战者，甚至远远超过之。最显著的例子（虽然没那么知名）其实是五子棋（尽管大家拿来练手写 alpha-beta 的第一个棋好像一般都是五子棋，但是采用 AlphaZero 原理的五子棋引擎 katagomo 的的确确将最强的 NNUE 甩了几百 elo）。

当然，这样一个伟大的成果自不可能是空中楼阁。所以在涉足它之前，我们需要先扫清其周边的算法基石。

朴素 MCTS

我们有无数种方法来证明，人脑在处理我们讨论的博弈问题时使用的方法不同于 alpha-beta。例如从事实上看，存在一类人类能够处理而 alpha-beta 不能够处理的完全信息棋类。或者从直觉上，人脑像 alpha-beta 那样做地毯搜索看起来就非常难以实现。

但是差别在哪？

在国际象棋中，鳕鱼可以轻松地从当前局面向后算十几步；在慢棋中给定足够长时间，人类特级大师也可以算到这个深度。但两者的不同点在于，算到这个深度时，鳕鱼需要遍历近百万个节点（在未引入 NNUE 技术时，这个数字还要更大），而人类考虑的分支（变例）则不会超过两位数。

因此我们可以就此做出猜测，人类的思考方式更近似一种“偏离散”，对宽度上的分支做了高度剪枝的算法。

当然，“高度剪枝”的同时还能不会漏招满天飞，这体现的是人脑经过训练能达到一个很厉害的估值精度。这一点其实也是不证自明的，不然我们也不会用人类经验来编写传统 alpha-beta 引擎的估值函数了。

不过在这一个章节，我们暂时忽略后者，而注重于这一搜索方式本身。

朴素 MCTS 就是对这一思考方式的一种初步模拟尝试，让我们看一看它的四个步骤。

选择。从根节点出发，按照某一方法不断选择所谓"最有潜力"的节点，直到到达叶节点。

扩展。若到达的节点并非终止节点，对其所有走法扩展出叶子节点，随机选择一个进行下一步骤。

模拟。随机落子直到游戏结束，记录胜负结果。

回溯。使用胜负结果更新所有相关节点的信息。

“选择”阶段，原始 MCTS 的公式是最朴素的贪心，但是这样显然会导致严重的局部最小值风险，因此我们现在一般使用 UCB(上置信界) 公式：

\text{UCTValue} = \text{exploitation} + \text{exploration} = \text{wins}/\text{visits} + \text{C} \cdot \sqrt{\ln(\text{visits'}) \over \text{visits}} “模拟”阶段其实是比较难以理解，但同时很关键的一个部分。 其实容易发现，“模拟” 只是在给局面找一个估值函数。你完全可以继续用你手写的函数代替这一部分，那 “模拟” 的意义何在呢？ 这里需要提到一件事情，就是 `MCTS` 的效率（正确性是有论文证过的，效率没有），以及先前提到的 `alpha-beta` 剪枝带来的期望深度折半的效果，其实都是极大依赖于所谓 “棋的自然度” 的。考虑一个极端情况，黑方必须连续走对一百步棋才能获胜，走错一步就输，且中间过程不存在任何可供学习的局面特征，那么此时无论 `alpha-beta` 还是 MCTS 都几乎要搜满整个博弈树才能找到解。但我们又注意到，这样的情形人脑其实也没啥好办法，所以我们并不会认定这昭示了这些算法原理上的根本缺陷。 而我们日常中遇到的，“自然” 的棋，其自然性其实可以表述为某种意义上的连续性。比如对于一个某方优势的局面，一个“自然”的棋总会有一个特性：优势方大多数情况总是更好走。这是“随机落子”的动机之一。 另一动机则和 “水平线效应” 有关。先前读到这一名词时，你是否觉得，这个东西是任何对称信息博弈算法都根本无法避免的问题？MCTS 和 AlphaZero 就是对它的一次挑战。你可以感性地理解为，一个在中间截断的估值函数，是几乎不可能 “在极限意义下”趋近于任何局面的真实评估状态的，但是一个有益的想法是，我们抛弃挖掘局面静态性质的定势，注重于延伸至终局后得到的“胜，负，和”本身，这就是 MCTS 采取的思想。 剩余两个部分似乎没有什么特别值得注意的。也许应当留心的一个细节是，注意在回溯时的“分数视角”问题，比如当前这个局面是红方行棋，你更新该节点时其实应该采取蓝方视角。 ## 朴素 MCTS 的人类智慧 朴素的 MCTS 在大部分棋类游戏中无法打败精细优化的 `alpha-beta`，毕竟它难能可贵的其实是“只需要规则”的普适性本身。不过，任何东西总是有人类智慧的，这一节中，我们就来简单看一看前 `AlphaZero` 时代的 `MCTS` 人类智慧。 ### 优化模拟策略 随机走子的收敛速度还是过于慢了，因此我们自然会想到使用一些方法来优化走子模拟的质量。这些方法可以比较 trivial,为了速度着想一般也都比较 trivial。 对于五子棋，重力四子棋等很容易成杀或构成足以在数步内成杀的威胁的棋类，对这些威胁的简单判定就可以显著地提升随机模拟的质量。 一个更广泛的想法则是仍然部分地利用起评估函数，例如裁剪掉与评估最大值相差极大的选择或直接根据评估函数进行加权。但是这个过程实际是在 MCTS 这个辛辛苦苦搭建的普适化框架上重新引入了估值函数的缺点，一般来说即使能带来相较于朴素 MCTS 的性能提升，也无法媲美同等优化程度的 `alpha-beta`。 ### RAVE 方法 可能是最有用的一个启发方法。`RAVE`，全称` Rapid Action Value Estimation`（快速动作值估计）。顾名思义，是以“动作”，即着法出发的一个启发式优化。它尝试从全局视角出发，在不同分支间进行搜索信息的互相利用。 具体而言，`RAVE` 向 UCT 公式中加入了一个 `RAVE` 参数 $\beta$，得到的新 $\text{UCTValue'}$ 如下所述： $$\text{UCTValue'} = \beta \cdot Q(\text{move}) + （1- \beta） \cdot\text{UCTValue} $$ 其中 $Q(\text{move})$ 为当前走法在全部分支中得到的胜利数与访问数之比。 `RAVE` 的动机在于，如果某一步棋在一个局面下表现良好，那么在类似局面中，这一步棋也很可能是优解。它主要针对初期探索的收敛速度。容易发现，`RAVE` 的效果通常会随着搜索的深入而减弱。因此，我们通常会额外引入权重衰减机制，使其贡献占比逐步减少，最终由纯粹的原版公式所接管。 ### Truncated Rollouts 在朴素 `MCTS` 中，模拟阶段的随机走子会持续到局面抵达终态。这有时是浪费的，有时甚至是极度耗时，难以实现的，在大棋盘的开局阶段或会陷入反复拉锯循环的棋类中这一问题尤其突出。 此时一个自然的想法就是模拟到一定步数后截断，转而使用估值函数替代。读者可能会疑惑：你不是认为在 `MCTS` 中引入估值函数是尴尬突兀的吗？但这一情况并不一样。 第一，当这种情况发生时，由于模拟深度过大，后期模拟所在的状态空间是极大的，这意味着它们实际对算法的收敛与评估的拟合产生的帮助是可以忽略的。那么此时进行截断其实对 `MCTS` 本身的普适性并无损害，因此它至少是有益无害的。 第二，此处我们对评估函数的需求实际并不高，甚至于最粗糙的评估方法都能胜任这个任务。因为此时我们需要的不再是一个精细的结果，而只是一个“判定胜负”的替代品。 ### 杂项 仅列举一些名字与简单介绍。 **回传价值衰减** 回传时对不同深度的祖先进行不同程度衰减（一般越靠近根节点衰减越多），鼓励算法更关注当前节点的局部信息。 **Tree $\to$ Dag** 类似于置换表，将不同分支的相同局面合并，这样搜索结构就不再是树了，变成了有向无环图。也许大家也想到了这个东西，但实际上它实现中需要注意的东西是比较多的。 **多线程 MCTS** 其实 `MCTS` 在原理上比 `alpha-beta` 更适合上多线程，性能损失也更小。 ## Alpha...Zero！ 铺垫了这么些，终于该来到正餐了。 虽然它是十年前才出现的新成果，但是正和大部分深度学习领域的成果一样，其核心其实理解起来并没有那么困难。 接下来我们仍然会先讲解 `AlphaZero` 使用的算法与前文所述朴素 `MCTS` 算法的异同。但是由于它可能是本文的主角，在这之后会有一个对其网络结构，参数，优化及其它细节的更详细讲解（~~才不是因为我花大力气实现了它~~）。对了，如果你真的想要实现它，请务必读完后面所有部分，因为我是按照内容关联性来写的文章，需要实现的必要部件未必被总结在一起。 ### 将重心转向评估 -- policy-value 架构的动机 朴素 `MCTS` 给出了一个很有前途的搜索架构。但是与之相比，我们所使用的评估方法 -- 随机模拟，尽管也有其蕴含的道理，看着就非常虎头蛇尾了。 当然一个更为直观的证明仍然来自于对我们自身的观察。一个熟练的棋手可以看一眼棋盘不经思考就给出一步尚可的棋步，难道这来自于单次或多次随机模拟？这显然难以令人信服。 因此我们现在的目标变为仿照人类思考方式找到一个更为精确的评估函数构造方式。 你可能感到疑惑：那么随机模拟就这样领盒饭了？在形式上，的确如此。但是他带给我们的思想，即直接以终局结果作为拟合目标，仍然会在 `AlphaZero` 方法中扮演重要的角色。 那么回归正题，经过对人类思维模式的观察，`AlphaZero` 的设计者认为其可以被抽象提炼为两个部分 -- `policy` 网络与 `value` 网络。 试想你正面对一道 OI 题。你发现题目中有 "对符合 XX 条件的序列计数"字样，可能会瞬间想到 "有很大可能我需要刻画符合该条件的序列的特性，也有部分可能我应该做容斥"，那么这就类似于 `policy` 网络的作用，即给出当前局面下应该执行不同棋步的各自概率；你做了一大堆转化与一般化后，最后得到了一个很简洁的充要条件，你觉得已经转化到头了，此时你会快速判断一下这个条件看上去是否可做，此时你使用的就是 `value` 网络。 `value` 网络与我们先前反复提及的所谓“估值函数”是接近的，但 `policy` 网络则全然是一个新概念。它的灵感便来源于我们反复提及的，人类的“对局面的第一感”；技术上的动机，则更接近于对 `MCTS` 搜索框架的进一步改造 -- 若大模型只是在评估局面上具有很高精度，朴素 `MCTS` 本身的收敛速度也将会限制其能向后看到的着法深度，但若利用同样高精度的 `policy` 网络，就可以解决这一问题，**且这几乎是免费的午餐**，甚至于倒贴的午餐，因为在实现中我们会将 `value` 和 `policy` 集成于同一网络，而这一结构甚至有助于降低网络的过拟合现象，不过这个留到后文再去说。 ### Zero 的核心 -- 自对弈 现在我们择定了我们需要训练的对象，是时候考虑如何进行训练了。 最朴素的想法自然是，人工收集并标注人类大师棋谱的 `policy`(例如将实际落子位置设为 1，其余设为 0)与 `value` 标签。 事实上，最初版的 `alphago`（注意没有 `zero`）也确实是这么干的，也凭此战胜了李世石，这已经足以体现出神经网络评估相较于传统搜索在这类棋上的优越性。 但若仅此为止，其尚远远不能称为对称性博弈算法的一大飞跃，原因有三： 其一，利用神经网络进行评估其实并非什么新鲜研究，早在上个世纪就有人做过相关试验了，只是效果很差。那么为什么 `alphago` 效果好了呢？主要还是依赖于深度学习优化理论与网络结构理论的发展，而非自身理论的某些重要飞跃。 其二，如果网络的训练需要基于大量的人类棋谱，其自然说明众多小众棋类，新发明的棋类无缘享受这一福泽，那么这个算法的泛用性就要被打上大大的问号，甚至于 `alphago` 中的 `go` 能否被去掉都会成为未知数。 其三，从始至终对 `alphazero` 系列算法的研究都是寄希望于“找到一个更接近人脑的棋类算法`。人类能够从无到有发展出一个棋的完整理论，而你的算法要依靠于这套完备的理论才能训练。这便意味着这个最本源的动机只能被标记为失败。 所幸此时一个比较天才的想法拯救了我们。训练要棋谱，棋谱不够。但是棋谱显然不一定必须由人类下出来。如果我们的模型水平高于人类，我们将能够通过自己与自己对弈来生成棋谱。....等等，"水平高于人类" 这个条件真的是必要的吗？ 你可能顿时豁然开朗，但转眼间就想到了一个问题 -- 学习自身的棋谱，会不会其实什么都学习不到？这其实是一个很严厉的诘问，但我们可以暂时用一个粗糙的解释来搪塞过去。我们使用带一定搜索量 $v$ ($ v > 1$) 的 `MCTS` 方法来生成棋谱。那么得到棋谱的质量显然高于纯模型（即 $v = 1$）。假定模型能够学习到所训练棋谱的一切特征，那么训练后的水平将会比训练前更高，依次类推即可。 话虽说如此，训练过程中也确实会遇到各类过拟合，盲区等问题，这些会在后面再被提到。因此你可以理解为，根据广泛的测试，自对弈作为训练数据生成方式是没有决定性问题的。 最后残留的一个问题就是打标签了。`policy` 的训练标签似乎是明了的，我们可以直接取 `MCTS` 搜索后得到的每一棋步的分别遍历次数；但 `value` 就有些存疑了。直接使用那个局面下搜索得到的评估？实践证明这是不可取的，极易导致对局面的局部最优盲区。但是我们回想一下之前提及的一些思想... 对了，直接取自对弈的终局结果即可。（即 `Win/Draw/Lose`) 因为这一标准是客观的，也是我们寻求最优化的目标本身。 讲两句闲话。`AlphaZero` 方法**求解**游戏的能力是非常非常强劲的。此处求解指的是得出该游戏是先手必胜，后手必胜，亦或平局。诸如五子棋这样的低难度求解棋类，单张 4090 和一个优化精细的 `AlphaZero` 实现仅需半天不到就可以在开局获得 $99\%$ 的胜率。对于那些必胜回合数更长的游戏也是如此，例如 `Breakthrough`（突破棋）。这些是 `alpha-beta` 引擎所难以媲美的。而这一点正是通过“直接以棋局结果为训练目标”的思路所得以实现。 ### 梳理一下流程 介绍到这里，我们其实已经可以勾勒出算法的全部步骤了。 由模型进行推理部分，我们将去除随机模拟的部分，转而直接由 `value` 模型得出局面胜率后进行反向传播。 对 `policy` 模型的使用则基于一个对 `UCT` 公式的改动。得到的新公式被我们称为 `PUCT`(`Prediction based UCT`)。 $$\text{PUCTValue} = \text{exploitation} + \text{exploration} = \text{wins}/\text{visits} + \text{C-PUCT} \cdot \text{prior} \cdot {\sqrt{\text{visits'}} \over \text{visits}}$$ 公式中的 $\text{prior}$ 即为 `policy` 网络给出的走法先验概率，其余与 `UCT` 公式含义保持一致。**请注意**，该公式的形式与 `UCT` 公式有较大差异，例如 $\text{visits}$ 不再在根号内。另外原先的探索常数也被新的 $\text{C-PUCT}$ 常数所取代，它一般取 $1$。 需要注意，适用于朴素 `MCTS` 算法的大部分启发式优化都不再适用于新的搜索过程。因为模型本身就能给出相当精确的评估，此时再加入 `RAVE` 等粗糙的启发显然是帮倒忙。 在训练中，我们固定自对弈的单步模拟量（通常至少为 `200` 以上），获得一定数量的棋谱。以上一节所述方法标注局面的训练数据，令模型进行拟合。 `AlphaZero` 的原始论文中，还写了一步，是将训练得到的模型与上一版本模型进行回测，若胜率高于 $50 \%$ 才予保留。但是后面谷歌研究人员做了个实验，发现长远来看，每次无条件保留新得到的模型才是更好的选择，而且这样还能节省回测的时间。因此我们也可以忽略这个最后一步。 ### 模型结构与参数 到了这一章节，我们将不得不面对一些深度学习的内容。所幸，上天给我们开了个小后门 -- 绝大部分棋类都可以直接照搬同一套模型结构，而不需要进行特殊化的定制。但尽管如此，你还是需要知道一点基本概念的。我们以 Q&A 的形式来呈现它们。 **Q.一般使用何种网络作为主要结构？** A.`Alphago Zero` 使用的是 `CNN`（卷积神经网络），后续研究也发现 `CNN` 能够胜任大部分的棋类游戏。若一定需要更具体的经验，可以大致认为，`CNN` 更擅长满足一定的平移不变性与局部模式影响较大的棋（最典型例子围棋五子棋），反之则稍弱（最典型例子象棋）。 据我所知，目前为止不使用 `CNN` 的 `AlphaZero` 系引擎似乎只有一个，是国象的 `Lc0`，它使用了 `Transformer`。但是 `CNN` 显然更简单，更成熟，是我们自己开发时毫无疑问的首选。 **Q.除了 CNN 之外还需要什么？** A.`ResNet`（残差网络）。`CNN+ResNet` 的组合可能效果不是最好，但绝对不差。`ResNet` 是个很厉害的东西，但同时也很简单。简单表述，就是每隔两层 `CNN` 连一条跨越边，这样信息可以简单地通过跨越边实现“跳过某个层”的操作，此时我们设计更深的网络就几乎不存在副作用了。这样设计后每条跨越边之间的两个 `CNN` 可以被称为一个“残差块”。 **Q.模型大小如何表述？小模型好还是大模型好？** A.你需要知道 `CNN` 有个参数叫 `channel`（通道数）。使用 `CNN+ResNet` 的前提下，如果我们假定所有卷积层的通道数相同，网络的大小就可以以残差块数量和每个卷积层的通道数来表示，缩写为 `x b(blocks) y c(channels)`。常见的大小有 `6b96c`，`10b192c`，`20b384c` 等等。 还有一些模型通道数并不相同，如 `nbt`(瓶颈结构)。此时表述后面会加上这些单词，如 `24b512c-nbt`。 几乎所有情况下，如果推理时的算力固定，大模型（但搜索速度更慢）棋力都会强于小模型（搜得更快）。但是如果我们要自己进行训练，则必须要考虑到训练时的成本。哪怕极小的模型（比如我的显卡就很烂（1660S），因此做实验时使用的是 `4b36c`) 都可以达到远高于人类（及大部分 `alpha-beta` 引擎）的水准。所以，作为实现尝试的话，先炼一个小模型试试也许是明智的。你家里卡很豪华的话当我没说。 **Q.棋盘以什么形式输入进网络？** A.这个问题是必要的。棋盘的输入形式对训练效果影响确实不小。一个永远不会差的选择是 `one-hot` 方法。即对于每一种棋子分别赋予一个维度，然后每个棋盘格都用 `棋子种类数` 个数进行标识。这样做存在的一个问题在于可能训练数据量过大直接爆显存，但是其它的那些更紧凑的输入方式好像我一个没有尝试过，没法评论。 **Q.`value` 和 `policy` 的输出端该怎么安排？** A.在放置完残差块后，我们从最后一个残差块引出两条连接，分别连接一个小的卷积层，这两个卷积层再分别连接两层的全连接层，最后再分别连接 `value` 和 `policy` 的输出层。这个结构是我试错出的一个不错的结构，大家要写的话可以先试试这个，具体参数可以参考我的代码。 `policy` 层的激活函数与误差函数当然是毫无疑问的 `softmax` 与多分类交叉熵。 `value` 层，一般来说最推荐的是分别输出胜负和的概率然后用多分类交叉熵。这个其实是有道理的，比如 $100\%$ 概率和棋与 $50\%$ 概率胜，$50\%$ 概率负最终的胜率都是 $50\%$，意义还是有很大不同的，如果混在一起似乎不太好。但是问题也不太大，所以你比较懒的话用 $\tanh$ 加上 `Mean Squared Error` 也是可行的。 **Q.移子棋的 `policy` 怎么办？** A.好像和网络结构的关系一般，但我不知道这个问题应该在哪里提及，就放这里了。容易发现，落子棋的 `policy` 表示是自然的，但移子棋就不那么自然了。 如果每个棋子的移动方向很少（如只能向四周移动），我们仍然可以通过把 `policy` 大小改成 `4*SIZE` 的方式来解决。但类似于国际象棋这样的，难道我们比如建立一个 `SIZE*SIZE = 8^4` 的 `policy` 吗？这样不论对于效率还是训练效果都是很不好的。此时一个技巧是，我们将“选子”和“落子”分成两部分，也就是说，在棋盘表示中再加入一个“这个格子是不是被选的”的维度。如果一个都没被选，那就是 `policy` 要给出选每个子进行移动的概率，否则就是将选定棋子移动到每个格子的概率。 **Q. 其余值得特别提一下的超参数？** A.单次训练的自对弈局数。这个一般来说取一万，太大了影响效率，太小了会出问题。但是如果确实是小棋的话小一点也无所谓。 `batch_size & 学习率`。用 `Adam` 优化器的话 `512/0.002` 是很好的。 `epoch&early_stop`。每一次训练最多训 `5` 个 `epoch` 就饱和了。另外强烈建议加早停（`early_stop`），每一个 `epoch` 结束后看验证集 `loss` 如果涨了就立刻回退到上一个 `epoch` 后并停止。 **Q.如何充分利用 gpu 算力进行自对弈？** A.如果你真的跑起来了，会发现用 cpu 自对弈实在是慢完了，因此我们必须使用 gpu。但是 gpu 也存在劣势，就是内存调度很慢。因此如果你还是像原来一样单个单个局面喂进去，速度甚至会变慢。因此，一个显然的事情是我们需要每次喂一个 `batch` 的数据。这个 `batch_size` 显然因显卡而异，我取的是 512。 一个想法是我们用类似朴素 `MCTS` 多线程化的思想，但这样就过于繁琐了。在这一过程中一个更取巧的想法是直接同时进行 `batch_size` 局的自对弈，然后每个局面每一模拟量的推理请求就可以顺理成章地作为一个 `batch` 被喂进去了。 如果在实现过程中遇到了这里没提及的问题，可以先去翻翻我的代码，如果还没搞懂可以私信问我，我会把它加进来。 ### `AlphaZero` 的人类智慧 人类智慧生生不息。 **狄利克雷噪声**。这个不是人类智慧，这个是包含在原论文中的自对弈的必要组成部分。如果我们一昧只根据纯模型来进行自对弈，陷入局部最优解的概率会大大增加。此时，我们必须引入随机来引导模型探索未尝试过的着法。 所谓“狄利克雷噪声”，即在自对弈中扩展根节点时，利用狄利克雷分布生成一组随机数，以一定的加权比例与模型给出的 `policy` 混合（比例一般取 `0.25`)。 **温度控制方法**。这个技巧最先由 `Katago` 引入。其目的和狄利克雷噪声一样，都是预防局部最优解，但是切入点不同。 这个优化的切入点在于，我们发现当一个着法的 `policy` 与其它着法变得悬殊时，经过自对弈的 `MCTS` 访问量会变得更为悬殊，这是不利于探索的。因此，我们引入一个温度 `T`，初值取 `1.2 \to 2.0` 的一个值，随着游戏进行以一定比例缩减。每次扩展根节点引入狄利克雷噪声前，将得到的 `policy` 进行“钝化”，即令原先的 `policy` 分别为 $p_1,p_2,...$，则： $$p'_i = {p_i^{1 \over T} \over \sum p_j^{1 \over T}}$$ 这样的一个钝化目的在于逼迫着模型不断验证（或证否）自己最为青睐着法的优越性。 **Fast Game& Slow Game** 我们发现，相比于 `policy` 标签，用于训练的 `value` 标签实际是脱节的。因为一局可以生成很多本质不同的 `policy` 数据，却只能提供一组本质不同的 `value` 数据。因此，我们不妨创造一种所谓 "`fast game`"，进行低模拟量的快速自对弈来得到更多 `value` 训练数据，而 `policy` 的训练数据仍然由原模拟量的自对弈得到。 **Surprise Weighting** 所谓的“妙手启发”。仍然是为了更快收敛与防止盲区提出的优化。在自对弈过程中，如果数步后神经网络给出的胜率与当前胜率有较大差异，那说明这一步很可能是网络未能识别出来的妙手/失误。此时我们加大对这几个局面训练时的加权即可。 更多的各类人类智慧可以参考 [katago 的 github](https://github.com/lightvector/KataGo/blob/master/docs/KataGoMethods.md)。他们对于很多相对 `trivial` 的优化基于数据进行了有效性的验证。 我的代码的仓库地址：https://github.com/MsvcPytorch/MyAlphaZero/tree/main 几年前还写过一个 `AlphaBeta` 的五子棋引擎，在同一个用户的仓库下面。对 `ab` 算法有兴趣的读者可以去翻那个的代码。 作者不会用 git，所以好像就是把源文件全传上去然后乱写了一通 readme，不保证能跑起来。