The Chess Mind

The source I saw said Karpov has confessed but Kasparov claims this is a ruse by Karpov to erase the record of his defeats.

Fantastic post!! You got me! Congratulations! 1-0 for you! If not for the comments unerneath, I would not have realised it's April!!

Dennis, I thought you always tried april fools jokes on anything but april 1st .. I still remember this Karpov - Fischer game!

American wrestling is fixed?!? :-)

Dennis and Bobby are correct. I computed the Shannon-Kolmogorov entropy of the moves when modeled as a Markov decision process under conditional Bayesian estimation, and found that the first and second eigenvalues nearly coincide for these games. This indicates a lack of expansion in the underlying weighted process graph, hence the games are determinable from a source with a shorter specification. I need to double-check these results via more-modern techniques involving ordered binary decision diagrams (OBDDs), but the significance is already in the Three-Sigma range. Since these formulas come from physics and Bobby's father was a well-known physicist---and since Botvinnik himself knew Kolmogorov and used some of this stuff in his engineering research---I wouldn't put it past Fischer to have recognized this.

Not totally tied to the day, this...

In my book, ChessBase deserves credit for taste, for NOT making analogy to the "Hitler Diaries" case, especially given Bobby's views.

Now that it's April 2, here's something serious that uses the same terms and concepts I was throwing around. If someone chose a chess position and had you play "Twenty Questions" to identify it, how many questions would you need? Claude Shannon estimated the number of legal chess positions as 4.63 x 10^42 ~= 2^142, so 142 questions always suffices. But most legal positions are totally insane, with zero chance of being reached by any players who are developed enough to keep score. So how many questions do we need to cover a range of positions that includes those reached in all recorded games, and all those with any real possibility of being reached in centuries to come, even in Baseline or Fischer Random chess?

If we could get the number of questions down to 64, by a process that computers can swiftly execute, it would be a big win. This is because modern computer architecture naturally organizes into 64-bit words (the 1990s standard was 32-bit words). Indeed, all chess programs "hash" positions whose evaluations need to be recorded into 64-bit words by the technique of "Zobrist Keys"---and then if you allocate a hash table with (say) 2^25 = 32 million entries, they get hashed further into 25-bit words. This technique loses data when two different positions have the same code, and at least one computer blunder (Shredder 9.0 failing to recapture a Bishop versus Paolo Lafuente in 2005) has been blamed on such a "hash collision". Although foolproof 64-bit codes might not help with the "second-level hash" to 25 bits, they would definitely help with opening books and endgame tables.

Now to tie this to my joke comment, an OBDD is exactly the formalization of a winning "Twenty Questions" strategy, and it accomplishes Kolmogorov-compression of the objects being described. Papers using this technique for middlegame positions can be found on Bernard Balkenhol's website, http://www.balkenhol.net/ (click "Publications" then find "Data compression in encoding chess positions"), and for endgames, see the Master's Thesis on the chess page of Jesper Torp Kristensen: http://www.daimi.au.dk/%7Edoktoren/master_thesis/. Incidentally, Kristensen was supervised by complexity theorist Peter Bro Miltersen, with whom my most recent PhD graduate Maurice J. Jansen is doing a postdoc.