簡而言之

  • MistyFlipJungle 下的是翻棋鬥獸棋，4×4 的鬥獸棋，所有棋子都背面朝下；對照精確殘局庫，它在 99% 到 100% 的情況下選出最佳殘局著法。
  • 搜尋量增加 512 倍約可換來 242 Elo，而較強的引擎仍有 23% 的對局會輸。隨機翻棋決定了足夠多的對局，搜尋無法弭平這個差距。
  • 大部分棋力來自第一步：只要有搜尋，就能以約 99% 的比率擊敗隨機著法，大約是通往完美的八成路程。
  • 已解出的小型版本都是和棋。在表中儲存取勝距離，修正了引擎一直守著已勝殘局卻不去完成的問題。

我做了 MistyFlipJungle，一個接近完美的翻棋鬥獸棋引擎。翻棋鬥獸棋是 4x4 的鬥獸棋，開局時每顆棋子都背面朝下。你可以 在 Mistboard 上與 MistyFlipJungle 對弈。 重點不只是做出一個強棋手。這個引擎是量測工具：一份搜尋量比另一份多 512 倍的副本，仍然會輸掉彼此對局的 23%。

所以這是一篇不一樣的引擎文章。暗棋問的是，當局面樹中有機率節點時該量測什麼。鬥獸棋問的是，在完全資訊的動物棋裡古典搜尋能走多遠。翻棋鬥獸棋問的是，當棋子一開始是隱藏的，還有多少棋力能存活下來。比感覺上的少。

量測項目 結果
搜尋階梯，1k 到 512k 節點 512 倍算力範圍共 242 Elo
搜尋量多 512 倍 輸掉 23% 的對局
搜尋量多 8 倍 輸掉 37% 到 40%
任何搜尋對隨機著法 約 99%（隨機方 800 局全敗）
殘局（≤5 子）對照精確殘局庫 99% 到 100% 為最佳著
中局（5 至 6 子）對照精確求解器 200 著中 200 著為最佳

這個遊戲

翻棋鬥獸棋在 4x4 棋盤上進行，共十六隻動物，每方八隻。所有動物開局都背面朝下。輪到你時，可以翻開一格，揭示一隻隨機的動物，或把一隻正面朝上的動物走一格。吃掉對手所有棋子即獲勝。

吃子依等級：強者吃弱者。有兩個例外很重要。鼠吃象，最弱的打敗最強的。而同級的兩隻動物互換，兩者都離開棋盤。

吃子順序，由強到弱

象
獅
虎
豹
狼
狗
貓
鼠

每隻動物可吃其右方者。鼠也能吃象，同級的兩隻動物互換，兩者都離開棋盤。

完整規則並附可對弈棋盤：mistboard.com/rules/jungle-flip。

標準鬥獸棋，也就是上一篇文章裡的完全資訊版本，是純計算：你看得見整個棋盤。翻棋鬥獸棋把棋子藏起來，翻開的格子身分是隨機的。變異性就來自這些翻棋。

引擎

Rust、alpha-beta 搜尋、手工評估函式，沒有神經網路。Negamax 搭配置換表、迭代加深、吃子的靜態搜尋，以及 killer 與 history 著法排序。評估值是子力加機動性，另有一個厭和項。強度以節點預算而非時鐘決定，因此同一局面在任何機器上都回傳相同著法，量到的差距屬於引擎而非硬體。

翻棋是機率節點。在翻棋處，其值是袋中可能揭示的各棋子的平均，並以 star-minimax 剪枝，也就是機率節點版的 alpha-beta。著法排序值得一席之地：killer 與 history 排序把達到給定深度所需的節點數減半，並與未剪枝的搜尋核對，確認回傳的值完全相同，因此在相同預算下大約多換得一著深度，而不改變搜尋計算的內容。

殘局另行處理，使用精確殘局庫。翻棋鬥獸棋的殘局可用逆向分析求解：從每個結束局面往回推，記錄雙方最佳著法下的結果。我把表存成扁平陣列並用完美索引（不需鍵值），結果佔兩個位元，再加一個位元組存到達該結果的距離，並跨核心平行建表。平行化的陷阱在於：表透過把每個局面映射到顏色標準形而減半，而一步安靜著法會翻轉輪誰走棋，因此一個局面的子節點可能落在與天真的分桶切法所假設的不同桶裡。求解過程是單調的，一個局面只會從未知轉為固定結果，這正是平行建表安全的原因。

量測方式

自我對弈量的是兩個版本中哪個較強，而不是哪個下得好：同一引擎的兩份副本共享相同盲點，若兩者都誤判某個局面，它們之間的分數對此毫無說明。著法品質改為對照殘局庫來評分。

在可解的殘局（最多五子）中，引擎在 99% 到 100% 的情況下走出最佳著，失誤都是搜尋深度問題，更深的搜尋即可解決。建在殘局庫之上的前向求解器可以再往前一點，進入仍有格子背面朝下的五子與六子中局；在其中 200 個局面上，它每次都符合最佳著。

這種覆蓋範圍止於精確計算的極限，也就是接近終局處。開局，也就是翻棋發生的地方，規模太大而無法求解，所以這裡沒有任何東西驗證引擎的開局下法。「近乎完美」指的是在我能檢查的局面中近乎完美。

棋力上限

為了在沒有精確答案的情況下量測開局，我比較了不同強度的引擎。四份副本分別搜尋 1k、8k、64k 與 512k 節點，進行成對、交換先後手的循環賽，每組配對 120 局，並從結果擬合出等級分：

