Minimax & Alpha-Beta Pruning - CSU083 | Shoolini University

Minimax & Alpha-Beta Pruning

2025, February 20

1. Prerequisites

Before understanding Minimax and Alpha-Beta Pruning, you should be familiar with the following foundational concepts:

2. What is Minimax & Alpha-Beta Pruning?

2.1 Minimax Algorithm

The Minimax algorithm is a decision rule used in turn-based, two-player games where one player (MAX) tries to maximize the score while the other (MIN) tries to minimize it.


def minimax(node, depth, is_maximizing):
    if depth == 0 or is_terminal(node):
        return evaluate(node)
    
    if is_maximizing:
        best = float('-inf')
        for child in get_children(node):
            value = minimax(child, depth - 1, False)
            best = max(best, value)
        return best
    else:
        best = float('inf')
        for child in get_children(node):
            value = minimax(child, depth - 1, True)
            best = min(best, value)
        return best

2.2 Alpha-Beta Pruning

Alpha-Beta Pruning optimizes Minimax by eliminating branches that do not affect the final decision, reducing unnecessary computations.


def alpha_beta(node, depth, alpha, beta, is_maximizing):
    if depth == 0 or is_terminal(node):
        return evaluate(node)
    
    if is_maximizing:
        best = float('-inf')
        for child in get_children(node):
            value = alpha_beta(child, depth - 1, alpha, beta, False)
            best = max(best, value)
            alpha = max(alpha, best)
            if beta <= alpha:
                break  # Prune
        return best
    else:
        best = float('inf')
        for child in get_children(node):
            value = alpha_beta(child, depth - 1, alpha, beta, True)
            best = min(best, value)
            beta = min(beta, best)
            if beta <= alpha:
                break  # Prune
        return best

3. Why Does This Algorithm Exist?

The Minimax algorithm is crucial for decision-making in adversarial environments where two players have conflicting goals.

4. When Should You Use It?

5. How Does It Compare to Alternatives?

5.1 Strengths

5.2 Weaknesses

5.3 Comparison with Other Methods

"
Algorithm Best Use Case Complexity Strength Weakness
Minimax Perfect-information games O(b^d) Finds optimal moves Slow for deep trees
Alpha-Beta Pruning Large game trees O(b^(d/2)) More efficient Still exponential
Monte Carlo Tree Search (MCTS) Complex, probabilistic games O(n log n) Good for Go & real-world AI Non-deterministic results
Reinforcement Learning Unknown environments Varies Adapts to learning Training-intensive

6. Basic Implementation

6.1 Minimax Algorithm Implementation (Python)

The following implementation includes the Minimax algorithm with Alpha-Beta pruning for a simple two-player game.


class Game:
    def __init__(self, values):
        self.tree = values  # Predefined game tree values (leaf nodes)

    def minimax(self, depth, node_index, is_maximizing, alpha, beta):
        if depth == 2:  # Leaf node reached
            return self.tree[node_index]

        if is_maximizing:
            best = float('-inf')
            for i in range(2):  # Two children per node
                value = self.minimax(depth + 1, node_index * 2 + i, False, alpha, beta)
                best = max(best, value)
                alpha = max(alpha, best)
                if beta <= alpha:
                    break  # Prune
            return best
        else:
            best = float('inf')
            for i in range(2):  # Two children per node
                value = self.minimax(depth + 1, node_index * 2 + i, True, alpha, beta)
                best = min(best, value)
                beta = min(beta, best)
                if beta <= alpha:
                    break  # Prune
            return best

# Example game tree with predefined leaf values
values = [3, 5, 6, 9, 1, 2, 0, -1]
game = Game(values)

# Start Minimax with Alpha-Beta Pruning
optimal_value = game.minimax(0, 0, True, float('-inf'), float('inf'))
print("Optimal Value:", optimal_value)

7. Dry Run of the Algorithm

7.1 Example Tree Structure

We will manually track Minimax with Alpha-Beta pruning on the following tree:

         (?)
        /   \
      (?)   (?)
     /  \   /  \
   (3)  (5) (6) (9)
   (1)  (2) (0) (-1)

7.2 Step-by-Step Execution

Let's track the function calls with Alpha-Beta pruning.

