The Checkers Terminator

Marion Tinsley, the greatest checkers player who ever lived, managed to narrowly beat a computer in 1992. Today, the best a player of his caliber could manage would be a tie. That’s because computer researchers at the University of Alberta have managed to “solve” the game. By analyzing an oppon­ent’s moves, their program can coun­ter with a winning strategy or, at worst, play to a ­draw.

Despite checkers’ reputation as an easy game, solving it, say Jonathan Schaeffer and his colleagues, “pushes the boundary of artificial intelligence [AI].” The game’s possible positions, with 24 pieces moving on 32 black squares, amount to 500 billion billion (5 x 1020).

Efforts to construct a ­checkers-­playing program capable of beating a human began back in the 1950s with pioneering work by Stanford University’s Arthur Samuel; in 1963 his program won a game (but not the match) against a capable player. That victory was “heralded as a triumph for the fledgling field of AI,” say the authors, all of whom are connected with the University of Alberta. But it was the Chinook program, launched by Schaeffer in 1989, that took on Tinsley (whose declining health prevented him from finishing a rematch). The version of the program available at the time relied on a database of all possible endgame positions once players were down to four pieces a side. Anything beyond that outstripped existing computing capacity.

The current version of Chinook employs a ­five-­piece-­or-­fewer-per-side endgame database (39 trillion possible positions!), as well as two ­forward-­searching algorithms that kick in from the first move, analyzing possible outcomes of moves in terms of achieving a win, loss, or ­draw.

The database still does not contain all possible positions that can arise in the game. Compiling such a database, the authors say, though theoretically possible, would make playing the game “impractical with today’s technology.” It would take too long for the computer to crunch the data. Nonetheless, Schaeffer and colleagues believe that, armed with their current program, they could do no worse than tie a ­mistake-­free player. (Even the great Tinsley lost three times from 1950 to 1991.)

Is there any significance to all of this, beyond mere ­game-­playing? Schaeffer and his coauthors think so. “The project has been a marriage of research in AI and parallel computing, with contributions made in both of these areas”; they performed computations on up to 50 computers ­simultaneously.

Behind such practical concerns, though, lurks the geeks’ grail: With checkers now largely conquered, will chess ever be solved? Maybe, the researchers say, but not for a long time. The possible moves in checkers, though vast, represent only the square root of the possible chess moves, which are something on the order of 10120. (Scientists estimate the number of atoms in the known universe at only 1075.) “Playing chess is like looking out over a limitless ocean,” Tinsley once said. “Playing checkers is like looking into a bottomless well.”

* * *

The Source: “Checkers Is Solved” by Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, and Steve Sutphen, in Science, Sept. 14, 2007.

Photo courtesy of Flickr/Steve Snodgrass