Minimax Algorithm এবং Alpha-Beta Pruning

1. Minimax Algorithm

Minimax Algorithm একটি decision-making অ্যালগরিদম যা সাধারণত two-player games (যেমন দাবা বা টিকট্যাকটো) জন্য ব্যবহৃত হয়। এটি একটি গাছের মতো কাঠামো তৈরি করে যেখানে প্রতিটি স্তর একজন প্লেয়ারকে প্রতিনিধিত্ব করে। Maximizing Player (অর্থাৎ, যে প্লেয়ারটি সর্বাধিক স্কোর পেতে চায়) এবং Minimizing Player (যে প্লেয়ারটি প্রতিপক্ষকে সর্বনিম্ন স্কোর পেতে চায়) এই দুটি প্লেয়ারের মধ্যে সর্বোত্তম পদক্ষেপ নির্বাচন করার জন্য Minimax অ্যালগরিদম কাজ করে।

Minimax অ্যালগরিদমের পদ্ধতি:

1. Maximizing Player সর্বোচ্চ স্কোরের দিকে এগিয়ে যায়।
2. Minimizing Player সর্বনিম্ন স্কোরের দিকে এগিয়ে যায়।
3. প্রতি স্তরের গাছ থেকে মূল্য নির্ধারণ করা হয় এবং সর্বোত্তম সিদ্ধান্ত নেওয়া হয়।

এটি একটি recursive অ্যালগরিদম যেখানে প্রতিটি স্তরে সর্বোচ্চ এবং সর্বনিম্ন মূল্য বের করে backtrack করা হয়।

Minimax Algorithm Implementation:

public class Minimax {
    static final int MAX = 1;
    static final int MIN = -1;

    // Method to evaluate the utility of the board
    public static int evaluate(int[][] board) {
        // Sample evaluation function for a Tic Tac Toe game
        // 1 represents maximizing player, -1 represents minimizing player
        // Evaluate rows, columns, and diagonals for a win
        for (int row = 0; row < 3; row++) {
            if (board[row][0] == board[row][1] && board[row][1] == board[row][2]) {
                if (board[row][0] == 1) return 10;  // Maximizing player wins
                else if (board[row][0] == -1) return -10;  // Minimizing player wins
            }
        }
        for (int col = 0; col < 3; col++) {
            if (board[0][col] == board[1][col] && board[1][col] == board[2][col]) {
                if (board[0][col] == 1) return 10;  
                else if (board[0][col] == -1) return -10;  
            }
        }
        if (board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
            if (board[0][0] == 1) return 10;  
            else if (board[0][0] == -1) return -10;  
        }
        if (board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
            if (board[0][2] == 1) return 10;  
            else if (board[0][2] == -1) return -10;  
        }
        return 0;  // No winner
    }

    // Minimax algorithm implementation
    public static int minimax(int[][] board, int depth, boolean isMax) {
        int score = evaluate(board);

        // If Maximizing Player has won, return score
        if (score == 10) return score;

        // If Minimizing Player has won, return score
        if (score == -10) return score;

        // If the board is full, return 0 (tie)
        if (isBoardFull(board)) return 0;

        // If it is the Maximizing Player's turn
        if (isMax) {
            int best = Integer.MIN_VALUE;
            // Try all moves for maximizing player
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[i][j] == 0) {
                        board[i][j] = 1;
                        best = Math.max(best, minimax(board, depth + 1, !isMax));
                        board[i][j] = 0;
                    }
                }
            }
            return best;
        } else {
            int best = Integer.MAX_VALUE;
            // Try all moves for minimizing player
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[i][j] == 0) {
                        board[i][j] = -1;
                        best = Math.min(best, minimax(board, depth + 1, !isMax));
                        board[i][j] = 0;
                    }
                }
            }
            return best;
        }
    }

    // Check if the board is full
    public static boolean isBoardFull(int[][] board) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == 0) return false;
            }
        }
        return true;
    }

    // Function to find the best move for the current player
    public static void findBestMove(int[][] board) {
        int bestVal = Integer.MIN_VALUE;
        int row = -1;
        int col = -1;

        // Try all possible moves and evaluate them
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == 0) {
                    board[i][j] = 1;  // Maximizing player
                    int moveVal = minimax(board, 0, false);
                    board[i][j] = 0;

                    if (moveVal > bestVal) {
                        row = i;
                        col = j;
                        bestVal = moveVal;
                    }
                }
            }
        }

        System.out.println("The best move is at row: " + row + " col: " + col);
    }

    public static void main(String[] args) {
        int[][] board = {
            {1, -1, 1},
            {0, -1, 0},
            {1, 0, 0}
        };
        
        findBestMove(board);
    }
}

ব্যাখ্যা:

• evaluate: এটি একটি সিম্পল ইভ্যালুয়েশন ফাংশন যা টিক ট্যাক টোয় গোলাপের জন্য কাজ করে।
• minimax: এটি রিকার্সিভভাবে সর্বোচ্চ (maximizing) এবং সর্বনিম্ন (minimizing) স্কোর নির্ধারণ করে।
• findBestMove: এটি গ্রিডে সর্বোত্তম পদক্ষেপ খুঁজে বের করে।
• isBoardFull: এটি চেক করে যদি পুরো বোর্ড পূর্ণ হয়ে যায়।

