Wednesday, November 11, 2009

#51 - The Death of Checkers

It was the decade when...

Computers beat us at our own game, again!


Checkers, the popular grid-based board game found in rec rooms and retirement communities everywhere, died in 2007 at the age of 472, give or take a few thousand years.

The cause was murder. Jonthan Schaffer, a professor of computer science at the University of Alberta, has taken responsibility for the death, even to go so far as boasting about it. "Thank God it's over," said Schaffer, showing little remorse for his deed. After writing a mathematical proof proving that a perfect game of checkers ends in a draw, Schaffer developed a computer program called Chinook which was incapable of losing to a challenger. The game was "solved."

Checkers, or "draughts" as it is called in England, began life some 5000 years ago; boards dating from this era have been discovered in the archaeological record in both Ur and Ancient Egypt. Latrunculi was a checkers variation played by Roman soldiers. Other iterations of the game were played in both 10th century Persia and by 13th Century Spanish Moors. The rules of modern checkers were solidified around 1535 in France when the game was titled Jeu forcé.

Though simpler than chess, Checkers has some 500 Billion billion (1020) possible legal board positions. Such a large amount of possible variation made the game nearly invincible for centuries. With the advent of powerful microprocessors in the 1980's, computer scientists saw an opportunity to crack open at a hitherto impenetrable mathematical complexity. Schaffer and his team in Alberta had been working on Checkers demise for 18 years, sometimes employing as many as 200 computers at a time, all calculating possible endgame positions. 1014 calculations were needed to analyze the endgames and complete the proof. In 2007, Chinook was released and vanquished its foe.

Checkers was not the first game to go the way of the Dodo. Connect Four was mathematically solved in 1988 by Jamed D. Allen and Victor Allis, independently of each other no less. Still unsolved, computer chess took great leaps forward in 1997 when Deep Blue defeated world champion chess grandmaster Gary Kasparov. But given that Chess has some 1040 possible legal board positions, a true solution to the game seems a far off dream for computer programmers. To this day, Checkers remains the most complex game to be murdered by modern technology.

In addition to Chess, Checkers is survived by Yahtzee, Marbles, Othello and Poker. Checker's brother Tic Tac Dough died in infancy.

You AUGHT to remember...

No comments:

Post a Comment