[FOM] Checkers is a draw
joeshipman at aol.com
Mon Jul 23 23:00:30 EDT 2007
The idea is not to convince the GM that Chinook is perfect, it is to
convince the GM that checkers is a draw, and backtracking is what makes
this possible. The best chess computers have rating of 3000 (meaning
they would beat the world champion 3 times out of 4), but I can very
easily and quickly find a way to beat them if I am allowed to backtrack
and they are committed to playing the same move when they get the same
position. The interactivity is a tremendous advantage for the
backtracking player, and a GM who could never find a way to win with
either color with any amount of backtracking would develop a firm
conviction that the game was a draw.
> This is a good example of a kind of interactive proof not typically
> treated formally -- although the database itself can be converted to
> real formal proof whose size is probably measured in hundreds of
> terabytes, and so is not "humanly feasible" to check, the applet
> allows you to play against the database is a sort of interactive
> that would convince a world-class grandmaster in a humanly feasible
> amount of time, but would not convince an ordinary checker player.
It would convince a world-class grandmaster that Chinook is an
strong player, but it would not necessarily convince said grandmaster
Chinook is a *perfect* player.
AOL now offers free email to everyone. Find out more about what's free
from AOL at AOL.com.
More information about the FOM