Tuesday, August 21, 2007

Checkers- Clarification by Schaefer

Aaron Sterling pointed Jon Schafer (the checkers guy!) to my entry and Scott's entry on checkers, and the comments on it. the comments on it. Then Aaron Sterling and Jon Schaefer had an email discussion about the checkers result. Here is the transcript abbreviated.

Sterling: Please clarify what you mean by checkers being solved. As you can see from the discussion, there is lack of agreement on what the Science article really meant.

Schaefer: Checkers has been weakly solved. The game is a proven draw and the proof online gives the sequence of moves for white and black to achieve the draw.

Sterling: More pointedly: what percentage of the total gametree is now determined?

Schaefer: We considered 1014 positions out of the total search space of 1020.

Sterling: If the search area was pruned, what were the criteria used for that?

Schaefer: Lines of play that were provably irrelevant to determining the final result were ignored.

Sterling: Is there even a shred of possibility that a "supposedly losing" move could in fact lead to a won position, and so certain game lines were improperly excluded from search?

Schaefer: None.

Sterling: Most significantly, perhaps, is this only a statement about 8x8 checkers, or does it generalize in any way?

Schaefer: 8x8 checkers only. The program can, however, be used to solve any game of checkers (it does, in fact, work for an 8x8 variant and 10x10 international checkers).


  1. This raises the interesting question of: what, if any, relationship does the problem class in which a generalized problem falls have with finite instances of that problem? We know generalized Checkers is EXPTIME-complete, so there's no polynomial-time solution in terms of the board size, but it's trivial to solve on small boards, and evidently within reach to solve on the medium-size boards that are complex enough to satisfy humans. Does this make it any harder than a game that generalizes to a PSPACE-complete problem? Or should we be comparing the sizes of the state spaces instead?

  2. In most instances of the n x n checkers problem, n has more than a billion billion digits.

    So I think there is a flaw in calling the 8x8 problem medium-sized.