C++-এ গেম থিওরিতে মিনিম্যাক্স অ্যালগরিদম (আলফা-বেটা প্রুনিং)

বিবরণ

আলফা-বেটা প্রুনিং হল মিনিম্যাক্স অ্যালগরিদমে ব্যবহৃত একটি অপ্টিমাইজেশন টেকনিক। এই অ্যালগরিদমের আইডিয়া হল গেম ট্রির যে ব্রাঞ্চগুলো ইভ্যালুয়েট করার প্রয়োজন নেই সেগুলো কাটা, কারণ ইতিমধ্যে ভালো মুভ আছে।

এই অ্যালগরিদমে দুটি নতুন ফিল্ড আছে:

• Alpha − এটি ম্যাক্সিমাইজার প্লেয়ার যে বেস্ট ভ্যালু (ম্যাক্সিমাম) গ্যারান্টি করতে পারে বর্তমান লেভেলে বা তার উপরের লেভেলে
• Beta − এটি মিনিমাইজার প্লেয়ার যে বেস্ট ভ্যালু (মিনিমাম) গ্যারান্টি করতে পারে বর্তমান লেভেলে বা তার উপরের লেভেলে

উদাহরণ

যদি গেম ট্রি হয়:

arr[] = {13, 8, 24, -5, 23, 15, -14, -20}

তবে অপ্টিমাল ভ্যালু হবে 13 যদি ম্যাক্সিমাইজার প্রথম খেলে।

অ্যালগরিদম

1. গেম ট্রির রুট থেকে DFS ট্রাভার্সাল শুরু করুন
2. আলফা এবং বেটার প্রাথমিক মান সেট করুন:
   a. alpha = INT_MIN (-INFINITY)
   b. beta = INT_MAX (+INFINITY)
3. DFS ফ্যাশনে ট্রি ট্রাভার্স করুন যেখানে ম্যাক্সিমাইজার প্লেয়ার হাইএസ്റ്റ স্কোর পেতে চায় এবং মিনিমাইজার প্লেয়ার লোয়েস্ট স্কোর পেতে চায়।
4. ট্রাভার্সাল সময় আলফা এবং বেটা ভ্যালু আপডেট করুন

উদাহরণ কোড

#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