I'm a big fan of the TV show "Jeopardy!", so I eagerly tuned in when IBM's computer, Watson, went up against long-time champions Ken Jennings and Brad Rutter in February 2011. The outcome -- Watson as the runaway champion -- wasn't surprising, but it was fun to watch. IBM got to showcase how far artificial intelligence has come, but it took more than a few decades to get there. The roots of Watson's triumph lie in a much humbler machine playing an ancient game: chess.
The first references to chess date back to about 600 AD in what is now northern India, and trade routes spread the game across the world. By the 1800s, there were official chess organizations and championships. But before that, there was the very first chess-playing machine -- sort of. An inventor named Wolfgang von Kempelen created The Turk for the Empress of Austria-Hungary, and the machine toured around Europe for years. But The Turk was a fake; there was a person hidden inside.
Still, it showed that we were interested in the idea of being beaten at our own game by a machine. It might seem silly at first to put time and energy into having a computer play chess. But the idea was that if a computer could "think" well enough to play chess, maybe it could help solve even more complex problems. Before we'd even built computers to take on the task, there was a computer program designed to play the game. Alan Turing, considered the father of artificial intelligence and computer science, wrote a program and played chess with himself on paper in 1947. By the late 1950s, an IBM programmer who just happened to also be a chess player had created a computer program that could play a full game of chess.
Being able to play chess is one thing. Being able to actually win -- and beat master chess players -- is an entirely different thing. Read on to find out how a computer finally became a chess master.
I, Chess Master
In order to program a computer to play chess, you need knowledge of chess techniques and strategies -- just knowing how the pieces move isn't enough. People play chess by strategizing and recognizing patterns of play. Computers use both algorithms (step-by-step instructions) and heuristics (trial-and-error problem solving). Specifically, a system that incorporates the minimax algorithm and the alpha-beta pruning technique.
The minimax algorithm allows the computer to search through every possible move as well as the opponent's possible responses. The "minimax" part comes from the computer's need to figure out the best and worst moves (both its own and its opponent's) after each turn. Alpha-beta pruning means that the computer creates two "trees." Tree A considers every possible chess move to a certain extent. Then it "prunes" Tree A to create tree B, which further explores the moves that look the best. As you might imagine, today's computers can do this with amazing speed -- far faster than any human ever could.
By the 1960s, computer chess programs were good enough to beat amateurs. In 1967, MIT professor and chess player Richard Greenblatt created the Mac Hack IV chess program, and the computer using it became the first to beat a person in a chess tournament. It wasn't a chess master, though. In 1968, International Chess Master David Levy bet that no computer could beat him at chess in 10 years, and that if he did win, it would be another ten after that before a computer beat him.
Levy won the bet, but in 1989, it finally happened. Deep Thought, initially created by programmers at Carnegie Mellon University, beat Levy. In 1997, Deep Blue -- predecessor to Deep Thought -- beat Gary Kasparov, a Chess Grandmaster (the highest level you can attain in the FIDE, the world chess organization) and reigning World Champion. Since then, there have been more computer victories, but as one computer science professor put it, "the science is done" [source: New York Times]. We've taken computer-vs.-human chess as far as it can go -- but there are plenty of other games to dominate.
I have to confess, I'm not much of a chess player. I haven't played in so long, in fact, that I don't know if I could even tell you how each piece is supposed to move. But I admire the skill that it takes, and I'm amazed by the ability to foresee what one's opponent is going to do. Some people may have disliked it when computers beat chess champions, or when Watson won "Jeopardy!", but I think they're forgetting who created the computers. The fact that a computer can "think" and make decisions like a person is a testament to human abilities, too.
- Computer History Museum. "Mastering the Game: A History of Computer Chess." 2012. (Sept. 7, 2012) http://www.computerhistory.org/chess/index.php
- Frederic, Friedel. "A short history of computer chess." Chess Base. (Sept. 7, 2012) http://www.chessbase.com/columns/column.asp?pid=102
- Lasar, Matthew. "Brute force or intelligence? The slow rise of computer chess." Ars Technica. Aug. 4, 2011. (Sept. 7, 2012) http://arstechnica.com/gaming/2011/08/force-versus-heuristics-the-contentious-rise-of-computer-chess/2/
- Markoff, John. "Computer Wins on 'Jeopardy!': Trivial, It's not." The New York Times. Feb. 16, 2011. (Sept. 7. 2012) http://www.nytimes.com/2011/02/17/science/17jeopardy-watson.html?_r=2&adxnnl=1&pagewanted=all&adxnnlx=1347068342-MDmSbz3O+sRgs0zMXfxAvg
- McFarland, Thomas. "Some Important Events and Names in Chess." University of Wisconsin Whitewater. Nov. 20, 2011. (Sept. 7. 2012) http://math.uww.edu/~mcfarlat/177hist.htm