---

Chess

---

AITopics > Games & Puzzles > Chess

Tweet  

Chess is the Drosophila of artificial intelligence. - Alexander Kronrod, Russian mathematician In 1965, the Russian mathematician Alexander Kronrod said, "Chess is the Drosophila of artificial intelligence." However, computer chess has developed much as genetics might have if the geneticists had concentrated their efforts starting in 1910 on breeding racing Drosophila. We would have some science, but mainly we would have very fast fruit flies. - from AI as Sport, by John McCarthy

Introductory Readings

Mastering the Game: A History of Computer Chess. An online exhibit from the Computer History Museum. "The history of computer chess is a five-decade long quest to solve a difficult intellectual problem. The story starts in the earliest days of computing and reflects the general advances in hardware and software over this period. This on-line exhibition contains documents, images, artifacts, oral histories, moving images and software related to computer chess from 1945 to 1997." Be sure to visit the interactive exhibit: Chess Software Basics.

• Also see this related video (approx. 2 hours): The History of Computer Chess: An AI Perspective. Produced by the Computer History Museum and available from Google Video (September 8, 2005). "This panel [Murray Campbell, Edward Feigenbaum, David Levy, John McCarthy, and Monty Newborn], comprising seminal contributors to the solution of this challenge -- including two of AI’s leading pioneers -- will discuss these and other questions as well as the origin and development of computer chess and what it tells us about ourselves and the machines we build."

The Immortal Game. Tech Nation podcast (October 3, 2006) available from IT Conversations. "Dr. Moira Gunn [host of Public Radio's Tech Nation] speaks with David Shenk, author of 'Data Smog' and 'The Immortal Game - A History of Chess,' about how chess influenced the first computer scientists, and how Garry Kasparov dealt with being beaten by a computer."

Kasparov sought for chess degree. BBC (June 5, 2001). "Scotland's Aberdeen University is preparing to launch the world's first doctoral programme in chess this year - and is hoping former world champion Garry Kasparov will agree to lecture. Professor Peter Vas says the aim is to produce chess grandmasters, and to develop intelligent computers that can learn from their own experience."

Chess Master Mastered: Kasparov v. Deep Blue. From The Why Files (May 29, 1997). This report covers topics such as: Deep Blue's guts, spilled; Is this computer smart?; and, Making sense of Blue's bash.

Deep Blue Wins. Hosted by IBM. This site is a treasure chest of information and includes commentaries, guest essays, even video clips of the famous rematch won by Deep Blue on May 11th, 1997.

Making Computer Chess Scientific. By John McCarthy. "I complained in my Science review see below] of Monty Newborn's Deep Blue vs. Kasparov that the tournament oriented work on computer chess was not contributing as much to the science of AI as it should. AI has two tools for tackling problems. One is to use methods observed in humans, often observed only by introspection, and the other is to invent methods using ideas of computer science without worrying about whether humans do it this way. Chess programming employs both. Introspection is an unreliable way of determining how humans think, but introspectively suggested methods are valid as AI if they work.Much of the mental computation done by chess players is invisible to the player and to outside observers. Patterns in the position suggest what lines of play to look at, and the pattern recognition processes in the human mind seem to be invisible to that mind. However, the parts of the move tree that are examined are consciously accessible.It is an important advantage of chess as a Drosophila for AI that so much of the thought that goes into human chess play is visible to the player and even to spectators."

• Also see these related items from John McCarthy:

