How Game AI Makes Decisions — From Minimax to Alpha-Beta Pruning

allows swapping evaluation strategies (e.g., material count vs. positional weights) without altering the search logic.

• Alpha-Beta Bounds: The search must track alpha (best value maximizer can guarantee) and beta (best value minimizer can guarantee). Pruning occurs when beta <= alpha, indicating the current branch cannot influence the final decision.

2. Implementation (TypeScript)

The following implementation demonstrates a production-ready structure with interfaces, type safety, and integrated pruning.

// Domain Interfaces
interface GameState {
    isTerminal(): boolean;
    getLegalMoves(): Move[];
    applyMove(move: Move): GameState;
    clone(): GameState;
}

interface Move {
    id: string;
    // Move metadata for ordering heuristics
}

interface Evaluator {
    score(state: GameState): number;
}

// Search Configuration
interface SearchConfig {
    maxDepth: number;
    timeLimitMs?: number;
    moveOrdering?: boolean;
}

// Core Search Engine
class AdversarialSearcher {
    private evaluator: Evaluator;
    private config: SearchConfig;

    constructor(evaluator: Evaluator, config: SearchConfig) {
        this.evaluator = evaluator;
        this.config = config;
    }

    public findBestMove(state: GameState): Move | null {
        const legalMoves = state.getLegalMoves();
        if (legalMoves.length === 0) return null;

        let bestMove: Move | null = null;
        let bestScore = -Infinity;
        let alpha = -Infinity;
        let beta = Infinity;

        // Move ordering optimization: try promising moves first
        const orderedMoves = this.config.moveOrdering 
            ? this.orderMoves(legalMoves, state) 
            : legalMoves;

        for (const move of orderedMoves) {
            const nextState = state.applyMove(move);
            // Root is always maximizing
            const score = this.searchNode(nextState, this.config.maxDepth - 1, false, alpha, beta);
            
            if (score > bestScore) {
                bestScore = score;
                bestMove = move;
            }
            alpha = Math.max(alpha, score);
        }

        return bestMove;
    }

    private searchNode(
        state: GameState,
        depth: number,
        isMaximizing: boolean,
        alpha: number,
        beta: number
    ): number {
        if (depth === 0 || state.isTerminal()) {
            return this.evaluator.score(state);
        }

        const legalMoves = state.getLegalMoves();
        const orderedMoves = this.config.moveOrdering 
            ? this.orderMoves(legalMoves, state) 
            : legalMoves;

        if (isMaximizing) {
            let maxEval = -Infinity;
            for (const move of orderedMoves) {
                const nextState = state.applyMove(move);
                const evalScore = this.searchNode(nextState, depth - 1, false, alpha, beta);
                maxEval = Math.max(maxEval, evalScore);
                alpha = Math.max(alpha, evalScore);
                if (beta <= alpha) break; // Prune
            }
            return maxEval;
        } else {
            let minEval = Infinity;
            for (const move of orderedMoves) {
                const nextState = state.applyMove(move);
                const evalScore = this.searchNode(nextState, depth - 1, true, alpha, beta);
                minEval = Math.min(minEval, evalScore);
                beta = Math.min(beta, evalScore);
                if (beta <= alpha) break; // Prune
            }
            return minEval;
        }
    }

    private orderMoves(moves: Move[], state: GameState): Move[] {
        // Heuristic ordering: e.g., captures first, checks first
        // Implementation depends on game specifics
        return moves; 
    }
}

3. Rationale

• Separation of findBestMove and searchNode: The root node requires tracking the best move, while internal nodes only return scores. This separation clarifies the control flow.
• Move Ordering: Alpha-Beta efficiency is highly sensitive to move order. Best moves should be explored first to trigger early pruning. The orderMoves hook allows injecting domain-specific heuristics (e.g., capturing moves in chess) to maximize pruning rates.
• Bounds Propagation: alpha and beta are passed down and updated. This ensures that pruning decisions are based on the global context of the search, not just local subtree values.

Pitfall Guide

Production game AI often fails due to subtle implementation errors rather than algorithmic flaws. The following pitfalls are common in real-world deployments.

1. State Mutation Corruption

   • Explanation: Modifying the game state in-place during recursion without restoring it causes the search tree to become corrupted. Subsequent branches evaluate incorrect states.
   • Fix: Use immutable state objects or implement a strict undoMove mechanism. Prefer applyMove returning a new state instance for safety, despite allocation overhead.

