Is there any project coming to solve chess?

[syzygy]

I don't think it's impossible.

I do think it is impossible. I suspect that a minimal proof tree to show that black has a draw starting from the starting position is too large to store and verify. The branching factor is just too high. (That SF has an effective branching factor <2 is meaningless in this context.)

So even if you have an oracle that spits out the best move for black in each position in less than a nanosecond, you woudn't be able to verify the resulting proof tree before, say, the sun runs out.

You do not need a chess tree in order to prove for every draw that it is a draw and there are positions that you can prove that there are draws by other ways(for example fortress positions but hopefully not only fortress positions).

I can prove many draws without a tree and for example I can prove KB vs K is a draw even in 1000,000,000*1,000,000,000 board when tablebases are too big to generate.

In order to solve chess we need to work about a static evaluator that does not search a tree and evaluate win draw loss with a proof for many positions.
Using this evaluator the proving tree in order to prove a draw is going to be significantly smaller.

I do not believe that chess allows for enough of such shortcuts for them to make any meaningful impact.

I am not saying that I can "prove" that chess cannot be solved. I am just claiming that chess cannot and thus will not be solved, not even ultra weakly, by mankind in the remaining time that earth can sustain human life.

[jefk]

chesskobra wrote
the game theoretic value of the initial position has been determined", which is not the case of chess

