Minimax
Minimax is a recursive backtracking decision-making algorithm used in two-player, zero-sum, perfect-information games. It models the interaction between two adversarial agents—Maximizer and Minimizer—under the assumption that both agents act rationally to maximize their respective utilities while minimizing the opponent's. By exhaustively evaluating or heuristically bounding the game tree to a specified depth limit, Minimax computes the optimal move sequence, forming the foundational core of classical game-playing AI and decision optimization.
HOW-TO IMPLEMENT & CONFIGURE
- Modern runtime environment supporting recursive stack frames (Python 3.11+ or C++20)
- Object-oriented or functional state representation interface defining legal moves and terminal conditions
- Heuristic evaluation function mapping board states to real-valued utility scores
Architectural Setup & Game State Interface
Define a robust, immutable or mutable state interface that exposes valid transitions, terminal evaluations, and game outcome flags to prevent state pollution during deep recursive search branches.
from abc import ABC, abstractmethod
from typing import List, Any
class GameState(ABC):
@abstractmethod
def get_legal_moves(self) -> List[Any]:
pass
@abstractmethod
def make_move(self, move: Any) -> 'GameState':
pass
@abstractmethod
def is_terminal(self) -> bool:
pass
@abstractmethod
def evaluate(self) -> float:
passCore Minimax Engine with Alpha-Beta Pruning
Implement the core recursive minimax function integrated with alpha-beta pruning to eliminate sub-trees that cannot influence the final decision, reducing the branching factor from b to approximately the square root.
def minimax(state: GameState, depth: int, alpha: float, beta: float, maximizing_player: bool) -> tuple[float, Any]:
if depth == 0 or state.is_terminal():
return state.evaluate(), None
legal_moves = state.get_legal_moves()
best_move = None
if maximizing_player:
max_eval = float('-inf')
for move in legal_moves:
next_state = state.make_move(move)
eval_score, _ = minimax(next_state, depth - 1, alpha, beta, False)
if eval_score > max_eval:
max_eval = eval_score
best_move = move
alpha = max(alpha, eval_score)
if beta <= alpha:
break
return max_eval, best_move
else:
min_eval = float('inf')
for move in legal_moves:
next_state = state.make_move(move)
eval_score, _ = minimax(next_state, depth - 1, alpha, beta, True)
if eval_score < min_eval:
min_eval = eval_score
best_move = move
beta = min(beta, eval_score)
if beta <= alpha:
break
return min_eval, best_moveVerification, Profiling & Unit Testing
Verify correctness using a known deterministic domain like Tic-Tac-Toe or simplified chess endpoints. Profile call counts and recursion depth to ensure the pruning mechanism suppresses redundant state evaluations.
import unittest
class MockGameState(GameState):
def __init__(self, val, terminal=False):
self.val = val
self.terminal = terminal
def get_legal_moves(self): return [1, 2]
def make_move(self, m): return MockGameState(self.val + m if m==1 else self.val - m)
def is_terminal(self): return self.terminal
def evaluate(self): return float(self.val)
class TestMinimax(unittest.TestCase):
def test_minimax_optimal_path(self):
initial = MockGameState(val=0)
score, move = minimax(initial, depth=2, alpha=float('-inf'), beta=float('inf'), maximizing_player=True)
self.assertIsNotNone(move)Production Hardening & Transposition Tables
Mitigate exponential time complexity blowup in production systems by layering Transposition Tables (Memoization caches using Zobrist Hashing) and Iterative Deepening to safely operate within strict execution latency budgets.
class TranspositionMinimax:
def __init__(self):
self.cache = {}
def search(self, state, depth, alpha, beta, maximizing):
state_hash = hash(state)
if (state_hash, depth, maximizing) in self.cache:
return self.cache[(state_hash, depth, maximizing)]
# Compute standard minimax and cache results
result = minimax(state, depth, alpha, beta, maximizing)
self.cache[(state_hash, depth, maximizing)] = result
return result