Is there any project coming to solve chess?

[towforce]

1) if there is a forced win then there must be winning strategy (Zermelo)
2) but there is no winning strategy (Mcts and/or Chinese database with minima
3) So if there is no forced win for White then it's a draw

Only point 2 above is not 'rigorous' according to the math purists. However, i claim that if
there is a winning strategy, then a solid Mcts search would increase after time the indication of winning chances. In chess it doesn't.
Only thing to remain, 'prove' that the Mcts search which we use nowadays (eg in shashchess or Lco)
is solid. Well imo it's evident, while likely still some things could be improved on the Mcts
search, it's already by now is fit for purpose. Requiring to Prove it in a rigorous mathematical sense
would be imo almost just as ridiculous as proving the syzygy bases are correct.

Excellent! I believe I understand the evidence clearly now.

I have a question. Assume that a winning strategy exists: ShashChess and LC0 clearly don't know this strategy. This matters because they therefore might not recognise an improving position when it's presented to them, right?

[Uri Blass]

1) if there is a forced win then there must be winning strategy (Zermelo)
2) but there is no winning strategy (Mcts and/or Chinese database with minima
3) So if there is no forced win for White then it's a draw

Only point 2 above is not 'rigorous' according to the math purists. However, i claim that if
there is a winning strategy, then a solid Mcts search would increase after time the indication of winning chances. In chess it doesn't.
Only thing to remain, 'prove' that the Mcts search which we use nowadays (eg in shashchess or Lco)
is solid. Well imo it's evident, while likely still some things could be improved on the Mcts
search, it's already by now is fit for purpose. Requiring to Prove it in a rigorous mathematical sense
would be imo almost just as ridiculous as proving the syzygy bases are correct.

Excellent! I believe I understand the evidence clearly now.

I have a question. Assume that a winning strategy exists: ShashChess and LC0 clearly don't know this strategy. This matters because they therefore might not recognise an improving position when it's presented to them, right?

The fact that comp-comp games are draw in many different lines is a strong evidence that chess is a draw.

It is not only that white is not able to win but that even if white is allowed to forbid black to play 3 different moves of his choice at move 1 then white cannot win.

[towforce]

1) if there is a forced win then there must be winning strategy (Zermelo
2) but there is no winning strategy (Mcts and/or Chinese database with minima
3) So if there is no forced win for White then it's a draw

Only point 2 above is not 'rigorous' according to the math purists. However, i claim that if
there is a winning strategy, then a solid Mcts search would increase after time the indication of winning chances. In chess it doesn't.
Only thing to remain, 'prove' that the Mcts search which we use nowadays (eg in shashchess or Lco)
is solid. Well imo it's evident, while likely still some things could be improved on the Mcts
search, it's already by now is fit for purpose. Requiring to Prove it in a rigorous mathematical sense
would be imo almost just as ridiculous as proving the syzygy bases are correct.

On further thinking, I'm also going to ask about part 1 of the evidence:

"if there is a forced win then there must be winning strategy (Zermelo)"

Can you explain why this must be so in a clear and concise way, please?

My problem is this: based on the evidence, I believe that it's likely that relatively simple underlying patterns exist for evaluating chess positions accurately most of the time. However, I know that I haven't proved this, and that I might therefore be wrong. If I am wrong, then (assuming that chess is a win for white) the winning strategy is going to be extremely complex: probably too complex for an MCTS to discern - or to discern from the Chinese database. An MCTS is just not going to be lucky enough to hit the strategy consistently enough to show the kind of improvement you're looking for - and it won't be obvious in the Chinese database.

[syzygy]

i've noted your Ad Hominem remark that the concept of a mathematical proof eludes me. Maybe i should report it (*).

Go ahead, but if you believe that is an ad hominem attack, then you are mistaken. (I guess the previous sentence is also an ad hominem attack?)

In the meantime, apparently verbal, semantic logic apparently eludes you. Point is, as long as there is no clear definition of what ultraweak solving of game as chess should be, there -at least imo- is no need for a rigorous math proof

There is a clear definition: a mathematical proof that the initial position is theoretically drawn (or won for white or won for black).

For many things in reality you don't need mathematical proofs.

But if the definition requires it, then by definition you need a mathematical proof.

You are simply not interested in an ultraweak solution to chess. That is fine!

But because it's not a 'proof' it may never convince some the mathpurists/ number crunchers.

Indeed, if you do not have a proof, then you will not convince me that you have a proof.

