解決動物將棋
簡而言之
- 動物將棋是 3×4 的兒童將棋，已被強解：後手在 78 著取勝。田中哲朗於 2009 年解決了它。
- 我用 Rust 從零重現了這個結果：全部 246,803,167 個可達局面，在 50,000 個樣本上與 Robert Clausecker 的獨立解答零不符。
- 打入讓它變深。移除被吃棋子可以回到場上的規則，局面數降到 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，經授權使用。