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).
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?
ReplyDeleteIn most instances of the n x n checkers problem, n has more than a billion billion digits.
ReplyDeleteSo I think there is a flaw in calling the 8x8 problem medium-sized.