要点

  • MistyFlipJungleは、全駒が裏向きの4×4闘獣棋であるめくり闘獣棋を指し、厳密なテーブルベースと照合すると終盤の最適手を99〜100%の確率で選ぶ。
  • 探索を512倍にして得られるのは約242 Elo で、強い側のエンジンでも23%の対局を落とす。ランダムなめくりが十分な数の対局を決めてしまい、探索ではその差を埋めきれない。
  • 強さの大半は最初の一歩にある。とにかく探索するだけでランダムな指し手に約99%勝ち、最善手までの距離のおよそ80%を占める。
  • 解決済みのミニチュア版は引き分け。勝ちまでの距離をテーブルに保存することで、勝ち終盤をいつまでも決めきれなかったエンジンが直った。

全駒が裏向きで始まる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マス動かす。相手の駒をすべて取れば勝ちだ。

取りは序列に従う。強い動物が弱い動物を取る。重要な例外が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%が、ランダムに指すことからとにかく探索することへの、この一歩だ。その上のはしごは浅い。

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

運によって圧縮されたゲームとしてはバックギャモンが定番だが、めくり闘獣棋のほうが圧縮は強い。盤は小さく、終盤は解かれており、序盤は完全にランダムだ。

最善手対最善手

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

双方の最善手のもとでは、これらは引き分けになる。厳密な値はゼロで、最適な手順は毎回引き分けになる。最善手を指す2人は互いに勝てない。

単一の終盤局面ではなく序盤から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局、それぞれ別の盤に。矢印でどれでも1手ずつ、全裏向きから終局まで辿れる。第5局は距離の節で分解した引き分け局だ。古いテーブル、距離の指標なし、エンジンが8手番続けて決めきれなかった勝ち終盤。そのバグの展示物としてここに残してある。距離付きのテーブルなら同じ局面に勝ち、鼠が3手で象を取る。

現在地

ここでは技術は実在する。242 Elo のはしごは本物の差で、長いマッチなら強いエンジンが勝つ。上限は単局にある。配置とめくりが任意の1局の大部分を決めるので、はるかに強いプレイヤーでもしばしば負け、1つの結果はどちらが上かをほとんど語らない。技術は平均に現れ、1局には現れない。

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

資料：