FOM: Mathematical knowledge vs. Chess knowledge

[Soren Moller Riis]

------------------------------------------------------------------------
Mathematical knowledge (MK) versus Chess knowledge (CK):
------------------------------------------------------------------------
Contains some highly speculative questions/suggestion of how the 
MK versus CK could illustrate some points concerning the P=NP question.


Joe Shipman wrote:

> Every chess player with significant practical experience knows that 
> the advantage of a Queen in the initial position is enough to win.  
> This is truly a known fact, in the philosophical sense of justified 
> true belief.  It is also clearly a mathematically formalizable 
> statement.  But this fact is not (yet) mathematical knowledge because 
> we have nothing even remotely approaching a mathematical proof.  

It is plausible that there is no short proof of this fact in ZFC. Actually
it seem plausible that the fact would need to have long proofs in ANY axiom 
system which gives the user anything we would call mathematical certainty.

It seems plausible that the shortest proof in any such system
essentially consists of listing the major part of the variation tree
possible doing some short cuts in simple positions near the leafs.

How does chess-masters actually analyse a position (say in postmortem analysis 
after a game). They select critical lines and form judgements. Now no one have 
ever been able to construct a single non-trivial chess position in which 
chess judgement (like this is won/draw/lost, or this move can be ignored for 
it is bad etc...) would count as a mathematical proof.
For this reason we postulate that chess knowledge only can become 
mathematical knowledge by spelling out and replacing all chess judgements 
with further analysis and new chess judgements further
down the variation tree. Only when very close to the leaves when the
game stops being a game of skill but rather just implementation
of a uniform easily describable strategy we might be able to avoid
considering all variations.

Now consider the generalisation of chess where the board is extended
to size n times n. The initial position is similar to ordinary chess,
with some reasonable way to put pices behind the pawns. Also we
add more rows of pieces behind the pawns as n tends to infinity. 
Let us call this game G_n.

To a chess player it would be completely obvious that G_n is a theoretical
draw for all n \geq 8. Not completely obvious for n=8 perhaps, but certainly
it is clear that whites advantage of having the first move will disappear 
when n gets larger.

Consider the statement:

S: For all n > 8, G_n is a draw (if both parties plays optimal).

It seems plausible that the shortest ZFC-proof that G_n is a draw have a 
number f(n) of steps in the proof which tends to infinity for n going to 
infinity. If this is right S is not provable in ZFC.
Actually (again of course speculating) it seems plausible that
S cannot be established in ANY axiom system which gives the user anything 
we would call mathematical certainty. 
(I am aware all this could be awfully wrong. There are known examples (from the
game Hex) where general arguments can prove existence of a winning strategy.
Also there might be some strange asymptotic arguments which works).

Suggestive speculation: 
S is undecidable in ANY axiom system which have a chance of giving the user 
something which could be identified as mathematical certainty. 

I hope such wild speculations occasionally are OK on this list. Perhaps one 
could replace S by other more mathematical propositions. If we replace S by
a consistency statement we do not quite get what I have in mind. What
I suggest is that perhaps there is some invariant 
`mathematical certainty' which simply not is present in chess knowledge
like S.

LET ME EMPHASISE: I do not think chess players have some mystical powers 
by which they obtain  knowledge. I belive we all have an ability to reason 
in different modes. Some of those modes might not be mathematical yet 
occasionally they lead to conclusion of a higher degree of certainty than 
the one which is achieved through most mathematical proofs. 


Forgive me for speculating further. Could one not argue that a proof
of P=NP (in ANY axiom system which gives the user anything we could label 
as mathematical certainty) is doomed because it would give non-trivial 
knowledge about chess (knowledge not formed as chess knowledge, 
but formed in the mathematical sense). If P=NP there would be a procedure
which would find wins in $k$-moves ($k$-fixed) on arbitrary large boards
without searching the whole tree of variations to depth $k$. This is plausible.

Thus I suggest that we need to consider most of the variation tree to achieve
mathematical knowledge that a move is the strongest. I also suggest (in 
complete agreement with chess experience) that we do NOT need to consider very
many lines to find the strongest move. Thus it is not unreasonable that

J: There a polynomial time algorithm which finds wins in 
$k$-moves on a n times n chessboard.

The same intuition from above suggest:

J': J cannot be proved in ANY axiom system which have a chance of giving the 
user something which could be identified as mathematical certainty.

If these speculations are right we get:


Suggestion:
If P=NP this cannot be proved in ANY axiom system which provides
mathematical certainty.


Put slightly different:

Suggestion:
P=NP only have a chance of being proved in an axiom system which 
includes principles which implies the validity of certain non-trivial
chess judgements.


Could one replace "chess knowledge" in the above arguments by something
more mathematical appealing? Is all this relevant for fom? 
If nothing else it shows that it is possible to acquire knowledge 
(in a non-mathematical way) about parts of the mathematical world.
 


Søren Riis

Research fellow at the Fields Institute Toronto. PhD 1994 from university
of Oxford (Bounded Arithmetic). On leave from the international PhD school
at BRICS Aarhus. Have played chess on international level (elo 2300, and
a Danish rating equivalent of a US rating of 2400). I qualified to play for 
the Danish championship in correspondence chess, before I stopped playing
chess. I have never lost a game of correspondence chess. 
I am a keen amature bridge player. I have played with many of the professionals 
top players in Denmark.