Pillar 08 · Combinatorial State Trees
The Strategy Space & Combinatorics
Humans play games; artificial agents search trees. Trace the combinatorial complexity spectrum from strongly solved games (Connect Four, Checkers) to superhuman neural search (AlphaZero, KataGo, AlphaStar).
Game Tree Complexity HierarchyFrom Shannon's Number to Go and StarCraft II
Selected Complexity Node: 8x8 Grid (64 Squares)
Unsolved (Superhuman AI)Chess
State Space Size
10^47
Game Tree Leaves
10^123 (Shannon Number)
Branching Factor (b)
~35
Average Plies (d)
80
Milestone AI Architecture
Deep Blue (1997) -> Stockfish NNUE (2020) -> AlphaZero (2017)
Alpha-Beta Minimax with Quiescence Search, History Heuristics, NNUE Evaluation & MCTS Deep RL.
Praxologium Agent Bridge
"Heuristic evaluation functions prune the vast combinatorial tree to guide optimal move selection."
Algorithmic Tree Search Paradigms
Minimax with Alpha-Beta Pruning1950s–1990s
Traverse tree depths, pruning branches where beta <= alpha, guaranteeing identical outcome to full minimax.
Complexity Gain: Reduces effective branching factor from b to sqrt(b) in optimal move ordering.
Applied: Chess, Checkers, Othello, Connect Four.
Monte Carlo Tree Search (MCTS)2006–Present (Coulom, Kocsis & Szepesvári)
Four-phase loop: Selection (UCT formula), Expansion, Simulation / Rollout, Backpropagation.
Complexity Gain: Focuses computational budget on high-probability promising subtrees without requiring static heuristics.
Applied: Go, Hex, General Game Playing (GGP).
Deep Reinforcement Learning (Actor-Critic / AlphaZero)2017–Present (Silver et al.)
MCTS guided by neural networks (p_theta, v_theta) trained tabula rasa via self-play without human data.
Complexity Gain: Replaces random rollouts with value network inference, achieving superhuman performance across diverse games.
Applied: AlphaZero (Chess, Shogi, Go), MuZero (Atari + Board Games).