Algorithm Reference

A comprehensive guide to the AI algorithms used across game-playing AI systems.

Fundamental Algorithms

Minimax

Purpose: Find the optimal move in perfect-information games

Idea: Recursively explore all moves, assuming both players play optimally

Time Complexity: O(b^d) where b = branching factor, d = depth

Space Complexity: O(d) for recursion stack

Best For: Small games (tic-tac-toe, chess at shallow depths)

Worst For: Games with large branching factors (100+ moves per position)

def minimax(position, depth, isMaximizing):
    if isTerminal(position):
        return evaluate(position)
    
    if isMaximizing:
        maxEval = -infinity
        for move in getLegalMoves(position):
            eval = minimax(makeMove(position, move), depth-1, False)
            maxEval = max(maxEval, eval)
        return maxEval
    else:
        minEval = +infinity
        for move in getLegalMoves(position):
            eval = minimax(makeMove(position, move), depth-1, True)
            minEval = min(minEval, eval)
        return minEval

Alpha-Beta Pruning

Purpose: Optimize minimax by eliminating irrelevant branches

Idea: Track alpha (max lower bound) and beta (min upper bound); prune when alpha >= beta

Time Complexity: O(b^(d/2)) with perfect move ordering; O(b^d) in worst case

Space Complexity: O(d)

Speedup: 100-1000x in practice

Key Insight: The order we examine moves dramatically affects pruning efficiency

def alphaBeta(position, depth, alpha, beta, isMaximizing):
    if isTerminal(position):
        return evaluate(position)
    
    if isMaximizing:
        for move in getLegalMoves(position):
            eval = alphaBeta(makeMove(position, move), depth-1, alpha, beta, False)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break  # Beta cutoff
        return alpha
    else:
        for move in getLegalMoves(position):
            eval = alphaBeta(makeMove(position, move), depth-1, alpha, beta, True)
            beta = min(beta, eval)
            if beta <= alpha:
                break  # Alpha cutoff
        return beta

Transposition Tables

Purpose: Avoid re-evaluating positions that can be reached via different move orders

Idea: Hash the current position and cache its value

Hit Rate: 30-50% in typical games

Memory: Requires careful tuning of table size

Zobrist Hashing: Fast, collision-resistant position hashing using XOR

transpositionTable = {}

def alphaBetaWithTT(position, depth, alpha, beta, isMaximizing):
    positionHash = hash(position)
    
    if positionHash in transpositionTable:
        entry = transpositionTable[positionHash]
        if entry['depth'] >= depth:
            return entry['value']
    
    if isTerminal(position):
        value = evaluate(position)
    else:
        value = alphaBeta(position, depth, alpha, beta, isMaximizing)
    
    transpositionTable[positionHash] = {
        'value': value,
        'depth': depth
    }
    return value

Game Search Algorithms

Iterative Deepening

Purpose: Search progressively deeper until time runs out

Advantage: Anytime algorithm; can stop at any time with best result so far

Overhead: Re-searches shallower positions, but typically only 10% slower

Use When: Time limits are strict and variable

def iterativeDeepening(position, timeLimit):
    bestMove = None
    startTime = currentTime()
    
    for depth in range(1, maxDepth):
        if (currentTime() - startTime) > timeLimit:
            break
        
        value, move = alphaBeta(position, depth, -infinity, +infinity, True)
        bestMove = move
    
    return bestMove

Monte Carlo Tree Search (MCTS)

Purpose: Estimate move values through simulated play-outs

Idea: Balance exploring new moves with exploiting good ones (exploration-exploitation tradeoff)

Best For: Games with high branching factor, hidden information, or no good heuristics

Phases:

Selection: Navigate tree using UCB1
Expansion: Add new child
Simulation: Play random moves to terminal
Backpropagation: Update node statistics

Scalability: More iterations = stronger play

class MCTSNode:
    def __init__(self, position):
        self.position = position
        self.visits = 0
        self.wins = 0
        self.children = []

def mcts(root, iterations):
    for _ in range(iterations):
        node = root
        
        # Selection/Expansion
        while not isTerminal(node.position) and node.children:
            node = selectBestChild(node)
        
        if not isTerminal(node.position):
            node = expandNode(node)
        
        # Simulation
        result = simulate(node.position)
        
        # Backpropagation
        while node:
            node.visits += 1
            if result == node.player:
                node.wins += 1
            node = node.parent

    return selectBestChild(root)  # Exploitation only

def selectBestChild(node, C=1.414):
    return max(node.children, 
               key=lambda c: c.wins/c.visits + C*sqrt(log(node.visits)/c.visits))

Specialized Techniques

Move Ordering

Goal: Examine best moves first to maximize alpha-beta pruning

Strategies:

Killer Moves: Track moves that caused cutoffs at same depth
Threat Ordering: Check offensive/defensive moves first
Capture-First: Examine captures before quiet moves
History Heuristic: Use past success as predictor

Evaluation Functions

Design domain-specific heuristics to estimate position quality without full search:

def evaluateChess(position):
    score = 0
    
    # Material count
    for piece, value in pieceTables.items():
        score += countPieces(position, piece) * value
    
    # Position bonuses
    score += evaluatePawnStructure(position)
    score += evaluateKingSafety(position)
    score += evaluatePieceActivity(position)
    
    return score

Endgame Databases

Pre-compute perfect play for positions with few pieces:

Tic-Tac-Toe: All 5,478 positions
Checkers: ~500 billion 10-piece endgames
Chess: 7-piece tablebases available online

Benefits: Instant perfect moves in endgame, immediate win/loss detection

Hidden Information & Stochastic Games

Belief State Tracking

Maintain probability distribution over possible game states:

class BeliefState:
    def __init__(self, observations):
        self.possibleStates = generateConsistentStates(observations)
        self.probabilities = uniformDistribution(self.possibleStates)
    
    def update(self, newObservation):
        filtered = [s for s in self.possibleStates 
                   if consistent(s, newObservation)]
        self.possibleStates = filtered
        self.probabilities = uniformDistribution(filtered)
    
    def expectedValue(self, move):
        return sum(p * utility(move, state) 
                  for state, p in zip(self.possibleStates, self.probabilities))

Information Set Abstraction

Group states that are indistinguishable from a player’s perspective, reducing complexity

Used in: Poker AI, imperfect information games

Comparison Table

Algorithm	Best For	Complexity	Notes
Minimax	Perfect info, small	O(b^d)	Exhaustive search
Alpha-Beta	Perfect info, medium	O(b^(d/2))	Pruning optimization
Transposition Tables	Any search	O(n) lookup	Cache hits reduce work
MCTS	High branching, hidden info	O(iterations)	Statistical sampling
Iterative Deepening	Time-limited	Same as base	Anytime algorithm
Minimax + Heuristic	Large games	O(b^d) truncated	Chess, checkers