Thursday, May 14, 2009

Computer Backgammon


The first strong computer opponent was BKG 9.8. It was programmed by Hans Berliner in the late 1970s on a PDP-10 as an experiment in evaluating board positions. Early versions of BKG played badly even against poor players, but Berliner noticed that the critical mistakes the program made were always at phase changes. He applied basic principles of fuzzy logic to smooth out the transition between phase changes, and by July 1979, BKG 9.8 was ready to play against then current world champion Luigi Villa. It won the match, 7-1, becoming the first computer program to defeat a world champion in any game, although this was mostly a matter of luck, as the computer happened to get better dice rolls than its opponent in that match.


Beginning in the late 1980s, creators of backgammon-playing software began to have even more success with a neural network approach. TD-Gammon, developed by Gerald Tesauro of IBM, was the first of these computer programs to play at or near the expert level. This program's neural network was trained using Temporal Difference learning applied to data generated from self-play.


This line of research has resulted in two modern commercial programs, Jellyfish and Snowie, the shareware BGBlitz (implemented in Java), and the free software GNU Backgammon, that play on a par with the best human players in the world. It is worth noting that without their associated weights tables which represent hours or even months of tedious neural net training, these programs play no better than a human child.


It is interesting to contrast the development of backgammon software with that of chess software:


For backgammon, neural networks work better than any other methods so far. For chess, brute force searching, with sophisticated pruning and other refinements, works better than neural networks.


Every advance in the power of computer hardware has significantly improved the strength of chess programs. In contrast, additional computing power appears to improve the strength of backgammon software only marginally.


For both backgammon and chess, it is at present unclear whether the best computer or the best human is best overall. For most other games, one or the other is unambiguously stronger.
About the Author

No comments: