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
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
email@example.com Cambridge University, England. [Research student]