• AI as Sport: John McCarthy's review of Monthy Newborn's Kasparov versus Deep Blue. Computer Chess Comes of Age. [Author's note: This review appeared in Science on 1997 June 6. The version here may be improved from time to time.] "Monty Newborn, who has been an active organizer of computer chess tournaments and helped arrange the Kasparov-Deep Blue matches, here recounts the 50 years of computer chess that led to the preceding, 1996, match, won by Kasparov.Ideas about chess algorithms as well as advances in computer hardware were involved. However, it is a measure of our limited understanding of the principles of artificial intelligence (AI) that this level of play requires many millions of times as much computing as a human chess player does. Moreover, the fixation of most computer chess work on success in tournament play has come at scientific cost.In 1965 the Russian mathematician Alexander Kronrod said, 'Chess is the Drosophila of artificial intelligence.' However, computer chess has developed much as genetics might have if the geneticists had concentrated their efforts starting in 1910 on breeding racing Drosophila. We would have some science, but mainly we would have very fast fruit flies."
• Basic Questions in John McCarthy's What is Artificial Intelligence? (November 2004): "Alexander Kronrod, a Russian AI researcher, said 'Chess is the Drosophila of AI.' He was making an analogy with geneticists' use of that fruit fly to study inheritance. Playing chess requires certain intellectual mechanisms and not others. Chess programs now play at grandmaster level, but they do it with limited intellectual mechanisms compared to those used by a human chess player, substituting large amounts of computation for understanding. Once we understand these mechanisms better, we can build human-level chess programs that do far less computation than do present programs. Unfortunately, the competitive and commercial aspects of making computers play chess have taken precedence over using chess as a scientific domain. It is as if the geneticists after 1910 had organized fruit fly races and concentrated their efforts on breeding fruit flies that could win these races."

Rise of the Machines - Chess computers are beating grand masters with ever-greater ease, and even more demoralizing, they're beginning to do it with style. By Philip E. Ross. IEEE Spectrum Web Only News (August 8, 2005). "It seems the scales are finally tipping in the decades-long struggle of human grand masters and chess machines. The humans are looking increasingly like the palookas that impresarios used to pit against champion boxers, just to attract spectators."

Chess Programming. By Francois-Dominic Laramee for Gamedev.net. "This is the first article in a six-part series about programming computers to play chess, and by extension other similar strategy games of perfect information. Chess has been described as the Drosophila Melanogaster of artificial intelligence, in the sense that the game has spawned a great deal of successful research (including a match victory against the current world champion and arguably the best player of all time, Gary Kasparov), much like many of the discoveries in genetics over the years have been made by scientists studying the tiny fruit fly. This article series will describe some of the state-of-the-art techniques employed by the most successful programs in the world, including Deep Blue." All six articles are available online and the tpics covered include: Games of Perfect Information, Board Representations, Search Techniques, Transposition, Forward Pruning, Minimax, Evaluation Functions, and much more.

General Readings

A Decade After Kasparov's Defeat, Deep Blue Coder Relives Victory. By Robert Andrews. Wired (May 11, 2007). "The first, Deep Thought, emerged in 1988 from the drawing board of Carnegie Mellon grad student Feng-hsiung Hsu, who was hired by the computer maker a year later with the express intention of usurping the primacy of human logic. Upon joining IBM, Hsu recruited several programmers, including his computer science classmate, Canadian Murray Campbell, with whom he had prototyped an early chess-playing computer named Chiptest several years earlier. ... It was the third incarnation, dubbed Deep Blue, that finally knocked the master from his perch 15 months later. The match immediately became an iconic symbol of the advances made in artificial intelligence and supercomputing. ... Wired News: Why do you think the match captured the public imagination to such a great degree? Campbell: Not everybody plays but everybody knows that chess is a very difficult game -- you can devote your whole life to playing chess and still have room for improvement. So it's understood that chess is a game which requires intelligence and so for a machine to play at the level of the world champion is a sign that computers have progressed further than maybe some people had thought they had. In one sense, it's just one milestone among many along the way, but it's one that the general public could understand more easily. ... WN: What are Deep Blue’s roots, and on what technological principles did its forebears operate? Campbell: Claude Shannon, the famous computer scientist and mathematician proposed that chess was a grand challenge for these new things called computers -- if you could get a computer to play chess at the world champion level, you had done something really special. There was a turning point in the '70s when it was realized that, if you let computers do what they do best -- that is, search through as many possibilities as they can as quickly as they can -- and stop the pretense of trying to emulate how humans play, you actually got better performance. And so, from that day on, computers, including Deep Blue, tended to be focused on searching through as many possible chess moves as they could in the amount of time that was available for a computation."

• Also see: This Day in Tech - May 11, 1997: Machine Bests Man in Tournament-Level Chess Match. By Tony Long. Wired (May 11, 2007).

How Chess Computers Work. By Marshall Brain for HowStuffWorks. "If you were to fully develop the entire tree for all possible chess moves, the total number of board positions is about 1, 000, 000, 000, 000, 000,000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, or 10¹²⁰, give or take a few. That's a very big number. For example, there have only been 10²⁶ nanoseconds since the Big Bang. There are thought to be only 10⁷⁵ atoms in the entire universe. When you consider that the Milky Way galaxy contains billions of suns, and there are billions of galaxies, you can see that that's a whole lot of atoms. That number is dwarfed by the number of possible chess moves. Chess is a pretty intricate game! No computer is ever going to calculate the entire tree. What a chess computer tries to do is generate the board-position tree five or 10 or 20 moves into the future."

Chess. By Douglas Bryson. Scotland on Sunday (January 26, 2003). "Garry Kasparov challenges the Deep Junior computer program in a $ 1m match today in New York. ... Former Scottish champion David Levy is the president of the International Computer Games Association ( ICGA) under whose auspices the match takes place. Levy famously won bets placed in the 1960s that he would not be beaten by a computer. The www.icga.org website reveals the background story to the Levy wagers. Professor Donald Michie, founder of the Department of Machine Intelligence and Perception at Edinburgh University, invited Levy to the 1968 Artificial Intelligence ( AI) workshop in the capital. Levy had won the Scottish championship title earlier that year and was playing a friendly game against John McCarthy, a Stanford professor and a leading expert on AI. McCarthy lost to Levy, but remarked: 'Within 10 years there will be a program that can beat you.'"

Deep Blue. By Murray Campbell, A. Joseph Hoane Jr, and Feng-hsiung Hsu. In Artificial Intelligence, January 2002 (Volume: 134, Issue: 1-2). Abstract excerpt: "This paper describes the Deep Blue system, and gives some of the rationale that went into the design decisions behind Deep Blue."

Comparing Baduk and Chess. By Nam Chi-hyung. The Korea Times July 7, 2005). "For more than 2,500 years, Baduk has meant so much more than just a game to many people; it is regarded as an art, science and even a pedagogy in Korea, China and Japan, and has spread to the western world. Now, it offers not only entertainment and the thrill of competition, but it also provides a useful tool for studying human mental faculties and artificial intelligence. Baduk is often compared with Chess, which is also a popular ancient game. ... [I]n Baduk, the ultimate goal of securing the world as one’s own is achieved through competition, rather than by the destruction of the opponent."

