Programming

Forum Archive : 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?     

 

Programming

Adjusting to a weaker opponent  (Brian Sheppard, July 1997) 
Anticomputer positions  (Bill Taylor+, June 1998) 
BKG 9.8 vs. Villa  (Raccoon+, Aug 2006) 
BKG 9.8 vs. Villa  (Andreas Schneider, June 1992) 
BKG beats world champion  (Marty Storer, Sept 1991) 
Backgames  (David Montgomery+, June 1998)  [Long message]
Blockading feature  (Sam Pottle+, Feb 1999)  [Long message]
Board encoding for neural network  (Brian Sheppard, Feb 1997) 
Bot weaknesses  (Douglas Zare, Mar 2003) 
Building and training a neural-net player  (Brian Sheppard, Aug 1998) 
How to count plies?  (Chuck Bower+, Jan 2004)  [GammOnLine forum]
How to count plies?  (tanglebear+, Mar 2003) 
Ideas for improving computer play  (David Montgomery, Feb 1994) 
Ideas on computer players  (Brian Sheppard, Feb 1997) 
Introduction  (Gareth McCaughan, Oct 1994) 
Measuring Difficulty  (John Robson+, Feb 2005)  [GammOnLine forum]
Methods of encoding positions  (Gary Wong, Jan 2001) 
N-ply algorithm  (eXtreme Gammon, Jan 2011) 
Neural net questions  (Brian Sheppard, Mar 1999) 
Pruning the list of moves  (David Montgomery+, Feb 1994) 
Search in Trees with Chance Nodes  (Thomas Hauk, Feb 2004) 
Source code  (Gary Wong, Dec 1999) 
TD-Gammon vs. Robertie  (David Escoffery, June 1992) 
Training for different gammon values  (Gerry Tesauro, Feb 1996) 
Training neural nets  (Walter Trice, Nov 2000) 
Variance reduction in races  (David Montgomery+, Dec 1998)  [Long message]
Variance reduction of rollouts  (Michael J. Zehr+, Aug 1998)  [Long message]
Variance reduction of rollouts  (Jim Williams, June 1997) 
What is a "neural net"?  (Gary Wong, Oct 1998) 
Writing a backgammon program  (Gary Wong, Jan 1999) 

[GammOnLine forum]  From GammOnLine       [Long message]  Long message       [Recommended reading]  Recommended reading       [Recent addition]  Recent addition
 

  Book Suggestions
Books
Cheating
Chouettes
Computer Dice
Cube Handling
Cube Handling in Races
Equipment
Etiquette
Extreme Gammon
Fun and frustration
GNU Backgammon
History
Jellyfish
Learning
Luck versus Skill
Magazines & E-zines
Match Archives
Match Equities
Match Play
Match Play at 2-away/2-away
Miscellaneous
Opening Rolls
Pip Counting
Play Sites
Probability and Statistics
Programming
Propositions
Puzzles
Ratings
Rollouts
Rules
Rulings
Snowie
Software
Source Code
Strategy--Backgames
Strategy--Bearing Off
Strategy--Checker play
Terminology
Theory
Tournaments
Uncategorized
Variations

 

Return to:  Backgammon Galore : Forum Archive Main Page