Backgammon 'algorithm'
John Fahey
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.
John
---------------------------------------------------------
John Fahey
University of Canterbury
New Zealand
email: j.f...@csc.canterbury.ac.nz
Gareth McCaughan
John Fahey <j.f...@csc.canterbury.ac.nz> 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,
gj...@cus.cam.ac.uk Cambridge University, England. [Research student]
Anthony R Wuersch
Gareth McCaughan <gj...@can.pmms.cam.ac.uk> wrote:
>"fatboy" is rated at about 1740 at the moment, though it's probably not
>really quite that good.
Ed Rybak posted an excellent mail some weeks ago noting that short term
swings can easily range a hundred points in each direction from a rating
based on infinite play. So 1740 may mean true rating from 1640 to 1840.
I don't think fatboy's rating is too high. It has a list of many players
who quit before ending lost matches. fatboy singlehandedly caused me to
fall into the big losers rating list in August.
The neural network approach is not hard to implement. The code to update
network weights and evaluate through a network once inputs are determined
is very small.
The most important question is what inputs should be, i.e. representation.
Also if segmenting the game into different stages, each needing a different
representation and network, is correct or not.
Cheers,
Toni
--
Toni Wuersch
a...@world.std.com {uunet,bu.edu,bloom-beacon}!world!arw