C ++のゲーム理論（アルファベータプルーニング）のミニマックスアルゴリズム

説明

Aplha-Betaプルーニングは、ミニマックスアルゴリズムで使用される最適化手法です。このアルゴリズムの背後にあるアイデアは、より良い動きがすでに存在するため、評価する必要のないゲームツリーの枝を切り取っています。

このアルゴリズムは2つの新しいフィールドを導入します-

• アルファ-これは、マキシマイザープレーヤーが現在のレベルまたはそれ以上のレベルで保証できる最良の値（最大）です
• ベータ-これは、最小化プレーヤーが現在のレベルまたはそれ以上のレベルで保証できる最高の値（最小）です。

例

ゲームツリーが-

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

マキシマイザーが最初に再生される場合、最適値は13になります

アルゴリズム

1. Start DFS traversal from the root of game tree
2. Set initial values of alpha and beta as follows:
a. alpha = INT_MIN(-INFINITY)
b. beta = INT_MAX(+INFINITY)
3. Traverse tree in DFS fashion where maximizer player tries to get the highest score possible while the minimizer player tries to get the lowest score possible.
4. While traversing update the alpha and beta values accordingly

例

#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 << "\n";
   return 0;
}

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Result : 13