Headline Feeds
Back in 1994, a computer called "Chinook" became the World Checkers Champion. By 1996, the checkers world came to accept that the computer was better than any other player. However, it wasn't until more than decade later that the Chinook achieved perfection.
Chinook is now certifiably infallible and can never lose a game, according to researchers who say they've done the math necessary to prove it. If pitted against another perfect player -- presumably a Chinook clone -- every single match would end in a draw.
"Draws are common in checkers, particularly with master players, who make fewer bad moves," Richard Beckwith, the American Checker Federation's player representative, told TechNewsWorld. "I would guess 60 to 70 percent of games end in draws -- for masters."
Years of Research
It took a team of Canadian researchers led by Jonathan Schaeffer, a professor at the University of Alberta, and dozens of computers working around the clock 18 years to conclude that Chinook was unbeatable. They figured out every possible move in what appears on the surface to be a fairly simple game.
"Checkers is not a simple game," Schaeffer told TechNewsWorld. "The rules of the game are simple, and many people misconstrue that the simple rules imply that it's a simple game. It's got five hundred billion billion possible positions. That's a five followed by twenty zeros -- so it's a huge number."
In fact, there are so many possible options during the course of a single game, and so many possible positions on a board, that it's simply mind-boggling.
"Pretend the surface of the earth is a game of checkers," Schaeffer explained. "Take one square inch and break it into a thousand pieces. One of those one-thousandths-of-an-inch-sized pieces represents one checkers position."
A person's foot, then, Schaeffer noted, could cover twenty thousand possible checkers positions on the board. To cover them all, a human would have to step on every square inch of the earth's surface.
Win, Lose or Draw?
Tic-tac-toe is also a game that will end in a draw when played perfectly by both players. Unlike checkers, though, it only has 765 possible board positions. So, for most adults and savvy kids, tic-tac-toe commonly ends in a tie.
A similar game, Connect Four, also often ends in a tie, but that's not due to the inherent nature of the game. If played perfectly, it is a first-player-wins kind of game.
"If you know what you're doing," Schaeffer said, "if you play first, you will always win. In checkers, if you play first against a perfect opponent, you will only draw. ... Chess has never been proven to be a draw, but all the evidence suggests that it is," he added.
The Proof
The Chinook team published the results of their research on the Web site of the journal Science Thursday, but there's also proof available on the Chinook Web site posted by the University of Alberta. Visitors can walk through step-by-step game play to see which moves leave the board in a position of win, loss or draw. If that's not proof enough, visitors can also play Chinook for themselves, but the creators of the machine assure them they'll never actually win.
"I applaud Mr. Schaeffer's artificial intelligence achievement, as he has been hard at work for many years on this project; however, the fact that the game is a draw -- if both players play optimally -- was known long ago as a result of much human analysis," Beckwith noted.
"I don't expect any impact on face-to-face competition, as no human can possibly memorize the billions of combinations that Mr. Schaeffer has covered. Checkers still remains a highly strategic game when played head-to-head," he said.
Talkback: 
