[FOM] Checkers is a draw

joeshipman@aol.com 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.

-- JS


-----Original Message-----


> 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.

It would convince a world-class grandmaster that Chinook is an 
extremely
strong player, but it would not necessarily convince said grandmaster 
that
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 mailing list