russianlop.blogg.se

This seemed a puzzling result.Īn obvious solution to the deficiencies of the linear polynomial is to break the game up into phases.

Further, Samuel found ( Samuel 1967) that when he used nonlinear terms (where two or more features were related in the same term) his program’s performance did not improve. Samuel’s ( Samuel 1959) research first indicated this. Experience indicates that this is not sufficient for expert level performance. The best it can do is to indicate the average value that should be associated with a feature. A linear polynomial will not be sensitive to such problems. There are features that are important in the opening that are meaningless in the endgame. If one uses a linear polynomial evaluation function (one that has a constant coefficient and a single variable per term) in a large domain such as chess, one soon finds out that the function is not sensitive enough. Thus a computer backgammon program would appear to require evaluation much more than search, very much as humans play the game. Thus a look-ahead would have to acquiesce to a branching factor of about 400 for each ply of look-ahead, an exponential growth rate that could not be tolerated very long. This is because the throw of a pair of dice can produce 21 different results, and each such throw can be played about 20 different ways in the average position. The playing of excellent backgammon requires the application of considerable amounts of knowledge and intelligence.īackgammon probably cannot be played by using the chief crutch of most game-playing programs—the look-ahead tree search.

Its complexity approximates that of bridge or checkers, both of which can be played as an avocation or very seriously. The domain of backgammon comprises some 10 20 positions. Impeding the opponent involves making it as unlikely as possible for him to roll combinations that will help him in the near future. Furthering one’s own objectives can take the form of actually achieving a known good that is relatively permanent, or creating conditions for the likely achieving of such good by creating opportunities for favorable dice rolls in the near future. At a gross level of understanding, the best move is the one that does the most to further one’s own objectives and impede the opponent’s. There is skill involved in selecting the best move too. There is considerable skill involved in making, accepting, or rejecting such doubles. The player being doubled has the choice of giving up the game at the current stake, or continuing the game at doubled stakes with the proviso that only he can make the next double. Doubling is an action that a player can take that doubles the stakes under which the game is being played. The skill comes in selecting the best move associated with the actual dice throw, and in making correct decisions in connection with doubling. The chance element is introduced by the throw of dice at each player’s turn. Why should backgammon be an object of interest to science? Backgammon ( Magriel 1976) is a game of skill and chance. Two questions present themselves: (1) How was this achieved? and (2) What is the significance of the result? We try to answer these questions in this paper. This was the first time that a world champion of a recognized intellectual activity had been defeated by a man-created entity in a head-to-head test of skill. To the surprise of almost everybody, BKG 9.8 won by a score of 7–1. A winner-take-all purse of $5,000 was at stake. Luigi Villa, the newly crowned backgammon World Champion, played an exhibition match to 7 points with BKG 9.8, a computer backgammon program developed by me at Carnegie-Mellon University. On Jin Monte Carlo, an event of considerable scientific importance occurred. When in the course of cerebral affairs one species succeeds, no matter how slightly, in loosing the shackles of domination placed upon it by its parent species, scientific decorum requires that the facts pertaining to such an event be examined. We also present our SNAC method of constructing evaluation functions. This paper examines the scientific issues involved in constructing the program, an analysis of its performance, and the scientific significance of the win.

This is the first time a world champion in a recognized intellectual activity has been defeated by a man-made entity. On July 15, 1979, a backgammon computer program beat the World Backgammon Champion in a match to 7 points. 3597, monitored by the Air Force Avionics Laboratory under contract F33615-78-C-1551.Ībstract.

This research was sponsored by the Defence Advanced Research Projects Agency (DOD), ARPA Order No. Copyright © 1980 by North-Holland Publishing Company. Originally published in Artificial Intelligence, vol. Backgammon Computer Program Beats World Champion, by Hans J.