Chess will never be solved, here's why
Sort:
ChessEnthusiast48
Jan 24, 2022
0
#141
If the term “chess will be solved” when two humans are involved, it is impossible. If that will involve two computers against each other, that would mean computers will always play perfect, and if that is the case, will always end in a draw between two computers. There’s too many possibilities in a chess position after just 7 moves (I have read 3,284,294,545 from another posting) and it increases further that it is impossible for humans to calculate, let alone play perfectly. With computers, that remains to be seen (who knows, I am not sure though).
#166
There are more than 3284294515 ways to reach just the position after 1 e4 e5.
That is because in chess there are so many transpositions.
They can move knights for 49 moves. Then white plays e3. Then they play knights, bishop and queen for 49 moves. Then black plays ...e6. Then they play knights, bishops and queens for 49 moves. Then white plays e4. Then they play knights, bishops, and queens for 49 moves returning them all to their starting positions. Then black plays ...e5.
The number of possible games is irrelevant.
It is the number of positions that counts: an upper bound is 3.8521*10^37.
https://arxiv.org/pdf/2112.09386.pdf
Of these the vast majority is irrelevant.
After 1 e4 all positions with a white pawn on e2 are no longer relevant.
After 1...d5 all positions with a black pawn on d7 are no longer relevant.
After 2 exd5 all 1.89 * 10^33 32-men positions are no longer relevant.
After 2...Qxd5 all 1.71 * 10^34 31-men positions are no longer relevant.
In analogy to how checkers was solved about the square root of legal positions is relevant.
http://library.msri.org/books/Book29/files/schaeffer.pdf
Jan 25, 2022
0
#143
tygxc wrote:
...
It is the number of positions that counts: an upper bound is 3.8521*10^37.
https://arxiv.org/pdf/2112.09386.pdf
...
That depends on whether the game is played under basic rules or competition rules.
In the latter case that should read 3.8521*10^39 because the ply count is then a relevant attribute of the position. The paper you link to ignores the 50 move rule, as is traditional.
(Under basic rules there are א₀ ways of reaching the position after 1 e4 e5.)
Jan 25, 2022
0
#144
tygxc wrote:
...
Of these the vast majority is irrelevant.
After 1 e4 all positions with a white pawn on e2 are no longer relevant.
...
Are these not already excluded from the estimate by the argument in your first link, from which your figure 3.8521*10^37 is obtained?
#169
No, 3.8521*10^37 is an upper bound for the number of all legal positions without excess promotions. As soon as white plays 1 e4 all positions with a pawn on e2 are no longer relevant.
#168
I do not believe the 50-move rule has as much importance as you attribute to it. In practical play the stalemate rule is much more important than the 50-moves rule. The AlphaZero paper shows almost the same high draw rate with stalemate = win. The existence of a hidden long win for white or even for black is like the existence of Martians: they always hide when we look. With more time or with stronger human / engine players the draw rate goes up, not down.
Jan 25, 2022
0
#146
tygxc wrote:
...
In analogy to how checkers was solved about the square root of legal positions is relevant.
http://library.msri.org/books/Book29/files/schaeffer.pdf
You say in post #91
Thus 5 years and a few cloud engines suffice to solve it.
and from post #100 it appears you are proposing to solve the competition rules game of chess.
I won't, for the moment, comment on the practicality of that, but in view of #168 should you not at least revise your own estimate from 5 years to 50 years?
#171
I only reckon with all the Laws of Chess, including the 50 moves rule and the 3 fold repetition rule.
Without either the 50 moves rule or the 3 fold repetition rule chess is infinite and unsolvable.
With only the 3 fold repetition rule and without the 50 moves rule chess is finite and thus solvable, but the effort goes up dramatically for most probably the same result. It is not only that the number of positions goes up because of the ply count to add, it is also that the number of moves spent with x men before descending to x-1 men and thus approaching the 7 men endgame table base goes up.
Jan 25, 2022
0
#148
tygxc wrote:
#169
No, 3.8521*10^37 is an upper bound for the number of all legal positions without excess promotions. As soon as white plays 1 e4 all positions with a pawn on e2 are no longer relevant.
#168
I do not believe the 50-move rule has as much importance as you attribute to it. In practical play the stalemate rule is much more important than the 50-moves rule. The AlphaZero paper shows almost the same high draw rate with stalemate = win. The existence of a hidden long win for white or even for black is like the existence of Martians: they always hide when we look. With more time or with stronger human / engine players the draw rate goes up, not down.
Firstly you haven't actually solved chess if you ignore excess promotions, you've only solved chess without excess promotions.
I didn't dispute that in a game there can be no positions following e4 with a pawn on e2. What I questioned was your statement that this implied that the majority of the positions in the estimate in Gourion's paper were irrelevant.
Also it's simply a fact that there are 100 times as many competition rules positions as basic rules positions. Our respective opinions have no relevance.
Jan 25, 2022
0
#149
tygxc wrote:
#171
I only reckon with all the Laws of Chess, including the 50 moves rule and the 3 fold repetition rule.
All the laws of chess has to include clocks and arbiters.
There are two main games of chess described in the FIDE laws. "Basic Rules" and "Competition Rules".
The latter has multiple flavours and is less easy to analyse owing to the clocks and arbiters. Easier would be the basic rules game prior to 2017 which included a 50 move rule and a 3 move repetition rule, though traditionally these are ignored in analysis.
Without either the 50 moves rule or the 3 fold repetition rule chess is infinite and unsolvable.
That's nonsense. We've already covered it. You really need to read your responses.
See e.g. https://en.wikipedia.org/wiki/L_game that is an infinite game.
With only the 3 fold repetition rule and without the 50 moves rule chess is finite and thus solvable, but the effort goes up dramatically for most probably the same result. It is not only that the number of positions goes up because of the ply count to add, it is also that the number of moves spent with x men before descending to x-1 men and thus approaching the 7 men endgame table base goes up.
No it doesn't it goes down. Under basic rules there is no limit on the number of moves spent with x men before descending to x-1 men.
#173
Of course excess promotions like to 4 queens are part of solving chess. However in estimating the required effort, these can be neglected as these are very rare in practice. Many of the legal positions without any excess promotions make no sense and play no role in solving chess. So the included not sensible positions without excess promotions more than make up for the few legal positions with excess promotions that make sense.
After white plays 1 e4 all positions with a white pawn on e2 are no longer relevant. There are many, many of these. E.g. White Ke1, pawn e2, black Ke8 will never result from it. It is even clearer with each capture. There the Gourion paper tells how many positions are rendered irrelevant. The square root rule in analogy of the Schaeffer paper should account for these irrelevant positions.
The Gourion paper gives no estimate: it gives an upper bound.
Yes, if you include the ply count in the FEN of a position, then there are 100 more FEN. However, that plays no significant role and is thus a needless complication.
Jan 25, 2022
0
#151
tygxc wrote:
#173
Of course excess promotions like to 4 queens are part of solving chess. However in estimating the required effort, these can be neglected as these are very rare in practice. Many of the legal positions without any excess promotions make no sense and play no role in solving chess. So the included not sensible positions without excess promotions more than make up for the few legal positions with excess promotions that make sense.
I would guess that is correct, but it does assume that what is true in practice would also be true of perfect play in this respect.
After white plays 1 e4 all positions with a white pawn on e2 are no longer relevant. There are many, many of these. E.g. White Ke1, pawn e2, black Ke8 will never result from it. It is even clearer with each capture. There the Gourion paper tells how many positions are rendered irrelevant.
Exactly. That's why you can't remove these positions a second time as you attempted to do in #167.
The square root rule in analogy of the Schaeffer paper should account for these irrelevant positions.
The Gourion paper gives no estimate: it gives an upper bound.
Granted.
Yes, if you include the ply count in the FEN of a position, then there are 100 more FEN. However, that plays no significant role and is thus a needless complication.
It should add 40 years to your own estimate (on which I again reserve comment) of the time required for a solution. I don't know if you would regard that as significant.
If you solve simpler positions, as has already been done in the tablebases, then there are significant effects in many cases. Six to seven percent of the evaluations in the KNNKP or KQNKRBN endgames already mentioned are different and in some cases where the evaluations are the same the moves required are different under basic rules and competition rules.
There are, of course many other tablebased endgames with similar results and these can be expected to mushroom as the number of men increases.
So far as I'm aware draughts has only been weakly solved and, since you base your proposed procedure on Schaeffer's method, I assume you propose only to weakly solve chess.
In a strong solution, however, even positions with fewer than five men on the board are affected. E.g. the percentage of White to play KBNK positions that are won would drop from approximately 100% under basic rules to around 50% under competition rules.
The position shown below (from https://www.chessgames.com/perl/chessgame?gid=1716505 ) is an example of a win under basic rules but a draw under competition rules.
White to play, ply count = 81
#176
"That's why you can't remove these positions a second time as you attempted to do in #167."
I remove the irrevlevant positions only once by taking the square root.
"the percentage of White to play KBNK positions that are won would drop from approximately 100% under basic rules to around 50% under competition rules."
No, that is not true. KBN-K is always a win in less than 50 moves. It is a 4-men position that necessarily stems from a 5-men position. As soon as the won 4-men position is on the board, there is a win in less than 50 moves. Of course if white starts to play aimlessly then white may arrive at a position where the win is no longer possible as the ply count is already to high from the aimless moves.
Jan 25, 2022
0
#153
tygxc wrote:
#176
"That's why you can't remove these positions a second time as you attempted to do in #167."
I remove the irrevlevant positions only once by taking the square root.
You said
...
It is the number of positions that counts: an upper bound is 3.8521*10^37.
https://arxiv.org/pdf/2112.09386.pdf
Of these the vast majority is irrelevant.
After 1 e4 all positions with a white pawn on e2 are no longer relevant.
...
How that amounts to removing the irrelevant positions by extracting their square root is beyond me. The "vast majority of positions" you say are irrelevant are not included in the original figure, so you can't say "Of these the vast majority is irrelevant" that is attempting to remove them twice.
"the percentage of White to play KBNK positions that are won would drop from approximately 100% under basic rules to around 50% under competition rules."
No, that is not true. KBN-K is always a win in less than 50 moves.
Try winning the position I gave under competition rules against e.g. Stockfish. What you say is not true quite clearly is true. You don't need a tablebase to verify it.
KBN-K is a win in less than 50 moves under either set of rules only if it's a win in the first place. Not always.
It is a 4-men position that necessarily stems from a 5-men position. As soon as the won 4-men position is on the board, there is a win in less than 50 moves. Of course if white starts to play aimlessly then white may arrive at a position where the win is no longer possible as the ply count is already to high from the aimless moves.
That's why I made the distinction between solved and weakly solved.
Jan 25, 2022
0
#154
Very roughly, there was a "square root" saving in the solution of checkers by combining two parts - a limited endgame table base and an opening strategy for each side, with the two meeting in the middle. This is what avoiding a full tablebase of all legal positions. To say this is challenging for chess is an understatement.
#178
"How that amounts to removing the irrelevant positions by extracting their square root is beyond me. The "vast majority of positions" you say are irrelevant are not included in the original figure, so you can't say "Of these the vast majority is irrelevant" that is attempting to remove them twice."
No, all positions with a white pawn on e2 and with a black pawn on d7 are included in the original upper bound. All positions with 32, 31, 30, 29, 28, ... 7, 6, 5, 4, 3, 2 men are included in the original upper bound. Each pawn move and each capture renders a huge number of positions irrelevant. Checkers was solved by only the square root of the number of legal positions. Hence it is plausible to apply the square root in chess too to account for all positions rendered irrelevant.
Jan 25, 2022
0
#156
Note that the "square root" quantification of the saving is based on to only dealing with 1 move for a selected side at each point, to generate first a white strategy, then a black strategy, each achieving a draw (of course if one side has a win, only one strategy is needed). However, this only achieves a square root saving relative to the total number of possible games. In chess, the total number of positions is much smaller, and it is not clear the saving relative to the position complexity of the game - the total number of legal positions - is close to this.
Jan 25, 2022
0
#157
tygxc wrote:
#178
"How that amounts to removing the irrelevant positions by extracting their square root is beyond me. The "vast majority of positions" you say are irrelevant are not included in the original figure, so you can't say "Of these the vast majority is irrelevant" that is attempting to remove them twice."
No, all positions with a white pawn on e2 and with a black pawn on d7 are included in the original upper bound.
I stand corrected. So they are. Apologies.
#181
This is the paper about checkers
https://www.cs.mcgill.ca/~dprecup/courses/AI/Materials/checkers_is_solved.pdf
See figure 2:
"Positions may be irrelevant because they are unreachable or are not required for the proof."
Jan 25, 2022
0
#159
tygxc wrote:
#181
This is the paper about checkers
https://www.cs.mcgill.ca/~dprecup/courses/AI/Materials/checkers_is_solved.pdf
See figure 2:
"Positions may be irrelevant because they are unreachable or are not required for the proof."
Which is true, but doesn't answer @Elroch's post #181.
#184, #181
"Note that the "square root" quantification of the saving is based on to only dealing with 1 move for a selected side at each point, to generate first a white strategy, then a black strategy, each achieving a draw" ++ No, that is not how checkers was solved. See the paper. They started from an opening database and then calculated towards an endgame table base using a checkers program called Chinook. The number of positions used in the proof that checkers is a draw turned out to be the square root of the number of legal positions.
"However, this only achieves a square root saving relative to the total number of possible games."
++ No the number of positions used in the proof is the square root of the number of legal positions. The number of games plays no role.
"In chess, the total number of positions is much smaller"
++ No, in chess the number of positions is much larger: 3.8*10^37.
"it is not clear the saving relative to the position complexity of the game - the total number of legal positions - is close to this." ++ Yes, we do not know until chess is solved. Maybe for chess it is more than the square root, maybe it is less than the square root. It is plausible to assume that for chess it is about the square root as well just like it was for checkers.