Is there any project coming to solve chess?

[Jouni]

In TCEC they just played 4 very long games with SF and Lc0 (6 hour + 1 minute). All were draw within 32-34 moves! One difference SF starts with 1.e4 and Lc0 with 1. d4.

[Dann Corbit]

In TCEC they just played 4 very long games with SF and Lc0 (6 hour + 1 minute). All were draw within 32-34 moves! One difference SF starts with 1.e4 and Lc0 with 1. d4.

SF must be Fischer, who loved 1.e4
LC0 must be Berliner, who loved 1.d4
It turns out, they were both right.

[Leo]

No.

[Uri]

Solving chess is probably not possible in our lifetime.

You see this is just one of many things that today's technology is just not capable of doing but it could become very possible in a million years from today.

In a million years from now our computer technology could become like almost magical compared to what is available today.

This is why I think that today is a bad time to be alive and that's because many of our technologies are still in their very infancy.

But If I lived a million years into the future then I am sure that I could have been happier and more satisfied with life than what it available to me today.

[Dann Corbit]

I don't think it's impossible. Consider the perft using gpu cards that reached perft(15). Consider also that a move generator must know won-lost/drawn/undecided about every position it generates. GPUs become more and more powerful, and there is the AMD architecture that allows transparent memory access. An and/or proof search could be used to search and an internet full of absurdly fast GPU cards which could divide the work. Without any special eval code we already know won and lost and drawn. It's just the other nodes that need expanded. I don't know how efficient an and/or dfs proof search can be, but we can basically run at the speed of the move generator to get the data we need for searching. 8 man TB files would help close the other end by serving as an oracle. The big worries are, I suppose, that memory speed and disk speed do not advance exponentially like CPUs and software advanced. This performance wall is much more to be feared than the end of Moore's law because new technologies will allow more CPU advancements.
Quantum computing may be another avenue. There is already a quantum algorithm for search.

[jefk]

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

In mathematical game theory, a game is apparently only completely
'solved' if any imagineable position can be solved perfectly;
but then we get in the area of problem chess; this means in the
end we will get programs composing problems which will
be hard for other programs to solve perfectly;
a huge waste of time and resources imho (*)
and anyway not real chess but problem chess.

As for solving chess like checkers has been solved,
this imo is possible within a few years; it's already
clear that the outcome is a draw, there's no win possible
for White (there's only one bad move for White btw, 1.g4).
It would require sufficient connection(s) between
an opening base (such as the Chinese database) and
the endgame bases, to show a win for White indeed
is not possible; meanwhile results from eg. toplevel
correspondence chess and reasoning (Zermelo's theorem in game
theory) suggest chess almost has been weakly solved;
it's a draw.
For the math purists, the accurate term should be,
that it's (almost?) ultraweakly solved.
https://en.wikipedia.org/wiki/Solved_game

Well i don't care i must say about such terms.
It's clear now already that chess is a draw, So for
all practical purposes, it already has been solved.

PS most -even difficult problems in problem chess are usually
handled quite well by the top engines, then later in problem chess
you can think of composing harder and harder problems,
and long spiral of increasing futility; but also then you
don't imo have to solve such (immense theoretical problem
compositions) completely perfectly; it's for all practical
purposes sufficient to indicate whether it's a win (if score >3 or so)
or a draw. Anyway it would be another discipline, , i.e. not with
positions not normally a result of a well played game, thus like I
already wrote problem chess, not (the game of) normal chess.

(*) whereby I doubt btw whether 'quantum computing' would have
any added value in such exercises.

[Uri Blass]

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

In mathematical game theory, a game is apparently only completely
'solved' if any imagineable position can be solved perfectly;
but then we get in the area of problem chess; this means in the
end we will get programs composing problems which will
be hard for other programs to solve perfectly;
a huge waste of time and resources imho (*)
and anyway not real chess but problem chess.

As for solving chess like checkers has been solved,
this imo is possible within a few years; it's already
clear that the outcome is a draw, there's no win possible
for White (there's only one bad move for White btw, 1.g4).
It would require sufficient connection(s) between
an opening base (such as the Chinese database) and
the endgame bases, to show a win for White indeed
is not possible; meanwhile results from eg. toplevel
correspondence chess and reasoning (Zermelo's theorem in game
theory) suggest chess almost has been weakly solved;
it's a draw.
For the math purists, the accurate term should be,
that it's (almost?) ultraweakly solved.
https://en.wikipedia.org/wiki/Solved_game

Well i don't care i must say about such terms.
It's clear now already that chess is a draw, So for
all practical purposes, it already has been solved.

PS most -even difficult problems in problem chess are usually
handled quite well by the top engines, then later in problem chess
you can think of composing harder and harder problems,
and long spiral of increasing futility; but also then you
don't imo have to solve such (immense theoretical problem
compositions) completely perfectly; it's for all practical
purposes sufficient to indicate whether it's a win (if score >3 or so)
or a draw. Anyway it would be another discipline, , i.e. not with
positions not normally a result of a well played game, thus like I
already wrote problem chess, not (the game of) normal chess.

(*) whereby I doubt btw whether 'quantum computing' would have
any added value in such exercises.

I think that it is easier to have some unbeatable engine in chess then proving chess is a draw.

I am not sure if it will be possible to prove that chess is a draw in the next few years.

Chess engines are not designed to prove draws and 0.00 evaluation is not a proof of draw.
I know no chess engine that when I analyze position it say proved draw and stop to analyze because if you are sure the position is a draw there is no reason to continue to analyze.

Even in positions when I am 100% sure of draw I see no engine say proved draw and stop to analyze
I composed a position when I am sure it is a draw for the discussion and I can prove a draw because second best move has a mate score

1k6/1p2ppqr/6p1/Q7/7r/8/8/5K2 w - - 0 1

I guess that chess engines can also prove a draw even if I remove the rooks if they are designed to do it because black can probably force a repetition or tablebase draw or mate if white refuse to force a draw but no chess engine is designed to do it.

I would like to talk about percentage of solving chess from pgn (what is the perecentage of positions from pgn that engine can solve and say win draw or loss) but unfortunately programmers and testers are not interested in percentage of solving chess and the only thing that interest them is rating of their engine.

I see no ranking list of chess solvers to claim Engine A is leading with 22.1% and second place is engine B with 21.9% of solving chess.

[syzygy]

I fully agree that the output of an unsound searcher proves nothing, but the output can still be used to cross out unpromising lines. I remember from reading about the construction of the checkers proof that Chinook was used to "prove" certain positions to be a win or loss, e.g. if they evaluated to >+4 or <-4.

Might have been this paper: https://icga.org/icga/journal/contents/ ... -01-08.pdf

4.2 Proof Solver (back end)

Pseudo-code for the back-end prover is shown in Figure 4. It is a novel combination of a traditional heuristic alpha-beta search and a proof search.
The (cheap) heuristic search value is used to determine whether the current position is relevant to the current proof threshold. The (expensive) proof search attempts to formally prove the result of the current position. The latter is only done if the former indicates it is needed.

Each back-end position is first searched by an alpha-beta searcher using a heuristic evaluation function and the endgame databases. The search is limited to 25 seconds, reaching a depth of 17 to 23 ply plus search extensions. The heuristic value returned is compared to the search threshold. Values outside the threshold range are considered as likely wins/losses by the proof tree manager. If the heuristic value is more than twice the size of the threshold, then no further processing is done; the formal proof search is postponed until later in the proof when we will have more confidence that we really need this result.

I somehow managed to copy and paste the wrong link. The correct link is: http://webdocs.cs.ualberta.ca/~jonathan ... eckers.pdf

[syzygy]

It sounds to me like they search it anyway, but wait until it has to be searched, so a sort of delay queue.

I think only when they know it is necessary.

E.g. if the heuristic search suggests that in position P moves m1 to m5 are losing, but m6 seems to lead to a draw, then there is no need to invest time in a proofnumber search to confirm that m1 to m5 are losing. So while a heuristic search does not prove that a position is winning or losing (unless it happens to return a mate score), it can still help to cut branches that are less likely to contribute to a proof that a certain position is winning (or losing or drawn) and to find branches that deserve a better look.

[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.