How dice helped a computer learn backgammon

A program learning through self-play needs useful experience from somewhere. If its early strategy repeatedly produces the same situations, it can improve against its own weaknesses while learning very little about the rest of the game. At backgammon, the dice keep changing the lesson.

In the early 1990s, IBM researcher Gerald Tesauro developed TD-Gammon, which learned a position evaluator by playing against itself. His 1992 paper reported that the initial system had learned useful play from game outcomes without a collection of expert moves to copy. The legal-move rules and game results still had to be supplied; “learning from scratch” did not mean discovering the rules.

Learning an expectation from a noisy result

The evaluator’s task was to estimate an eventual outcome from a board. A completed game provides one result, while the position’s value concerns what would happen across its possible futures. These can differ even when the player makes no mistake.

Even a perfect evaluator can lose this game

You play Ivory. Both players have already borne off fourteen checkers. You win if you bear off your last checker on this roll; otherwise Red will bear off theirs next turn. We count wins only, with no cube.

Reveal the exact chances

You win on 27 of the 36 rolls, or 75%. The nine losing rolls are 1–1 and both orders of 1–2, 1–3, 1–4 and 2–3. They cannot cover six points, even with four moves for 1–1. Losing on one of them establishes no error by the evaluator or player.

Read the position

Ivory, point: number of checkers. 6: 1. Red: 24: 1. On the bar: Ivory 0, Red 0. Borne off: Ivory 14, Red 14.

For this small race, we can count every roll and know the answer exactly. An evaluator reporting a 75% winning chance would be correct before the dice, including on the quarter of occasions that end in defeat. Training it to regard each individual loss as proof that the original position was bad would confuse an outcome with an expectation.

In a full game, counting all futures is impractical. A learning system has to combine many observations and transfer what it learns between related positions. The target is a useful prediction across those situations, rather than a verdict that the winner made the better decisions in every game.

Temporal-difference learning uses the change between successive predictions to guide those adjustments, with the actual outcome supplying the final signal. If a position was judged promising and its continuation is consistently judged worse, the earlier estimate has something to learn from that disagreement without waiting for every game to finish.

Why the dice helped supply experience

Tesauro’s 1995 discussion identified the dice as a source of variety in training. He also noted that backgammon’s dynamics helped early self-play games reach an ending, producing a reward from which the system could learn. These were explanations of why this task had proved productive, not a theorem that random games are easy to learn.

Consider what a legal roll does to a practice game. A player hoping to attack can receive a roll that makes escape more urgent; a promising position can turn into a difficult defence. Even if the program applies the same decision rule whenever it sees a given board and roll, different dice sequences carry it through different parts of the game.

That variety is useful only if learning turns it into better decisions. More unusual positions can also mean more things to get wrong, and chance makes individual results less reliable evidence. The dice provide experience and noise together.

Another group tried a much simpler learning method

Jordan Pollack and Alan Blair later developed a competitive backgammon evaluator through a different method: make small changes to a network, play a challenger against the current network, and use their results to guide improvement. Their 1998 paper argued that the game’s dynamics and the changing self-play opponent helped explain the success.

This was not a claim that their system reproduced all of TD-Gammon’s strength. It showed that understanding the result required examining the learning environment as well as the particular update algorithm. A training method works through the experience it receives, and that experience depends on the game and the opponent it generates.

The price still appears in the search

When the trained player has to choose a move, future dice remain expensive to examine. Each possible roll can produce a different set of legal replies. The feature that varied its practice also widens the search needed to calculate far ahead.

Deterministic games can supply exploration through their training procedures too. AlphaZero’s work on chess, shogi and Go demonstrates that dice are no requirement for powerful self-play learning. The backgammon story is more specific: randomness was one useful ingredient in the environment where an early system succeeded.

That is a different question from which game has the largest search tree. It also explains why TD-Gammon’s contribution to opening theory came from a player that had learned to judge positions, rather than calculated the entire game.