backgammon programs using other techniques

BKG 9.8

Not a learning program, but of historical interest. BKG version 9.8 by Hans Berliner became famous by beating the then-world champion Luigi Villa by 7-1 in a seven-point match in 1979, playing worse but getting lucky dice rolls. Its practical importance is as a demonstration of the importance of avoiding artificial sharp edges in your evaluation function, for example by having separate midgame and endgame evaluators. The problem and its solution were clearly explained by Berliner in 1980, but some hand-written programs even today suffer from it.

Backgammon Computer Program Beats World Champion (1980)
Hans J. Berliner
Paper about the program and match, emphasizing the importance of a smooth evaluation function.

Motif

Motif is a freely-available Java program that you can play on the web, written by Tom Keith of Backgammon Galore!

Motif’s evaluator is a simple statistical model, which can also be seen as a neural network. Keith tuned its parameters by hand to reproduce the values of a training set of sample backgammon positions. He created the sample positions with a simple program which played against itself, and estimated their true evaluations by using the same program to roll out the positions.

He repeated this process, using Motif version 0 to create a new training set and so on, to make Motif version 1. The paper “Bootstrap learning of alpha-beta-evaluation functions” by Alois Heinz and Christoph Hense (see online papers) used the same iterative learning method with a different kind of evaluator. This can be seen as temporal difference learning with large offline steps, rather than the small reinforcement-learning-style increments of TD-Gammon and other online learners.

Motif looks ahead two ply (one play for each side), though Keith describes it as doing one-ply lookahead. (Gnu Backgammon counts plies the same way.)

Motif Backgammon
Tom Keith
Play against the program, if you have a Java-capable browser. There’s also a page explaining how Motif works.

MVP Backgammon

MVP Backgammon is a shareware Windows backgammon program which uses a modular neural network evaluation function designed by Justin Boyan for his 1992 master’s thesis. The network was trained by temporal difference learning, but its structured architecture is considerably different from the undifferentiated backprop network of TD-Gammon.

MVP Backgammon
MVP Software
An advertisement for MVP Backgammon, offering free download of a shareware version and selling a “professional” version.

Modular neural networks for learning context-dependent game strategies (1992, 41 pages)
Justin Boyan
Postscript. A master’s thesis. Compares monolithic networks to modular networks (which divide the space of game positions into classes and learn different evaluations for each class). Relies on temporal difference learning. Results for tic-tac-toe and backgammon. The backgammon program competed under the name MAESTRO. See Marco Wiering’s more recent work on this topic under online papers.

Silicon Highlands Backgammon

This now-commercial Windows program by Bob Landwehr has an evaluator optimized by a genetic algorithm. There’s no mention of neural networks. This author reports of version 1.0 that the program has an “unusual playing style, with surprising skill in complex situations and surprising blunders in simple ones”. Version 2.0 is the latest that I know of.

Apparently Silicon Highlands is weaker than the neural net programs. The author doesn’t say anything about the knowledge representation used, so we can’t draw firm conclusions, but I take this as another bit of evidence that neural nets are a good, natural representation for backgammon evaluators.

Bob’s Backgammon 2.0
Bob Landwehr
The web site includes some rather vague information about the genetic algorithm used. It doesn’t seem to have been updated since the 1990’s, unfortunately.

review of Silicon Highlands Backgammon
Peter Ozanne
An informal review of version 1.0, with remarks on the program's playing strength. This must be considered out of date.