Computers, Games and the Real World. By Matthew L. Ginsberg. Scientific American (special issue: Exploring Intelligence - Winter 1998). "More than just competing with people, game-playing machines complement human thinking by offering alternative methods to solving problems."

The Deep Blue Team Plots Its Next Move. John Horgan of Scientific American interviews the Deep Blue team three weeks after the 1996 match. (Scientific American - Explore; March 8, 1996.)

Chess, China, and Education - An interview with Feng-Hsiung Hsu. Ubiquity (July 27 - Auguest 2, 2005; Volume 6, Issue 27). "Feng-Hsiung Hsu, whose book 'Behind Deep Blue' told the story of world chess champion Garry Kasparov was defeated by the IBM computer known as Deep Blue, is now a senior manager and researcher at Microsoft Research Asia. ... UBIQUITY: When did you get interested in chess, and then computer chess? HSU: I think I started playing chess when I was in primary school. I thought of it as just another game, and liked it the way kids always like to play games. But then when I was in college one day I bumped into a book in the library that was a classic for computer chess, called 'Computer Skills in Men and Machines.' ... UBIQUITY: Your Deep Blue chess strategy was a brute force strategy, is that right? HSU: That was my initial starting point, after reading a paper by Ken Thompson that experimentally verified how you can increase program playing strength by improving computation speed. So we decided to push speed, which we knew how to do and was interesting by itself from a computer science point of view. Of course, when you compete against the world champion you realize you need more than just brute force, obviously. ... UBIQUITY: So where is the state of art of computer chess now? ... "