"
Step Node Minimax Decision Alpha Beta Pruning?
1 Root (Max) Explore Left Child -∞ +∞ No
2 Left Child (Min) Explore Left Subtree -∞ +∞ No
3 3 & 5 (Leaf Nodes) Min = 3 -∞ 3 No
4 1 & 2 (Leaf Nodes) Min = 1 -∞ 1 Prune Right
5 Left Child Evaluated Max = 3 3 +∞ No
6 Right Child (Min) Explore Left Subtree 3 +∞ No
7 6 & 9 (Leaf Nodes) Min = 6 3 6 No
8 0 & -1 (Leaf Nodes) Min = -1 3 -1 Prune Right
9 Right Child Evaluated Max = 3 3 +∞ No
10 Root Decision Optimal Move = 3 - - -

7.3 Final Result

The algorithm determines that the optimal value for the root node is 3, with Alpha-Beta pruning significantly reducing calculations.

8. Time & Space Complexity Analysis

8.1 Time Complexity of Minimax

The Minimax algorithm explores all possible game states up to a given depth.

Minimax examines all nodes in the game tree, leading to:

$$O(b^d)$$

Best, Worst, and Average Cases
"
Case Complexity Reason
Worst Case O(b^d) Explores the entire tree exhaustively.
Best Case O(b^d) No pruning occurs, so still exhaustive.
Average Case O(b^d) Same as worst case unless pruning helps.

8.2 Time Complexity with Alpha-Beta Pruning

Alpha-Beta pruning reduces unnecessary evaluations, eliminating many branches.

In an ideal scenario (best ordering of nodes), pruning reduces complexity to:

$$O(b^{d/2})$$

"
Case Complexity Reason
Worst Case O(b^d) No pruning occurs (bad node ordering).
Best Case O(b^{d/2}) Pruning eliminates almost half the search space.
Average Case O(b^{d/1.5}) Some pruning occurs, reducing but not halving work.

9. Space Complexity Analysis

9.1 Memory Consumption in Minimax

Memory consumption depends on storing recursive function calls and game states.

Overall space complexity:

$$O(d)$$

9.2 Memory Consumption with Alpha-Beta Pruning

Pruning does not significantly change space usage since it only prevents unnecessary function calls.

10. Trade-Offs & Considerations

10.1 Strengths of Minimax

10.2 Weaknesses of Minimax

10.3 Trade-Offs with Alpha-Beta Pruning

"
Factor Minimax Alpha-Beta Pruning
Computation Speed Slow (O(b^d)) Faster (O(b^{d/2}))
Space Complexity O(d) O(d)
Optimality Always optimal Always optimal
Usefulness in Large Games Limited Pruning improves scalability

Key Insight: Alpha-Beta Pruning should always be used with Minimax, as it provides the same results faster.

11. Optimizations & Variants

11.1 Common Optimizations in Minimax

Minimax can be optimized in several ways to reduce computation time and improve efficiency.

1. Alpha-Beta Pruning
2. Move Ordering
3. Transposition Tables (Memoization)
4. Iterative Deepening
5. Heuristic Evaluation Functions
6. Quiescence Search
7. Monte Carlo Tree Search (MCTS)

11.2 Variants of Minimax

"
Variant Description Best Use Case
Standard Minimax Explores all possible moves without pruning. Small games like Tic-Tac-Toe.
Alpha-Beta Pruning Reduces unnecessary computations by pruning branches. Large game trees like Chess.
Expectiminimax Handles stochastic games by considering chance nodes. Games with randomness like Backgammon.
Monte Carlo Tree Search (MCTS) Uses random simulations instead of brute-force search. Games like Go, where branching factor is high.

12. Iterative vs. Recursive Implementations

12.1 Recursive Minimax


def minimax(node, depth, is_maximizing):
    if depth == 0 or is_terminal(node):
        return evaluate(node)
    
    if is_maximizing:
        best = float('-inf')
        for child in get_children(node):
            value = minimax(child, depth - 1, False)
            best = max(best, value)
        return best
    else:
        best = float('inf')
        for child in get_children(node):
            value = minimax(child, depth - 1, True)
            best = min(best, value)
        return best

12.2 Iterative Minimax


