No human checkers player can beat computer program ‘Chinook’

Scientists have used hundreds of computers to develop a checkers program they claim no human player can beat. Draughts, known as checkers in America, is a popular board game with a history that dates back 5,000 years. In checkers, disc-shaped counters move diagonally on a chequered board one square at a time and jump over an opponent’s pieces to capture them.

The game is essentially simple, but scientists had to work out responses to every possible move, which meant sifting through 500 billion-billion (five followed by 20 zeroes) different play positions.

The team of computer scientists at the University of Alberta in Edmonton, Canada, worked for 18 years analysing 500 billion-billion possible combinations of moves to find the perfect strategy in any situation.

The research results have been published in the journal Science.

Against a human who plays flawlessly, the computer game – called ‘Chinook’ – would end in a draw.

Though simpler games, such as tic-tac-toe and Connect Four, have been “solved,” this is the first time that researchers have cracked a game of such complexity, according to Professor Jonathan Schaeffer of Edmonton, Alberta, leader of the research team.

Professor Jaap van den Herik, a professor at the University of Maastricht in the Netherlands and editor-in-chief of the International Computer Games Association Journal, described the feat as “a magnificent performance” and “another milestone.”

Checkers, which became popular in Spain in the mid-16th century, is a game between two players who move 24 red and black, or red and white, pieces over an 8-by-8 square board, eliminating opposing pieces by ‘jumping’ them. The player who first runs out of either pieces or moves is the loser.

Jonathan Schaeffer proved that checkers, when played perfectly by both opponents, ends in a draw, something that until now had only been speculation.

Schaeffer said in an interview, “The new program pushes the state of the art by a huge amount. We developed some technologies and some ideas that allowed us to solve this roughly 10 million times faster than normal.”

Other researchers are working on more complex problems, such as trying to determine whether chess, when played flawlessly, always results in a draw or a win for the white pieces, which move first.

Jaap van den Herik said that solving Go, a Japanese game played on a 19-by-19 board, is beyond the present capabilities of humans or machine.

Checkers, says Schaeffer, represents the most computationally challenging game solved to date. The program can achieve a draw against any opponent, playing either black or white pieces.

Scientists have for decades fed algorithms – sets of instructions – into increasingly powerful computers in a quest to demonstrate machine intelligence. The proving grounds have often been the boards of analytical games such as chess and checkers.

In 1997, the ‘Deep Blue’ program of International Business Machines Corporation (IBM) had beaten chess grandmaster Garry Kasparov.

The new checkers program ‘Chinook’ draws its strategy from a 237-gigabyte database that stores 39 trillion piece positions. An earlier version of Chinook was defeated in 1992 by checkers world champion Marion Tinsley, who had lost only three matches in 41 years. In a 1994 rematch, an improved Chinook tied six games with Tinsley before the champion withdrew, citing illness. He died eight months later.

Solving checkers required running as many as 200 computers, including machines in California, the United States, and Alberta, Canada, simultaneously.

The team perfected ‘Chinook’ running the Unix operating system on computers from IBM, Sun Microsystems Incorporated, and Hewlett-Packard.

Chinook now contains all the information needed to predict the best move to play in every situation of a game. Even making no mistakes, the best an opponent taking on the program could achieve would be a draw.

Schaeffer, who believes that scientists will next crack the board game Othello, will pit his ‘Polaris’ poker program against two human professionals for Canadian $50,000 (US $47,946) in prize money at a Vancouver, Canada, tournament later in July 2007.