Is there any project coming to solve chess?

[jefk]

towforce you wrote:
"
"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? "

not yet (in clear and concise way) but here is a ref for you:
https://www.rasmusen.org/GI/reader/04a.zermelo.pdf

For the rest i'm (gradually) withdrawing from the discussion here (again)

[towforce]

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

I think you can make a case that chess is drawn by the legal definition of proof, which is "beyond reasonable doubt."

Unfortunately, however, there have been cases where defendants have been found guilty by this definition, sent to prison, and then later have been able to actually PROVE that they did not commit the crime (or that the evidence on which they were convicted was flawed).

[towforce]

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?

For me, that was a good and helpful post. Thank you!

[towforce]

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)

That is very helpful in the context of this discussion. Thank you.

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.

I need to give a long answer to this, but I have a tight schedule today, so with apologies I'm going to give quick answers which I know are unsatisfactory:

(1) chess's arbitrary rules (castling, en passant, pawn moves etc) are an impediment to finding simple underlying patterns - but only a minor one. I'll give 3 quick examples of complexity handled with simple algorithms (I could give you many more)

* The WWII Enigma encryption device had 3 wheels and a plug board (the "steckerboard"). The plug board was supposed to add complexity. The real problem, though, is the 3 wheels: the plug board adds so little extra complexity that it barely gets mentioned in most articles about the decryption of the device: once the wheels have been cracked, the plug board is just a quick/easy mathematical trick (quick/easy once you know it, of course! In WWII, Britain had a lot of quality people working on decryption)

* At a glance, human DNA doesn't even have enough code to build a lung. I'm not an expert, but it seems to be all about driving growth by picking the right simple pattern in the right location and then knowing when to stop. Then you can build a whole human from less DNA than one would expect to be necessary to build a lung (and unlike humans, most animals are born with complex behaviours built into their firmware: after a horse has been born, it will be up and running around in just a few minutes. Human babies also have these, but they're not so obvious as the horse's)

* fruit flies have a lot of complex behaviours: flight control, landing, finding food (no two pieces of food look the same), eating the food, finding a mate, mating - and many others. The complexities they face are FAR worse than chess's arbitrary rules. Yet they do all this with just 135,000 neurons,

(2) Sometimes, things you'd expect to add complexity to a problem actually simplify it. An obvious example is the reflection in the Enigma encryption device: it was supposed to make the decryption more difficult - but it actually made it MASSIVELY easier. This is true in general in encryption (yes - I know chess is not an encryption puzzle!): the skill of designing an encryption algorithm is to avoid patterns that are "easy" to find - but if you don't know what you're doing, adding to the encryption algorithm can very easily cause patterns to arise due to the convolution between the different parts of the algorithm

For simple games, humans usually find simplifying algorithms that enable the game to be played at close to the optimal level. Just because humans cannot find such algorithms for more complex games doesn't mean that they don't exist: they're actually very likely to exist. It's just that you cannot find them in the same way that you found them in the simple game.

I know the first thing I have to do: I have to demonstrate that I can build a polynomial that gives the correct evaluation for all positions in tic-tac-toe. That will be a "start".

[jefk]

Chesskobra

Lco on Nibble gives w/d/l, in parts per thousand, example, it starts with (approx) :

