[FOM] Re: Is Chess ripe for foundational exposition/research?

[Timothy Y. Chow]

Harvey Friedman listed three possibilities for chess:

> 1. [...] If one has this fundamental tactical competence - say at the
> level of an average grandmaster - then chess assumes the nature of a
> rich mathematical science, where fundamental principles and the creative
> imagination take over, in much the same way that they do in mathematical
> science.

> 2. [...] Specific tactics rule, and great chess - even in the hands of
> the greatest players - is principally a matter of ad hoc deep analysis,
> centered around accidental tactical factors, together with a deep
> knowledge of the competing general principles (flawed, with limited
> applicability), and great experience and concentration.

> 3. A third possibility, of course, is that what I had hoped for and came
> to believe - at one time - through the writings of E. Lasker, M. Euwe,
> and H. Berliner, and others, is actually true, and that we don't need
> any massive amount of chess experience to get to the foundationally
> interesting chess matters.

Here are some facts that may be relevant to the discussion.  As I thinked
I've mentioned on FOM before, generalized chess is EXPTIME-complete.  So
in particular, there is provably no polynomial-time algorithm for solving
generalized chess.  I regard this as prima facie evidence for option 2.
There may be principles, heuristics, and approximation algorithms that
capture a lot of what happens in chess, but there will always be a large,
hard core of tactics that resists simple analysis.  Some other evidence in
this direction: John Watson's excellent book "Secrets of Modern Chess
Strategy" goes to great lengths to demonstrate that modern chess, at the
highest level, explodes with examples where concrete possibilities
override even the most tried-and-true general principles.  Watson's whole
book is a treatise *against* the rather naively optimistic views about
chess theory that many earlier commentators held.

Consider also the endgames that have been solved exactly and whose correct
solutions seem to defy explanation in conceptual terms.

  http://www.chessbase.com/newsdetail.asp?newsid=239

These show that the EXPTIME-completeness result isn't just an asymptotic
fact; serious complexities show up already on the 8x8 board.

Having said all this, I do not think that it necessarily precludes 1
and/or 3 from being true as well.  The fact that theoremhood in ZFC is
undecidable, or that the existence of a proof of length n (expressed
in unary) of a given statement is NP-hard, puts a bound on how much
sense we can make of mathematics, but doesn't stop us from constructing
lots of beautiful mathematics.  So in principle I think there could be
such a thing as a "foundational exposition" of chess.

I don't think, however, that chess is "ripe" for such an exposition.
First let's see if we can find polynomial-time algorithms (or
approximation algorithms) for restricted classes of endgames in
generalized chess.  If we can't even do that, then I think it's far too
ambitious to seek the "right" general principles for chess in general.

Tim