[Computational Complexity] Checkers- Clarification by Schaefer
- Aaron Sterling pointed Jon Schafer (the checkers guy!) to my entry andScott'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?
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).
Posted By GASARCH to Computational Complexity at 8/21/2007 10:26:00 AM