विवरण
Aplha-बीटा प्रूनिंग एक अनुकूलन तकनीक है जिसका उपयोग मिनिमैक्स एल्गोरिथम में किया जाता है। इस एल्गोरिथम के पीछे का विचार गेम ट्री की शाखाओं को काट दिया गया है जिसका मूल्यांकन करने की आवश्यकता नहीं है क्योंकि बेहतर चाल पहले से मौजूद है।
यह एल्गोरिथम दो नए क्षेत्रों का परिचय देता है -
- अल्फा - यह सर्वोत्तम मूल्य (अधिकतम) है जिसे मैक्सिमाइज़र प्लेयर वर्तमान स्तर या इसके ऊपर के स्तर पर गारंटी दे सकता है
- बीटा - यह सबसे अच्छा मूल्य (न्यूनतम) है जिसे न्यूनतम खिलाड़ी वर्तमान स्तर या इसके ऊपर के स्तर पर गारंटी दे सकता है।
उदाहरण
अगर गेम ट्री है -
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