A No-Win Solution for Checkers

Science  14 Sep 2007:
Vol. 317, Issue 5844, pp. 1465b
DOI: 10.1126/science.317.5844.1465b

Computer scientists have traditionally used games such as chess as test cases for research in artificial intelligence. Less challenging games that have a small search space can be completely solved with computers by examining every possible set of moves from a given starting position. Chess has an immense search space that would require the fastest computers eons to solve, but other games provide tough but feasible challenges. Schaeffer et al. (p. 1518, published online 19 July; see the 20 July news story by Cho) report their solution of the game of checkers. If black moves first, and the opponents execute perfect play, the game ends in a draw. The analysis began in 1989 and required dozens of computers for a complete solution.

Navigate This Article