2. The Horizon Effect

   • Explanation: The agent pushes a negative outcome just beyond the search depth limit, appearing to avoid the problem while actually delaying an inevitable loss.
   • Fix: Implement Quiescence Search. When depth reaches zero, continue searching only "noisy" moves (e.g., captures, checks) until the position is stable. This prevents the agent from making superficially safe moves that hide tactical disasters.

3. Evaluation Function Bias

   • Explanation: Heuristics that overvalue specific features (e.g., material count) cause the agent to ignore positional nuances or long-term strategic advantages.
   • Fix: Balance evaluation components. Use weighted sums with tuned coefficients. In advanced systems, employ machine learning to derive evaluation weights from game data rather than manual tuning.

4. Alpha-Beta Logic Errors

   • Explanation: Swapping alpha and beta updates or using incorrect initial values (Infinity vs -Infinity) breaks pruning logic, leading to incorrect moves or missed optimizations.
   • Fix: Use strict typing and unit tests with known positions. Verify that alpha is only updated in maximizing nodes and beta in minimizing nodes.

5. Ignoring Move Ordering

   • Explanation: Without move ordering, Alpha-Beta pruning degrades to standard Minimax performance. The agent wastes cycles exploring irrelevant branches.
   • Fix: Implement move ordering heuristics. Prioritize moves that caused cutoffs in previous iterations (Transposition Tables) or domain-specific priorities like captures and checks.

6. Depth Limit Artifacts

   • Explanation: Agents may play "waiting" moves to extend the game indefinitely if the evaluation function doesn't penalize depth or repetition.
   • Fix: Add a small penalty for each ply searched to encourage decisive play. Detect and penalize repeated states to prevent infinite loops.

7. Evaluation Cost Bottlenecks

   • Explanation: A complex evaluation function can dominate runtime, limiting search depth more than the branching factor.
   • Fix: Profile evaluation time. Incremental updates (updating only changed features) are often faster than full recomputation. Cache evaluation results using Transposition Tables.

Production Bundle

Action Checklist

• Define Immutable Transitions: Ensure applyMove returns a new state or supports reliable undo operations.
• Implement Pluggable Evaluator: Decouple scoring logic to allow independent tuning and testing.
• Add Alpha-Beta Bounds: Replace naive Minimax with Alpha-Beta pruning immediately; the code complexity increase is minimal.
• Integrate Move Ordering: Add heuristics to sort moves before iteration to maximize pruning efficiency.
• Enable Quiescence Search: Extend search for tactical moves at leaf nodes to mitigate the horizon effect.
• Add Iterative Deepening: Search incrementally (depth 1, 2, 3...) to allow time-controlled moves and reuse previous results.
• Profile Node Count: Monitor nodes visited vs. depth achieved to validate pruning effectiveness.

Decision Matrix

Scenario	Recommended Approach	Why	Cost Impact
Simple Puzzle / Solitaire	Greedy or DFS	No opponent; static environment.	Low
Turn-Based Strategy	Minimax + Alpha-Beta	Adversarial; deterministic.	Medium
High Branching / Stochastic	Monte Carlo Tree Search (MCTS)	Minimax struggles with huge branching factors or randomness.	High
Real-Time Constraints	Iterative Deepening + Alpha-Beta	Allows interruptible search and time management.	Medium
Complex Evaluation Needed	Alpha-Beta + Transposition Table	Caches results to avoid redundant computation.	High Memory

Configuration Template

Use this template to initialize the search engine with production-safe defaults.

const defaultSearchConfig: SearchConfig = {
    maxDepth: 4,
    timeLimitMs: 500,
    moveOrdering: true,
};

// Example Evaluator Implementation
class MaterialEvaluator implements Evaluator {
    score(state: GameState): number {
        // Domain-specific scoring logic
        // Returns positive for maximizing player advantage
        return 0; 
    }
}

// Usage
const searcher = new AdversarialSearcher(new MaterialEvaluator(), defaultSearchConfig);
const bestMove = searcher.findBestMove(currentState);

Quick Start Guide

1. Define State Interface: Implement GameState with isTerminal, getLegalMoves, and applyMove. Ensure state immutability.
2. Write Evaluator: Create an Evaluator that scores positions. Start with simple heuristics (e.g., material balance) and refine later.
3. Instantiate Searcher: Create AdversarialSearcher with your evaluator and a conservative maxDepth (e.g., 3 or 4).
4. Execute Search: Call findBestMove during the agent's turn. Integrate with your game loop.
5. Optimize: Add move ordering and Quiescence Search once the baseline is functional. Profile performance to adjust depth limits.