Conventional Wisdom Says Machines Cannot Think. By George Johnson. The New York Times (May 9, 1997). "Whether the machine or the man ultimately wins the rematch between Deep Blue and Garry Kasparov, it is probably just a matter of time before a computer prevails. What is far less certain is just what to make of such a victory."

By Ray Kurzweil. KurzweilAI.net (October 19, 2002). "The Deep Fritz computer chess software only achieved a draw in its recent chess tournament with Vladimir Kramnik because it has available only about 1.3% as much brute force computation as the earlier Deep Blue's specialized hardware. Despite that, it plays chess at about the same level because of its superior pattern recognition-based pruning algorithm. In six years, a program like Deep Fritz will again achieve Deep Blue's ability to analyze 200 million board positions per second. Deep Fritz-like chess programs running on ordinary personal computers will routinely defeat all humans later in this decade."

Junior high-tech. By Aviv Lavie. Ha`aretz (September 28, 2002). "The balance has shifted from supercomputers like Deep Blue to home computers. 'People used to think that the computer's quality as a player was directly related to its power of calculation,' says [Amir] Ban, 'and they kept trying to give it more and more calculating power. Now we know that beyond a certain limit, what really counts is artificial intelligence - in other words, the quality of the moves and the computer's ability to analyze complex situations.' ... Over the years, the way that artificial intelligence is manifested in chess has been the topic of numerous scholarly articles. In 1958, the first program that could play according to all the rules of chess appeared."

Do not pass Go. Computers can beat the world's best chess players but have yet to master other classic games like Go. By David Levy. The Guardian (October 24, 2002). "Ever since Garry Kasparov's sensational 1997 loss to the IBM chess monster Deep Blue, the chess world has thirsted for revenge. But the first opportunity ended in failure in Bahrain on Saturday, when Kasparov's former pupil and successor as World Champion, Vladimir Kramnik, could only draw an 8-game match against one of the world's leading chess engines, Fritz. But this was just the latest in a long series of human versus computer encounters that illustrate the inexorable march of artificial intelligence (AI). It's a story that began at a Dartmouth University conference in 1956, when several of the founding fathers of AI defined the goals of that infant science. One of them was to create a computer program that could defeat the world chess champion. Success would, those scientists believed, reach to the very core of human intellectual endeavour. By the early 1990s, due in no small part to the successes achieved in computer chess, the interest of the AI community had spread to many other games of skill, including backgammon, bridge, Go and Scrabble. Where exactly are we now in this fascinating struggle? ... Two games proving even tougher to crack than chess are bridge and Go."

If a Machine Creates Something Beautiful, Is It an Artist? By Dylan Loeb McClain. The New York Times (January 25, 2003;no fee reg. req'd). "But if computers become better than humans at chess, does that mean that computers are being artistic or that chess is essentially a complicated puzzle? The question arises partly because of the very different ways that humans and computers play chess. ... Murray Campbell, a developer of Deep Blue who still works at I.B.M., said that Deep Blue's designers had adopted a scientific and an engineering approach when building the computer, but that the results could be viewed as artistic, regardless of what produced them. 'The question reminds me of the question that often gets asked in artificial intelligence,' he said. 'Is the system intelligent? It is because it produces intelligent behavior. If it does something artistic, then it is artistic. It does not matter how it did it.'"

Computer Chess and Search. By T.A. Marsland, Computing Science Department, University of Alberta. (Article prepared for the 2nd edition of the Encyclopedia of Artificial Intelligence, S. Shapiro (editor), to be published by John Wiley, 1992.) Sections include: Landmarks in Chess Program Development; Minimax Search; The Alpha-Beta Algorithm; Minimal Game Tree; Forward Pruning; and more.

Slaughter on Seventh Avenue. "The world's number one is still licking his wounds after IBM's chess computer beat him last month. But is Kasparov right to feel so hurt by the defeat? Donald Michie thinks not." By Donald Michie. New Scientist Magazine (June 7, 1997).

J. Nievergelt, R. Gasser, F. Maser, C. Wirth. (Available in several formats from CiteSeer.) "The peculiar difficulty of King (K) and Pawn (P) endgames comes from the fact that Pawns can be promoted to any other piece: Queen (Q), Rook (R), Bishop (B), Knight (N). Thus an exhaustive analysis of KP endgames with a total of p Ps potentially calls upon all endgames with 2 Ks and p pieces of the right color. But the vast majority of KP endgames are decided soon after (or even before) a P promotion, because the material balance typically changes drastically - one party has a Q, the other does not. Thus, storing all the support databases of other piece endgames is an extremely expensive overhead when compared to their rare use. We are experimenting with simple and often safe heuristics of the type: In a KP endgame, if Black promotes a P to a Q, and within x plies can prevent White from promoting one of its Ps, Black wins. This particular heuristic has well-known exceptions, such as when a White P on the seventh rank ensures a draw. Thus it is supplemented by other heuristics that, jointly, capture elementary chess lore about KP endgames."

Playing Your Cards Right - Poker comes out of the back room and into the computer science lab. By Ivars Peterson. Science News (July 18, 1998). "Poker is an example of a game of incomplete information in which chance plays a role. Whereas a chess player sees the disposition of all the pieces all the time, a poker player sees only some of the cards -- drawn or dealt from a shuffled deck -- that are in play."

The Meaning of Computers and Chess - What Deep Junior, Deep Blue, and Garry Kasparov teach us about intelligence, human and artificial. By Philip Ross. IEEE Spectrum Web Only News (March 1, 2003). "The original chess-playing algorithm, proposed more than 50 years ago by Claude Shannon, the electrical engineer who founded information theory, begins with the search function, which generates all possible move sequences to a certain depth, set by the computer's speed and memory. ... Deep Junior seems to have played about as well as Deep Blue, although its hardware was perhaps only 1 or 2 percent as powerful. ... [I]t is improved chess-playing software that mainly explains Deep Junior’s success, in part because programmers, working with grandmaster advisers, have learned how to encode many aspects of chess knowledge that had previously been unmanageable. Deep Junior’s handlers could not hope to match Deep Blue’s search capabilities, so they concentrated on tweaking Deep Junior's evaluation function."

Chess, Deep Blue, Kasparov and Intelligence. "The second chess match between IBM's Deep Blue and Kasparov in the Spring of 1997 resulted in victory for Deep Blue. This in turn led to discussion and opinion in the press concerning the significance of this and the relation between Human and Machine or Computational Intelligence. [Here] are some articles taken from the Archives of the New York Times." Part of Prof. Charles Schmidt's Cognition and Computation course materials.

Monster in a Box - The inside story of an ingenious chess-playing machine that thrilled crowds, terrified opponents, and won like clockwork. By Tom Standage. Wired (March 2002/10.03). "After two games against the Turk, Charles Babbage began to sketch out plans for his own thinking machine. This was the genesis of the first mechanical computer. ... Indeed, Kempelen's contraption has taken on a new significance since the invention of the digital computer. Artificial intelligence researchers started writing chess-playing programs in the 1940s, showing just how prescient Kempelen had been in suggesting that the game was a good first step for machine intelligence. And with its setup of a man pretending to be a machine, the Turk anticipated the standard test proposed by British scientist Alan Turing in 1950: A device can be deemed intelligent if it can pass for a human in a written question-and-answer session."

Related Resources

ChessBase. Chess programs, chess news, and the home of both Deep Fritz & Deep Junior.

Chess Links. Maintained by the University of Pittsburgh Chess Club. A comprehensive list of links, including to web servers for online play.

International Computer Chess Association. "The ICCA was founded by computer chess programmers in 1977 to organise championship events for computer programs and facilitate sharing of technical knowledge via the ICGA Journal (formerly the ICCA Journal). The ICCA also seeks to represent the Computer Chess World via contacts with Computer Science Organizations, Commercial Organisations, and the International Chess Federation (FIDE). In recent years, the ICCA Journal has widened its scope to include papers on other games, and the organisation proposes to change its name to ICGA at the next triennial meeting in 2002."

Kasparov Chess. Among the many resources you'll find here is KC Magazine.

Mastering the Game: A History of Computer Chess. An exciting online exhibit from the Computer History Museum.

"Thinking Machine 4 explores the invisible, elusive nature of thought. Play chess against a transparent intelligence, its evolving thought process visible on the board before you. The artwork is an artificial intelligence program, ready to play chess with the viewer. If the viewer confronts the program, the computer's thought process is sketched on screen as it plays." Created by Martin Wattenberg, with Marek Walczak, and as explained on the About page, it "uses only basic algorithms from the 50s (alpha-beta pruning and quiescence search)."

The Turk. A chess program from The University of Alberta GAMES Group.

Related AITopics Pages

• Bridge
• Checkers
• Crossword Puzzles
• Go
• History
• More Games & Puzzles
  • including Shogi (Japanese chess) and Xiangqi (Chinese Chess)
• Othello
• Poker
• Scrabble
• Sports
• Traveling Salesperson & NP-Complete Problems
• Video Games

Other References Offline

The ICCA/ICGA Journal. From the International Computer Chess Association.

Atkinson, George W. 1993. Chess and Machine Intuition. Ablex Series in Artificial Intelligence. Norwood, NJ: Ablex. A readable look at the development and people involved in computer chess programming.

Campbell, Murray and Andreas Nowatzyk , Feng-hsiung Hsu, Thomas Anantharaman. A Grandmaster Chess Machine. Reprint of an article that was originally published in the October 1990 issue of Scientific American. "In the 40 years since this magazine published the original prospectus for a chess computer, machines have vanquished first novices,then masters and now grandmasters. Will Gary Kasparov be next?" (Scientific American - Saidebar, April 21, 1997.)

Chase, W. G., and H. A. Simon. 1973. The Mind's Eye in Chess. In Visual Information Processing, ed. Chase, W. G., New York: Academic Press.

Coles, Stephen L. 1994. Computer Chess: The Drosophila of AI. AI Expert Magazine / available from Dr. Dobb's Journal.

Frey, Peter W., editor. 1984. Chess Skill in Man and Machine. New York: Springer-Verlag. Although not current, this book provides an excellent look at the development of computer chess, and includes chapters on how humans play, and the early US vs. USSR tournaments.

Levy, Stephen. 1997. Man vs. Machine. Newsweek 129: 50-56.

Levy, David N. L., editor. 1988. Computer Games I. New York: Springer-Verlag. Chapter 2 offers several important early papers on programming computers to play chess.

Levy, David., editor. 1988a. Computer Chess Compendium. New York: Springer-Verlag. A collection of important papers on developments in computer chess playing programs.

Newell, A., J. C. Shaw, and H. A. Simon. 1958. Chess-Playing Programs and the Problem of Complexity. In Computers and Thought, ed. Feigenbaum, Edward and Julian Feldman, New York: McGraw Hill, 1995. Other important articles by Newell, Shaw and Simon have been reprinted in Computers and Thought, including: Empirical Explorations of the Logic Theory Machine, 1957; and GPS, A Program That Simulates Human Thought, 1961.

Newborn, Monty. 1996. Kasparov versus Deep Blue. Computer Chess Comes of Age. Springer-Verlag, New York, 1996.

• Reviewed by John McCarthy in AI as Sport in Science, June 6, 1997.

Newborn, Monroe. 1975. Computer Chess. New York: Academic Press. An excellent source for the history of AI chess, beginning with Baron von Kempelen's infamous Turk (1769) and continuing with descriptions of early contributions to the field by Shannon, Turing, Bernstein, Newell, Shaw, Simon, McCarthy, Greenblatt and others.

Powell, Corey S. Kasparov vs. Deep Blue - IBM's silicon powerhouse plays a rematch with the world's chess champ. Scientific American (Sidebar; April 21, 1997).

Schaeffer, Jonathan and Aske Plaat. 1997. Kasparov versus Deep Blue: The Re-match. ICCA Journal, vol. 20, no. 2, pp. 95-102.

Shannon, Claude E. 1950. Programming a Computer for Playing Chess. Philosophical Magazine, (Series 7), vol. 41, pp. 256-275. A classic paper.

Waldrop, Mitchell M. 1997. How the Chess Was Won. Technology Review 100: 33-36.