1.e4, pct WDL (ppthsnd) 333 440 227 (55.3 pct combined)
1.d4 WDL 328 450 222 (55.3 pct combined

And i leave it to a faster computer (with fast GPU) to continue such a search.

The combined pct indicator (55.3) nowadays is an estimate of expected game score according to this ref:
https://lczero.org/blog/2020/04/wdl-head/
And for 100 pct draws -as i expect in the end- it should go down from 55. to 50.00. Unfortunately-
(for the rigourness of my arguments) this percentage (55.3) is going down in (weak) waves
For example it may go down to 55.1 then slightly up again after a few mins to 55.2 (but usually
not higher than the then the previous max) and then down again to 44.9 etc. Similar with
Shashchess Mcts the combined indicator clearly goes down from 55 pct relatively
fast (on my comp 6 thrds) to eg 53 pct, and then most likely to 50 pct. So imo
these 'weak'' diminishing waves don't matter, in the end it will approach 50 pct (draw)

[jefk]

Towforce you wrote:

"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?"

No i don't think so, in fact I think this would be highly unlikely.

you also wrote:

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

Again I (tend to) disagree; MCTS is looking deeply (with Shashchess until the endgame in some situations and
in more situations if you let it search for longer times), and would find a winning strategy if there would be one
(but there isn't). The Chinese database is confirming the results; its is not only SF on one position, it is a deep
database which has been minimaxed. This is imo an almost as solid indication as a pure Mcts search
on a strong comp (or preferably a supercomp in GPU terms ) would be.

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

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

Not if all we need is a position where SF blunders away the draw. You just need a single line where SF misses a crucial variation or severely misjudges the position. SF may be able to hold the vast majority of positions that evaluate to -0.5 or whatever, but this is pretty much meaningless if we are talking about an engine being truly unbeatable.

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.

I think your game is less drawish since you have abolished stalemate.

[jefk]

Syzygy wrote:

"If white has a winning strategy, then it will be a narrow one."

very narrow imo, something like 1 divided by 10^20. But there only are 20 openings positions, so such a winning line
cannot exist (proof by contradiction). Example, let's assume a move as 1.b3 would be the beginning of a 'winnning line'
But then subsequently it also should always win against all subsequent possible -good- responses by Black , (five or six or so).

Other argument the move 1.g4 with minus 150 in the chin database is maybe a relatively narrow tree indicating
it's -probably- a losing move; But for the other moves we all get 0.0 in the Chin base, and there's
no move (eg 1.b3 or whatever) that indicated eg. a 1.00 for a.b3 or whatever.

PS you earlier wrote that in your opinion it's likely that there is a winning linend i would be the ideal person
to find such line(s). Brief -superfluous- answer: in the past i tried that, of course, but found out there simply isn't
such a line, not in the least because of the relatively high drawing margin in chess with the current rules.
NB after more analysis we cannot even find a 'best' (opening) line, but that's another subject.
The Chinbase isn't so good in this respect because you have to look at the nr of possible good responses
after a specific opening move, eg. after 1.a3 there are many solid responses for Black, but after 1.e4 or 1.d4
there only are about 2 or 3 solid responses (depending on your definition of 'solid') .

Ask chess GM Avrukh, prolific author of the GM repertoire series (Quality Chess). At first he wrote a (paper)
book about -mainly- the Catalan but lateron it was found that after Bb4+ (Bogo style) and a later c6 and
then b6 there's no fundamental advantage anymore. Then he wrote another Gm repertoire 1.d4 book,
now with the Semislav; like d4 d5 c4 c6 Nf3 Nf6 e3 Bf5 (or d4 Nf6 c4 c6 Nf3 d5 e3 Bf5) but as you can
see in the Chinbase in this 'positional line in the end White cannot maintain the (tiny) advantage.
Besides that, Black can avoid this line going for anti-Meran Slav (first ...e6 instead of c6) or Gruenfeld.
And the move 1.e4 also doesn't lead to a (tiny) advantage, not even in the GM repertoire series,
but then you have to check multiple books. Similar for 1.c4 or 1.g3 (and the rest is worse, with 1.g4 as
worst of all). So i presume by now the GM's know that searching for winning lines is a futile exercise;
Dutch opening book maker (eg for TCEC) has the same (or similar) opinion according to his
words in the latest magazine of the Dutch computer chess association (CSVN). CSVN magazine nr2
November 2023 p 21 (when talking about the Rebel(16.2) opening book.

[syzygy]

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.

Well, this is the definition that everybody accepts, and that alone makes it valid. The recent Othello paper (which is the reason for this thread) uses this definition. Indeed it comes from the PhD thesis of Victor Allis (who mentions that Paul Colley suggested it, but he did not give a reference).

There is no law of nature or logic that prescribes that "ultraweakly solved" has a particular meaning, but people interested in "solving" computer games have agreed on this term as a shorthand for "we have solved the game in the sense that we have established with certainty the game-theoretic value of the initial position".

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.

Any definition was defined by someone. The Othello guy accepts this definition, the Chinook guys accept the defintion, Allis and Van den Herik obviously accept the definition. When academics talk about a game being solved, they need to be precise about whether they have solved each position or just the initial position, and whether they have an actual winning (or drawing) strategy, and then it helps to agree on terminology. So this is just about language. You can choose to speak a different language, but then communication breaks down.

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)

Why should I disagree? It confirms that what is needed is (mathematical) "proof", not just (numerical) "evidence".

Many mathematical proofs are non-constructive. I can prove that any prime number p of the form 4n+1 is the sum of two squares p = a² + b² without coming up with a way to find a and b.

It seems unlikely to me that a non-constructive proof of the initial position in chess being a draw is possible, but I cannot prove that no such proof exists.

[syzygy]

PS you earlier wrote that in your opinion it's likely that there is a winning linend i would be the ideal person to find such line(s).

I was talking about a winning line against a deterministic engine.
Indeed I am convinced that if someone picks a deterministic engine (e.g. by limiting SF to 1 thread, a fixed number of nodes per move, a fixed size of the TT, etc.) then you will quite easily find a winning line. That winning line will work only against that particular engine.

Brief -superfluous- answer: in the past i tried that, of course, but found out there simply isn't such a line, not in the least because of the relatively high drawing margin in chess with the current rules.

But when you know that the opponent uses a particular fixed opening book, would you not be able to find a line that gains an advantage against that book?

A deterministic engine is basically a very large opening book with one move for each position. Being deterministic is a huge weakness.