To repeat what I have said before: whether chess is in all likelihood a draw according to the experts is an entirely different question from whether chess has been ultraweakly solved.

You are convinced that chess is a draw. I am not trying to argue against that.

We agree that chess being a draw (or a win for white or a win for black) has not yet been mathematically proven. So we agree that chess has not yet been ultraweakly solved. The two preceding sentences are equivalent.

Some math purists even stricter tyan you might also claim you did't solve the 7 men endgame theory, you just made some tables, who says there can't be some holes in these tables, can you Prove that ?

I have no proof of correctness of the generator program. At least the 3/4/56/6-piece tables were verified for consistency, but this does not conclusively prove that the positions classified as a draw are really draws (there could be some kind of cycle of mistakes that the verification method cannot catch). So far all mistakes that were reported were in the probing code and not in the tables themselves. But this is obviously not a mathematical proof.

If you have a particular position that is won or lost, then the tables can be used to generate a proof tree for the win or the loss. This proof tree could be verified by hand or by a simple computer program (e.g. a computer program simple enough that it can be formally proven to be correct). For draws this is more tricky.

In principle the generator could be proven to be correct, and the tables could be re-generated to rule out that bits flipped during the original generation (but I believe the 7-piece tables were all generated using error-correcting memory). While there is no formal mathematical proof, at least all the ingredients for a proof are there. The full computation was done, you just need to trust that the computation was correct (or verify the correctness of the generator). For chess from the initial position, no full computation was done, nor is this computation feasible with the resources available today or in the future.

[syzygy]

I think that even if some engine is a weak solution for chess then proving it is practically impossible today.

We agree on that. If we could prove it, then we could ultraweakly solve chess, and I do not believe that we can ever do that.

I do not know if stockfish at some 1,000,000,000 nodes per move is a weak solution for chess but even if it is not a weak solution for chess then I believe that we are very close to have a weak solution for chess simply because the draw margin in chess is relatively big,

I do not consider "1 mistake per 1,000,000 games" to be any closer to a weak solution than "1 mistake per 100,000 games". A weak solution cannot make any mistake, ever, no matter the counterplay. Given that the evaluation and search of any engine that plays chess at a few minutes per move will inevitably have holes, I do not believe that we are anywhere close to that. Draw margin has not much to do with that.

[syzygy]

"if there is a forced win then there must be winning strategy (Zermelo)"

Can you explain why this must be so in a clear and concise way, please?

If there is a forced win, then mini-max (or alpha-beta) gives you a winning strategy. (You will need to calculate all branches of the search tree until the end of the game.)

So Zermelo's result is trivial if you are aware of mini-max.
https://en.wikipedia.org/wiki/Zermelo%2 ... me_theory)

My problem is this: based on the evidence, I believe that it's likely that relatively simple underlying patterns exist for evaluating chess positions accurately most of the time. However, I know that I haven't proved this, and that I might therefore be wrong.

I don't see any reason why there should be simple underlying patterns (i.e. considerably simpler than calculating from the initial position to the end of the game). The rules of chess make it an interesting game for (many) humans, but these rules seem too arbitrary and chaotic to leave room for any nice underlying structure. Just think of en passant, castling, and pawn moves (and the 50-move rule). And even if you restrict to pawnless positions without castling and without 50-move rule, the possibilities are just too complex. Just think of such "simple" combinations of pieces as in KQvKR, KBNvK, KBNvKN, etc.

If I am wrong, then (assuming that chess is a win for white) the winning strategy is going to be extremely complex: probably too complex for an MCTS to discern - or to discern from the Chinese database. An MCTS is just not going to be lucky enough to hit the strategy consistently enough to show the kind of improvement you're looking for - and it won't be obvious in the Chinese database.

With this I agree. If white has a winning strategy, then it will be a narrow one.

[chesskobra]

There are a few points about MCTS and its variants that one should bear in mind before drawing even empirical conclusions.

(Quoting from https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) Pure MCTS converges to optimal play as the number of games played tends to infinity *in board filling games* like Go and Hex.... Although it has been proven that the evaluation of moves in Monte Carlo tree search converges to minimax *when using UCT*, ... etc.

(Now my rant.) So we should not simply accept simulations results of Lc0 or any other engine unless the engine is build to test algorithms (with known convergence properties) in their pure form.

Another issue is how would MCTS work if we were to track three or more states (e.g. W/D/L) as opposed to total payoff in N games. This will be relevant to the weights used in sampling. (This latter issue I have not looked into, but I will. But I suspect that this will be theoretically more challenging for proving convergence properties.)

