Hi there, I''ve just recently started a university project to build a game of backgammon. My experience with AI is very limited. I was wondering if anybody could recommend an approach to implementing an intelligent backgammon computer player. If I could get some references to existing alogorithms, or learn what kinds of AI to apply to a game like backgammon. Any advice would be helpful. Thanks.

Well, a standard alpha-beta search should do the trick fine. If you don''t know what this is, there are tons of tutorials on the web, go to google and do a search on "alpha-beta game search".

Once you come up with an evaluation function for a static board position (which is the toughest parts of developing a good AI) you can apply standard search techniques and enhancements.

Some of these enhancements are things like using negascout, hash tables, mtd(f) searching, building an opening book and an endgame table and things like early cutoffs in the search tree.

For backgammon itself, you have the random element of the dice, so that makes searching a bit trickier. Given your die roll, you can search all the possible moves resulting from that die roll, then search all the possible moves the opponent can do with all the possible die rolls and return the opponents best move. This is the foundation of game search, the minimax algorithm, which once again has plenty of literature out there. Basically you are assuming that the opponent will always take there best move, and you do this recursively to come up with the best possible counter yourself.

You will also need to take probability into account, as there is only 1 way to roll a two, but there are 2 ways to roll a 4, etc. If you choose to move two seperate men on that turn then obviously those would be equal probabilities.

Anyhow, good luck with game AI, I''ve had a blast with it over the past couple of years .

The most commonly accepted way of doing a backgammon AI is to use backpropigation ( an artificial neural network ) I''ve heard from people on the ASP boards from guys who have done this that you can get a pretty mean backgammon AI after just 1000 iterations.

For reference just plug "backpropagation backgammon" into google and you''ll get lots of hits.

A 1000 iterations eh? Would you like to bet money on that? ;0)

ks2001, do a search for "TD-Gammon" and "Tesauro" and you will find out most of what you need to know.



ai-junkie.com

quote: Original post by Premandrake
You will also need to take probability into account, as there is only 1 way to roll a two, but there are 2 ways to roll a 4, etc.

In this situation I would advise using the ''Expectimax algorithm''. You can find papers for it online.

Cheers,

Timkin

lol fup - yeah count me in on that bet too will ya.

Here is some info on backgammon approaches, including TD-gammon.

Thanks everyone! I appreciate all the input. Now, off to work!!!

Uh, yeah i guess pretty mean could be taken wrong. It''s probably better phrased as, the AI will be able to make it through a game of back gammon without looking too stupid (with each iteration being a full game of backgammon)