我做了 MistyFlipJungle，一個接近完美的翻棋鬥獸棋引擎。翻棋鬥獸棋是 4x4 的鬥獸棋，所有棋子開局時都是蓋著的。你可以 在 Mistboard 上與 MistyFlipJungle 對戰。 目的不只是做出一個強的棋手。引擎本身就是量測工具：搜尋量是另一方 512 倍的版本，仍然會輸掉彼此之間 23% 的對局。

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

量測項目 結果
搜尋階梯，1k 到 512k 節點 在 512x 的運算量跨度上相差 242 Elo
搜尋量多 512x 輸掉 23% 的對局
搜尋量多 8x 輸掉 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。在西洋棋裡，這麼多運算量值好幾百分。每 8x 一階的增幅維持在 64 到 89 Elo 附近，並在頂端趨平：320k 到 640k 節點只值 6 Elo。

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

有一個躍升很大，在最底層。1k 節點的搜尋約有 99% 的時候打敗隨機走子的棋手（各層合計，隨機方 800 局全敗），差距接近 850 Elo。從隨機到完美的距離中，約有 80% 就在這一步，也就是從隨機走子變成有搜尋。它上面的階梯很淺。

調整評估值毫無作用。更好的子力值、鼠與象的專項項、以及避免和棋，在成對自我對戰中全都沒有差別。在這麼受機率左右的遊戲裡，評估值的差異會被沖淡。

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

完美對完美

搜尋階梯只是估計開局，並沒有解出它。足夠小的遊戲可以徹底求解。我把完整的迷你版本從頭到尾解完，包含開局的翻棋：兩子與四子，開局時每格都蓋著，依完整規則下到終局。

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

要從開局解出一個六子的遊戲，而不只是單一殘局局面，就已經跨過四千萬個不同局面：正是同一道牆讓完整遊戲遙不可及。所以這對小版本是精確的，對完整的十六子遊戲則未經證明。

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

求解的現況

逐層看這個遊戲對照精確計算的狀況。這些表不計時鐘（忽略 40 著無進展規則），涵蓋各子數下每一個完全揭露的局面；每筆記錄存下雙方最佳著法下的結果，以及到該結果的距離。

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

六子在租來的伺服器上建得出來，但對引擎毫無價值：五子的覆蓋已經涵蓋了每一個能查到表的殘局，其餘的靠搜尋就下得接近最佳。再往上，要解出完整遊戲就意味著要解開局，而開局就是翻棋樹：十六個不同的棋子以隨機順序被翻出，可達狀態數在 10^11 以上的量級。前一節的迷你版本是連那棵樹一起從頭解到尾的；十六子的遊戲不是，而我看不到通往它的路。

距離那一欄，是我第一次做錯的部分。最初的表只存勝、和、負，別的都沒有，這足以評分著法，但不足以下完一局。下面觀看器裡的第 5 局就是這樣：從第 24 著起，黑方有一虎一鼠對紅方孤象，在表中是必勝（鼠在三著內困住象，因為象不能吃鼠）。黑方從未把這個勝勢送掉，也從未把它兌現。每個獲勝著法分數都一樣，機動力當作平手的判準在其中挑一個，輸的一方樂於原地繞圈，重複局面規則就判成和棋。連續八回合，引擎握著必勝、走出表格評為最佳的著法，卻一點進展都沒有。

存下距離就修好了：3 步勝現在勝過 9 步勝，所以引擎會走最短的必勝路線，並把必敗拖長。從必勝的殘局庫局面出發，它現在恰好以表上的步數結束，而第 5 局的殘局以鼠三著吃象作收。西洋棋幾十年前就碰過同一件事，這也是為什麼 Syzygy 表在勝/和/負旁邊附上一個距離度量。有些教訓你會在 4x4 的棋盤上重新發現一次。

看它下棋

引擎以全力自我對戰。五局，各自一個棋盤。用箭頭逐著瀏覽任一局，從全部蓋著到終局。第 5 局就是距離那一節所剖析的和棋：舊的表，沒有距離度量，一個必勝殘局被引擎連續握了八回合卻沒下完。它留在這裡當作那個 bug 的展品。換上帶距離的表後，它在同一個局面下贏了，鼠三著吃象。

現況

棋力在這裡是真的。242 Elo 的階梯是真實的差距，而在長賽程中較強的引擎會贏。天花板落在單局上：發到的棋與翻出的棋決定了任何一局中很大的比例，所以即使強得多的棋手也常輸，而單一結果對誰更強幾乎說明不了什麼。棋力顯現在平均值裡，不在單局裡。

引擎在我能檢查的地方接近完美，在我不能檢查的地方未經驗證，那就是開局。我唯一還沒有的量測，是對上強人類棋手的等級分，那是僅剩的、不必依賴引擎或其求解器、也不必承接它們漏掉的東西的檢驗。

資源：