全ての駒が裏向きで始まる4x4の闘獣棋、めくり闘獣棋のためのほぼ最善のエンジン MistyFlipJungle を作った。 Mistboard で MistyFlipJungle と対戦できる。 狙いは単に強いプレイヤーを作ることではなかった。エンジンは測定器だ。探索量が512倍多いコピーでも、対戦の23%を落とす。

だからこれは少し違う種類のエンジン記事になる。暗棋は偶然ノードがあるゲームで何を測るべきかを問う。闘獣棋は完全情報の動物ゲームで古典的探索がどこまで通用するかを問う。めくり闘獣棋は、駒が隠されたまま始まるとき技量がどれだけ残るかを問う。体感よりは少ない。

測定項目 結果
探索の階段、1kから512kノード 計算量512倍の範囲で242 Elo
探索量512倍 対戦の23%を落とす
探索量8倍 37〜40%を落とす
探索あり対ランダム 約99%（ランダムは800局中0勝）
終盤（5駒以下）対厳密テーブルベース 99〜100%が最適
中盤（5〜6駒）対厳密ソルバ 200手中200手が最適

ゲームについて

めくり闘獣棋は4x4の盤で、各側8体ずつ計16体の動物を使って指す。全ての動物は裏向きで始まる。自分の手番では、タイルを1枚めくってランダムな動物を公開するか、表向きの動物を1マス動かす。相手の駒を全て取れば勝ちだ。

取りは強さの順に従う。強い動物が弱い動物を取る。例外が2つ重要だ。鼠は象を取る。最弱が最強を破る。そして同じ強さの動物同士は相討ちになり、両方が盤から消える。

取りの順序、最強から最弱へ

象
獅子
虎
豹
狼
犬
猫
鼠

各動物は右側の動物を取れる。さらに鼠は象を取り、同じ強さの動物同士は相討ちで両方が盤から消える。

遊べる盤付きの完全なルール：mistboard.com/rules/jungle-flip。

標準の闘獣棋、つまり前回の記事で扱った完全情報版は純粋な計算だ。盤面が全部見える。めくり闘獣棋は駒を隠し、めくったタイルの正体はランダムになる。ばらつきの源はこのめくりだ。

エンジン

Rust、アルファベータ探索、手作りの評価関数、ニューラルネットワークなし。置換表付きのネガマックス、反復深化、取りに対する静止探索、キラー手とヒストリーによる手順序付け。評価は駒得と機動力に引き分け回避項を加えたもの。強さは時計ではなくノード数の予算で決めるので、同じ局面ならどのマシンでも同じ手を返し、測った差はハードウェアではなくエンジンに帰属する。

めくりは偶然ノードになる。めくりの地点では、袋から出得る駒についての平均が値となり、偶然ノード版のアルファベータであるスターミニマックスで枝刈りする。手順序付けは十分に働く。キラーとヒストリーの順序付けで、ある深さに達するのに必要なノード数が半分になり、枝刈りなしの探索と照合して同じ値を返すことを確認した。つまり探索が計算する内容を変えずに、同じ予算でおよそ1手分の深さを買っている。

終盤は別扱いで、厳密なテーブルベースを使う。めくり闘獣棋の終盤は後退解析で解ける。終了局面すべてから逆向きに進めて、最善手での結果を記録する。テーブルは完全インデックス（キーなし）のフラット配列として保存し、結果に2ビット、そこまでの距離に1バイトを使い、コア並列で構築した。並列化の落とし穴はこうだ。各局面を手番色について正規形へ写すことでテーブルは半分になるが、静かな手は手番を反転させるので、ある局面の子が、バケット単位の素朴な分割が想定するのとは別のバケットに入り得る。解の過程は単調で、局面は未知から確定した結果へ一度しか変わらない。これが並列構築を安全にしている。

測り方

自己対戦が測るのは2つのバージョンのどちらが強いかであって、どちらかがうまく指しているかではない。同一エンジンのコピー2つは同じ盲点を共有するので、両方が同じ局面を読み違えていれば、両者間のスコアはそれについて何も語らない。手の質はかわりにテーブルベースで採点する。

解ける終盤（5駒まで）では、エンジンは99〜100%の割合で最適手を指し、外した分は探索深さの問題で、より深い探索で解消した。テーブルベース上に構築した前進ソルバはもう少し先まで届き、タイルが裏向きのままの5駒・6駒の中盤に入る。そのうち200局面では毎回最適手と一致した。

この網羅は厳密計算が止まるところ、つまりゲーム終盤付近で止まる。めくりが起こる序盤は大きすぎて解けないので、ここではエンジンの序盤の指し手を何も検証していない。「ほぼ最善」とは、私が確認できる局面においてほぼ最善という意味だ。

技量の上限

厳密な答えなしに序盤を測るため、強さの異なるエンジンを比べた。1k、8k、64k、512kノードを探索する4つのコピーが、先後を入れ替えたペア対局の総当たりを組み合わせごとに120局行い、結果からレーティングを当てはめた。

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

探索量512倍の増加はおよそ242 Eloに相当する。チェスなら同じ計算量は数百Elo分の価値がある。刻みは8倍ごとに64〜89 Elo付近にとどまり、上の方では平坦になる。320kから640kノードは6 Elo分だった。

番狂わせの率はレーティングが示唆するより大きい。8倍強いエンジンは対戦の37〜40%を落とし、512倍強い側は23%を落とす。めくりだけで決まる対局が十分に多く、探索を増やしても差は埋まらない。

