Attention everyone playing checkers at a park, in grade school, or on the massive rug at Cracker Barrel: You can take your pieces and go home. After five thousand years of game play, checkers has been solved.
Researchers at the University of Alberta led by Jonathan Schaeffer have created an unbeatable checkers program called Chinook. “There isn’t a human alive today that can ever win a game anymore against the full program,” Schaeffer says—although he does leave open the possibility that a person could eke out a draw in the unlikely event that she played a perfect game. Not only is Chinook unbeatable, but it has run through every possible move and every possible board configuration, so it will never, ever be surprised.
Give up now, puny human.
Schaeffer started the project on one computer in 1989. It quickly blossomed into an enormous endeavor; at one point, more than 200 computers were involved in the research. Like SETI@home, the program that uses a massive network of computers to search the skies for extraterrestrial life, these machines worked on the problem when they weren’t otherwise occupied—at night, on weekends, and over the summer. “We’re a computer science department, so we have a lot of computers,” Schaeffer says. “Most of the computers are just lying around here.”
It took somewhat longer than expected, but Schaeffer finally figured out what turned out to be the surprisingly complicated problem. Chinook's success marks another next step forward in machines' long march toward dominance of every game of skill. The trend could perhaps be traced back to chickens playing tic-tac-toe. Given a bit of training and the first move of the game—and really, a tic-tac-toe player without hands deserves at least that—an average chicken becomes unbeatable.
Since then scientists have created programs proficient at a myriad of games including backgammon, Scrabble, and of course chess; IBM’s Deep Blue defeated a human grandmaster in 1997. Schaeffer’s research group is also advancing the frontiers on games like hearts and poker.
Teaching computers to play games, and then pitting them against humans, is more than just a diversion. Programs like Chinook make it possible to do harder computations, enabling scientists to tackle more “serious” problems like analyzing protein structures or puzzling out how genes work. Teaching computers to play games also shows researchers how to model the human mind more effectively. “I’m a researcher in artificial intelligence,” Schaeffer says.“I’m interested in making computers behave in human-like ways. I’ve always chosen to work with games because the rules of games are easy, and they’re fun.”
An unanticipated benefit of Chinook is that it helps checkers players, who have started bringing their puzzles and arguments to Schaeffer to solve. In one case, Chinook settled a dispute that was almost two centuries old.
In 1800, an article in a checkers journal presented a particular checkers situation and argued that, barring any mistakes, white would win the game. Other checkers players, who obviously had a lot of time on their hands, disagreed, sparking an intense debate: With this configuration, if both players played flawlessly, would the white player win or draw? For a century, a storm of articles tackled the question, often going hundreds of moves deep into hypothetical games to prove their points. In 1900, a paper finally convinced the community that white would in fact win. The scenario became known as the “100-year Position.” In 1997, checkers grand master Don Lafferty asked Schaeffer to confirm this assumption. In a “split second,” Schaeffer says, Chinook found that white would draw, not win. Lafferty looked at the proof and immediately groaned: The commonly accepted proof had an error on the third move that dozens of checkers experts had missed. The position has since been renamed the “197-year Position.”
Now that chess and checkers are old news, other scientists in Schaeffer’s group, including Martin Muller and Akihiro Kishimoto are turning their eyes to what many see as an ultimate test of artificial intelligence: the traditional East Asian board game go. Despite the researchers’ optimism and a handful of papers marking incremental progress, go enthusiasts like Roy Laird, chairman of the board of the American Go Association, remain skeptical that computer will ever match a human at go.
“Go is really the only game that hasn’t been more or less solved for the computer,” Laird says. “It’s too hard. I like to call go the last refuge of human intelligence.”
Triumphs of AI in the Game World
1770 Wolfgang von Kempelen creates the first chess-playing machine.
1948 Alan Turing writes the first chess-playing program using a pencil and paper. Lacking an actual computer, he can only testing by acting like the computer himself.
1952 Christopher Strachey writes the first checkers program in London.
1952 Maurice Wilkes and a team of Cambridge scientists program EDSAC to play tic-tac-toe.
1956 Arthur Samuel of IBM writes the first checkers program that could “learn”.
1962 MIT scientist Alan Kotok creates a program that can beat amateurs at chess.
1963 Arthur Samuel’s checkers program wins a single match against Robert Nealey, a checkers master from Connecticut.
1966 MIT’s MacHack VI, developed by Richard Greenblatt, becomes the first computer to play in a human-oriented chess tournament.
1970 Albert Zorist writes the first program to play go at the Universityof Wisconsin-Madison.
1977 Northwestern University’s CHESS 4.6, written by Larry Atkin and David Slate becomes the first computer to beat a Class A human player.
1978 A team of MIT students builds a computer out of Tinker Toys that plays tic-tac-toe.
1979 BKG9.8, created by Hans Berlinger of Carnegie Mellon University, beats backgammon world champion Luigi Villa (though backgammon enthusiasts insist that it just got lucky).
1984 Mike Caro, a professional poker player, writes a poker program called Orac. According to its poker buddies it won more games than it lost, but this was never documented.
1988 HiTech, created by Murray Campbell, Carl Ebeling, and Gordon Goetsch from Carnegie Mellon, wins the Pennsylvania State Chess Championship and is the first computer to be rated Grandmaster.
1989 Jonathan Schaeffer, of the University of Alberta, creates Chinook.
1992 Chinook fails to defeat checkers champ Marion Tinsley.
1994 Chinook wins world championship. It’s the first computer program to win a world championship for humans in any game.
1997 Deep Blue beats chess world champion Garry Kasparov.
1997 Logistello, programmed by Michael Buro of the University of Alberta, beats Othello world champion Takeshi Murakami.
1998 Maven, programmed by Brian Sheppard, beats the two-man team of world champion Joel Sherman and runner-up Matt Graham at Scrabble.
1999 Duke scientist Michael Littman creates Proverb, which can solve 90% of the New York Times crossword puzzle accurately (95% during the week, 85% on the weekends).
2002 John Romein and Henri Balof the Free University in Amsterdam solve awari.
2003 Milan Stojanovic of Columbia University and Darko Stefanovic of the University of New Mexico announce their creation of MAYA a DNA computer that plays tic-tac-toe
2006 MAYA becomes unbeatable at tic-tac-toe.
2007 Quackle, invented by Eyal Amir and Mark Richards at the University of Illinois, becomes the first computer to win a Scrabble tournament.
