資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告