动物将棋已被完全解决
动物将棋（「どうぶつしょうぎ」）是一款在3×4棋盘上、用八枚棋子进行的儿童将棋游戏。它已被完全解决：在双方最佳着法下，先行的一方会输。
职业将棋棋手北尾まどか于2008年设计了这款游戏，用来教孩子下将棋。2009年，田中哲朗计算出了每一个可达局面的精确值。后手方获胜，用时78着。
本文讲述这一解法揭示了什么，以及为什么这么小的棋盘会产生如此深奥的对局。深度来自将棋的一条规则，而大多数小型抽象游戏都没有这条规则：被吃掉的棋子会重新回到棋盘上。
来源： 田中哲朗，《棋类游戏「どうぶつしょうぎ」的分析》（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着。当子力不断循环回场，小游戏也会变得很深。
资源：
- 田中哲朗，《棋类游戏「どうぶつしょうぎ」的分析》：最初的求解（日文）。
- brianhliou/dobutsu-shogi：我从零写的Rust求解器和浏览器。
- clausecker/dobutsu：Robert Clausecker独立完成的开源解法，我的求解器就是对照这份完整残局库校验的。
- 棋子与棋盘美术 © 藤田麻衣子，出自由北尾まどか设计的《どうぶつしょうぎ》（「Let’s Catch the Lion!」），Nekomado，经授权使用。