def iterative_minimax(root):
    stack = [(root, 0, True, float('-inf'), float('inf'))]  # (node, depth, is_max, alpha, beta)
    best_value = None
    
    while stack:
        node, depth, is_max, alpha, beta = stack.pop()

        if depth == 0 or is_terminal(node):
            value = evaluate(node)
        else:
            if is_max:
                value = float('-inf')
                for child in get_children(node):
                    stack.append((child, depth - 1, False, alpha, beta))
            else:
                value = float('inf')
                for child in get_children(node):
                    stack.append((child, depth - 1, True, alpha, beta))
        
        if best_value is None or (is_max and value > best_value) or (not is_max and value < best_value):
            best_value = value
    
    return best_value

12.3 Comparison of Iterative vs. Recursive

"
Factor Recursive Iterative
Implementation Complexity Simple & intuitive More complex
Memory Usage O(d) (stack space) O(d) (explicit stack)
Performance Efficient for small depths More stable for deep trees
Control & Debugging Hard to control Easier to modify dynamically
Best Use Case Small, simple games Large-scale AI applications

12.4 Key Insights

13. Edge Cases & Failure Handling

13.1 Common Pitfalls in Minimax & Alpha-Beta Pruning

1. Handling Terminal States Incorrectly
2. Incorrect Evaluation Function
3. Unbounded Recursion
4. Inefficient Move Ordering in Alpha-Beta Pruning
5. Handling Draws & Stalemates
6. Floating-Point Precision Issues
7. Handling Games with Randomness (Expectiminimax)

14. Test Cases to Verify Correctness

14.1 Basic Unit Test Cases (Python)

These tests validate the correctness of Minimax with Alpha-Beta Pruning.


import unittest

class TestMinimax(unittest.TestCase):
    def setUp(self):
        # Sample game tree for testing
        self.game = Game([3, 5, 6, 9, 1, 2, 0, -1])

    def test_minimax_correctness(self):
        """ Test Minimax returns the correct optimal value """
        result = self.game.minimax(0, 0, True, float('-inf'), float('inf'))
        self.assertEqual(result, 3)

    def test_terminal_state(self):
        """ Test that terminal states return correct heuristic value """
        terminal_result = self.game.minimax(2, 0, True, float('-inf'), float('inf'))
        self.assertIn(terminal_result, [3, 5, 6, 9, 1, 2, 0, -1])

    def test_alpha_beta_pruning_effectiveness(self):
        """ Test that alpha-beta pruning correctly reduces node evaluations """
        unoptimized_count = self.game.minimax(0, 0, True, float('-inf'), float('inf'))  # Without pruning
        optimized_count = self.game.minimax(0, 0, True, float('-inf'), float('inf'))  # With pruning
        self.assertLess(optimized_count, unoptimized_count)

    def test_draw_scenario(self):
        """ Test that the game detects a draw correctly """
        draw_game = Game([0, 0, 0, 0, 0, 0, 0, 0])
        result = draw_game.minimax(0, 0, True, float('-inf'), float('inf'))
        self.assertEqual(result, 0)

if __name__ == "__main__":
    unittest.main()

14.2 Test Cases for Edge Cases

"
Test Case Expected Outcome
Terminal state reached at depth 0 Returns heuristic value of the node
All moves lead to a draw Returns a neutral evaluation (e.g., 0)
Alpha-beta pruning eliminates redundant computations Fewer nodes evaluated compared to Minimax without pruning
Handling deep recursion (depth > 10) Does not exceed maximum recursion depth
Game with randomized elements (Expectiminimax needed) Fails (since Minimax is deterministic)

15. Real-World Failure Scenarios

15.1 Chess Engine Mistakes

15.2 AI in Tic-Tac-Toe Playing Suboptimally

15.3 Computational Overhead in Large Games

15.4 Alpha-Beta Pruning Misuse

15.5 Stochastic Games Like Backgammon

15.6 Adversarial AI in Cybersecurity

Key Insight: Minimax & Alpha-Beta pruning are powerful but must be carefully implemented to avoid inefficiencies and miscalculations.

16. Real-World Applications & Industry Use Cases

16.1 Game AI Development

Minimax is widely used in turn-based strategy games where AI opponents need to make optimal decisions.

16.2 Robotics & Autonomous Agents

Used in decision-making for robots in adversarial environments.

16.3 Cybersecurity & Intrusion Detection

Minimax helps model attacks and defenses in cybersecurity.

16.4 Financial Trading & Risk Management

Minimax is used to model worst-case scenarios in financial risk assessment.

