我做了 MistyFlipJungle，一个接近完美的翻棋斗兽棋引擎。翻棋斗兽棋是4x4的斗兽棋，开局时每枚棋子都背面朝下。你可以 在 Mistboard 上与 MistyFlipJungle 对弈。 目的不只是造出一个强棋手。引擎本身就是测量仪器：搜索量为另一方512倍的副本，仍会输掉23%的对局。

所以这是另一类引擎文章。暗棋问的是：当存在机会节点时该测量什么。斗兽棋问的是：在完全信息的动物棋里经典搜索能走多远。翻棋斗兽棋问的是：当棋子一开始就是隐藏的，还有多少棋力能留存下来。比感觉上的要少。

指标 结果
搜索阶梯，1k 到 512k 节点 512倍算力跨度上相差242 Elo
搜索量提升512倍 输掉23%的对局
搜索量提升8倍 输掉37%到40%
任意搜索对随机走子 约99%（随机方800局全负）
残局（≤5子）对照精确残局库 99%到100%为最优着
中局（5到6子）对照精确求解器 200着中200着最优

这个游戏

翻棋斗兽棋在4x4棋盘上进行，共十六只动物，每方八只。所有动物开局时都背面朝下。轮到你时，可以翻开一枚棋子，随机揭示一只动物，或者把一只已翻开的动物走一格。吃光对方全部棋子即获胜。

吃子按等级：强者吃弱者。有两个重要的例外。鼠吃象，最弱克最强。同级的两只动物则同归于尽，双双离场。

吃子顺序，由强到弱

象
狮
虎
豹
狼
狗
猫
鼠

每只动物可吃其右侧的动物。鼠另可吃象，同级的两只动物同归于尽，双双离场。

完整规则与可试下的棋盘：mistboard.com/rules/jungle-flip。

标准斗兽棋，也就是上一篇里的完全信息版本，是纯粹的计算：整盘局面一览无余。翻棋斗兽棋把棋子藏了起来，而翻开的棋子身份是随机的。方差正来自这些翻子。

这个引擎

Rust，alpha-beta 搜索，手工评估函数，没有神经网络。带置换表的 negamax、迭代加深、吃子静态搜索，以及 killer 和 history 着法排序。评估函数是子力加机动性，外加一个厌和项。棋力以节点预算而非时钟衡量，因此同一局面在任何机器上都返回同样的着法，测出的差距属于引擎而不是硬件。

翻子是机会节点。在翻子处，其值是对袋中可能揭示的所有棋子取平均，并用 star-minimax（机会节点版本的 alpha-beta）剪枝。着法排序物有所值：killer 和 history 排序把达到给定深度所需的节点数减半，并与未剪枝搜索核对确认返回值完全一致，因此在同样预算下大约多买到一层深度，而不改变搜索算出的结果。

残局单独处理，用精确残局库。翻棋斗兽棋的残局可以用逆向分析求解：从每个已结束的局面倒推，记录双方最佳着法下的结果。我把表存成带完美索引的扁平数组（无键），两位存结果加一字节存到达该结果的距离，并在多核上并行构建。并行化中的陷阱是：表通过把每个局面映射到颜色规范形式而减半，而一步安静着会改变轮到谁走，于是一个局面的子节点可能落进与朴素分桶所设想的不同的桶里。求解过程是单调的，一个局面只会从未知变为固定结果，这正是并行构建安全的原因。

如何测量

自我对弈衡量的是两个版本中哪个更强，而不是两者是否下得好：同一引擎的两个副本共享相同的盲点，若两者都误判某个局面，它们之间的比分对此毫无说明。着法质量改用残局库来评分。

在可求解的残局（至多五子）上，引擎在99%到100%的场合走出最优着，漏掉的那些是搜索深度问题，加深搜索即可解决。基于残局库构建的前向求解器能再往前一点，覆盖仍有棋子背面朝下的五子和六子中局；在其中200个局面上，它每次都与最优着一致。

这种覆盖止步于精确计算能力的边界，也就是接近终局处。开局，也就是翻子发生的地方，规模太大无法求解，因此这里没有任何东西能验证引擎的开局表现。「接近完美」指的是在我能检验的局面里接近完美。

棋力天花板

为了在没有精确答案的情况下衡量开局，我比较了不同强度的引擎。四个分别搜索1k、8k、64k和512k节点的副本进行循环赛，每组配对进行成对的换先后手对局，各120局，再由结果拟合等级分：

1k nodes     +0
8k nodes    +89
64k nodes  +153
512k nodes +242

搜索量增至512倍大约值242 Elo。在国际象棋里，这么多算力值好几百分。各档间大致维持在每8倍64到89 Elo，到顶端趋平：320k到640k节点只值6 Elo。

