[FOM] Checkers is a draw
joeshipman at aol.com
Sun Jul 22 10:56:34 EDT 2007
How large is the database storing this proof? The online version
consists of a game tree in which the terminal nodes are not positions
whose value is obvious, so most of the database is no online.
This is a good example of a kind of interactive proof not typically
treated formally -- although the database itself can be converted to a
real formal proof whose size is probably measured in hundreds of
terabytes, and so is not "humanly feasible" to check, the applet which
allows you to play against the database is a sort of interactive proof
that would convince a world-class grandmaster in a humanly feasible
amount of time, but would not convince an ordinary checker player.
From: Timothy Y. Chow <tchow at alum.mit.edu>
The results of the computation have been placed online at:
AOL now offers free email to everyone. Find out more about what's free
from AOL at AOL.com.
More information about the FOM