proof

[jefk]

so below there's a (very rough and preliminary) a draft preprint for arxiv or so proving chess is solved
(well at least 'ultraweakly' as is the jargon in contemporary game theory); in the past I referred to
some reasoning in game theory mentioning a theorem by Zermelo, which was considerd insufficient 'proof'
on this forum by some skeptics; in some way understandable, considering that in math rigorous logic
is obliged by definition and somehow I couldn't (yet) made the jump from Zermelo (and the Chinese
database results) to a real 'proof'. So here's -below- now another imo now even more compelling reasoning
method to achieve the similar result i.e. an 'ultraweak' solution for the game of chess.
This latest research is based on backward induction which is well known principle in math and game theory;
the reader doesn't have to be a Johnny von Neumann to see what i mean (although ofcourse one may
be skeptical again about the mathematical rigor in the methods i use(d); whatever, personally i think it's
valid reasoning and for me it's 'only' a matter of communication in conveying the logic of the end result
(which has some usefulness in the practice of computer chess in eg. areas as opening theory (searching for a
White win or large advantage is a futile endeavor, and correspondence chess (at high level all draws nowadays)

---------------------------------------------------------------------------
Title: Chess is solved

Abstract:

In this (draft) paper, I present an ultraweak solution for the game of chess, indicating that it is a draw, and a tentative weak solution supporting this conclusion. While I consider the ultraweak solution to be sound, derived from logical reasoning and examination of the chess game tree, the weak solution is based on practical results in computer chess, combined with the reasoning for the ultraweak solution. These provide strong arguments to believe that chess is a draw with perfect play for both sides. However, a strong solution, solving all possible positions, remains an open challenge and is likely to be extremely difficult to achieve.

Introduction:
-----------------
The problem of solving a two-player game with perfect information is well-defined in game theory. The definitions of an ultraweak, weak, and strong solution are provided in the literature [1]. An ultraweak solution for a game like Hex was found many years ago through logical reasoning [2]. In the field of game theory, as discussed by the International Computer Games Association (ICGA), the game of checkers was weakly solved years ago at the University of Alberta by Dr. J. Schaeffer and his team [3]. Before publishing their results, they had already published a paper on their research methods [4], which I considered for my project of solving chess but skipped for practical reasons.

In their project, they used a considerable amount of computer resources, computing billions of positions and building substantial endgame databases ('table bases') and opening theory databases for checkers using computer methods. Similarly, the game of Othello appears to have been recently weakly solved [5], although still under investigation by some skeptics. Meanwhile, it is considered very difficult to find such solutions for games with more degrees of freedom, such as draughts and, even more challenging, chess, due to the extremely large tree of possible positions.

Nevertheless, in this paper, using logical reasoning for an ultraweak solution and experimental results supported by such reasoning for a weak solution, I present an ultraweak and weak solution for the game of chess, proving that it is a draw with perfect play.
Note that in addition to logical reasoning, the findings in this paper are based on extensive reading about game theory and many years of experience in computer chess, correspondence chess (holding the CCM title), investigations and research into chess opening theory, particularly minimaxing large (and later huge) trees based on evaluation of endnodes, as done by the program Bookbuilder, which was developed on my initiative many years ago [6]. The conclusions of this research were recently confirmed by the 'Chinese' opening database for chess with billions of positions, incorporating a minimax function [7].

Reasoning and Results:
The Ultraweak and Weak Solution(s) for Chess (It's a Draw):

A) The goal of the game is checkmate, which must originate from the opening position. It is reasonable to start with the fastest possible checkmates, such as (assuming the reader is familiar with algebraic chess notation and annotation like '?' for a bad move):

1. e4 f6?! 2. xx g5?? 3. Qh5#
Note that there are many moves Black could have made to avoid this mate, and there are no other ways for White to achieve a mate in 3 moves. Try to find other mate-in-3 lines, as a challenge.

Scholar's Mate: 1. e4 e5 2. Bc4 Nc6 (or similar) 3. Qf3 d6?? (or similar) 4. Qxf7#

Again, Black has numerous options to avoid this mate, and other possible mates in 4 moves for White are similar, e.g., with 2. Qf3 and Bc4 (transposition).

A mate in five: 1.e4 e5 2. Qh5 Bc4 3. Bg7?? (or e.g., g6??) 4. Qxf7#
Black has many options to avoid this mate in 5 moves.
A mate in six: 1. e4 e5 2. Nf3 f6?! 3. Bc4 c6 4. Nxe5 fxe5 5. Qh5+ Ke7?? (...g6 is better) 6. Qxe5#
This could have been easily avoided.
Blackburne-Shilling Mate in 7:
1.e4 e5 2. Nf3 Nc6 3. Bc4 Nd4 4. Nxe5?? Qg5 5. Nxf7?? Qxg2 6. Rf1 Qxe4+ 7. Be2 Nf3#
And so on. It is clear that Black always has enough move options to avoid checkmate. This is the tree of drawing opportunities, and this tree grows exponentially as the game progresses. In other words, checkmates possibly delivered later in moves 5, 6, 7, etc., can be evaded even more easily than in the first two examples. Why? Well, unless pieces are captured (which can also be evaded), Black's pieces usually have more than one (or several) possible moves, thus the move tree expands at such a rate that evasion of checkmate becomes relatively easy.

Elaborating on this reasoning, if we go forward from move 1 and consider all possible checkmates within a certain number of moves, it is obvious that such checkmate sequences are severely limited, especially compared to other lines where White will not achieve such a checkmate. But going forward with this method, we theoretically explore all possible checkmate sequences. It is apparent that Black can avoid such sequences in earlier situations, mate in 3, 4, 5, and so on, but then going forward, the same is true: Black can continue to evade such forced mates. Now, in real games, assuming that a game has ended in a win for White (per definition, a checkmate, unless Black resigned), then reasoning backward via the backwards induction method and the same reasoning as used earlier (that Black can avoid the checkmate), it must be clear that Black could have avoided such checkmate situations in real (longer) games. Note that such reasoning may require a cognitive leap to fully understand it, but it is 100% logically correct.
But then, the reader may ask, why do games for humans often end in a win for Black or White? The answer is simple: erroneous play, either one side made a (tactical) mistake, or didn't see a winning plan coming, and thus neglected to evade that plan.

B) Similarly, White can evade Black's mates, starting from the beginning: 1. f4 (or f3) e6 or e5 2. g4?? Qh4#, and so on. Again, try to find other lines with mate-in-2 for Black (not possible).

Some mate-in-3 sequences (with many errors by White) can be constructed similarly:

1.a3 e6 2. f3 c6 3. g4?? Qh4#
And an example of a mate in 4 for Black:

1.c3 e6 2. b3 Qh4 3. Bb2 Bc5 4. Na3 Qxf2# (similar to a reversed Scholar's Mate)
Try to find other examples yourself (there are not many; these are rare lines).
White can easily avoid them, and possible checkmates delivered later by Black can be avoided even more easily.

In a similar way, Black can always avoid a mate by White.

As additional reasoning, consider the hypothetical situation that White could win; then, White should be able to win against all possible responses by Black. But after one move (e.g., e4), let's assume Black already has about three defensive moves that, according to opening theory, are equalizing (sometimes more than three). Then, after White's second move, there are about three more, and so on until the end of the game. Thus, for a game of about forty moves, the number of possible equalizing moves for Black is the enormous 3^40 (approximately 2.8x10^22). The chance for a White win in all situations (variations) is one divided by this number, effectively zero.

Note that some skeptics could suggest that there may be specific positions or sequences of moves where Black cannot avoid losing, even with optimal play, and that these rare situations need to be accounted for to definitively prove that chess is a draw with perfect play. My reaction is that they ignore the logical correctness of the backward reasoning (almost like complete induction) that such 'rare' situations/positions cannot occur if Black avoids them in an earlier phase. With 'perfect play' or at least adequate play, Black should, of course, avoid such positions (similar to the situation in the initial position where White should avoid losing by not playing 1. g4?).
Thus, although not formulated (yet) maybe in a rigorous mathematical way, with sufficient knowledge about the rules of chess (and piece movements, and so on), it must be clear that my reasoning is correct and can be (and most likely is) the basis for a solid 'proof.' We do not even need complicated graph theory, with topology, etc.; simple graph and topological-based reasoning (expanding 2D move option space/tree) shows that chess is a draw.

QED, chess is a draw (with perfect or at least adequate play). Thus, it is ultraweakly solved.

As an example where a game is not a draw, in the game of Four in a Row, the first mover can always win, but in this game, the tree for the 'second' (even ply) mover is not expanding; it is narrowing. This is completely different from chess. In checkers and draughts, it is a bit more complicated, but I am not an expert in those games (apparently, zugzwang plays a role in endgames). However, for chess, it is a matter of simple logic and experience (and understanding) to see that the above reasoning is correct: it must be a draw and thus ultraweakly solved.

(Intermezzo 1)
Hint to solve checkers and draughts with such reasoning methods: We can also (try to) start with the quickest wins for both sides. However, these games are considerably longer than chess, and showing that evasion of such wins is possible may be more difficult (or not). I would suggest using graph theory and computational methods, e.g., as in [8].

(Intermezzo 2)
As we can see, Black can deliver a faster checkmate than White (under A). We also know that the move 1. g4? is not good for White. So fundamentally speaking, Black has a slight (tiny) advantage in the game of chess (thus engines or GMs suggesting otherwise, such as Leela Chess Zero, must have it wrong). Of course, if we look at proper 'positional' play, after good initial moves for White like e4, d4, or Nf3, it is usually Black who has fewer options for good (drawing) moves, and thus, in practice, it is often thought that White has a (tiny) advantage. As shown in this paper, such a tiny (imaginary) advantage is not enough to ensure a win for White.

A (Tentative) Weak Solution:
As for a weak solution for chess, usually derived from number crunching, this means evading checkmate not only from the start but also for later positions. In this situation, we do not need almost brute-force number crunching (like the Chinese database expanding until the endgame databases). Our current NNUE-based engines like Stockfish, with modern hardware, can maintain the draw with sufficient calculation time (let's say one hour or so). This is also clear in modern ICCF correspondence chess, where nowadays, at the top, all games end in a draw. Earlier, it was already known that the higher the player (or engine strength), the higher the draw percentage, especially for slower games. Thus, for perfect play, the draw percentage will become 100%.

We can say that chess is also weakly solved. Only a 'strong solution' (finding the best move for any possible position, being a legal possible result from the starting position, with mistakes allowed for both Black and White) will theoretically take a longer time.
People who sometimes suggest 'chess will never be solved' apparently mean a strong solution but forget that, in practice, chess is already weakly (or at least ultraweakly) solved.

(Preliminary) Conclusions:

As made clear in this article and is widely known for games like Hex, Nim, etc., we do not always need number crunching to (weakly or ultraweakly) solve a game, as was done for Four in a Row, Checkers, and Othello. While it was thought to be extremely difficult to solve chess due to the large number of possibilities, in fact, with logical reasoning, the opposite is true. Because of the large number of drawing possibilities, it has been deduced that the game is a draw with perfect play, an ultraweak solution.

Subsequently, a tentative 'weak' solution is presented, supported by experimental findings in computer chess (e.g., ICCF correspondence chess, where modern 'NNUE' chess engines can be used).

Since I am not a pure mathematician (but knowledgeable about mathematics as a physicist) and not affiliated with a university (as people like Dr. J. Schaeffer and Prof. J. van den Herik are), I will reasonably expect quite some skepticism about my findings, especially the conclusions. Provided such skepticism contains positive suggestions, e.g., for further research, either in chess or the mentioned games of checkers and draughts, I will, of course, welcome such comments or follow-up articles (referring to this one).
In this respect, I am already used to quite some negativity, as experienced over the years when discussing this topic on an online forum for computer chess [9]. Similar discussions about the topic have been held on an online playing arena for chess [10], in which I did not engage (it did invoke my interest, however, when I noticed that there was still at least one person who believes in theory that White could possibly win in chess with perfect play).

If, for a stringent 'weak' solution, some academics or computer science research groups find it necessary or theoretically required to perform an (almost) complete 'number crunching' of the tree, they have my blessings. With sufficient pruning (e.g., alpha-beta) and incorporating, of course, the many possibilities of (positional) transpositions and the '8-men' endgame table base (including the kings), this can be done. I think that within ten years or so, they would arrive at the same result (namely, that it is a draw).
The problem of strongly solving chess remains, but it is considered more a matter of 'problem (puzzle) chess' than a practical matter (the difference with the large discipline of problem chess is that in a strong solution for real chess, the positions must be shown to be a possible result of legal moves).
Feedback is welcome, especially from mathematicians with knowledge of game theory (and preferably the game of chess at
a reasonable level), but preferably not on talkchess.com (by e.g. programmers, mediocre chess players, drunk English,
obnoxious American Phd students or otherwise).

References:
[1] https://en.wikipedia.org/wiki/Solved_game
[2] https://www.cs.cmu.edu/~hde/hex/hexfaq/ ... 20to%20win.
[3] https://www.science.org/doi/10.1126/science.1144079
[4] https://arxiv.org/html/2310.19387v3
[5] https://www.ijcai.org/Proceedings/05/Papers/0515.pdf
[6] www.chessdb.cn
[7] https://sourceforge.net/projects/bookbuilder/
[8] https://charlesreid1.github.io/cse-143- ... ckers.html
[9] www.talkchess.com
[10] www.chess.com

[towforce]

First things first: I agree that chess is drawn: the evidence is overwhelming.

Now let's look at jefk's proof: as I read it, I found myself asking, is this a proof by induction (link), or is it inductive reasoning (link)?"

Proof By Induction

1. Prove that if something is true for one item in a series, then it must also be true for the next item in the series

2. Prove that it is true for the first item in the series

3. You've now proven that it's true for every item in the series


Inductive Reasoning

Clyde is an elephant, and Clyde is grey. Nellie is an elephant and Nellie is grey. Therefore, all elephants are grey.

Inductive reasoning isn't always correct, but it's actually the type of reasoning that human's rely on the most.


Based on the above, my judgement is that jefk's case of is more inductive reasoning than a proof by induction. So it's good reasoning, but for me it falls below the exalted level of a proof.

[Jouni]

Did you notice TCEC 100 game match Stockfish - Leela with no book? All games draws with their powerful hardware.

[JacquesRW]

but for me it falls below the exalted level of a proof.

Understatement of the year.

[towforce]

Did you notice TCEC 100 game match Stockfish - Leela with no book? All games draws with their powerful hardware.

Even before chess computers became as strong as humans, it was known that the draw ratio increases with the strength of the players. This has continued to hold true, and now the top engines might well be getting close to a level at which they become unbeatable.

Like I said, the overwhelming weight of evidence favours chess being a draw.

[Viz]

Not a proof

[Bo Persson]

Did you notice TCEC 100 game match Stockfish - Leela with no book? All games draws with their powerful hardware.

So now we have 100 grey elephants.

Still not a proof, if there is a single pink one somewhere else.

[jefk]

towforce, it was a combination of partly inductive reasoning (proof by induction) and inductive reasoning
(in particular backwards induction), added with some abductive elements
https://en.wikipedia.org/wiki/Abductive_reasoning
(as pointed out here in the past by mr 'smatovic')

key point (repeating myself, but for clarity) was the combination of 1) Black can avoid forced checkmates
from ply 3,4,5,6 etc. and 2) because the 'tree' (of possible checkmates lines) is (exponentially) widening,
there's 3) no way White can force a mate after ply 10,11,12, etc ad infinitum. QED