Moreover, all these algorithms will have very poor convergence properties if the subtree consisting of forced win/draw lines is very small compared to the whole tree.

Question to jefk - you mentioned 55% and going down - what is 55%? If it is scoring rate (total payoff), then it is a combination of wins and draws (by white I presume). If so, then even if it goes to 50%, it doesn't mean anything. I would like to see an algorithm, with known convergence properties, that keeps track of W/D/L separately, and that shows that the D part goes up to 1. That will be some empirical evidence. Also, is it a coincidence that it is not 45% (white score) and going up?

[Uri Blass]

I think that even if some engine is a weak solution for chess then proving it is practically impossible today.

We agree on that. If we could prove it, then we could ultraweakly solve chess, and I do not believe that we can ever do that.

I do not know if stockfish at some 1,000,000,000 nodes per move is a weak solution for chess but even if it is not a weak solution for chess then I believe that we are very close to have a weak solution for chess simply because the draw margin in chess is relatively big,

I do not consider "1 mistake per 1,000,000 games" to be any closer to a weak solution than "1 mistake per 100,000 games". A weak solution cannot make any mistake, ever, no matter the counterplay. Given that the evaluation and search of any engine that plays chess at a few minutes per move will inevitably have holes, I do not believe that we are anywhere close to that. Draw margin has not much to do with that.

The draw margin is clearly important and with bigger draw margin it is easier to have unbeatable engine.

Imegine a game that I am going to call chessD
when the rules are the same as chess before one side mate the opponent but mate is not the end of the game.

The target of chessD is not only to mate the opponent and after you mate the opponent you are allowed to capture the king of the opponent and do not lose but you need also to capture all the opponent pieces in order to win(otherwise it is a draw).

The draw margin of this game is bigger relative to chess and it is easier to make some unbeatable engine in this case inspite of the fact that the number of legal positions in chessD is higher relative to chess.

[jefk]

about a (posssible) 'ultraweak solution'' (horrible term anyway because it's not so 'weak'):

syzygy wrote:
"There is a clear definition: a mathematical proof that the initial position
is theoretically drawn (or won for white or won for black)."

Really.. (?!?!!!???!? ).
So... who made this definition, where is it stated (except on Wikipedia or so which I dont
'regard as sufficiently credible (*) and by which people eg in the math world is it accepted.
So again for third time, please provide us with some credible references.
Simple as that.

You *might* be right with your definition, if sufficient scientists would agree about that definition;
but if it's only defined by eg. vd Herik or so then it's imo just a loose statement, not a definition.
here's the wikipedia entry
https://en.wikipedia.org/wiki/Solved_game
NB it states (for an ultraweak solution): a 'non-constructive' proof would be sufficient.
may be you also would disagree on that ? Then try to change the
wikipedi entry (and add a specific reference i suggest, which is currently missing)

Hint maybe it was stated in ref 1 of the wikipedia article :
Allis, Louis Victor (1994-09-23). Searching for Solutions in Games and Artificial Intelligence (PhD thesis). Maastricht: Rijksuniversiteit Limburg.
For you this ''definition'' almost seems like an axiom in math; imo it isn't .
Example: see this article by Jaap vd Herik (**)
https://web.archive.org/web/20170912011 ... 853d7b.pdf
Here on p 2 he states: "ultra-weakly solved" means that the game-theoretic value of the
initial position has been determined, as per terminology "proposed" by Allis(7)
Same ref again, a Phd thesis (no big deal). And using words as "determined" (not "proven") and "proposed
terminology" (which is not the same as well established 'definition' (as you are claiming)
Anyway, i've done some more work for you and here is this mr Allis (in wonderland?)
https://en.wikipedia.org/wiki/Victor_Allis
and here is his Phd Thesis (!)
https://web.archive.org/web/19970607124 ... hesis.html
Anyway he's not an assistant professor anymore
https://web.archive.org/web/19970606231 ... /home.html

So while we may have a to look at his thesis (which is not a math bible btw), my impression is that we could debate
ad infinitum in such way, and quite frankly i have better things to do; i dont care zip about whether it's Ultraweakly
solved or not; whatever it means For me, its 'essentially solved; and some discussions (about Mcts being
able to always(*) find a 'winning strategy' etc. wil only confirm this, I think.

(*) not always, but for the finite game of chess it's imo sufficient
(**) who is an applied mathematician (Phd in Delft) not a math purist
(or more politely, a theoretical mathematician( like you apparently

[jefk]

https://web.archive.org/web/19970607124 ... hesis.html