คำอธิบาย
การตัดแต่งกิ่ง Aplha-Beta เป็นเทคนิคการเพิ่มประสิทธิภาพที่ใช้ในอัลกอริธึม minimax แนวคิดที่อยู่เบื้องหลังอัลกอริธึมนี้ถูกตัดออกจากผังเกมซึ่งไม่จำเป็นต้องได้รับการประเมินเนื่องจากมีการเคลื่อนไหวที่ดีกว่าอยู่แล้ว
อัลกอริทึมนี้แนะนำสองฟิลด์ใหม่ -
- อัลฟ่า - นี่คือค่าที่ดีที่สุด (สูงสุด) ที่ผู้เล่นตัวขยายใหญ่สุดสามารถรับประกันได้ที่ระดับปัจจุบันหรือระดับที่สูงกว่า
- เบต้า - นี่คือค่าที่ดีที่สุด (ขั้นต่ำ) ที่ผู้เล่นย่อขนาดสามารถรับประกันได้ที่ระดับปัจจุบันหรือระดับที่สูงกว่า
ตัวอย่าง
หากผังเกมเป็น −
arr [] ={13, 8, 24, -5, 23, 15, -14, -20} ค่าที่เหมาะสมที่สุดจะเป็น 13 หากตัวเล่นตัวขยายใหญ่สุดเล่นก่อน
อัลกอริทึม
<ก่อน>1. เริ่มการข้ามผ่าน DFS จากรูทของเกม tree2 ตั้งค่าเริ่มต้นของอัลฟ่าและเบต้าดังนี้:ก. อัลฟา =INT_MIN(-INFINITY)b. เบต้า =INT_MAX(+INFINITY)3. ต้นไม้สำรวจในรูปแบบ DFS ที่ผู้เล่นตัวขยายใหญ่สุดพยายามที่จะได้คะแนนสูงสุดในขณะที่ผู้เล่นตัวย่อเล็กสุดพยายามที่จะได้รับคะแนนต่ำสุดที่เป็นไปได้4. ขณะสำรวจอัปเดตค่าอัลฟ่าและเบต้าตามลำดับตัวอย่าง
#include#include #include #include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) โดยใช้เนมสเปซ std;int getHeight( int n) { ผลตอบแทน (n ==1) ? 0 :1 + log2 (n / 2);}int minmax (ความสูง int, ความลึก int, int nodeIndex, bool maxPayer, ค่า int [], int alpha, int beta) { ถ้า (ความลึก ==ความสูง) { คืนค่า [ nodeIndex]; } if (maxPayer) { int bestValue =INT_MIN; สำหรับ (int i =0; i <ความสูง - 1; i++) { int val =minmax(ความสูง, ความลึก + 1, nodeIndex * 2 + i, เท็จ, ค่า, อัลฟา, เบต้า); bestValue =สูงสุด (bestValue, val); อัลฟา =สูงสุด (อัลฟา, ค่าที่ดีที่สุด); ถ้า (เบต้า <=อัลฟา) แตก; } คืนค่า bestValue; } อื่น ๆ { int bestValue =INT_MAX; สำหรับ (int i =0; i <ความสูง - 1; i++) { int val =minmax(ความสูง, ความลึก + 1, nodeIndex * 2 + i, จริง, ค่า, อัลฟา, เบต้า); bestValue =นาที (bestValue, val); เบต้า =นาที (เบต้า, bestValue); ถ้า (เบต้า <=อัลฟา) แตก; } คืนค่า bestValue; }}int main() { ค่า int[] ={13, 8, 24, -5, 23, 15, -14, -20}; ความสูง int =getHeight(SIZE(values)); ผลลัพธ์ int =minmax(ความสูง, 0, 0, จริง, ค่า, INT_MIN, INT_MAX); cout <<"ผลลัพธ์ :" <<ผล <<"\n"; คืนค่า 0;}
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์ :13
