数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学博弈论中的极小极大算法（Alpha-Beta 剪枝）C++实现
描述
Alpha-Beta剪枝是一种用于极小极大算法的优化技术。该算法的思想是剪掉游戏树中不需要评估的分支，因为已经存在更好的移动。
该算法引入了两个新字段：
- 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
更新于：2019年10月22日
2K+ 次浏览
广告