Checkers “solved” using up to 200 computers at a time
By Kyle Sherer
August 7, 2007
August 8, 2007 After 18 years of work, Jonathan Schaeffer from the University of Alberta, has announced the completion of Chinook, a checkers playing program that has calculated every possible playing scenario on a checkers board with ten checkers or less remaining. After evaluating the data, Schaeffer’s team concluded that whenever two players play through a game without making a single error, they will unavoidably reach a draw. It means that whenever Chinook plays competitively, be it with a computer or human, it simply will not lose.
There are three levels of mathematically solving a game. An ultra weak solution predicts what the result of the game will be if both sides play flawlessly, but is termed “ultra weak” because it does not necessarily construct the process of play, but merely proves that such a process exists. As such it is fairly inconsequential to players. A strong solution, in contrast, is able to calculate perfect play for any player, from any state of the board, and provide a step by step breakdown. The solution Schaeffer’s team has calculated is called a “weak” solution and lies somewhere in between. Chinook can calculate perfect play, thus securing a win or a draw for the chosen player, but only from a given position – in this case, when the board has ten checkers or less remaining. However, because all completed checkers games must pass through this state, it is mathematically sufficient proof that perfect play on both sides will eventually lead to a draw and makes the program unbeatable in combative play. To secure the solution, Schaeffer had to use upwards of 200 computers at a time, (at the peak of operations, 500), to plot the 500 billion billion positions necessary. However, while this 18 year effort sounds inconceivable, it is only the latest, hi-tech step in the very well trodden path of man’s obsession with games.
While checkers and chess as we know them today have been around since, respectively, the 16th and 15th centuries, their precursors were present in ancient India and Egypt. A combination of simplicity of form and complexity of function has allowed board games to captivate society for almost as long as society has existed. We are attracted intellectually by board games such as checkers or chess, because their immense complexity demands a certain respect – with trillions of possible board configurations, even those (human) players who master it cannot hope to even scratch the surface of what constitutes possible game play. The number of legal positions in Chess is 10 to the power of 123; a figure so big that, well... its big.
But though the sheer maths of chess and checkers is incalculable to human minds, they are also games of comforting simplicity. In both games, players must achieve a single, clear objective by following clearly defined rules. To express such unimaginable complexity through such an understandable medium appeals to the personal side of us – this is perhaps why we find the idea of solving a board game so interesting. And though the invention of computers has finally given us a means to feasibly pursue this desire, it is by no means new. In the 18th century, Baron Wolfgang von Kempelen boasted that a robotic device of his own design, named the Turk, could beat any human player at chess. His intimidating contraption was made to look like a tin-pot sorcerer, complete with smoke pipe, seated at a cabinet in front of an ornate chess board. Debuting at a time when public interest in “automata” was at a high, the Turk both captivated and unnerved the populace. Despite the fact that Schaeffer has presented his advances to a more refined audience, (and despite the fact that Chinook, unlike the Turk, is demonstrably not controlled by a midget squatting undetected in the casing), his addition has been met with a similar reaction. Editorials and articles are divided between those who see it as a significant advance in computer science and those who see Schaeffer as a spoilsport and Chinook almost as a betrayal. ‘What possible benefit,’ they inquire warily, ‘could come out of solving Checkers?’
Schaeffer himself struggles to find an answer. While other commentators claim that the complicated algorithms and processes used could be turned towards medical science, Schaeffer comments that “The world is not going to be revolutionized." Most likely, they will be used by the next talented and passionate scientist who wants to solve chess. As for Schaeffer, he has turned towards more fertile grounds – creating a computer program that can play superior poker. His poker playing program was narrowly defeated by pros at a recent tournament. However, most commentators concede that it is probably only a matter of time before computers claim this trophy as well. There’s no point asking why people will strive to make it happen – indeed, if Chinook has showed us anything it’s that unrelenting curiosity is directed equally to matters of great, and seemingly trivial, importance. It’s just one of the rules of the game.