Temporal Difference Learning and TD-Gammon

Board games have been a testing ground for AI since Shannon proposed a chess algorithm in 1950 and Samuel built his checkers learner in 1959. The appeal is clear: the rules are precise, the environment is fully observable, and performance is easy to measure. But backgammon posed a unique challenge.

First, the state space is enormous — over $10^{20}$ possible positions. Brute-force search, which worked well in chess and checkers, was hopeless because of the dice: each ply has 21 possible dice combinations with ~20 legal moves each, giving a branching factor of several hundred per ply, far too large for deep search.

Second, the traditional approach — having human experts hand-craft an evaluation function over years of knowledge engineering — hit a ceiling. Expert beliefs about backgammon strategy kept changing over the decades; programmers were building on shifting ground.

Third, supervised learning from expert-labeled positions (the approach used by Neurogammon, Tesauro's earlier program) achieved only intermediate play. The training data reflected human biases and blind spots, limiting what the network could learn.

The core insight of temporal difference learning is deceptively simple: instead of waiting until the end of a game to learn, update your estimates after every move based on how your prediction changed.

Think of it as a weather forecaster who doesn't wait until the end of the week to check their Monday forecast. Instead, they compare Monday's forecast to Tuesday's — if Tuesday's forecast is more accurate (because it has fresher data), the difference between the two is a useful learning signal right now.

In TD-Gammon, the neural network outputs a prediction $V(s_t)$ — its estimate of the probability of winning from the current board state $s_t$. After the next move produces state $s_{t+1}$, the network computes a new prediction $V(s_{t+1})$. The difference between these two predictions is the TD error — the learning signal that drives weight updates.

TD-Gammon used a standard multi-layer perceptron with a single hidden layer. The architecture is straightforward — its power came from the training procedure, not architectural novelty.

Input encoding: The board state was encoded as a vector of ~198 raw features (number of white/black checkers at each of the 24 positions, plus bar and off counts). Later versions added hand-crafted features from Neurogammon, bringing the total to ~294 inputs.

Hidden layer: 40 to 80 hidden units with sigmoid activation. Each hidden unit computes a weighted sum of all inputs, then squashes it through a sigmoid to produce a value between 0 and 1. This nonlinearity lets the network learn context-sensitive evaluations — for example, that the value of holding a particular point depends on where the other checkers are.

Output: Four sigmoid units representing the probability of each outcome — white win, white gammon, black win, black gammon. The network's estimate of expected value (equity) is derived from these probabilities.

The self-play training procedure is where TD-Gammon's magic happens. Here is the complete loop:

1. Initialize randomly. The network starts with random weights — its initial strategy is pure noise. Games take hundreds or thousands of moves because neither side plays sensibly.

2. Play a complete game. At each turn, the network evaluates all legal moves by feeding each resulting board state through the network. It picks the move with the highest estimated win probability — greedy action selection.

3. Update after every move. After each move, the TD(λ) rule computes the error between the current prediction and the next prediction, and adjusts weights accordingly. At game end, the actual outcome (win/loss/gammon) replaces the next prediction.

4. Repeat. The network plays another game against its updated self. Over hundreds of thousands of games, play quality improves dramatically.

Tesauro identified three reasons why TD learning succeeded so well in backgammon, forming important lessons for future applications of reinforcement learning:

1. Relative accuracy matters more than absolute accuracy. TD-Gammon's value estimates were often off by a tenth of a point in absolute terms — seemingly too large for master-level play. But when comparing two candidate moves, both estimates were wrong by nearly the same amount (because the resulting positions are similar). The errors cancelled, leaving the ranking correct. This similarity-based error cancellation is a powerful property of neural network generalization.

2. Stochasticity is a feature, not a bug. The random dice rolls forced the network to explore a wide variety of positions during self-play. In deterministic games like chess, self-play can get stuck in narrow loops, developing strategies that are self-consistent but globally poor. The dice act as a natural exploration mechanism, preventing this trap.

3. Linear concepts emerge first. In the early phase of training, the network learned simple context-free rules — "blots are bad," "points are good" — that can be expressed as linear functions of the raw inputs. These simple rules gave better-than-beginner play and provided a solid foundation for later learning of nonlinear, context-sensitive concepts. This curriculum-like progression — linear before nonlinear — may be why training from random weights worked at all.

TD-Gammon's influence extended far beyond computer science. Its play style frequently differed from traditional expert strategies — and in several cases proved superior.

The most famous example: for 30 years, experts universally preferred "slotting" as an opening move with rolls like 2-1, 4-1, or 5-1. TD-Gammon's rollout analysis showed that splitting the back checkers was actually better. Top players experimented with the split, found tournament success, and the slotting play "virtually disappeared from tournament competition." A machine trained with no human knowledge overturned decades of human conventional wisdom.

Kit Woolsey, rated #3 in the world, wrote: "TD-Gammon's positional judgment is far better than mine... its judgment on bold vs. safe play decisions, which is what backgammon really is all about, is nothing short of phenomenal."

TD-Gammon proved three principles that would echo through decades of AI research: self-play can discover superhuman strategies, neural networks can approximate value functions in enormous state spaces, and temporal difference learning can solve the credit assignment problem in long games.

These exact principles — scaled up with deeper networks, Monte Carlo Tree Search, and massive compute — became the foundation of AlphaGo, which defeated the world Go champion in 2016. AlphaZero then generalized the approach to chess and shogi, mastering each from scratch in hours. The line from TD-Gammon to AlphaZero is direct and unmistakable: self-play + neural evaluation + learning from temporal differences.

TD-Gammon's deepest lesson is not about backgammon — it's about the power of learning by doing. A system that starts knowing nothing, plays against itself, and learns only from its own prediction errors can surpass the accumulated wisdom of human experts. This principle — that self-play with the right learning signal can discover what no teacher could teach — is one of the most profound insights in the history of artificial intelligence.