|
|
Programming |
Programming Computers to Play Backgammon
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| From Backgammon Times, Volume 2, Number 1, Winter 1982. |
In today's era of advanced computer technology, computers are being programmed to play games with increasing skill. For example, the top chess-playing computers can beat 99% of tournament players, and the best othello player in the world is a computer. Backgammon, however, has proven to be a more difficult game to program successfully: even the finest programs will make moves that advanced intermediate players would sneer at. Why is it that backgammon programs do not play as well as chess or othello programs? Is backgammon more difficult, or is it simply that there has been less effort in this field? This article will examine some of the problems encountered in game programming, and will explain why backgammon is, in fact, harder to program than other games.
A computer cannot "think" better than a human; in fact, a computer does not think at all. When a computer tries to find the best move in either chess or backgammon, it looks at all possible moves, evaluates them based upon predefined criteria, and then selects the best of these moves. The computer's advantage is that it does this very quickly—it can analyze several hundred or thousands positions in the time a human takes to analyze one position. Another advantage that the computer has is that it is thorough—it cannot have a "blind spot" and miss a possible move.
The human has an advantage over the computer because he can be selective: he can concentrate on those considerations he feels are important in the particular situation. For example, with an opening roll of 4-3, the computer will consider 6/3, 6/2 as a possible move. If the criteria within the program are correct, the computer will reject this; however, it will be analyzed in the same manner as any other play. An experienced human player will immediately reject this move as ridiculous.
More importantly, a human can look ahead at how a game is likely to develop and make his moves accordingly. It is very difficult to program a computer to do this, for the computer cannot be imaginative at all—it must strictly follow its program. In chess, the look-ahead concept can be developed to some degree. In any given position, there might be a dozen "reasonable" moves among many more legal plays. The computer can be programmed to dismiss those that are not "reasonable." Then the opponent's possible replies to each of these reasonable moves are analyzed, and the computer's responses to these, and so on for as many moves as time allows. (Remember, a fast computer can run through several thousand of these sequences in a second!)
When a final position is reached, the computer evaluates it based upon programmed criteria. After evaluating all final positions, the computer then selects the move which will lead to the best position. This process closely approximates the way a human chess player analyzes a position.
In backgamon, the look-ahead problem is complicated by the uncertainty of the dice rolls. The thirty or more legal moves available for each roll of the dice must first be analyzed. This must be multiplied by the twenty-one possible dice rolls (6-1 is considered the same as 1-6.) Therefore, for each move there would be about 600 plays to be analyzed. To look ahead just to the computer's next move would involve about 360,000 possible positions to analyze—too great a task for even the fastest computers to accomplish in a reasonable amount of time.
The approach generally used in backgammon programs is to evaluate each legal play based on factors such as points held, blots left, etc., and then to make the play which is evaluated as the best. Humans basically do the same thing, but their evaluation functions are better because they are flexible and are able to take into consideration resulting future positions. This last feature is something which has proven very difficult to program a computer to do, and it results in computers making some abnormal-looking plays.
The best backgammon-player program is one written by Hans Berliner, with consultation from Paul Magriel. In 1979, this program won a seven-point match against Luigi Villa, winner of the World Championship. While the program performed surprisingly well as a whole, several of the plays illustrate the difficulties involved in programming computers to play expert level backgammon.
|
Position 1. Black (computer) to play 5-4. |
Apparently the evaluating part of the program misevaluated the importance of the blot because Black has a stronger board and both players have two men back. All of this is true, but the program did not look ahead to likely resulting positions. If the blot is hit, Black may run out of men to play with. Even if the blot is missed, it will still have to be made safe on the next roll, causing Black to lose communication with his runners and take pressure off of the opposing midpoint.
By looking only at the stronger immediate position (possession of a better point and more builders), it failed to look down the road a move or two to see the dangers of this play. A good human player would recognize that holding the midpoint might well be important in a few rolls and that leaving a direct shot is quite dangerous, despite a stronger home board.
|
Position 2. Black (computer) to play 4-2. |
The human player could see that there probably won't be a shot for a few rolls and that he will have plenty of time to put his board back together. He will also realize that it is critical to get the third man to the twenty point immediately so that he can play 5's and 6's. The computer, unable to look ahead, failed to find the correct play.
One of the greatest strengths of backgammon-playing computers is that they can analyze end-game positions extremely well. Calculations that would take humans weeks can be accomplished in a matter of seconds, and end-game plays, equities, and cube decisions can be computed exactly. Computers can also be handy for simulating simple positions like bearoffs—if you want to know what your chances are in a given position, you can have the computer "roll it out" 10,000 times in the blink of an eye.
In conclusion, the top backgammon players of the world need not be concerned with being replaced by a computer yet. However, as computers and their programs become more sophisticiated and as man learns more about how his own mind works, it is not impossible that computers may well "conquer" backgammon as they have done in so many other games.
| More articles by Kit Woolsey |
|
| More articles by Kent Goulding |
|
| More articles on programming backgammon |
|
Return to: Backgammon Galore |
|
