Is there any project coming to solve chess?

[syzygy]

first you have to define more rigidly, what is (or what you mean with) 'solving' a game (like chess).

Good poinmt. I think most people wanting to see chess "solved" would at least for a short moment be happy with a conclusive proof that the starting position is a draw (or win for white or a win for black).

For the math purists, the accurate term should be, that it's (almost?) ultraweakly solved.
https://en.wikipedia.org/wiki/Solved_game

That is the correct term, but we are nowhere near ultraweakly solving chess.

So for all practical purposes, it already has been solved.

Just as, for all practical purpose, pi is a rational number.

[Uri Blass]

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.

[jefk]

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

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.

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.

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'.
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)

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)

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)

PS it's easy to make strong statements like 'chess will never be solved'etc, in the past there was someone who claimed chess will never be able to beat grandmasters, nowadays there still are people claiming we never will have AGI, and so on, and so on. An IBM director made a claim computers will never be popular (for at home use), and there was someone who claimed airplanes will never be able to fly (because they are heavier than air).
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 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

[carldaman]

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

[chesskobra]

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)

Is this an argument given by AI? The argument given there makes no sense mathematically even though it uses some terms like topology, DAGs etc. It is just hand-waving. One test of such arguments (and for that matter many arguments in mathematics as well) is asking questions like why the argument does not apply to some other game in which one side has winning strategy? In other words, what is specific to chess in that argument?

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)

Strategy stealing arguments are subtle and prone to be misused. Take a look at the strategy stealing argument for Hex in some book, and ask questions like why it doesn't work for some other game? What stops the second player from stealing the first player's strategy? to really understand the arguments and assumptions made.

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)

This is mixing mathematics (e.g., Zermelo's theorem) and pseudoscience like advantage measured in pawns. The pseudoscience may be useful to create good computer programs, but it is not useful in maths.

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

If there is a mathematical proof, it will be accepted. People debate endlessly about whether 0.33... = 1/3 or not because they do not want to know any proper mathematical definitions. It is not an equality in the algebra of rational numbers. One side is a series, we have defined what is convergence of a series, limit of the sequence of partial sums, and so on. Then we only use a notation (if we really require it) to represent a certain series by 0.333... and its limit by 1. So mathematicians don't have any debates about such things. These are debates in high school maths created by people who do not know much maths.

[smatovic]

...maybe we need something new for this task, "Hyper-Turing-Machines"?

Hypercomputation
https://en.wikipedia.org/wiki/Hypercomputation

Computing with "qu-infs" with infinite superpositions?
https://en.wikipedia.org/wiki/Hypercomp ... tum_models

I forgot, but there was some kind of "qu-inf" calculus mentioned, in contrast to current qu-bits based on quantum-gates.

--
Srdja

[Jouni]

My post was inspired by othello paper. It predicts chess to be the next solved game. Checkers was solved 2007 and othello 2023. So chess 2039 ?

[jefk]

chesskobra, you sound like a mathematician, ok; but I wonder
how long is your experience with computer chess (if you refer
to a project as the Chinese dastabase as 'pseudoscience').
Sure years, ago a centipawn advantage (for the first move) didn't
mean much, but we have progressed a lot nowadays. I presume you know about
the chess project by Alfazero, and then the Nnue engines. Ergo (cp) scores can be converted to a statistical expectation, and the 0.0 (backsolved!) score (except for 1.g4 or possibly 1.f3 etc) from the Chinese database
strongly indicate a 100 pct draw expectation (ideally engines
should indicated a w/l/d expectation but that's another matter).
With alfabeta you don't hit the egtb scores, agree, but presume you
also know about MCTS (Monte Carlo) search methods ? Under certain conditions this search (as Alfazero and Leela use) is equally good (or even better than) alfabeta. And.. in such a way we certain can hit the endgame bases at least for some percentage of the lines, usually the most relevant lines.

Then some other points: yep the topology story was by (Claude)
AI, and indeed i think it was partly hallucinating; although apparently Conway around 1970 already talked about topology and game theory; and graph
theory may certainly be of interest when thinking more deeply about the game of chess ( and it's gameplay, rules, and outcome). That a strategy stealing
argument doesn't work for chess I also accept, but then I do believe there is a strategic equilibrium and such an argument may possibly be used later on in a more sophisticated 'proof' (that chess is ultraw. solved).

Someone wrote that if there would be such a (sophisticated) proof,
it would be accepted; well not in this forum, is my impression, at least
not by all of us. Some will simply insist on brute calculation
with alfa-beta, in the old checkers/Schaeffer way; but this
is not going to happen, ofcourse, and imo also isn't needed.
But computational assistance will be useful, although also
not always accepted by math purists, i guess. The claim
that Othello has been solved was made by a (bioinformatics)
computer scientist, maybe also as some marketing stunt (for
this Japanese) netwok/supercomputer company):
https://arxiv.org/pdf/2310.19387.pdf
https://www.discovermagazine.com/techno ... of-othello
Not really a game theorist, but personally i do accept the result.

For chess, the evidence nowadays imo is overwhelming that chess is
a draw. And i could think of a team of people (*) writing a paper that chess has been ultraweakly solved and the outcome is a draw. Alfazero, combined with Zermelo's theorum and practical research, testing is not pseudoscience.

(*) eg. someone from the Chinese database project, someone from Deepmind (eg Hassabis), with some guidance by some impartial computer scientists or practical game theorists instead of math purists nay sayers who will claim chess will 'never be solved'. Otherwise, i may well try to write an article myself, maybe not on arxiv, but on researchgate or so.

Mind you, i know about the philosophy of science, and there's more science than only math (where sometimes rigid proofs are required, to
determine if a conjecture is really true). In physics, if there is an established theory e.g. quantum elektrodynamics, all you can do is try to falsify it (Popper); if you can't falsify it, you can assume the theory is good enough for all 'practical purposes' (QED has been shown to be in agreement with quantitative experiments) to some thirty decimals);
chess btw is only a game, not of infinite length (as e.g. pi) and
we also don't have to argue whether 1/2 +1/4+1/8 etc is 0.999999...
or can be assumed to be 1.0000... That's secondary school math, I
agree, and in a similar way demanding all kinds of game theoretical
nittygritty by math purists for ultraweakly solving a relativly simple and obviously 'balanced' (**) game of chess is imo impractical, unscientific, unreasonable.

(**) 'balanced' for White vs Black wrt the outcome. But if there's not first win for White, then the result must be a draw. Thus we only need a proof the game is 'balanced' . well all modern computational efforts in this respect are showing the game is balanced, this is almost as clear and solid
as the datacrunching efforts of Shaeffer (checkers) and Takiwaza (Othello)

[Dann Corbit]

Re: "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"

Everyone already thinks it's probably drawn. That has nothing to do with proving it. Is is possible that every human on earth could be convinced chess is a draw, but for it not to even be weakly proven.

Heuristic evidence is never a proof unless it is utterly exhaustive.

If we found a large planet entirely populated by birds we named quiggs, then examined of one trillion of then, finding every single one to be white and male is not a proof that all quiggs are white or that all quiggs are male.

We may likely think it true, but it's not a proof. If we examined every single one and had a way to prove we examined them all, that could be a proof, assuming that they are not capable of changing sex or color.

[Dann Corbit]

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.