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
热门推荐
6 保研的祝福语简短
10 年轻20岁祝福语简短
11 朋友结婚祝福语信息简短
12 女孩婚礼贺卡祝福语简短
13 30段点歌简短祝福语
14 虎年春节祝福语图文简短
15 写给后妈祝福语大全简短
16 简短回复生日祝福语
17 校长送毕业祝福语简短
18 毕业立体贺卡祝福语简短