|Norvig I 192
Chess/artificial intelligence/Norvig/Russell: Chess was one of the first tasks undertaken in AI, with early efforts by many of the pioneers of computing, including Konrad Zuse in 1945, Norbert Wiener in his book Cybernetics (1948), and Alan Turing in 1950 (see Turing et al., 1953)(2). But it was Claude Shannon’s article Programming a Computer for Playing Chess (1950)(3) that had the most complete set of ideas, describing a representation for board positions, an evaluation function, quiescence search, and some ideas for selective (nonexhaustive) game-tree search. Slater (1950)(4) and the commentators on his article also explored the possibilities for computer chess play. D. G. Prinz (1952)(5) completed a program that solved chess endgame problems but did not play a full game.
Stan Ulam and a group at the Los Alamos National Lab produced a program that played chess on a 6×6 board with no bishops (Kister et al., 1957)(6). It could search 4 plies deep in about 12 minutes. Alex Bernstein wrote the first documented program to play a full game of standard chess (Bernstein and Roberts, 1958)(7). The first computer chess match featured the Kotok–McCarthy program from MIT (Kotok, 1962)(8) and the ITEP program written in the mid-1960s at Moscow’s Institute of Theoretical and Experimental Physics (Adelson-Velsky et al., 1970)(9).
The first chess program to compete successfully with humans was MIT’s MACHACK-6 (Greenblatt et al., 1967)(10). The $10,000 prize for the first program to achieve a USCF (United States Chess Federation) rating of 2500 (near the grandmaster level) was awarded to DEEP THOUGHT (Hsu et al., 1990) (11) in 1989. The grand prize, $100,000, went to DEEP BLUE (Campbell et al., 2002(12); Hsu, 2004(13)) for its landmark victory over world champion Garry Kasparov in a 1997 exhibition match.
Norvig I 193
HYDRA (Donninger and Lorenz, 2004(14)) is rated somewhere between 2850 and 3000, based mostly on its trouncing of Michael Adams. The RYBKA program is rated between 2900 and 3100, but this is based on a small number of games and is not considered reliable. Ross (2004)(15) shows how human players have learned to exploit some of the weaknesses of the computer programs.
1. Wiener, N. (1948). Cybernetics. Wiley.
2. Turing, A., Strachey, C., Bates,M. A., and Bowden, B. V. (1953). Digital computers applied to games. In Bowden, B. V. (Ed.), Faster than Thought, pp. 286 - 310. Pitman.
3. Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(4),
4. Slater, E. (1950). Statistics for the chess computer and the factor of mobility. In Symposium on Information Theory, pp. 150-152. Ministry of Supply
5. Prinz, D. G. (1952). Robot chess. Research, 5, 261- 266.
6. Kister, J., Stein, P., Ulam, S., Walden, W., and Wells, M. (1957). Experiments in chess. JACM, 4,
7. Bernstein, A. and Roberts, M. (1958). Computer vs. chess player. Scientific American, 198(6), 96-
8. Kotok, A. (1962). A chess playing program for the IBM 7090. AI project memo 41, MIT Computation
9. Adelson-Velsky, G. M., Arlazarov, V. L., Bitman, A. R., Zhivotovsky, A. A., and Uskov, A. V. (1970).
Programming a computer to play chess. Russian Mathematical Surveys, 25, 221-262.
10. Greenblatt, R. D., Eastlake, D. E., and Crocker, S. D. (1967). The Greenblatt chess program. In Proc.
Fall Joint Computer Conference, pp. 801-810.
11. Hsu, F.-H., Anantharaman, T. S., Campbell, M. S., and Nowatzyk, A. (1990). A grandmaster chess machine. Scientific American, 263(4), 44–50.
12. Campbell, M. S., Hoane, A. J., and Hsu, F.-H. (2002). Deep Blue. AIJ, 134(1–2), 57–83.
13. Hsu, F.-H. (2004). Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. Princeton University Press.
14. Donninger, C. and Lorenz, U. (2004). The chess monster hydra. In Proc. 14th International Conference on Field-Programmable Logic and applications, pp. 927-932.
15. Ross, P. E. (2004). Psyching out computer chess players. IEEE Spectrum, 41(2), 14-15._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010