Digg
StumbleUpon
Reddit
Del.icio.us
Facebook
Help
Print
Email
RSS
The Next Jump in Artificial Intelligence
Computer program is unbeatable at checkers.
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 gameplay, checkers has been solved.
For 97 years, checkers masters
thought that white would always win
in this situation. The computer program
Chinook
proved them all wrong
in less than a second.
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.”
To transform Chinook into the perfect checkers player, Schaeffer had to analyze every possible scenario and have Chinook determine the best move in each one. That amounted to 500 billion billion different arrangements of pieces. Schaeffer—a self-acknowledged “awful” checkers player—drafted the checkers community to help teach the program what constituted a screw-up versus a brilliant counter-intuitive move. Soon, everyone who was serious about checkers knew Schaeffer and what he was trying to do with Chinook.
Schaeffer's creation was able to beat human checkers masters as early as 1994, but his goal was the perfect program, the one that would "solve" checkers. The 32-bit computers that were easily available in 1997 weren’t capable of handling Schaeffer’s calculations, so he took a four-year hiatus from the project to let Moore’s Law catch up. In 2001, he started again with 64-bit processors.
“I recall when he originally started this project, he thought it was going to be a pushover,” says Richard Beckwith, player representative for the American Checker Federation. “He didn’t think there was really a whole lot to checkers. And here we are 20 years later.”
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.”