Abstract
Jonathan Schaeffer 1* , Neil Burch 1, Yngvi Björnsson 1, Akihiro Kishimoto 1, Martin Müller 1, Robert Lake 1, Paul Lu 1, Steve Sutphen 1 1 Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada.
* To whom correspondence should be addressed.
Jonathan Schaeffer , E-mail: jonathan@cs.ualberta.ca
The game of
checkers has roughly 500 billion billion possible
positions (5 x 10
20). The task of solving the game, determining
the final result in a game with no mistakes made by either player,
is daunting. Since 1989, almost continuously, dozens of computers
have been working on solving
checkers, applying state-of-the-art
artificial intelligence techniques to the proving process. This
paper announces that
checkers is now solved: perfect play by
both sides leads to a draw. This is the most challenging popular
game to be solved to date, roughly one million times more complex
than Connect Four. Artificial intelligence technology has been
used to generate strong heuristic-based game-playing programs,
such as DEEP BLUE for chess. Solving a game takes this to the
next level, by replacing the heuristics with perfection.
Jonathan Schaeffer's quest for the perfect game of checkers has ended. The 50-year-old computer scientist from the University of Alberta in Edmonton left human players in the dust more than a decade ago after a trial by fire against the greatest checkers champion in history.
Schaeffer's odyssey began in the late 1980s. He had written a top chess program but IBM was on the verge of pouring its far vaster resources into Deep Blue. "I like to be competitive," he says, so he turned his attention elsewhere. "I naively thought I could solve the game of checkers," he recalls. "You can teach somebody the rules in a minute."
Setting out with 16 megabytes of computer memory, he quickly found that checkers, like chess, was too rich with possible positions to dash off a solution. So he switched gears, vowing to topple legendary checkers champion Marion Tinsley, who had lost only five games in tournament play between 1950 and 1992.
In 1992 Schaeffer's program Chinook took on Tinsley, who had resigned as world champion when the American Checker Federation and English Draughts Association temporarily refused to sanction the man-computer matchup.
The program actually beat Tinsley twice, but computer glitches led to a forfeit that gave the human a 3-2 lead with two games left in a best-of-40 match. Schaeffer set Chinook on an aggressive course to try to recoup, resulting in another loss for the computer that cost it and its creator the match, Schaeffer recounted in his book One Jump Ahead.
Early this decade he decided that improved computer speed and memory had brought his goal of solving the game within reach. The first of the solution's two pieces builds on work begun during the Tinsley days. The Alberta researchers exhaustively checked the final stages of play for any arrangement of 10 pieces or less, identifying which of the 3.9 x 1013 positions won, lost or drew.
Next they identified 19 representative opening sequences and searched through subsequent moves for connections to winning or drawing final positions, ignoring pointless back-and-forth moves or those that led to poor positions.
If the sequence of possible moves branches like a tree, the group found that main branch after main branch led to a draw. On April 27, Schaeffer says, the program traced the final branches, completing his 18-year task. He had received his king.
Article credit
Computer checkers
