オセロ 4.0 探索の可視化 – ゲームAIの先読みを目で見る

ゲームAIの解説書を読むと「アルファベータ法で先読みする」と書いてあります。理屈は分かっても、実際にどんな順番で手を調べ、どこで打ち切っているのかは、文章だけではなかなか頭に入りません。

そこで、オセロの対戦相手（COM）が先読みしている様子を、そのまま画面で見られるようにしました。プログラムを勉強している方向けのバージョンです。

何が見えるのか

盤の下にある「いまの盤面で読ませる」を押すと、COM の先読みが始まります。1 ステップずつ進めながら、次の 4 つを目で追えます。

いちばん見てほしいのが枝刈りです。打ち切りが起きると、調べずに済ませた手が赤い破線のノードとして現れます。「このマスは候補だったけれど、調べるまでもなく却下された」ということが一目で分かります。

「枝刈り: する／しない」を切り替えると、同じ局面でどれだけ手間が変わるかが数字で出ます。実際に測った値がこちらです。

深く読むほど差が開きます。ちなみに実戦の「普通」は 5 手読みで、枝刈りなしなら 45 万ノードかかる計算を、4 千ノードほどに抑えています。

ノードの枠の色は手番を表します。青が COM（白）の番で点数を最大にしたい場面、オレンジがあなた（黒）の番で点数を最小にしたい場面です。交互に入れ替わるのがミニマックス法の考え方そのものです。

内部では「探索しながら描く」のではなく、いったん全部記録してから再生する方式にしています。探索中に「ノードに入った／点数をつけた／枝刈りした／戻った」というできごとを配列に貯めておき、画面はそれを順番に再生するだけです。

こうすると巻き戻しができますし、何より対局用の思考ルーチンに手を入れずに済みます。記録を取らないときは、従来とまったく同じ処理が走ります。

スマートフォンでも見られるように、操作ボタンは画面上部に貼り付くようにしました。樹形図をスクロールしながら「1つ進む」を押し続けられます。

インストール不要、ブラウザだけで動きます。