For the skeptics ok it's not a rigorous math proof (yet), I now agree, but the latest posting was additional evidence,
but the specific reasoning by itself still contains a -minor- logical hole, I can now admit after some further thought(s).
For example, assume that, comparable to 1.g4? possibly leading to a Black win, there would be a move for White like
eg. 1.Nf3, with building up of a positional advantage, and then leading to a checkmate after eg. 200 moves or so (in
reality this is not the case, but nevertheless, let's assume they hypothetical case). But then with my reasoning (with
the avoidable checkmates after move 4,5,6, etc), this might remain undetected(*), seems to me now..
(peculiar that only after writing something up, and/or posting it, some counter arguments pop up in my head,
but that's another matter; part of a scientific investigative process (which often works different for me being
a rather creative person than for an average math bloke, i guess). Nevertheless i won't give up, and I'll see if i
can fix the logical hole, and then .. (in a few months) I'll be Back !
NB as you can see i now clearly identified (and specified) myself a (small) flaw in the logical reasoning, instead of
the negativity and prejudic of persons as 'viz' (and some other one) just giving negative feedback without any
reasoning (the usual math inquisition, i suspect, and i'm getting used to this, as written earlier already).

PS that eg.1.Nf3 (or otherwise) won't lead to advantage is again obviously from the Chinese database.
My checkmating examples thereby now should be seen as additional, illustrative examples showing
there's not mate in 12 (like on Quora), 120, of 600 whatever pure math might hypothesize.
Ergo chess is a draw. And for me this is with such certainty that i claim that by now we can consider that chess
has been ultraweakly solved (also because there's not a clear definition for an ultraweak solution anyway,
as was debated already a year ago (some paper by vd Herik, quoting a Phd paper with an arbitrary and ad hoc
definition of an ultraweak solution found for Hex because of some logical reasoning. One can claim that
there's still no 100pct mathematical rigorous proof (that it's a draw) but at least i'm trying to use logical
reasoning. Just as logical as when i would claim the earth isn't flat or water usually is wet.

(*) there's imo probably some way to fix this, not even referencing to the Chinese database
but i have to think about it, and then writing it down again

[JacquesRW]

Ergo chess is a draw. And for me this is with such certainty that i claim that by now we can consider
that chess has been ultraweakly solved (because there's not a clear definition for an ultraweak solution, as
was debated already a year ago (some paper by vd Herik, quoting a Phd paper with an arbitrary and ad hoc
definition of an ultraweak solution found for Hex because of some logical reasoning.

Like any solution, it still needs to be proven. By definition, you have not ultraweakly solved anything, as you haven't provided a rigorous proof. Ultra-weak is a detail in that it only needs to be from startpos and doesn't need to provide an algorithm for perfect play.

One can claim that
there's still no 100pct mathematical rigorous proof (that it's a draw) but at least i'm trying to use logical
reasoning. Just as logical as when i would claim the earth isn't flat or water usually is wet.

One should claim that it isn't remotely close to a proof. A game being solved is a well-defined, mathematical thing. It is absolutely different from claims of "water is wet" (seriously?!?).

(which often works different for me being a rather creative person than for an average math bloke, i guess)

As an aside, the process of inventing complex proofs requires extraordinary amounts of creativity. Putting yourself on a pedestal of creativity compared to your "average math bloke" isn't a good look.

It is difficult to take stuff like this seriously when you don't seem to realise the standard that is required for a game to be considered "solved" in any sense.

[jefk]

jamie whiting wrote

Putting yourself on a pedestal of creativity compared to your "average math bloke" isn't a good look.

considering your reaction to my comment about water is wet demonstrates you don't see how i'm using
complexity theory to arrive at my conclusion(s). It's a matter of emergence, and a drawish nature
for balanced games is matter of emergence, whereby the rigorous math requirements of 'solving' like
you are referring to are superfluous. Having been educated in physics and not pure math may
be a reason i'm able to make such thought jumps, this is not putting myself on a pedestal, it's
simply discussing some narrow thinking in the current mathematical foundations of game theory
(whereby i expect this in coming decades will become more clear). When i referred to the Principia
Mathematica Bible this also was an ironic comment ofcourse as it's known that the Dutch mathematician
Brouwer severely criticized this work by Russell, and nowadays it's considered to be outdated.

As for me claiming to have a proof (for an ultraweak solution), if you would read accurately enough
through the reference i gave for abductive reasoning, you could point out that such reasoning is
usually not giving such 'proof's. quoting from the wikipedia article :

Abductive reasoning, unlike deductive reasoning, yields a plausible conclusion but does not definitively verify it.

Yet personally i believe that i'm on the right track, and besides using arguments as cumulative evidence
and abductive reasoning, for me it's clear that by now we know (from the starting position plus rules
plus some logical reasoning) that chess is a draw thus an 'ultraweak solution' (UWS).
The definition of this has been debated here previously with syzygy (look it up) and we didn't come
to any firm conclusion (except that this UWS idea was an ad hoc definition briefly posed in one sentence
in a very broad Phd dissertation discussing many topics regarding computer games and game theory;
and later quoted by prof vd Herik as if it was a (new) definition in some math Bible whether Principia
Mathematica, Fundaments of Game theory by Johnny von Neumann or otherwise; ridiculous, ofcourse.