リバーシは探索だけで足りたが、どうぶつしょうぎは2.1GBの解析を59KBに削る必要があった

測った結果

自己対局を1局ずつ行い、1手あたりの思考時間を計測しました(Node上での測定、各レベル1局)。

「やさしい」「ふつう」は固定の浅い深さなので、実質ゼロコストです。重いのは「つよい」だけで、そこは意図して1秒使っています。

平均が中央値より小さいのは、読み切れた局面では途中で打ち切っているためです。勝ち負けが確定したり、リバーシの終盤完全読みが早く終わったりすると、持ち時間を使い切らずに返ります。

持ち時間を5msの誤差で守る方法

探索の打ち切りで素直に書くと、再帰の各ノードで時刻を見ることになります。しかしDate.now()は毎ノード呼ぶには重く、探索速度がそのぶん落ちます。

採ったのは一定ノードごとにだけ時計を見る方法です。

private tick(): void {
  if (++this.nodes % TIME_CHECK_INTERVAL === 0 && this.now() > this.deadline) {
    throw new TimeUp()
  }
}

間隔はリバーシが2048ノード、どうぶつしょうぎが4096ノードごと。超過は最大でも「次のチェックまでに進むノード数ぶん」に限られ、実測では+4〜5msに収まりました。打ち切りは例外で投げ、呼び出し側で盤面を復元してから、最後に読み終えた深さの結果を使います(反復深化)。

共通してやったこと

どちらのゲームでも効いた実装は同じでした。

• 盤面はInt8Array1本で持ち、指す/戻すを同じ配列の上で行う。 探索中に盤のコピーを作らない
• リバーシは10×10の番兵付きにして、盤外判定を配列アクセスだけで済ませる
• αβ探索の手の並び順を工夫する。 リバーシは位置の重みが大きいマスから、どうぶつしょうぎは駒を取る手(特にライオンを取る手)から調べる
• 反復深化で、持ち時間内に読み終えた一番深い結果を採用する
• 計算はWeb Workerで動かす。 UIのスレッドを止めないため。Workerが使えない環境ではメインスレッドにフォールバックする

どうぶつしょうぎには加えて置換表(Zobristハッシュ、2つの32bit値で衝突を減らす)を入れています。持ち駒があり同じ局面に戻りやすいゲームなので、ここの効きが大きいためです。

逆に、速くしすぎた結果として最低450msは待つ処理も入れました。一瞬で指されると何が起きたのか分からないためで、速度の追求とは反対向きの調整です。

どうぶつしょうぎだけ必要だったもの

どうぶつしょうぎは既に完全解析されているゲームで、先手が負けることが分かっています。実際に自分でソルバーを書いて解かせたところ、次の結果になりました。

positions=213993386 immediate_win=127162333 win=174089910 loss=37228827 draw=2674649
initial: LOSS in 78 plies (max win distance 173)

2億1399万局面。初期局面は78手で先手の負けです。

問題はサイズでした。解析結果をそのまま持つとkeys.binが1.71GB、values.binが428MB、合わせて約2.1GB。ブラウザに配れる量ではありません。

そこで表に入れる局面を2段階で絞りました。

1. 後手CPUが最短勝ちの方針を取り続けたときに現れる局面だけを残す（全局面は要らない。勝ち筋の上に出てくる局面だけあればよい）
2. そのうち勝ちまで10手以上かかる局面だけを残す。それより短い勝ちは、ブラウザ側の探索が読み切れる

結果が 59KB です。約36,000分の1になりました。ブラウザは、短い勝ちは自分で読み、長い勝ちだけ表を引きます。事前計算と実行時探索の境界をどこに引くかで、配布サイズが決まるという形です。

その1秒に価値はあるのか

「つよい」だけ1手1秒使うので、それに見合う差が出ているかをリバーシで確かめました(先手後手を入れ替えながら対局)。

4局で石差合計+168、1局あたり平均+42です。64マスのゲームで平均42差なので、ほぼ一方的でした。深さ3から深さ12＋終盤16マスの完全読みへ上げたぶんは、はっきり結果に出ています。

同じ「ブラウザで動く軽量CPU」でも、ゲームによって必要なものが変わりました。探索で届く範囲なら探索だけでよく、届かないなら事前計算を足す。そして事前計算は全部持つ必要がなく、探索が届かない部分だけ持てば済みます。