Thuật toán Minimax trong Lý thuyết trò chơi (Alpha-Beta Pruning) trong C ++

Mô tả

Cắt tỉa Aplha-Beta là một kỹ thuật tối ưu hóa được sử dụng trong thuật toán minimax. Ý tưởng cho thấy thuật toán này là cắt bỏ các nhánh của cây trò chơi mà không cần đánh giá là đã tồn tại bước di chuyển tốt hơn.

Thuật toán này giới thiệu hai trường mới -

• Alpha - Đây là giá trị tốt nhất (tối đa) mà trình phát tối đa hóa có thể được tín nhiệm ở cấp độ hiện tại hoặc cấp độ cao hơn của nó
• Beta - Đây là giá trị tốt nhất (tối thiểu) mà trình phát thu nhỏ có thể giám sát ở cấp độ hiện tại hoặc cấp độ cao hơn của nó.

Ví dụ

Nếu cây trò chơi -

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

thì giá trị tối ưu sẽ là 13 nếu công cụ tối đa phát trước

Thuật toán

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

Ví dụ

#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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra tiếp theo -

Result : 13