大きな跳躍が1つ、最下段にある。1kノードの探索はランダムプレイヤーに約99%勝つ（各層を通じてランダムは800局中0勝）。差はおよそ850 Eloだ。ランダムから最善までの距離の約80%が、この1段、つまりランダムに指すことから探索すること自体への段差にある。その上の階段は浅い。

評価関数の調整は何の効果もなかった。駒の価値の改善、鼠と象に関する項、引き分け回避、どれもペア自己対戦では横ばいで戻ってきた。これだけ偶然の比重が大きいゲームでは、評価の差は洗い流される。

運で圧縮されたゲームといえば通常はバックギャモンだが、めくり闘獣棋はもっと圧縮されている。盤が小さく、終盤は解かれており、序盤は完全にランダムだ。

最善対最善

階段は序盤を推定するが、解くわけではない。十分に小さいゲームなら完全に解ける。私はミニチュア版を序盤のめくりを含めて端から端まで解いた。2駒と4駒、開始時は全タイルが裏向き、完全なルールのもとで終局まで。

双方が最善手を指すと引き分けになる。厳密な値はゼロで、最適な手順は毎回引き分けになる。最善を指す者同士は互いに勝てない。

単一の終盤局面ではなく序盤から6駒のゲームを解くだけで、すでに4000万を超える異なる局面に達する。フルゲームを手の届かないところに置いているのと同じ壁だ。というわけでこれは小さい版については厳密で、16駒のゲーム全体については未証明だ。

それでも最善手の価値は定まる。最善対最善は引き分け。最善対はるかに弱いプレイヤーはほぼ確実な勝ちで、ランダムに指す側は800局すべてを落とした。512倍強いエンジンが落とす23%はその間にある。実力の近い2者、ばらつきの中に収まる差、めくりが決める展開。負けはプレイヤー間の差から来るのであって、最善手そのものから来るのではない。

解明の現状

厳密計算に対してこのゲームがどこまで来ているかを、層ごとに示す。テーブルは時計なし（40手の無進展ルールを無視する）で、各駒数において完全に公開された局面をすべて網羅する。各エントリは最善手での結果とそこまでの距離を保存する。

駒数 局面数 最長の必勝手順 構築
2 28,800 9手 即時
3 1.9M 21手 2 秒
4 79M 41手 200 秒
5 2.3B 63手 ノートPCで4時間、2.8 GB
6 46B 未構築 数日、RAM 約140 GB

6駒はレンタルサーバなら構築可能だが、エンジンにとっては何の価値もない。5駒の網羅でテーブルに到達する終盤はすべて採点できるし、残りは探索がほぼ最適に指す。それを越えると、フルゲームを解くことは序盤を解くことを意味し、序盤とはめくりの木だ。16種の異なる駒がランダムな順で公開され、到達可能な状態は10^11以上のオーダーになる。前節のミニチュア版はその木を通して端から端まで解けている。16駒のゲームは解けておらず、そこへの道筋も見えない。

距離の列は、最初に私が間違えた部分だ。当初のテーブルは勝ち・引き分け・負けだけを保存していて、それは手を採点するには足りるが、対局を終わらせるには足りない。下のビューアの第5局がその姿だ。24手目から黒は虎と鼠で赤の孤立した象に対しており、テーブルでは必勝だ（象は鼠を取れないので、鼠は3手で象を追い詰める）。黒は勝ちを手放さない。だが実現もしない。勝ちにつながるすべての手が同じ評価値になり、機動力のタイブレークがその中から選び、負け側は動き回るだけで満足し、千日手のルールが引き分けを宣告した。8手番続けて、エンジンは必勝を保持し、テーブルが最適と採点する手を指し、まったく前進しなかった。

距離を保存すれば直る。3手詰めの勝ちが9手詰めの勝ちより上位になるので、エンジンは最短の必勝を選び、必敗は引き延ばす。テーブルベース上の勝ち局面からは、いまやテーブルの距離どおりに終わらせ、第5局の終盤は鼠が3手で象を取って終わる。チェスも数十年前に同じ問題にぶつかった。だからこそ Syzygy のテーブルは勝ち・引き分け・負けの隣に距離の指標を載せている。4x4の盤の上で再発見できる教訓もあるということだ。

対局を見る

フル強度でのエンジンの自己対戦。5局、それぞれ独立した盤で。矢印でどの局も、全部裏向きの状態から終局まで送れる。第5局は距離の節で解剖した引き分けの局だ。旧テーブル、距離指標なし、勝ちの終盤を8手番続けて保持しながら決めきれない。あのバグの展示物としてここに残してある。距離付きテーブルなら同じ局面に勝ち、鼠が3手で象を取る。

現在地

ここでの技量は実在する。242 Eloの階段は実際の差で、長いマッチなら強いエンジンが勝つ。上限があるのは単局だ。配置とめくりが1局の相当部分を決めるので、はるかに強いプレイヤーでも頻繁に負け、1つの結果はどちらが上かをほとんど語らない。技量は平均に現れ、1局には現れない。

このエンジンは私が確認できる範囲ではほぼ最善で、確認できない範囲、つまり序盤では未検証だ。手元にない唯一の測定は、強い人間に対するレーティングだ。エンジンやそのソルバに依存せず、それらの見落としを引き継がない、残された唯一の検証だ。

関連リンク：