解決動物將棋
動物將棋（「どうぶつしょうぎ」）是在 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，經授權使用。