翻翻棋：搜索量提升 512 倍，仍有 23% 的对局落败

一个带精确残局的搜索引擎

MistyJungleFlip 是 alpha-beta 搜索，配手工评估函数，没有神经网络：评估值由子力加机动性构成，另有一个小小的厌和项。棋力由节点预算而非时钟决定，因此同一局面在任何机器上都返回同一着法，测出的差距属于引擎而不是硬件。

翻棋是机会节点。它的价值是所有仍盖着的动物的平均值，并用 star-minimax，即机会节点版的 alpha-beta 进行剪枝。残局则来自精确残局库，从每个终局局面往回推解出。每个条目存储双方最佳着法下的结果，以及到达该结果的距离。

凡有精确答案之处，都拿来核对

自我对弈只能测出两个版本哪个更强，测不出它们是否下得好：同一引擎的两个副本共享同样的盲点。所以着法质量改为对照残局库来评分。在最多五子的残局中，引擎选出最优着法的比例为 99% 到 100%；失误都是搜索深度问题，更深的搜索就解决了。基于残局库构建的前向求解器能覆盖仍有棋子盖着的五子和六子中局；在其中 200 个局面上，引擎每次都走出了最优着法。

这种覆盖到精确计算的边界为止，也就是接近终局处。翻棋发生的开局阶段太大，无法求解，所以这里的一切都没有验证引擎的开局水平。

512 倍的搜索量，大约只值 242 Elo

为了在没有精确答案的情况下衡量开局，四个副本分别每着搜索 1k、8k、64k 和 512k 节点，进行成对换色的循环赛，每个配对 120 局。拟合出的等级分为 +0、+89、+153 和 +242。每 8 倍的台阶值 64 到 89 Elo，且在高端趋于平坦：320k 到 640k 节点只值 6 Elo。在国际象棋里，512 倍的算力值好几百分。

爆冷比等级分所暗示的更常见。搜索量多 8 倍的引擎会输掉 37% 到 40% 的对局；多 512 倍的输掉 23%。翻棋自身决定的对局足够多，更多搜索也补不上这个差距。

唯一的大台阶在最底部。1k 节点的搜索约 99% 地战胜随机走子（各档位共 800 局中随机方 0 胜），差距接近 850 Elo。从随机到完美的距离里，约 80% 就在这一步上，即从随便走子到开始搜索。调评估函数毫无作用：更好的子力价值、鼠与象的专项、厌和项，在成对自我对弈中全都没有变化。

完美对完美是和棋

足够小的版本可以彻底解出。两子和四子的版本，开局时所有棋子都盖着，按完整规则下到终局，在双方最佳着法下都是和棋：两个完美棋手无法战胜彼此。哪怕从开局解一个六子游戏，也已超过 4000 万个不同局面，正是这道墙让十六子的完整游戏无法企及，所以完整游戏未被证明。

这仍能给那 23% 定位。完美对完美是和棋。完美对远弱的棋手几乎必胜：随机走子方 800 局全败。两个接近的棋手处在中间，差距落在方差之内，由翻棋来决定。

残局库能走多远

这些表覆盖每个子数下所有完全翻开的局面，不计 40 个半回合的无进展规则。

六子表可以在租用的服务器上构建，但毫无增益：五子的覆盖已经能给每一个进入表中的残局评分。再往前，完整求解就意味着要解开局，而开局是一棵翻棋树：十六个不同棋子以随机顺序翻开，可达状态在 10¹¹ 量级以上。

最初的表里没有距离这一列。它们只存胜、和、负，这足以给着法评分，却不足以收官。在一盘自我对弈中，引擎有一虎一鼠对孤象，按表是必胜（鼠三着内困住象，因为象不能吃鼠）。连续八回合，它走出按表评为最优的着法，却毫无进展，因为每一步取胜着法得分相同，直到重复规则判为和棋。存入距离后，3 着取胜优于 9 着取胜：引擎选最短的必胜路线，并把必败局面尽量拖长，那个残局以鼠三着吃象告终。国际象棋的残局库，例如 Syzygy，附带距离也是同样的原因。

棋力体现在平均值上，而不在单局上

翻翻棋里棋力是真实存在的：242 Elo 的阶梯是真实差距，在长期对抗中更强的引擎会赢。但发牌和翻棋决定了任一局中相当大的一部分，所以哪怕强得多的棋手也常常落败，一局结果几乎说明不了谁更强。还缺的测量是对强人类棋手的等级分，这是唯一不依赖引擎或其求解器的检验。

本站的对局复盘把每一次翻子拆成决定和运气，让你看清自己的对局里哪部分是哪一种。规则页上的二十盘引擎对局是电脑自我对弈，引擎源码在 GitHub 上。