Computer Backgammon: From BKG to Neural Networks

Backgammon was one of the first classic games in which a computer beat a reigning world champion, and later one of the first where machines taught themselves to play at expert level. The story of computer backgammon also changed how humans play the game, because the programs revealed that many traditional moves were wrong.

BKG and the 1979 match

The first well-known strong program was BKG, written by Hans Berliner at Carnegie Mellon University in the 1970s. Instead of searching deeply through possible moves, as chess programs did, BKG evaluated positions using a set of hand-made rules about features of the board. Berliner found that his program's worst mistakes came at the points where the game changed character, for example when contact was about to end. He smoothed those transitions so the program's judgment did not jump suddenly from one style of play to another.

In 1979 BKG played an exhibition match against Luigi Villa, who had just won the World Championship in Monte Carlo, and won. It was a landmark result: a program had beaten a reigning world champion at a classic board game. Berliner himself acknowledged that the program had the better of the dice in that short match. Even so, the match showed that a computer could play backgammon well enough to compete with the best.

TD-Gammon and learning from self-play

The big breakthrough came in the early 1990s with TD-Gammon, developed by Gerald Tesauro at IBM. TD-Gammon used a neural network: a mathematical model that turns a description of the position into an estimate of the winning chances. Rather than being told what good play looks like, it learned by playing huge numbers of games against itself and adjusting its estimates after each move, a technique called temporal difference learning.

The result surprised experts. TD-Gammon reached a level close to the best human players, and some of its choices, especially in the opening, went against accepted wisdom. Strong players tested those choices, found that the program was often right, and changed their own play. Several standard opening moves used today owe their status to this period.

Modern programs

Later programs built on the same neural-network approach, with better inputs, more training and smarter search. Two widely used today are GNU Backgammon, which is free and open source, and eXtreme Gammon. Both play at a level generally regarded as stronger than any human, and both are mainly used as study tools: players analyze their matches, look up the best play in a position, and run rollouts, in which a position is played out thousands of times to estimate its true value. You can read how these tools measure errors and luck on our luck and skill analysis page.

Why backgammon suits neural networks

Backgammon and chess took different paths. In chess, programs got stronger mainly by searching deeper, and faster hardware brought steady gains. In backgammon, the dice give 21 distinct rolls at every turn, so the tree of possible futures branches far too quickly for deep search to be practical. What matters most is accurate judgment of the position itself, and that is exactly what a well-trained neural network provides. The randomness of the dice also helps training: self-play naturally explores a wide variety of positions.

What it means for players

Computers turned backgammon theory from a collection of opinions into something that can be checked. Today any player can test an idea against a world-class opponent at home. For more on how the internet and software changed the game, see the internet and backgammon, and for the wider story of the modern game, read that's history.