16.5 Medical Decision Support Systems

Used in AI-driven diagnosis and treatment planning.

16.6 Military & Defense Strategy

Minimax is applied in AI-driven tactical decision-making.

17. Open-Source Implementations

17.1 Minimax & Alpha-Beta Pruning in Open-Source Projects

17.2 Libraries & Frameworks for Minimax

18. Project: Implementing a Tic-Tac-Toe AI with Minimax

18.1 Project Description

We will implement an AI-powered Tic-Tac-Toe game where the computer uses Minimax to play optimally.

18.2 Python Implementation


import math

# Tic-Tac-Toe board representation
board = [" " for _ in range(9)]

def print_board():
    for i in range(3):
        print("|".join(board[i*3:(i+1)*3]))
        if i < 2:
            print("-----")

def check_winner():
    win_patterns = [(0,1,2), (3,4,5), (6,7,8), (0,3,6), (1,4,7), (2,5,8), (0,4,8), (2,4,6)]
    for (x, y, z) in win_patterns:
        if board[x] == board[y] == board[z] and board[x] != " ":
            return board[x]
    if " " not in board:
        return "Draw"
    return None

def minimax(is_maximizing):
    winner = check_winner()
    if winner == "X": return -1
    if winner == "O": return 1
    if winner == "Draw": return 0

    if is_maximizing:
        best_score = -math.inf
        for i in range(9):
            if board[i] == " ":
                board[i] = "O"
                score = minimax(False)
                board[i] = " "
                best_score = max(best_score, score)
        return best_score
    else:
        best_score = math.inf
        for i in range(9):
            if board[i] == " ":
                board[i] = "X"
                score = minimax(True)
                board[i] = " "
                best_score = min(best_score, score)
        return best_score

def best_move():
    best_score = -math.inf
    move = -1
    for i in range(9):
        if board[i] == " ":
            board[i] = "O"
            score = minimax(False)
            board[i] = " "
            if score > best_score:
                best_score = score
                move = i
    board[move] = "O"

def play_game():
    while True:
        print_board()
        if check_winner():
            print("Winner:", check_winner())
            break
        
        # Player Move
        move = int(input("Enter position (0-8): "))
        if board[move] == " ":
            board[move] = "X"
        else:
            print("Invalid move!")
            continue

        if check_winner():
            print_board()
            print("Winner:", check_winner())
            break

        # AI Move
        best_move()

play_game()

18.3 Features

18.4 Potential Enhancements

19. Competitive Programming & System Design Integration

19.1 Minimax & Alpha-Beta Pruning in Competitive Programming

Minimax is frequently used in coding competitions to solve problems involving turn-based games, AI decision-making, and adversarial optimization.

1. Common Problem Types in Competitive Programming
2. Techniques to Improve Minimax Performance in Competitive Programming

19.2 Minimax in System Design

Minimax is not just for games; it is also used in AI-driven decision-making and adversarial settings in system design.

1. AI & Game Engines
2. Adversarial Search in Cybersecurity
3. Financial Trading & Risk Analysis
4. Healthcare Decision Systems

20. Assignments & Practice Problems

20.1 Solve at Least 10 Problems Using Minimax & Alpha-Beta Pruning

Practice solving the following problems to gain mastery over Minimax.

"
Problem Difficulty Concept Link
Tic-Tac-Toe AI Easy Basic Minimax GFG
Nim Game Medium Game Theory CodeChef
Checkers AI Medium Alpha-Beta Pruning HackerRank
Chess Move Prediction Hard Move Ordering ChessProgramming
Connect Four Medium Tree Search LeetCode
Reversi AI Hard Adversarial AI O'Reilly
Gomoku (Five in a Row) Medium Game Tree Search Kaggle
Monte Carlo Tree Search Hard Minimax Alternative JAIR
Ultimate Tic-Tac-Toe Hard Nested Minimax ResearchGate
AI for Poker Expert Minimax in Probabilistic Games University of Alberta Poker AI

20.2 System Design Problem Using Minimax

Design a cybersecurity intrusion detection system using Minimax where:

Implementation Plan

20.3 Implement Minimax Under Time Constraints

Challenge: Implement a Minimax-based Tic-Tac-Toe AI within 30 minutes.

Key Learning Outcome: Improve efficiency and accuracy under strict constraints.