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. -John McCarthy, from AI as Sport.

From AI in the news: May 25, 2005: Only a pawn in its game. By Finlo Rohrer. BBC News. "Hydra is the latest chess supercomputer to lay down the gauntlet to the world's top players. Its architects say it is the greatest ever built, but don't expect it to rejoice in victory or get the post-match drinks in. It is a behemoth of a machine that pits 32 linked processors against its flesh-and-blood opponents. Hydra's backers claim it can analyse 200 million chess moves in a second and project the game up to 40 moves ahead. ... It will take on England's Michael Adams, the British No 1 and world No 7, in a six-match contest at Wembley from 21 June for a £80,000 purse. ... The machine has played eight games against grandmasters so far, winning six and drawing two."

• See our GENERAL INDEX TO AI in the news: GAMES & PUZZLES for more information about the match.

Good Places to Start

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."

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 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."

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.

Deep Blue's accomplishment as seen by two professors at Yale's Department of Computer Science:

• How Hard is Chess? By David Gelernter. ("[A]ppeared in Time, May 19, 1997.) "Deep Blue is just a machine. It doesn't have a mind any more than a flowerpot has a mind. Deep Blue is a beautiful and amazing technological achievement. It is an intellectual milestone, and its chief meaning is this: that human beings are champion machine builders."
• How Intelligent is Deep Blue? By Drew McDermott. ( "This is the original, long version of an article that appeared in the May 14, 1997 New York Times with more flamboyant title") "I agree that Deep Blue is not actually intelligent, but I think the usual argument for this conclusion is quite faulty, and shows a basic misunderstanding of the goals and methods of artificial intelligence. ... So, what shall we say about Deep Blue? How about: It's a 'little bit' intelligent. ... Saying Deep Blue doesn't really think about chess is like saying an airplane doesn't really fly because it doesn't flap its wings."

Readings Online

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 Is Too Easy. By Selmer Bringsjord. Technology Review. March/April 1998. "The victory last spring by IBM's Deep Blue computer over the world's greatest human chess player, Gary Kasparov, obliterated Dreyfus's prediction. But does it also argue for Strong rather than Weak AI ?"

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."

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."

Modern Masters of an Ancient Game. By Carol McKenna Hamilton and Sara Hedberg. 1997. AI Magazine 18 (4): 11-12. Describes awarding of the $100,000 Fredkin Prize to the team responsible for Deep Blue, the computer which beat world chess champion Gary Kasparov in the final game of a six-game match on May 11, 1997.

The Origins of Artificial Intelligence. Part of Andrew Hodges' Alan Turing Internet Scrapbook. "Alan Turing was based at Bletchley Park, Buckinghamshire, while acting as the leading cryptanalyst of German ciphers during the Second World War. It was during this period that he formulated the ideas that emerged after the war as Intelligent Machinery, and would now be called Artificial Intelligence. He must have been influenced by the astonishing power of mechanical methods at Bletchley Park. The codebreaking work at Bletchley Park was highly secret and discussed only with those directly involved; but Turing used games, particularly chess-playing, as a close analogy. ... After 1945 Turing often used chess-playing as an example of what a computer could do, and in his 1946 report on the possibilities of a computer, made his first reference to machine 'intelligence' in connection with chess-playing. In 1948 he met Donald Michie again and competed with him in writing a simple chess-playing algorithm."

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."

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).

All the Needles in a Haystack: Can Exhaustive Search Overcome Combinational Chaos? J. Nievergelt, R. Gasser, F. Maser, C. Wirth. "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.

The Game of Chess. By Herbert A. Simon and Jonathan Schaeffer. Handbook of Game Theory with Economic Applications, vol. 1, Robert J. Aumann and Sergiu Hart (editors), Elsevier Science Publishers, Netherlands, pp. 1-17, 1992. (Also available as CMU technical report AIP-105.) Available in several formats from CiteSeer.

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."

• Also available online, Chapter One, The Queen's Gambit Accepted, of his book, The Turk: The Life and Times of the Famous Eighteenth-Century Chess-Playing Machine.

Related Web Sites

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 and its collection of "Ask the Expert" questions (and answers) about computer chess.

Mastering the Game: A History of Computer Chess. An 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 Pages

• Bridge
• Checkers
• Crossword Puzzles
• Games & Puzzles Overview
• Games & Puzzles: General Index to AI in the news
• Go
• History
• More Games & Puzzles
  • including, Shogi (Japanese chess)
• Othello
• Poker
• Scrabble
• Sports
• Traveling Salesperson & NP-Complete Problems
• Video Games

More Readings

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.

Standage, Tom. The Turk: The Life and Times of the Famous Eighteenth-Century Chess-Playing Machine. Walker & Company, New York, 2002. "Part historical detective story, part biography, The Turk relates the saga of the machine's remarkable and checkered career against the backdrop of the industrial revolution, as mechanical technology opened up dramatic new possibilities and the relationship between people and machines was being redefined. Today, in the midst of the computer age, it has assumed a new significance, as scientists and philosophers continue to debate the possibility of machine intelligence. To modern eyes, the Turk now seems to have been a surprisingly farsighted invention, and its saga is a colorful and important part of the history of technology." From the "About the Book" page in the book's web site where you'll also find an interview with the author, Chater One of the book, and much more.

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