C++ में गेम थ्योरी में मिनिमैक्स एल्गोरिदम (अल्फा-बीटा प्रूनिंग)

विवरण

अल्फा-बीटा प्रूनिंग मिनिमैक्स एल्गोरिदम में एक अनुकूलन तकनीक है। यह गेम ट्री की उन शाखाओं को काट देती है जिनका मूल्यांकन आवश्यक नहीं है क्योंकि बेहतर चाल पहले से मौजूद है।

मुख्य अवधारणाएं

• Alpha: अधिकतमकर्ता (maximizer) खिलाड़ी जो सर्वोत्तम मान गारंटी कर सकता है
• Beta: न्यूनतमकर्ता (minimizer) खिलाड़ी जो सर्वोत्तम मान गारंटी कर सकता है

उदाहरण

गेम ट्री: {13, 8, 24, -5, 23, 15, -14, -20}

इष्टतम मान: 13 (यदि अधिकतमकर्ता पहले खेलता है)

उदाहरण कोड

#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 maxPlayer, int values[], int alpha, int beta) {
    if (depth == height)
        return values[nodeIndex];
    
    if (maxPlayer) {
        int bestValue = INT_MIN;
        for (int i = 0; i < 2; 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 < 2; 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