リバーシAIの作り方 - ランダムからαβ枝刈りまで段階的に実装する

「リバーシのAIを作りたい」と思ったとき、何から始めますか？

いきなり最強のアルゴリズムを実装しようとすると、挫折しがちです。この記事では、3段階の難易度に分けてリバーシAIを段階的に実装していきます。実際にADA Labのリバーシゲームで動いているTypeScriptのコードを使って解説します。

盤面の表現

まず、リバーシの盤面をプログラムでどう表現するかを決めましょう。

8×8グリッドと数値

盤面は8×8の二次元配列で表現します。各マスの値は以下の通りです：

TypeScriptでは number[][] 型の二次元配列（Board型）として扱います。

石を挟む判定（getFlips）

リバーシの核心は「相手の石を挟んで裏返す」というルールです。ある位置に石を置いたとき、8方向すべてをチェックして、挟める石を探します。

getFlips(board, row, col, player) は、指定位置に石を置いたときに裏返せる石の座標リストを返す関数です。この関数が返すリストが空でなければ、その位置は合法手ということになります。

合法手の列挙（getValidMoves）

getValidMoves(board, player) は、盤面上のすべての空きマスに対して getFlips を呼び出し、1つ以上裏返せるマスの座標を配列で返します。AIはこの合法手の中から次の一手を選びます。

Level 1: Easy AI - ランダム選択

まずは最もシンプルなAIから始めましょう。合法手の中からランダムに1つ選ぶだけです。

たった3行。これだけで「ルールに従って打てるAI」が完成します。

なぜランダムAIが重要なのか？

「ランダムに打つだけなんて、AIじゃないでしょ？」と思うかもしれません。でも、ランダムAIには重要な役割があります。

上位のAIを作ったとき、ランダムAIに勝率90%以上なければ何かがおかしい、という判断材料にもなります。

Level 2: Normal AI - 位置評価ヒューリスティック

ランダムAIの次は、「どのマスに打つのが有利か」を評価するAIです。リバーシには、打つべき場所と打ってはいけない場所がはっきりあります。

位置の重みマトリックス

リバーシ経験者なら「角を取れ」というのは常識でしょう。これを数値化したのが**位置の重みマトリックス（Position Weight Matrix）**です。

これを視覚的に表すと：

なぜ角が100点なのか？

角に置いた石は絶対に裏返されません。リバーシでは端に到達した石は安定石（stable disc）と呼ばれ、ゲーム終了まで自分の石のままです。角はその最たるもので、角を起点に辺沿いの石も安定石にできます。

なぜ角の隣が-20/-40点なのか？

Cスクエア（角の隣の辺のマス）とXスクエア（角の斜め隣のマス）に打つと、相手に角を取らせてしまう可能性があります。

Xスクエアが-40点と最も低いのは、斜め方向からの裏返しで直接角を献上する危険性が最も高いからです。

Normal AIの実装

位置の重みに加えて、裏返せる石の数もボーナスとして考慮します。

スコアの計算式は：

たとえば、角（重み100）で3枚裏返せるなら 100 + 3×2 = 106点。Xスクエア（重み-40）で5枚裏返せても -40 + 5×2 = -30点。角の方が圧倒的に高評価です。

このAIは1手先しか見ない（先読みしない）ものの、リバーシの定石に近い判断ができるため、ランダムAIよりずっと強くなります。

Level 3: Hard AI - ミニマックス法＋αβ枝刈り

いよいよ本格的なゲームAIです。「数手先まで読んで最善手を選ぶ」ことで、Normal AIを大きく上回る強さを実現します。

ミニマックス法とは？

ミニマックス法は、相手も最善手を打ってくると仮定して、自分にとって最も良い手を探索するアルゴリズムです。

重要なのは、自分は評価値を最大化したいのに対し、相手は評価値を最小化したいという点です。自分が良い手を打っても、相手も最善で返してくる。その前提で最も良い結果になる手を選びます。

αβ枝刈りで高速化

ミニマックス法の問題は探索量の爆発です。リバーシでは1手あたり平均10個程度の合法手があるため、5手先まで読むと 10^5 = 100,000 通りもの盤面を評価する必要があります。

αβ枝刈りは、「この先を調べても結果が変わらない」と分かった枝を切り落とすことで、探索を高速化します。

α（アルファ）は「最大化プレイヤーが保証できる最低スコア」、β（ベータ）は「最小化プレイヤーが保証できる最高スコア」を表します。β ≤ α になったら、その枝は調べる意味がないので打ち切ります。

実装コード

注目すべきポイントが3つあります：

1. パスの処理: 合法手がないとき、!isMaximizing で手番を切り替えて再帰する
2. beta <= alpha でbreak: これがαβ枝刈りの本体。不要な探索を打ち切る
3. applyMoveで新しい盤面を作る: 元の盤面を変更せず、コピーに対して石を置く（探索が壊れない）

盤面評価関数（evaluate）

ミニマックス法の「葉ノード」で呼ばれるのが評価関数です。盤面がどちらに有利かを数値で返します。この関数の精度がAIの強さを大きく左右します。

評価関数は4つの要素を組み合わせています：

モビリティはリバーシ特有の重要な概念です。自分の打てる手が多く、相手の打てる手が少ない状態は非常に有利です。相手を「打てる場所がない」状態（パス）に追い込むのが理想的な戦略です。

終盤の石数カウントが total > 50（残り14マス以下）で発動するのは、序盤・中盤では石の数より位置の方が重要だからです。しかし終盤では最終的な石の数が勝敗を決めるため、石数差を評価に加えます。

動的な探索深度

Hard AIの最後のポイントは、ゲームの進行に応じて探索の深さを変えることです。

なぜ中盤は深さ5で、終盤は最大10まで伸ばすのか？

• 中盤: 合法手が多い（平均10手程度）ため、深く読むと計算量が爆発する。深さ5でも十分に強い手を選べる
• 終盤: 合法手が急激に減る（3〜5手程度）ため、深く読んでも計算量は少ない。残り全手を読み切ることで最善手を確実に選べる

ブラウザ上で動作するため、思考時間が長すぎるとユーザー体験が悪くなります。深さ5は「強さ」と「応答速度」のバランスが取れた値です。

3段階のAI比較

最後に、3つのAIを比較してまとめます。

まとめ

リバーシAIは段階的に実装することで、アルゴリズムの本質が理解しやすくなります。

1. Easy（ランダム）: ゲームのルールさえ分かればすぐ作れる。デバッグにも有用
2. Normal（ヒューリスティック）: ドメイン知識（角の重要性）をコードに落とし込む面白さ
3. Hard（ミニマックス＋αβ枝刈り）: 探索アルゴリズムの醍醐味。評価関数の設計がAIの強さを決める

ミニマックス法とαβ枝刈りは、リバーシだけでなくチェスや将棋、囲碁のAIにも使われている汎用的なアルゴリズムです。リバーシは盤面が8×8と比較的小さいため、これらのアルゴリズムを学ぶ入門として最適です。

次回の記事では、このリバーシをオンライン対戦に対応させる方法を解説します。Cloudflare Durable ObjectsとWebSocketを使ったリアルタイム通信の実装に踏み込みます。

実際に動くコードは ADA Labのリバーシゲーム で体験できます。3段階の難易度を切り替えて、AIの強さの違いを実感してみてください。