Evaluating Classical Board States: From Handcrafted Heuristics to Neural Network Value Functions

In algorithmic game theory, two fundamental paradigms govern the development of competitive engines: explicit game-tree search and position evaluation. While brute-force search explores future decision branches, the evaluation function acts as the compass, distilling the high-dimensional complexity of a board state into a scalar value representing winning probability or expected utility.

Across classical board games—spanning deterministic perfect-information systems like chess and checkers, to stochastic imperfect-information environments like backgammon—the design of this evaluation function has traversed three distinct eras: linear handcrafted feature vectors, rollout simulations, and deep neural value approximations.

1. The Geometry of State Spaces

Before evaluating a board state, one must appreciate the sheer magnitude of the combinatorial state space. A complete traversal of any classical strategy game is mathematically impossible under physical computing constraints:

• American 8x8 Checkers (Draughts): Possesses approximately 5 × 10^20 reachable positions. It was weakly solved in 2007 by Jonathan Schaeffer's Chinook project through the synthesis of forward alpha-beta search and an endgame tablebase containing all positions with 10 or fewer pieces (3.9 × 10^13 states).
• Chess: Possesses a game-tree complexity estimated at 10^120 (the Shannon Number) and an estimated state-space complexity of 10^44 to 10^46 legal positions.
• Backgammon: Possesses roughly 10^18 legal checker configurations. However, the presence of stochastic chance nodes (rolling two six-sided dice yielding 21 distinct outcomes, or 36 equally weighted permutations) inflates the effective branching factor at each depth level to several hundred possible transitions.

2. Handcrafted Linear Heuristics and Minimax Search

The classical approach to evaluation relies on linear combinations of domain-specific features extracted from board geometry:

Evaluation(State) = w_1 * f_1(State) + w_2 * f_2(State) + ... + w_n * f_n(State)

In deterministic games like chess and draughts, features were meticulously engineered by international grandmasters and computer scientists:

• Material Balance: Direct piece valuation (e.g., standard pawn = 1, knight = 3, bishop = 3.25, rook = 5, queen = 9 in chess; men vs. kings in checkers).
• Positional Geometry: Control of key structural squares (the center four squares in chess; the double-corner diagonal and king-row stability in checkers).
• Mobility: The count of legal moves available to a side versus the opponent, penalizing cramped or boxed pieces.
• King Safety and Pawn Structure: Isolated, doubled, or backward pawns, compared against advancing passed pawns.

Coupled with Alpha-Beta Pruning, which eliminates branches guaranteed to be sub-optimal based on established bounds (alpha for the maximizer, beta for the minimizer), linear evaluation functions enabled engines like Deep Blue to calculate up to 200 million positions per second.

3. The Stochastic Challenge: Expectiminimax in Backgammon

In backgammon, standard Alpha-Beta pruning cannot be applied directly because player decisions alternate with stochastic dice rolls. Instead, search algorithms must utilize Expectiminimax, which introduces chance nodes taking the weighted average of all 36 possible dice outcomes:

Value(ChanceNode) = Sum[ P(Roll_i) * Value(DecisionNode_i) ]

Because every chance node branches 21 ways (15 asymmetric rolls with weight 2, and 6 doublets with weight 1), the depth of exhaustive search collapses. A 3-ply backgammon search requires evaluating tens of thousands of leaf nodes; a 5-ply search becomes computationally prohibitive in real-time play.

Consequently, early heuristic engines relied heavily on static features:

• Pip Count: The total sum of distances required for all 15 checkers to reach the bearoff tray.
• Anchor Points: Establishing defensive footholds on the opponent's home board (the 20-point or 21-point).
• Prime Length: The count of contiguous closed points, recognizing that a 6-prime creates an impassable barrier.
• Blot Vulnerability: The exact mathematical probability of single exposed checkers being hit by direct or indirect rolls.

4. The Neural Revolution: TD-Gammon and Reinforcement Learning

The breakthrough that permanently altered game AI occurred not in chess, but in backgammon. In 1992, Gerald Tesauro created TD-Gammon at IBM Research. Rather than employing grandmaster-crafted linear formulas, TD-Gammon utilized a multi-layer perceptron trained via Temporal Difference Learning [TD(lambda)] through self-play.

The network took a raw representation of the board state (checker counts across the 24 points, the bar, and off the board) and output four continuous probability estimates:

1. Probability of White winning a single game.
2. Probability of White winning a gammon (double points).
3. Probability of Black winning a single game.
4. Probability of Black winning a gammon.

Remarkably, without explicit human instructions on strategic themes like slotting, priming, or duplicate shots, TD-Gammon independently discovered positional principles that challenged human convention, prompting a wholesale revision of opening book theory among human champions.

5. Efficiently Updatable Neural Networks (NNUE)

In modern deterministic engines (such as Stockfish in chess and contemporary draughts analyzers), the evaluation paradigm has culminated in NNUE (Efficiently Updatable Neural Network).

NNUE replaces both complex manual feature extractors and heavy GPU-dependent deep networks with a lightweight CPU-friendly neural architecture. Because moving a single piece alters only a fraction of board inputs, the hidden layer activations can be incrementally updated in constant time via differential accumulation. This innovation allows modern engines to retain deep tree searches (30+ plies) while evaluating states through non-linear neural approximations rather than rigid handcrafted heuristics.

Conclusion: Synthesis of Search and Heuristics

Whether examining Chinook's perfect endgame tablebases, Stockfish's NNUE evaluations, or neural net rollouts in backgammon engines like wildbg and GNU Backgammon, the trajectory of computer strategy games reveals a unifying principle: raw computational power is meaningless without an evaluation metric that accurately mirrors game-theoretic equilibrium.