2. Alpha-Beta Pruning

Alpha-Beta Pruning হল Minimax অ্যালগরিদমের একটি উন্নত সংস্করণ যা অপ্রয়োজনীয় হিসাবগুলোকে বাদ দিয়ে সময় এবং মেমরি অপটিমাইজ করে। এটি Minimax অ্যালগরিদমের মতো কাজ করে, কিন্তু কিছু শাখা পরিত্যাগ (prune) করে যদি জানা যায় যে সেগুলি বর্তমান পছন্দের থেকে খারাপ ফলাফল দেবে।

Alpha-Beta Pruning এর মূল ধারণা:

1. Alpha: সর্বাধিক মূল্য যা বর্তমানে Maximizing Player প্রাপ্ত হতে পারে।
2. Beta: সর্বনিম্ন মূল্য যা বর্তমানে Minimizing Player প্রাপ্ত হতে পারে।
3. যদি Alpha >= Beta, তাহলে বর্তমান শাখাটি বাদ দেয়া হয় (pruned) কারণ এটি কোনও ভাল ফলাফল দেবে না।

Alpha-Beta Pruning Implementation:

public class AlphaBetaPruning {

    // Method to evaluate the utility of the board
    public static int evaluate(int[][] board) {
        // Same evaluation function as in Minimax (Tic Tac Toe example)
        for (int row = 0; row < 3; row++) {
            if (board[row][0] == board[row][1] && board[row][1] == board[row][2]) {
                if (board[row][0] == 1) return 10;
                else if (board[row][0] == -1) return -10;
            }
        }
        for (int col = 0; col < 3; col++) {
            if (board[0][col] == board[1][col] && board[1][col] == board[2][col]) {
                if (board[0][col] == 1) return 10;
                else if (board[0][col] == -1) return -10;
            }
        }
        if (board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
            if (board[0][0] == 1) return 10;
            else if (board[0][0] == -1) return -10;
        }
        if (board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
            if (board[0][2] == 1) return 10;
            else if (board[0][2] == -1) return -10;
        }
        return 0; // No winner
    }

    // Alpha-Beta Pruning algorithm
    public static int alphaBeta(int[][] board, int depth, int alpha, int beta, boolean isMax) {
        int score = evaluate(board);

        // If Maximizing Player has won
        if (score == 10) return score;

        // If Minimizing Player has won
        if (score == -10) return score;

        // If the board is full, return 0 (tie)
        if (isBoardFull(board)) return 0;

        // If it is the Maximizing Player's turn
        if (isMax) {
            int best = Integer.MIN_VALUE;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[i][j] == 0)

{ board[i][j] = 1; best = Math.max(best, alphaBeta(board, depth + 1, alpha, beta, !isMax)); board[i][j] = 0; alpha = Math.max(alpha, best); if (beta <= alpha) break; } } } return best; } else { int best = Integer.MAX_VALUE; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (board[i][j] == 0) { board[i][j] = -1; best = Math.min(best, alphaBeta(board, depth + 1, alpha, beta, !isMax)); board[i][j] = 0; beta = Math.min(beta, best); if (beta <= alpha) break; } } } return best; } }

// Check if the board is full
public static boolean isBoardFull(int[][] board) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == 0) return false;
        }
    }
    return true;
}

// Main method
public static void main(String[] args) {
    int[][] board = {
        {1, -1, 1},
        {0, -1, 0},
        {1, 0, 0}
    };

    int bestMove = alphaBeta(board, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
    System.out.println("Best Move Value: " + bestMove);
}

}

#### ব্যাখ্যা:
- **Alpha-Beta Pruning**: এটি Minimax অ্যালগরিদমের উন্নত সংস্করণ যেখানে প্রতিটি স্তরের মধ্য দিয়ে কিছু শাখা বাদ দেওয়া হয় (pruned)।
- **Alpha**: Maximizing Player এর জন্য সর্বোত্তম সম্ভাব্য ফলাফল।
- **Beta**: Minimizing Player এর জন্য সর্বোত্তম সম্ভাব্য ফলাফল।
- **Pruning**: যদি কোনও শাখার সম্ভাব্য ফলাফল **alpha** এবং **beta** এর মধ্যে নেই, তবে ঐ শাখাটি বাদ দেয়া হয়।

---

### সারাংশ

- **Minimax Algorithm** হল একটি সাধারণ এবং শক্তিশালী অ্যালগরিদম যা টু-প্লেয়ার গেমগুলোর জন্য উপযোগী, যেখানে দুটি প্লেয়ার সর্বোত্তম পদক্ষেপ খোঁজে। 
- **Alpha-Beta Pruning** হল Minimax অ্যালগরিদমের একটি উন্নত সংস্করণ যা অপ্রয়োজনীয় শাখাগুলো বাদ দিয়ে অ্যালগরিদমের কার্যকারিতা দ্রুত করে এবং মেমরি ব্যবহারের উন্নতি ঘটায়।