Backgammon Programming

Programming

Introduction

From:   Gareth McCaughan
Address:   gjm11@can.pmms.cam.ac.uk
Date:   11 October 1994
Subject:   Re: Backgammon 'algorithm'
Forum:   rec.games.backgammon
Google:   37dqas$go0@lyra.csx.cam.ac.uk

John Fahey wrote: > I was just wondering if anyone could give me direction in how to program > backgammon for a computer. I know that it has been done hundreds of times > already but I thought it would be a good challenge to expand my knowledge > of C. > I originally thought it would have to be an recursive method that looked > at all possibilities but I imagine that could get very slow. The other > method would obviously be some sort of strategy based one perhaps using > some statistics, but with a more 'human' approach. This I think would > require me to learn a lot more about the game, take longer to program, > and possibly end up being of limited ability. > I've never tried to do anything like this so if anyone can suggest any > sources of info, even on algorithms for other games then the help would > be appreciated. The brute-force searching approach mentioned in your second paragraph has been highly successful for chess. Unfortunately it's a dead loss for backgammon! The reason is that with chess it's possible to trim down the tree you're searching quite considerably (find out about alpha-beta pruning, and things), whereas for backgammon there is no escape from having at least 21 branches for every move (because there are that many possible die rolls). So, any computationally feasible approach looks like it's going to have to operate by having a good "flat" evaluator (by "flat evaluator" I mean the thing that gets called at the end of every branch of the tree, to say how favourable the position is) and thus not having to do much searching. Substantially the best backgammon program known to me is one called "TD-Gammon". Its flat evaluator is a neural network, which was trained by self-play (starting with random weights) using the method of temporal differences ("TD(0)", to be more precise). So you might like to find out about neural networks, and probably about the TD algorithm too. There are a couple of neural-net backgammon programs to be found on FIBS sometimes. "fatboy" is rated at about 1740 at the moment, though it's probably not really quite that good. "maestro" is rated at about 1570, and I've never played it so can't comment on whether that's what it deserves. TD (whose name on FIBS is "tesauro" -- its creator is Gerry Tesauro) is rated at about 1880. For comparison, the highest-rated player on FIBS is Kit Woolsey, at 1950, the lowest-rated has a rating of 1022, and the median player is at about 1510. (Considering only "established" players, i.e. ones who have played enough games to appear in the rankings.) If you're doing this to learn programming skills, then perhaps implementing a neural network at the same time as doing all the other things for a backgammon program is a bit too much work. There certainly are tolerably good non-neural-net backgammon programs; indeed, in 1979 one such program defeated the world champion. (But it was very lucky, and human play has improved a lot since then.) This program was the result of a lot of hard work by a team of experts in computer game playing, headed by Hans Berliner. There's an article by him in "Artificial Intelligence", vol.14 (1979), but I haven't read it and don't know whether it says anything interesting about the insides of the program. If you are going to do it with a neural network, be aware that you can make a big difference to the strength of your program by putting some useful information (about points made and things) into the representation of the board seen by the network. Er, also be aware that training a neural network takes a lot of computer time! One place where exhaustive search has its uses is in the late endgame. There is a program circulating called "race2" which computes equities for such positions exactly using exhaustive search; of course you can use this to work out the best move, and it's also useful for doubling decisions. However, it is only any use in simple positions, because otherwise the search just takes too long. There is a paper by Tesauro about TD-Gammon referenced in the FAQ list for rec.games.backgammon. I should warn you that it doesn't actually tell you anything about how to implement things, merely "we wrote this program and it's stunningly good" (which it is). There is an annual "Computer Olympiad" in which programs play each other at go, chess, backgammon etc. I think there is a book published after each one, containing papers by the people responsible for some of the programs there. The books are published in England by Ellis Horwood, and have the generic title "Heuristic programming in artificial intelligence". (With, I think, a number appended for all but the first, corresponding to the number of the Olympiad.) The ones I know of are edited by Levy and Beal. I haven't read any of them, but I would expect there to be useful ideas there for writing game-playing programs of all sorts. I hope this is of some use. Sorry I haven't been able to give you much detail... -- Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics, gjm11@cus.cam.ac.uk Cambridge University, England. [Research student]

Did you find the information in this article useful?

Do you have any comments you'd like to add?