1k nodes     +0
8k nodes    +89
64k nodes  +153
512k nodes +242

搜尋量提升 512 倍約換來 242 Elo。在西洋棋裡，這麼多算力值好幾百分。每 8 倍的級距維持在 64 到 89 Elo 附近，並在頂端趨於平緩：320k 到 640k 節點只值 6 Elo。

翻盤率比等級分所暗示的更大。強 8 倍的引擎會輸掉 37% 到 40% 的對局；強 512 倍的那個輸掉 23%。翻棋本身就決定了足夠多的對局，再多搜尋也補不上這個差距。

有一個跳躍很大，在最底端。1k 節點的搜尋約有 99% 的比率擊敗隨機棋手（隨機方在各層級共 800 局中全敗），差距接近 850 Elo。從隨機到完美的距離中，約 80% 就是這單一步：從隨機走子到開始搜尋。它上面的階梯很淺。

調整評估函式毫無作用。更好的子力價值、鼠與象的專門項、厭和傾向，在成對自我對弈中全都沒有差別。在這麼吃機率的遊戲裡，評估上的差異會被沖淡。

西洋雙陸棋是常見的運氣壓縮型遊戲；翻棋鬥獸棋壓縮得更多，棋盤更小、殘局已解、開局完全隨機。

完美對完美

這個階梯只是估計開局，並未求解它。足夠小的遊戲可以徹底解出。我從頭到尾完整解出了小型版本，包含開局翻棋：兩子與四子，開局時每格都背面朝下，依完整規則下到終局。

在雙方最佳著法下，它們都是和棋。精確值為零，最佳路線每次都和。兩個完美棋手無法擊敗彼此。

從開局而非單一殘局局面去解一個六子遊戲，就已跨越四千萬個不同局面：正是把完整遊戲擋在門外的那道牆。所以這對小型版本是精確的，對整個十六子遊戲則未經證明。

這仍然釘住了雙方最佳著法值多少。完美對完美是和棋。完美對遠弱的棋手幾乎必勝：隨機走子方 800 局全敗。強 512 倍的引擎仍輸掉的那 23% 落在中間：兩個接近的棋手，差距落在變異之內，由翻棋決定。這些敗局來自棋手之間的差距，而非來自雙方最佳著法本身。

求解的現況

以下逐層列出這個遊戲在精確計算下的進展。這些表不計時（忽略 40 著無進展規則），並涵蓋各子數下每個完全揭示的局面；每筆條目儲存雙方最佳著法下的結果與到達該結果的距離。

子數 局面數 最長必勝步數 建表
2 28,800 9 著 瞬間
3 1.9M 21 著 2 秒
4 79M 41 著 200 秒
5 2.3B 63 著 筆電上 4 小時，2.8 GB
6 46B 未建 數天，約 140 GB 記憶體

六子在租用的伺服器上可以建出來，但對引擎毫無價值：五子的覆蓋已能評分所有進入表中的殘局，其餘則由搜尋近乎最佳地下完。再往前，求解完整遊戲就意味著開局，而開局就是翻棋樹：十六顆不同棋子以隨機順序揭示，可達狀態數在 10^11 以上。上一節的小型版本已經連著那棵樹端到端解出；十六子的遊戲沒有，而我看不到通往它的路。

距離那一欄是我第一次做錯的部分。最初的表只存勝、和、負，別無其他，這足以評分著法，但不足以結束對局。下方檢視器中的第 5 局就是那個樣子：從第 24 著起，黑方有一虎一鼠對紅方孤象，在表中是必勝（鼠在三著內困住象，因為象不能吃鼠）。黑方從未把勝勢送掉，也從未把它轉化。每一個獲勝著法分數都一樣，機動性當作決勝依據從中挑選，輸的一方樂於原地兜轉，重複規則就判成和棋。連續八回合，引擎握著必勝、走出表中評為最佳的著法，卻毫無進展。

儲存距離就修好了：三著取勝現在排在九著取勝之前，所以引擎會選最短的必勝路線，並把必敗拖長。從表中的必勝局面出發，它現在會以表中距離精確結束，而第 5 局的殘局以鼠在三著內吃象收尾。西洋棋幾十年前就碰上同樣的事，這也是 Syzygy 表除了勝/和/負之外還附帶距離度量的原因。有些教訓，你有機會在 4x4 棋盤上重新發現一次。

觀看它對弈

引擎以全力自我對弈。五局，各自一個棋盤。用箭頭逐步瀏覽任一局，從全部背面朝下到終局。第 5 局就是距離那一節剖析的和棋：舊的表、沒有距離度量、一個引擎握了連續八回合卻沒結束的已勝殘局。它留在這裡作為那個缺陷的展品。有了距離表，它在同一個局面會取勝，鼠在三著內吃象。

現況如何

棋力在這裡是真實的。242 Elo 的階梯是真實的差距，長期對抗賽下來較強的引擎會贏。上限在單局：發牌與翻棋決定了任一單局中很大一部分，所以即使強得多的棋手也經常會輸，而單一結果幾乎說不出誰比較強。棋力顯現在平均，而不在單局。

這個引擎在我能檢查的地方近乎完美，在我不能檢查的地方未經驗證，也就是開局。我唯一缺的量測是對強人類棋手的等級分，那是剩下唯一不依賴引擎或其求解器、因而不會繼承它們盲點的檢驗。

資源：