อัลกอริทึม Minimax พร้อม Alpha-Beta Pruning ใน C++

Minimax Algorithm

อัลกอริทึมสำหรับ Game Theory (เช่น หมากรุก, Tic-Tac-Toe) ผู้เล่นสองฝ่าย:

• Maximizer: พยายามทำคะแนนสูงสุด
• Minimizer: พยายามทำคะแนนต่ำสุด

Alpha-Beta Pruning

เทคนิคตัดกิ่ง (pruning) เพื่อลดการค้นหา:

• Alpha (α): ค่าที่ Maximizer รับประกันได้แล้ว (lower bound)
• Beta (β): ค่าที่ Minimizer รับประกันได้แล้ว (upper bound)
• ถ้า β ≤ α → ตัดกิ่งได้ (prune) เพราะฝ่ายตรงข้ามจะไม่เลือกเส้นทางนี้

ตัวอย่าง Game Tree

ใบ (leaves): [13, 8, 24, -5, 23, 15, -14, -20]

ความสูง = 3 (8 ใบ = 2³)

Maximizer เริ่มก่อน → ค่าที่ดีที่สุดคือ 13

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
using namespace std;

int getHeight(int n) {
    return (n == 1) ? 0 : 1 + log2(n / 2);
}

int minimax(int height, int depth, int nodeIndex, bool isMaximizer, 
            const vector<int>& values, int alpha, int beta) {
    
    // ถึงใบ (leaf)
    if (depth == height)
        return values[nodeIndex];
    
    if (isMaximizer) {
        int best = INT_MIN;
        // Binary tree: 2 children
        for (int i = 0; i < 2; i++) {
            int childIndex = nodeIndex * 2 + i;
            if (childIndex >= values.size()) break;
            
            int val = minimax(height, depth + 1, childIndex, false, values, alpha, beta);
            best = max(best, val);
            alpha = max(alpha, best);
            
            if (beta <= alpha) break; // Beta cutoff
        }
        return best;
    } 
    else { // Minimizer
        int best = INT_MAX;
        for (int i = 0; i < 2; i++) {
            int childIndex = nodeIndex * 2 + i;
            if (childIndex >= values.size()) break;
            
            int val = minimax(height, depth + 1, childIndex, true, values, alpha, beta);
            best = min(best, val);
            beta = min(beta, best);
            
            if (beta <= alpha) break; // Alpha cutoff
        }
        return best;
    }
}

int main() {
    vector<int> values = {13, 8, 24, -5, 23, 15, -14, -20};
    int height = getHeight(values.size());
    
    int result = minimax(height, 0, 0, true, values, INT_MIN, INT_MAX);
    cout << "Optimal value: " << result << endl;
    
    return 0;
}

ผลลัพธ์

Optimal value: 13

การทำงานของ Alpha-Beta ในตัวอย่าง

Tree structure (depth 3, 8 leaves):

            Max (root)
           /    \
        Min      Min
       /  \     /  \
      M    M   M    M
     /\   /\  /\   /\
    13 8 24 -5 23 15 -14 -20

Pruning เกิดขึ้นเมื่อ Minimizer พบค่าต่ำกว่าหรือเท่ากับ Alpha ของ Maximizer

ประสิทธิภาพ

• โดยไม่มี Pruning: O(bᵈ) โดย b=branching factor, d=depth
• มี Alpha-Beta: O(bᵈ/²) = O(√bᵈ) ในกรณีดีที่สุด (perfect ordering)
• สำคัญ: ลำดับการเยี่ยมชมนODE ส่งผลต่อประสิทธิภาพมาก (ควรเรียง good moves ไปก่อน)