34 Why is it so hard to write a good backgammon program?
Description
This article is from the Backgammon FAQ, by Mark Damish damish@ll.mit.edu with numerous contributions by others.
34 Why is it so hard to write a good backgammon program?
There are two basic ways that a computer can play a game as well as or
better than humans. One is to be really smart, the other is to do an
awful lot of work. The general strategy most game-playing programs use
is to use an evaluation function that isn't very smart, but to make up
for it by looking ahead a lot of moves (doing a lot of work).
With chess, there are typically 20-30 moves by each player per turn.
With backgammon, there are 21 unique rolls and often 4-6 ways to play
each one (not counting doubles with could have 10 or more ways of
playing). This makes it very difficult to look ahead very many levels.
Looking ahead 3 moves by both players examining all possibilities when
there are 25 choices at each play requires evaluating "only" 244
million positions. If there are 90 ways to play each move, there are
530,000 million, positions.
With a game like chess, one can discard all but the best 5 or 10 plays
per person. With backgammon, there are always 21 different choices of
best plays, depending on the dice. This makes it crucial to have an
excellent evaluation function.
The difficulty in doing this is that factors such as the race have a
different effect on the value of the position depending on what stage
the game is in. Consider the concept of timing -- hard enough for
people to grasp, extremely difficult for computers.
Another example of the difficulty of evaluating plays: It's almost
always beneficial to close out your opponents checkers. But if you've
hit one checker and you almost have to hit a second to be able to win,
closing out your opponent is very bad.
-michael j zehr
Further information relating to machine learning in games may be found
at: http://forum.swarthmore.edu/~jay/learn-game/systems/gammon.html
Continue to:
My Books