that's your opininion, that it's *not* the case of chess.
Imo the game theoretical value of the initial position has
been established (via various methods) to be 0.0
so it's a draw (with imo 100 pct certainty, i have various
arguments for that which combined imo are enough to show
chess has been ultraweakly sovled but not going to post that here
(because then some people will still say it's not a 'rigorous proof'etc.

For the rest i'm more in line with the suggestion(s)
by Peter Osterlund (and not of syzygy).
question to syzygy: do you accept that Othello has been ultraweakly solved ?
As for building a book from the initial position, again, look
at the chinese database, it found important results, eg.
that 1.g4 is a bad move; it also clearly indicates a draw for
all sound opening moves as e4, d4 Nf3 and c4
(yes with imo 100 pct certainty; ofcourse it could be better,
Mcts instead of SFnnue, large/deeper book etc etc
But it wouldn't change anything from the conclusion (draw)

As for methods P.O. is suggesting various of such exercises besies the chinese
database already have been done eg. via (top)correspondence chess.
Here's the current world championship
https://www.iccf.com/event?id=100104

jef

PS here's a recent game i played on the ICCF server
https://www.iccf.com/event?id=101454
1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.d3 Bc5 5.c3 d6 6.a4 a6 7.Nbd2 O-O 8.O-O Ba7 9.h3 Ne7 10.Re1 Ng6 11.d4 c6 12.Bf1 Re8 13.Bd3 h6 14.Bc2 Qc7 15.Nf1 Be6 16.Be3 Rad8 17.Ng3 Bb8 18.Qb1 d5 19.exd5 Bxd5 20.Bxg6 Bxf3 21.dxe5 Rxe5 22.gxf3 fxg6 23.Qxg6 Rde8 24.Bd2 Rxe1+ 25.Bxe1 Rd8 26.c4 Qf7 27.Qxf7+ Kxf7 28.Bc3 Rd3 29.Kg2 Nd7 30.Ne4 Be5 31.a5 Kg6 32.Rb1 Kf5 33.Ng3+ Kf6 34.Ne4+ Kf5 35.Re1 Bxc3 36.bxc3 Nf6 37.Nc5 Rxc3 38.Nxb7 Rd3 39.Nc5 Ra3 40.Nxa6 Rxa5
In the end, i have one pawn more (in a double pawn situation), but it's a draw.

With modified endgame rules for ICCF I (or others with one pawn extra in the endgame) could get eg. 0.6 points in such a situatio instead of 0.5 rewarding my extra pawn witn 0.1, but then tournament software should be improved making such scores 0.6 instead of 0.5 possible
(although that's another topic again, of course)

[petero2]

The quote from Nowakowski (which in turn comes from Allis, "Searching for Solutions in Games and Artificial Intelligence) also contains the clause "assuming reasonable computing resources". It seems difficult to precisely define "weakly/strongly solved" in a meaningful way that excludes a provably correct minimax algorithm that takes 1e1000 years to run on current hardware.

However, I thought it would be more interesting to discuss my proposed informal definition of "weakly solved in practice". It seems to me the minimum requirement to make such a claim is to provide a chess playing entity that no one is able to beat from the starting position no matter how many times they try. I thought it would be interesting if someone that claims that chess has been "weakly solved in practice" would explain what this alleged chess playing entity would be.

[syzygy]

yes syzygy, for practical purposes (eg. in physics) we can regard pi as a rational number; in physics numbers are not infinitely long.

And I am not a physicist but a mathematician. In mathematics, a proof has to be fully rigorous. The term "ultraweakly solved" refers to mathematically proving that the starting position is a win, draw or loss for white. Overwhelming numerical evidence is meaningless.

As for a proof that pi is irrational, such proofs have been stated with reduction ad absurdum arguments (eg. Chudnovsky); if you think that is insufficient proof, and for a real 'proof' you want to calculate all decimals of pi to infinity, well good luck.

The Chudnosvky brothers have calculated very many digits of pi, which has nothing to do with a proof. That pi is irrational was proven by Lambert in 1761 by giving a rigorous argument.

As for chess, there is a reductio ad absurdum argument, namely, that if White despite have a little first move advantage) cannot win, then it must be a draw. Think of balanced games where the first moving side can only win if the second side (Black) makes a mistake. It's becoming more obvious every year, that chess is such a game.

Nothing to do with ultraweakly solving.

Thus, i doubt that for ('ultraweakly') solving a game, in all situations you have to calculate all (or most) variations from opening to endgame, like was done for checkers. I don't exclude the possibility that a brilliant game theorist in a few years will claim there's a proof that chess is in some way is a solved game and it's a draw. Then there's not need for an 'ultraweak' (calculated) 'proof'.

There are games that can be proved to be a win or a draw by a clever argument. I am very confident that chess is not such a game.

In chess, it is far more likely that white has a very ingenious winning strategy that is completely overlooked by humans and engines than that chess allows for some very ingenious "short" mathematical argument that proves it to be a draw. But I cannot mathematically rule out either possibility, so I cannot prove that chess is a draw, and I also cannot prove that chess will never be proved to be a draw. But I can claim that chess will not be ultraweakly solved just as I can claim that chess is a draw.

Besides the reductio ad absurdum argument (according to AI):
1)Topological proof: Chess has been proven to be a drawn game topologically based on properties of the graph of legal positions/moves under the no-repetition rule.
(Note checked the above, as it was unknown to me &unlikely;
see this for further info, it's above my current knowledge
https://poe.com/s/BTWfJWAl5SsvNv8CTeuq)

This is just nonsense. By the same non-argument, any chess position is a draw.

2)Strategy-stealing argument: If White could force a win, Black could emulate White's optimal moves and obtain at least a draw, a contradiction.
(note this is stated a bit too simple, imo, but it's clear that there's a strategic equilibrium in the game of chess)

Does not work for chess.

If chess allowed null moves, then you can prove that white cannot lose by a strategy-stealing arugment. Because if you assume black has a win, then white can steal black's winning strategy by playing a null move first (contradiction, so black has no win).
But obviously chess does not allow null moves.

2) Minimal winning margin: No line of perfect play has yet proven White can build an advantage beyond the 0.5 pawn margin indicative of a draw at highest levels.
(note this is true, and again, this makes it very likely there's not winning strategy for White, thus, applying Zermelo, it's a draw)

Anything that relies on "0.5 pawn margin" is not a mathematical proof.

PS it's easy to make strong statements like 'chess will never be solved

Sure, but I know what I am talking about and I am very confident that I will not have to eat my hat. So I am not talking about anything that convinces you that chess is draw, I am talking about a mathemtical proof. I am confident that the only way to prove chess is a win or a draw or a loss is by such huge amounts of computation that we simply lack the resources (including time).

I agree with you that chess very likely is a draw, and this only strengthens my confidence. Computationally it is much easier to prove a win than it is to prove a draw.

Don't make claims about things you don't know, rather say you suspect something (will turn out to be such and such in future, or not).

I see no problem with making claims. If in a few years or decades someone comes with a mathematically sound proof (an actual proof, not a bogus crackpot proof), then I will happily admit that I was wrong.

I suspect that in a few years it will be acknowledged by most game theorists that chess is a draw, and that 0.33333333333333 ad inifitum is 1/3
and that 1/2 + 1/4+ 1/8 + 1/16 etc is one aka 1.0000

No chance. Game theorists are not interested in numerical evidence. Game theory is not physics. "Ultraweakly solving" means mathematically ultraweakly solving.

[syzygy]

Pi can be closely approximated by the 22/7 ratio.

I remember that my teacher in elementary school explained that pi was "immeasurable" because the decimal expansion of 22/7 kept repeating.

[syzygy]

I don't think it's impossible.

I do think it is impossible. I suspect that a minimal proof tree to show that black has a draw starting from the starting position is too large to store and verify. The branching factor is just too high. (That SF has an effective branching factor <2 is meaningless in this context.)

So even if you have an oracle that spits out the best move for black in each position in less than a nanosecond, you woudn't be able to verify the resulting proof tree before, say, the sun runs out.

I don't think that Moore's law will ever run out. New technologies will be invented as they always have been. Chess is obviously exponential, but so is the advancement of computational power. I know it looks absurd, but what computers can do today would seem absurd twenty years ago.
I remember when pi was first computed to a million digits. Look at the shape of this graph:
https://en.wikipedia.org/wiki/Chronolog ... _of_%CF%80
I tend to agree with Ray Kurzweil that all technologies advance exponentially. I know there are huge problems in storage and computation, but I think that things that are impossible today will not remain impossible. Perhaps a 64 qbit quantum computer with a suitable algorithm can solve it in a few minutes. There are of course other possibilities and it may never be formally proven. But I am not sure of that yet.

There are laws of nature that most likely cannot be broken. As far as I understand, quantum computers are not of much help for the problem of verifying a minimal proof tree.

[Ajedrecista]

Hello:

Some definitions of ultra-weakly solved, weakly solved, strongly solved... can be found in this thread. Without any commitment, I want to share the references of these terms that are contained in the great book One Jump Ahead. Computer Perfection at Checkers. Revised Edition by Jonathan Schaeffer:

Chapter 24 "As Good As God" (page 430):

[...] Games where we know the perfect-play result but don't know how to achieve it are referred to as ultra-weakly solved.

Chapter 24 "As Good As God" (page 430):

Weakly solved games are those where the perfect-play result is known (Connect Four is a win), and a strategy for achieving that result from the start of the game is also known (you have the winning sequence of moves). In other words, you cannot set up any legal Connect Four position and get the perfect-play result; only those positions in the proof. Other weakly solved games include the Asian game of Gomoku (first player win) and the European game of Nine Men's Morris (draw).

Chapter 24 "As Good As God" (page 432):

Games where perfect information is known for every legally reachable position are called strongly solved. Chess and checkers endgame databases can be considered to be strongly solved: put any legal combination of eight or fewer checkers pieces on the board, and CHINOOK can tell you the result.

Chapter 28 "I Know I Can't Lose" (page 505):

Another issue was the notion of weakly solving the game. Many reporters didn't understand this concept and erroneously reported that we had solved every possible checkers position. Several people accessed our proof on the web and were mystified that they couldn't set up an arbitrary checkers position and get the proven result back. People had difficulty in understanding that a proof didn't imply an exhaustive enumeration of all possible positions.

I hope these references can be useful to all of you.

Regards from Spain.

Ajedrecista.

[syzygy]

For this definition to have practical value, it must be possible to run the entity on existing hardware in a reasonable amount of time, just as the mathematical "weakly solved" definition specifies that the algorithm must be possible to run on existing hardware in reasonable amount of time.

Mathematical definition doesn't say anything about existing hardware or reasonable time. https://en.wikipedia.org/wiki/Solved_game

That Wikipedia article contains the following text:

Given the rules of any two-person game with a finite number of positions, one can always trivially construct a minimax algorithm that would exhaustively traverse the game tree. However, since for many non-trivial games such an algorithm would require an infeasible amount of time to generate a move in a given position, a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time.

Whether that is part of the definition or not is debatable, but without such a rule, it can be claimed that chess has already been strongly solved by the mini-max algorithm, but that no one has bothered to execute the algorithm yet.

This is about weaklly and strongly solving, which requires providing an actual strategy to win (or draw). "Weakly solving" and "strongly solving" are indeed not fully mathematical concepts but include a practical component.

For ultraweakly solving a game, all we need is a mathematical proof that the game is a win for white (i.e. white has a winning strategy), or that the game is a win for black (i.e. black has a winning strategy) or that the game is a draw (i.e. both sides have a drawing strategy). Such a proof together with a trivial minimax program would in principle also give a weak solution, but not a usable one.

I would say weakly solved presupposes that the game has been ultraweakly solved: we must know in advance what the outcome (with perfect play) will be.

For a strong solution this is more tricky since there will usually be too many positions to tabulate all outcomes. I guess for a strong solution we need an algorithm that, given a position, outputs the (provably correct) game-theoretic outcome of the position within a "reasonable" time.

[Peter Berger]

In chess, it is far more likely that white has a very ingenious winning strategy that is completely overlooked by humans and engines than that chess allows for some very ingenious "short" mathematical argument that proves it to be a draw.

This is certainly true, but I’d go much further.
We don’t even know the theoretical game result.
All the draws make people overlook how narrow the path to equality has become at the same time
Does anyone know a clear way to equality for black after 1. E4 c5 2. Nf3 d6? I don’t.
So what is left to break? The Petroff, the Marshall, the Berlin, maybe some Kan or Sveshnikov Sicilian – these look difficult to win against right now . But this is not that many lines.
Uri Blass is the only one here who dared to make an absolute claim like: you can’t beat Stockfish at 1h/move on some computer – my intuition tells me that I’d make a good bet on Stockfish thinking for 100 hours , or in other words: chess is far away from being solved IMHO.

[syzygy]

chesskobra wrote
the game theoretic value of the initial position has been determined", which is not the case of chess

that's your opininion, that it's *not* the case of chess.
Imo the game theoretical value of the initial position has been established (via various methods) to be 0.0

Only because you refuse to use the accepted definition of "ultra-weakly solved". You are speaking a different language here.