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.