爆冷率比等级分暗示的要高。强8倍的引擎会输掉37%到40%的对局；强512倍的输掉23%。翻子本身就决定了足够多的对局，多搜索也补不上这个缺口。

有一级跳跃很大，在最底端。1k节点的搜索约99%的场合能击败随机走子方（各档合计800局中随机方一局未胜），差距接近850 Elo。从随机到完美的距离中，约80%就在这一步里，即从随机走子到开始搜索。它之上的阶梯很平缓。

调整评估函数毫无作用。更好的子力价值、鼠象关系项、厌和项，在成对自我对弈中结果都是持平。在一个如此依赖运气的游戏里，评估值的差异会被冲淡。

西洋双陆棋是常被提到的运气压缩型游戏；翻棋斗兽棋压缩得更狠，棋盘更小、残局已解、开局完全随机。

完美对完美

这个阶梯是对开局的估计，并没有把它解出来。足够小的游戏可以彻底求解。我把完整的迷你版本从头到尾解了出来，包含开局翻子：两子和四子，开局时每枚棋子都背面朝下，按完整规则下到终局。

在双方最佳着法下，它们都是和棋。精确值为零，最优变化每次都和棋。两个完美棋手无法击败彼此。

从开局而非单个残局局面去求解一个六子游戏，就已经跨过4000万个不同局面：正是这堵墙让完整游戏遥不可及。所以这对小型版本是精确的，对完整十六子游戏则未经证明。

但它仍然确定了双方最佳着法值多少。完美对完美是和棋。完美对远弱的对手几乎必胜：随机走子方800局全负。强512倍的引擎丢掉的那23%处在中间：两个水平接近的棋手，差距被方差淹没，由翻子决定胜负。这些败局来自棋手之间的差距，而非来自双方最佳着法本身。

求解进度

逐层来看，这个游戏在精确计算面前的状况。这些表不计时钟（忽略40着无进展规则），覆盖每个子力数下所有完全揭示的局面；每条记录存双方最佳着法下的结果以及到达该结果的距离。

子数 局面数 最长必胜路径 构建
2 28,800 9着 瞬时
3 1.9M 21着 2 秒
4 79M 41着 200 秒
5 2.3B 63着 笔记本上4小时，2.8 GB
6 46B 未构建 数天，约140 GB 内存

六子在租用的服务器上可以构建，但对引擎毫无价值：五子的覆盖已经能给所有进入表中的残局评分，其余部分搜索也走得接近最优。再往上，求解完整游戏就意味着求解开局，而开局就是翻子树：十六枚不同棋子以随机顺序揭示，可达状态量级在10^11或更高。上一节的迷你版本是连同那棵树一起从头到尾解出来的；十六子的游戏没有，而且我看不到通往它的路径。

距离那一列是我第一次做错的地方。最初的表只存胜、和、负，别无其他，这足以给着法评分，却不足以把棋下完。下面观棋器里的第5局就是这种情形：从第24回合起，黑方一虎一鼠对红方一只孤象，在表中是必胜（鼠在三着内困住象，因为象不能吃鼠）。黑方从未把胜势送掉，也从未把它兑现。每一步获胜着法得分都相同，机动性作为平局决胜项在其中挑选，劣势方乐得来回挪子，重复规则最终判和。连续八个回合，引擎握着一个必胜局面，走出表中评为最优的着法，却毫无进展。

存下距离就解决了：3着取胜现在优于9着取胜，于是引擎选择最短的必胜路线，并把必败拖长。从残局库中的必胜局面出发，它现在恰好在表中记录的步数内结束，而第5局的残局以鼠三着吃象收场。国际象棋几十年前就撞上过同样的问题，这正是 Syzygy 表在胜/和/负旁边附带距离度量的原因。有些教训你会在4x4的棋盘上重新发现一遍。

看它下棋

引擎以全力自我对弈。五局，各自一块棋盘。用箭头逐着回放，从全部背面朝下到终局。第5局就是距离那一节剖析的和棋：旧表，没有距离度量，一个引擎连握八个回合却下不完的必胜残局。它留在这里作为那个缺陷的展品。用上带距离的表后，同样的局面它能赢下来，鼠三着吃象。

现状

这里棋力是真实存在的。242 Elo 的阶梯是真实差距，长赛程下更强的引擎会赢。天花板在单局上：发牌与翻子决定了任一单局中很大一部分的结果，所以即使强得多的棋手也常会输，而一局结果几乎说明不了谁更强。棋力体现在平均值里，而不是某一局里。

在我能检验的地方，这个引擎接近完美；在我不能检验的地方，也就是开局，则未经验证。我唯一缺的测量，是对强人类棋手的等级分，这是仅剩的、不依赖引擎或其求解器、也不会继承它们盲点的检验。

资源：