动物将棋的完全解
简而言之
- 动物将棋是一款3×4的儿童将棋，已被强解：后手方在78着内取胜。田中哲朗在2009年完成求解。
- 我用Rust从零复现了这一结果：全部246,803,167个可达局面，与Robert Clausecker独立完成的解在50,000个抽样上零不一致。
- 打入让棋局变深。去掉被吃子可以重新回到棋盘的规则后，局面数降到962,894，最深的胜局从173着降到37着，开局也变成和棋。
- 局面浏览器会按双方最佳着法下的结果，为每一个合法着法标上颜色。
动物将棋（「动物棋」）是一款面向儿童的将棋游戏，棋盘为3×4，共八枚棋子。它已被完全解决：在双方最佳着法下，先行的一方必负。
职业将棋棋手北尾まどか在2008年设计了它，用来教孩子下将棋。2009年，田中哲朗算出了每一个可达局面的精确值。后手方在78着内取胜。
本文讲述这个解揭示了什么，以及为什么这么小的棋盘会产生一个如此深的棋局。深度来自将棋的一条规则，而大多数小型抽象棋类并没有它：被吃的棋子会重新回到场上。
来源： 田中哲朗，《An Analysis of a Board Game ‘Doubutsu Shogi’》（IPSJ SIG Notes, Vol. 2009-GI-22, 2009）。NII 永久链接
在下方探索完整的解。每一个合法着法都按双方最佳着法下的结果标了颜色，从任何你能走到的局面出发都可以。
绿色为胜，灰色为和棋，红色为负；标记数字是将死距离。拖动棋子或点击着法即可跟进变化。
游戏规则
每方有四枚棋子：狮子、长颈鹿、大象和小鸡，双方镜像摆放。每枚棋子上的圆点标出它能走到的格子。
着法
每枚棋子每回合走一格：
- 狮子：8个方向任选其一（相当于国际象棋的王）。
- 长颈鹿：横向或纵向走一格。
- 大象：斜向走一格。
- 小鸡：正前方走一格。前进到最远一行即升变为母鸡（除后方两个斜向外，任意方向走一格）。被打入到最远一行的小鸡不升变，因此就卡在那里了。
打入
每回合，你可以走一枚棋子，或者打入一枚棋子。吃掉的棋子会进入你的手中，在之后的回合里你可以把它打入任意空格，作为自己的棋子使用。被吃的棋子不会离场，而是改换阵营。这是将棋的标志性规则，国际象棋没有。
胜负判定
两种取胜方式：吃掉对方的狮子，或者把自己的狮子送到对方底线，且落在对方无法立即吃掉的格子上（试图）。
结论
动物将棋已被强解：一张查找表（即残局库）保存了每个可达局面的精确值，因此带有它的程序可以从任何局面走出完美着法，而不只是开局。田中从终局局面向后推算，构建出这张表，覆盖了棋局能够到达的每一个局面。
初始局面是后手方78着取胜（一着是一方走一步，所以78着相当于双方各39回合）。先手方因欠行而输：每一步都会让局面变差，而又不允许不走，所以先行本身就是劣势。
你可以观看这局78着的对局，一步一步走出完美着法，直到最后吃掉狮子。
我用Rust从零复现了这一切：一个规则引擎加一个逆向求解器。从初始局面枚举，正好还原出田中给出的可达局面数，246,803,167个局面（其中99,485,568个非终局），前提是我采用了和他一致的局面计数约定（试图在一着之后才结算）。局面值与Robert Clausecker的开源程序 dobutsu做了对照，那是一个独立完成的完整解，在我抽样的50,000个局面上零不一致。初始局面的评估值为 #-78（走棋方78着内被将死），而它的四个合法首着全部是负：
Gc4-c3 : #-78
Lb4-c3 : #-78
Lb4-a3 : #-78
Cb3xb2 : #-76
完整解的数字（田中的数据；我的枚举完全还原了局面数，胜负分布是他的结果）：
| 项目 | 数值 |
|---|---|
| 可达局面 | 246,803,167 |
| 非终局局面 | 99,485,568 |
| 胜 / 和棋 / 负（走棋方） | 56,474,473 / 2,682,700 / 40,328,395 |
| 每局面平均合法着法数 | 9.4 |
计算开销小到可以在一台机器上重跑。田中2009年的运行用的是一台2.6 GHz Opteron、16 GB内存的机器：枚举局面约19分钟，逆向分析5.5小时。我在Apple Silicon上用Rust重跑约75分钟，占用约7 GB内存，写出一个2.14 GB的排序记录残局库，随后压缩为333 MB的紧凑表。在线的局面浏览器通过一个常驻约400 MB的探询进程提供这个紧凑文件的查询。
第一版依赖一张散布在8 GB上的哈希表，这也是它远慢于Clausecker参考解（约一分钟，167 MB）的原因。他的版本给每个局面一个由内容算出的地址：哪些棋子在场、两只狮子在哪、其余棋子怎么排列。完全不做哈希，所以整张表就是一段连续的字节数组。移植这套索引后，我的求解降到243 MB、3.5分钟，同时更快也更小，因为在8 GB上随机访问会把缓存打乱，而紧凑数组不会。结果值完全一致，逐着与Clausecker的探询程序做了对照。要达到他那精确的167 MB，还需要再折叠一个我没有折叠的对称性，那更多是记账功夫，而非洞见。
值得一提的发现
除了标题里的结论，还有几点很突出。
胜局结束得快，但有一条长尾。 多数必胜局面在15着内结束；最深的必胜要走173着，远超开局的78着，而只有14个局面达到这个深度。下图以对数刻度按取胜距离统计必胜局面数：几步之后急剧下降，随后一条细长的尾巴一直延伸到173。
最深的那个胜局从下面这个局面开始，走棋方子力处于劣势，却仍能在173着后取胜：
在68个局面中，唯一的取胜着法是把小鸡打入一个它无法移动的格子。 落在对方底线的小鸡前方没有格子，因此这次打入几乎什么都没改变，接近于虚度一手。然而其他所有着法都输，偏偏这个近似虚手的着法能赢。下面的局面圈出了唯一能救棋的打入。
另外几项发现，不配图：
- 常常只有一个着法能赢。 约三分之一的必胜局面中，只有一个着法能保住胜势；其余任何着法都会丢掉。
- 欠行很常见。 开局并非特例：至少有21,839个局面属于这种陷阱，走棋就输，而如果允许不走则能守住。
- 约30%的必胜局面含有必然的将死，而且这些将死都很短：最长23着。
去掉打入规则
深度只有一个嫌疑对象：打入规则。被吃的棋子会回来，所以子力永远不会离开棋盘，局面不断重新组合，而不是逐渐稀疏走向残局。为了验证打入确实是原因，我在去掉这条规则后重新求解，让被吃子像国际象棋那样离场。结果崩塌了。可达局面从246,803,167降到962,894，最深的必胜从173着降到37着。开局的结论也翻转了：在真实规则下78着必负的先手方，现在成了和棋。同样的棋盘，同样的八枚棋子，只抽掉了一条规则。（没有外部求解器覆盖这个变体，所以它依赖的是我在标准规则上验证过的那套程序。）
| 有打入 | 无打入 | |
|---|---|---|
| 可达局面 | 246,803,167 | 962,894 |
| 最深必胜 | 173着 | 37着 |
| 开局结论 | 后手方78着取胜 | 和棋 |
结语
十二个格子、八枚棋子，被解出一个78着的必胜，尾巴一直延伸到173着。当子力不断循环回到场上，小棋局也能很深。
资源：
- 田中，《An Analysis of a Board Game ‘Doubutsu Shogi’》：最初的求解（日文）。
- brianhliou/dobutsu-shogi：我从零写的Rust求解器和局面浏览器。
- clausecker/dobutsu：Robert Clausecker独立完成的开源解，我的求解器就是与这份完整残局库做对照的。
- 棋子与棋盘美术 © 藤田麻衣子，出自由北尾まどか设计的《动物将棋》（どうぶつしょうぎ／「Let’s Catch the Lion!」），Nekomado 出品，经许可使用。