6x6リバーシの神

絶対に勝てない6x6リバーシを作りました。あなたは黒番、AIが白番です。

これは何？

6x6の盤面のリバーシは後手必勝 *1 であることが知られています。 このAIは白番（後手）で完璧にプレイします。つまり黒番のあなたは絶対に勝てません。無力感を楽しんでください。

技術的な話

このAIはWebAssemblyになっているので、全部あなたのブラウザの上で動いてます。真のサーバーレスです。

AIのソースコードはRustで書きました。わりと堅実なゲーム木探索になってます。UIは普通にTypeScriptとthree.jsで実装しました。

github.com

作った順に説明します。

盤面の表現

なにはともあれ、盤面を表すデータ構造を作りました（src/bitboard.rs）。 ファイル名の通り、ビットボードです。 Rustのu64（64ビット整数）を2つ使って1つの盤面を表現します（1つが黒石の位置、もう1つが白石の位置）。

着手可能数のカウントなどすべて、ビット演算を駆使してやります。 石をひっくり返す処理は探索性能に直結するのでがんばってます。 36マスすべてに特化したコードをマクロで生成してます（src/bitboard/flip.rs）。 ただし、最終的にWASMにするので、アセンブリを書くようなことはしてません。

ちなみにビットボードを選んだ理由は、そうしないとRustの所有権や借用がすごく面倒くさそうだったからです。 ビットボードならu64が2つだけなので、雑にCopyトレイトを実装しても大丈夫。

終盤のアルゴリズム

最初に書いた探索アルゴリズムは、単純なネガマックス法です。 これはゲーム終盤（空きマスが11個以下）の探索に使っています。

終盤の探索は、凝ったアルゴリズムより、定数オーダの最適化がよく効くところです。 たとえば、空きマスを探すために全マスをチェックすると遅いです（終盤の場合、多くのマスはすでに石があるので無駄）。 そこで、終盤の探索に入る前にすべての空きマスの位置を列挙して連結リストでつなぎ、再帰のたびにこのリストをなめるようにしています。

残念ながら、Rustはリスト構造の扱いが極めて不得意な言語です *2 。 Rustでリストを作るには（型チェックを通すために）リファレンスカウントのセルを使うのが定番のようですが、今回はパフォーマンスが重要なのでunsafeを使いました。 こういうときはunsafeで良いという知見をもらっていたので。

中盤のアルゴリズム

次に、単純なネガマックス法で深く読むことはできないので、空きマスが12個以上あるときのためのもう少し賢いアルゴリズムを実装しました。 置換表付きMTD(f)＋評価関数によるムーブオーダリングという、とても昔ながらの方法です（src/search/midgame.rs）。

評価関数は、手動で作った特徴量（いわゆるedge2xのパターンと、着手可能数）を入力とし、勝ちそうか負けそうかを予測します。 これの学習のために、中盤の盤面を数十万ほどランダム生成し、それぞれに対して終盤探索のアルゴリズムを使って実際の勝敗を判定しました。 そして実際の勝敗を教師データとして焼きなまし法と最急降下法を適当に使って重みを決めました（src/learn.rs）。 学習した重みは浮動小数点数が3000個ちょっとなので、Rustの配列としてコードに直接埋め込んであります（data/weight.rs）。

あと、ビットボードのedge2xパターンから高速に係数を算出するために、完全ハッシュを用意しました。

補足 このヒューリスティックな評価関数はあくまでムーブオーダリング（良さそうな手から先に調べることで枝刈りを増やすテクニック）のために使っているだけです。メインの探索では、空きマスが11個のところまで読んだら終盤探索アルゴリズム自体を評価関数として使います。なので、全体としては近似解法ではなく完全探索になります。

序盤のアルゴリズム

6x6のリバーシは1993年に後手必勝であることが示されたそうです。 当時のワークステーションで数週間くらいかけて探索したらしいですが、そんな計算も現代では一瞬……かと思ったのですが、ここまでで作ったアルゴリズムで初期盤面からの探索をすると、1分強かかりました。ディープラーニングで評価関数作ってムーブオーダリングするともっと速くなるのかなあ？

これでリアルタイムに探索するのは厳しいので、序盤の16手をあらかじめ計算してしまうことにしました。 黒が任意の手を選ぶのに対し、白の手は1つだけ覚えればいいので、深さ8のツリーを作ります。 白は最善手（最も大きい石差で勝つ手）のうち、黒の着手可能数が小さくなる枝を選ぶようにすることで、なるべく覚える数を減らしました。 結果的に、およそ10万盤面程度を覚えることになりました。

ツリー部分は簡潔データ構造を使ったLOUDSという表現でエンコードし、およそ700キロバイトとなっています *3 。 そんなに大きくないので、include_bytes!マクロでバイナリデータを直接実行ファイルに埋め込みました。

これでAIは完成です。

ブラウザで動かす

ここまでは、Linuxでのネイティブ実行ファイルとして作ってました。 今回は探索をブラウザで動かす目標だったので、wasm-bindgenでブラウザ向けのAPIを用意し（src/api.rs）、wasm-packでWebAssembly（以下wasm）にしました。 emscriptenに比べるとびっくりするほど簡単にwasmができたのでびっくりしました。

ただ、動かして見るとpanicで落ちました。 「やっぱりwasm生成は完成度そんなに高くないのかなー」などと他人のせいにしつつ、何が起きているか調べてみると、usizeでオーバーフローが発生してました。 試してたネイティブビルドは64ビットなのでオーバーフローしないのですが、wasmは32ビットなのでオーバーフローが起きる。 要するに完全に自分のせいでした。完成度高いなあ。

直したら無事にwasmがWeb workerから動きました。 なお、panicは調べ始めてから数十分で直せたのに対し、wasm+Web workerのwebpackの設定に数時間ほど消費しました。webpack許せない。

UI部分

ここまでRustで開発してきたので、UIもyewで！ などと考えなくもなかったのですが、この時点でRustへのヘイトが溜まりすぎていたのでTypeScriptで書きました。 いやー、ちょっとmapしたいだけなのにiterだのcollectだの書かないといけないとか、雑なコード書くとunwrapだらけになるし……。

閑話休題。

かっこいいUIを作りたくなったので、three.jsを使うことにしました。 最初はReactで実装しようとしましたが、three.jsが状態のかたまりで相性最悪だった *4 ので、素で書きました。

雑感

完全解析されているゲームは、どうやっても勝てないところを実際に体験したいですよね。 6x6リバーシのパーフェクトプレイの棋譜は発見者のJoel Feinsteinが書いたニュースレターを始めいろいろなところで見かけますが、インタラクティブにできるものは見つからなかったので作りました。

あと、wasmで遊んでみたかったのも動機です。 6x6リバーシは全盤面をデータベースにするのは明らかに無理なので、ブラウザで現実的に動かせる速度とバイナリサイズを実現するにはwasmがよいかなと。 はやくWebアプリのフロントエンドが全部wasmで動く世界になるといいなあ。

まとめ

6x6のリバーシはやっぱり勝てませんでした。

*1:後手が正しい手を選び続けたら、先手が絶対に勝てないこと。

*2:Rustとリストで検索すると「リスト構造は実用プログラムではほとんど登場しないからいいんだ」みたいな主張を多数見かけます。すっぱいぶどう？

*3:正確に言うと、ツリー構造のデータは80キロバイト程度で、大半は黒の手の価値（最終的な石差）と白が打つべき位置のデータです。

*4:最初は@react-three/fiberを試しましたが、まともにパフォーマンスを出すためにはアニメーション状態などをReactから別管理するしかなさそうで、Reactを使う意味が薄そうだった。