Catan

Hard Algorithms: Monte Carlo Tree Search, UCB1 Algorithm, Heuristic Evaluation

Catan

Hard Algorithms: Monte Carlo Tree Search, UCB1 Algorithm, Heuristic Evaluation

Overview

Catan is a settlement-building game with hidden card draws, multiple players, and non-deterministic elements. With ~10^43 possible game states, traditional minimax is infeasible. We use Monte Carlo Tree Search (MCTS) instead.

Game Summary

Players compete to build settlements, cities, and roads on an island. Resources (wood, brick, wheat, sheep, ore) are distributed based on dice rolls and card draws. First to 10 victory points wins.

Monte Carlo Tree Search (MCTS)

MCTS doesn’t require a heuristic evaluation function—it estimates move values through simulated play-outs.

mcts(state, iterations):
  root = createNode(state)
  
  for i = 1 to iterations:
    leaf = select(root)           // Selection & Expansion
    simulation = rollout(leaf)    // Simulation
    backpropagate(leaf, result)   // Backpropagation
  
  return bestChild(root, 0)  // Exploitation only

MCTS Phases

  1. Selection: Traverse tree using UCB1 formula to balance exploration/exploitation
  2. Expansion: Add new child node to leaf
  3. Simulation: Play random moves from leaf to terminal state
  4. Backpropagation: Update node statistics (visits, wins) back to root

UCB1 Algorithm

The Upper Confidence Bound algorithm selects nodes to explore:

UCB1(node) = (wins / visits) + C * sqrt(ln(parentVisits) / visits)

Where:

  • Exploitation: wins / visits (estimated win rate)
  • Exploration: sqrt(ln(parentVisits) / visits) (uncertainty bonus)
  • C: Constant controlling exploration rate (typically 1.414)

Advantages for Catan

  • No Heuristic Needed: Learns good moves through self-play
  • Handles Randomness: Simulations account for dice rolls
  • Scalable: More iterations = better play (CPU-limited)
  • Multi-Player: Naturally handles 3+ players

Interactive Demo

Play Catan against the AI:

Catan Game

Build settlements and cities to reach 10 victory points first.

Key Concepts

  • Iterations vs Quality: 1,000 iterations = ~1 sec, weak play; 100,000 = moderate strength
  • Parallel MCTS: Run simulations on multiple threads for better performance
  • Rave Moves: Track moves that were successful regardless of move order
  • Knowledge Priors: Bias simulations toward human-identified good moves

Implementation Challenges

  • Move Generation: Efficient legal move computation
  • Game State Representation: Compact storage for resources, roads, settlements
  • Heuristic Rollouts: Random simulations can be slow; use heuristics for faster estimates
  • Time Management: Allocate more time for critical decisions

Code on GitHub

View the MCTS implementation for Catan with various optimization techniques and AI difficulty levels.

Complexity Comparison

Game Algorithm Positions Branching
Tic-Tac-Toe Minimax 255K 5
Connect-4 Alpha-Beta 4.2T 7
Checkers Alpha-Beta + Endgame DB 5×10²⁰ 8
Catan MCTS ~10⁴³ 20-100

Next Steps

Explore Wingspan for probabilistic reasoning and hidden information management.