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

বিবরণ

Aplha-Beta pruning হল minimax অ্যালগরিদমে ব্যবহৃত একটি অপ্টিমাইজেশন কৌশল। এই অ্যালগরিদমের ধারণাটি গেইম ট্রির ডালপালা কেটে ফেলা হয়েছে যা মূল্যায়ন করার দরকার নেই কারণ আরও ভাল পদক্ষেপ ইতিমধ্যেই বিদ্যমান।

এই অ্যালগরিদম দুটি নতুন ক্ষেত্র-

• আলফা − এটি হল সর্বোত্তম মান (সর্বোচ্চ) যা ম্যাক্সিমাইজার প্লেয়ার বর্তমান স্তরে বা তার উপরের স্তরে গ্যারাটি করতে পারে
• বিটা − এটি হল সর্বোত্তম মান (ন্যূনতম) যা মিনিমাইজার প্লেয়ার বর্তমান স্তরে বা তার উপরের স্তরে গ্যারাটি করতে পারে৷

উদাহরণ

যদি খেলা গাছ হয় −

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

তারপর সর্বোত্তম মান হবে 13 যদি ম্যাক্সিমাইজার প্রথমে চলে

অ্যালগরিদম

উদাহরণ

#include #include #include #include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) namespace ব্যবহার করে std;int getHeight( int n) { ফেরত (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) { রিটার্ন মান[ nodeIndex]; } যদি (maxPayer) { int bestValue =INT_MIN; জন্য (int i =0; i <উচ্চতা - 1; i++) { int val =minmax(উচ্চতা, গভীরতা + 1, nodeIndex * 2 + i, মিথ্যা, মান, আলফা, বিটা); bestValue =max(bestValue, val); আলফা =সর্বোচ্চ (আলফা, সেরা মান); যদি (বিটা <=আলফা) বিরতি; } bestValue ফেরত দিন; } অন্য { int bestValue =INT_MAX; জন্য (int i =0; i <উচ্চতা - 1; i++) { int val =minmax(উচ্চতা, গভীরতা + 1, nodeIndex * 2 + i, সত্য, মান, আলফা, বিটা); bestValue =min(bestValue, val); beta =min(beta, bestValue); যদি (বিটা <=আলফা) বিরতি; } bestValue ফেরত দিন; }}int main() { int values[] ={13, 8, 24, -5, 23, 15, -14, -20}; int উচ্চতা =getHeight(SIZE(মান)); int ফলাফল =minmax(উচ্চতা, 0, 0, সত্য, মান, INT_MIN, INT_MAX); cout <<"ফলাফল :" <<ফলাফল <<"\n"; রিটার্ন 0;

আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি অনুসরণ করে আউটপুট −

ফলাফল :13