[FOM] Is Chess ripe of foundational exposition/research
urquhart at cs.toronto.edu
Thu Feb 5 19:46:43 EST 2004
FOM readers who were intrigued by the interesting postings
of Harvey Friedman and Tim Chow might find some more
food for thought in the two excellent collections:
"Games of No Chance" and "More Games of No Chance"
both published by Cambridge in the MSRI series.
In the first volume:
"On Numbers and Endgames: Combinatorial Game Theory in
Chess Endgames" by Noam D. Elkies.
This is a beautifully written article elucidating some
very fine points of chess endgame play using Combinatorial
Game theory in the style of "Winning Ways."
"Solving the Game of Checkers" by Jonathan Schaeffer and Robert Lake.
A very nice survey of what it means to solve the game of checkers.
Schaeffer is also the author of an excellent book on his development
of the world champion checkers player, "Chinook."
Open problem 29 in the first volume: Prove that black does not have
a forced win in chess.
In the second volume, the comments on the problem say: "Andrew Buchanan
has recently emailed me that he has examined some simpler (sub-)problems
in which the moves 1 e4,e5 are made, followed by a bishop move by each
player, or a Queen move by each player. He claims that at most six of each of
these sets of positions can be wins for Black."
As far as chess's relevance to FOM goes, I agree with Richard Teichmann and
Tim Chow that it is 99% tactics. Hence, it provides us with GOOD evidence
that P is not equal to NP.
More information about the FOM