C ++中博弈论中的Minimax算法（Alpha-Beta修剪）
描述
Aplha-Beta修剪是minimax算法中使用的一种优化技术。该算法的思想是切断游戏树的分支，由于已经存在更好的动作，因此无需进行评估。
该算法引入了两个新领域-
Alpha-这是最大化玩家可以在当前级别或更高级别保证的最佳值（最大值）
Beta-这是最小化播放器可以保证的当前值或更高水平的最佳值（最小值）。
示例
如果游戏树是-
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