C++ 게임 이론의 Minimax 알고리즘(알파-베타 가지치기)

설명

Aplha-Beta 가지치기는 minimax 알고리즘에서 사용되는 최적화 기법입니다. 이 알고리즘의 아이디어는 더 나은 움직임이 이미 존재하므로 평가할 필요가 없는 게임 트리의 가지를 잘라냅니다.

이 알고리즘은 두 개의 새로운 필드를 소개합니다 -

• Alpha - 최대화 플레이어가 현재 수준 또는 그 이상 수준에서 보장할 수 있는 최상의 값(최대값)입니다.
• 베타 - 현재 수준 또는 그 이상 수준에서 최소화 플레이어가 보장할 수 있는 최상의 값(최소값)입니다.

예시

게임 트리가 -

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