FOM: Mathematical knowledge vs. Chess knowledge
Soren Moller Riis
smriis at brics.dk
Thu Jan 22 16:21:17 EST 1998
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).
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
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:
If P=NP this cannot be proved in ANY axiom system which provides
Put slightly different:
P=NP only have a chance of being proved in an axiom system which
includes principles which implies the validity of certain non-trivial
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.
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.
More information about the FOM