摘要

  • MistyFlipJungle 下的是翻棋斗兽棋，即所有棋子都盖着的 4×4 斗兽棋，对照精确残局库，它在残局中选出最优着法的比例为 99% 到 100%。
  • 搜索量提升 512 倍大约只换来 242 Elo，而更强的引擎仍会输掉 23% 的对局。随机翻棋决定了足够多的对局，搜索无法弥合这一差距。
  • 棋力的大部分来自第一步：只要开始搜索，就能约 99% 地战胜随机走子，相当于走完了通往完美的约 80% 路程。
  • 被解出的微型版本都是和棋。在表中存入取胜距离，修好了此前那个握着已胜残局却永远收不了官的引擎。

我做了 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 与历史着法排序。评估值由子力加机动性构成，另有一个厌和项。棋力由节点预算而非时钟决定，因此同一局面在任何机器上都返回同一着法，测出的差距属于引擎而不是硬件。

翻棋是机会节点。在翻棋处，局面价值是袋中可能揭示的各棋子的平均值，并用 star-minimax，即机会节点版的 alpha-beta 进行剪枝。着法排序名副其实：killer 与历史排序把到达给定搜索深度所需的节点数减半，并与不剪枝的搜索对照确认返回值完全一致，因此它在同样预算下多买来约一着深度，而不改变搜索算出的结果。

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

如何测量

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

在可解残局（最多五子）上，引擎选出最优着法的比例为 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 局就是距离那一节剖析的和局：旧表，没有距离度量，引擎握着已胜的残局连续八回合收不了官。它留在这里作为那个 bug 的展品。换上带距离的表，它在同一局面取胜，鼠三着吃象。

目前的结论

棋力在这里是真实存在的。242 Elo 的阶梯是真实差距，在长期对抗赛中更强的引擎会赢。上限在单局上：发牌和翻棋决定了任一局中相当大的一部分，所以哪怕强得多的棋手也常常落败，一局结果几乎说明不了谁更强。棋力体现在平均值上，而不是单局上。

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

资源：