C++で実装するゲーム理論のミニマックス法とアルファ・ベータ枝刈りの徹底解説

概要

アルファ・ベータ枝刈り（Alpha-Beta Pruning）は、ミニマックス法で用いられる最適化手法の一つです。このアルゴリズムの基本的な考え方は、すでにより良い手が存在することが確定しているゲーム木の枝を、評価せずに切り捨てる（枝刈りする）ことで、探索の無駄を省き計算を高速化するというものです。

このアルゴリズムでは、次の2つの新しいパラメータを導入します。

• アルファ（α） − 現在のレベル、またはそれより上のレベルにおいて、最大化プレイヤーが保証できる最良の値（最大値）
• ベータ（β） − 現在のレベル、またはそれより上のレベルにおいて、最小化プレイヤーが保証できる最良の値（最小値）

例

次のようなゲーム木を考えます。

arr[] = {13, 8, 24, -5, 23, 15, -14, -20}

この場合、最大化プレイヤーが先手であれば、最適値は 13 となります。

アルゴリズムの手順

1. ゲーム木のルートからDFS（深さ優先探索）を開始する
2. アルファとベータの初期値を以下のように設定する
   a. alpha = INT_MIN（-∞）
   b. beta = INT_MAX（+∞）
3. DFSで木を探索する。最大化プレイヤーは可能な限り高いスコアを、最小化プレイヤーは可能な限り低いスコアを狙う
4. 探索を進めながら、アルファとベータの値を適宜更新する

C++による実装例

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getHeight(int n) {
   return (n == 1) ? 0 : 1 + log2(n / 2);
}
int minmax(int height, int depth, int nodeIndex,
bool maxPayer, int values[], int alpha,
int beta) {
   if (depth == height) {
      return values[nodeIndex];
   }
   if (maxPayer) {
      int bestValue = INT_MIN;
      for (int i = 0; i < height - 1; i++) {
         int val = minmax(height, depth + 1, nodeIndex * 2 + i, false, values, alpha, beta);
         bestValue = max(bestValue, val);
         alpha = max(alpha, bestValue);
         if (beta <= alpha)
            break;
      }
      return bestValue;
   } else {
      int bestValue = INT_MAX;
      for (int i = 0; i < height - 1; i++) {
         int val = minmax(height, depth + 1, nodeIndex * 2 + i, true, values, alpha, beta);
         bestValue = min(bestValue, val);
         beta = min(beta, bestValue);
         if (beta <= alpha)
            break;
      }
      return bestValue;
   }
}
int main() {
   int values[] = {13, 8, 24, -5, 23, 15, -14, -20};
   int height = getHeight(SIZE(values));
   int result = minmax(height, 0, 0, true, values, INT_MIN, INT_MAX);
   cout <<"Result : " << result << "
";
   return 0;
}

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Result : 13

枝刈りの効果

アルファ・ベータ枝刈りを用いることで、探索対象となるノード数を大幅に削減できます。最悪の場合の計算量は O(b^d) のままですが、探索順序が適切であれば実効的には O(b^(d/2)) まで改善でき、同じ時間で約2倍の深さまで探索できるようになります（bは分岐数、dは木の深さ）。この効率性から、チェスや将棋、オセロなどの盤面ゲームAIで広く活用されています。