Friday, July 20, 2007

Checkers decontstructed

Tic-tac-toe is a simple game, and virtually every 6-year old on the planet has mapped out every permutation of moves possible. Played properly, it's impossible to lose - which includes a game playing DNA computer.

Checkers, with a search space of 5x10^20 is a much more complicated game. After 18 years, researchers at the University of Alberta have finally 'solved' the game, proving that, like tic-tac-toe, when perfectly played always ends in a draw. This makes checkers, 1 million times more complicated than Connect Four (the previous title holder), the most complicated game to have all its maneuvers mapped out.


Anonymous Coward said...

wake me up when they've figured GO, with its e^100 possible moves...