Could chess be Solved using Summit plus Leela or AlphaZero

[Uri Blass]

For the genral problem of solving KQ vs K
I do not know if there is a mate solver that correctly can solve every position.
Chest is not correct here.

1k6/3Q4/8/3K4/8/8/8/8 w - - 8 5 (for history of game see pgn later in this post)

It is mate in 3 but chest is wrong and see mate in 2 when practically the only way to force mate in 2 is to allow a draw by repetition so I consider it wrong.

practically it should be easy to build a tablebases of KQ vs K for every specific history of game when you should consider positions that happened twice in the history as draws because if you get them again you draw by repetition.

Edit:I mean different tablebase so not a tablebase for all position histories but after you get a specific history build a tablebase for it.




[Event "Computer chess game"]
[Site "URIBLASS-THINK"]
[Date "2019.02.22"]
[Round "?"]
[White "UriBlass"]
[Black "ChestUCI"]
[Result "*"]
[BlackElo "2000"]
[Time "03:04:24"]
[WhiteElo "2000"]
[TimeControl "1200+60"]
[SetUp "1"]
[FEN "1k6/3Q4/8/2K5/8/8/8/8 w - - 0 1"]
[Termination "unterminated"]
[PlyCount "8"]
[WhiteType "program"]
[BlackType "human"]

1. Kc6 Ka8 2. Kd5 Kb8 3. Kc6 Ka8 4. Kd5 Kb8 *

[Uri Blass]

The question is could chess be solved. And the answer is no. If solved means knowing the outcome of any possible position W-L-D. And to play perfect chess. You would also need to know a move that maintains the balance leading to the next position.

A tablebase is not necessary for a game to be solved.
An algorithm that can solve it is good enough. (e.g. it is trivial to make an algorithm to do it for tic-tac-toe).
Just the pv and result would be good enough if the algorithm is correct. It does not take any serious storage to hold the pv.

The question is how much time the algorithm needs to run with the hardware we have today in order to consider the game to be solved.

If you can get the solution for every position in less than 1 second then I guess that you consider the game to be solved but what if you can do it but need 1 hour or need 1 year or need million years?

[Dann Corbit]

If we are talking about today's hardware, I guess we have to say it is not solved.
I was assuming future improvements.

If the progress were to continue for 100 years, we would fully search the whole tree or (for that matter) produce a solution to any question about a position in essentially zero time.

I do not know the formal rules for solving a game, so perhaps that is not good enough.

[mwyoung]

The question is could chess be solved. And the answer is no. If solved means knowing the outcome of any possible position W-L-D. And to play perfect chess. You would also need to know a move that maintains the balance leading to the next position.

The question is what do you mean by position and what do you mean by knowing the outcome of any possible position W-L-D?

For the first question I assume that position include also history of moves that may be relevant for the question if the position is win for one side or maybe a forced draw by 3-fold repetition or 50 move rule.

For the second question
Suppose you do not have a database that give the result of any possible position but you have a program that can practically get a position and tell you after some time that is not very big if the position is win for white or draw or win for black.

Do you consider chess to be solved?

If not then even KQ vs K is not totally solved today.

KQ vs K is generally a win but if you have some history of 45 moves of both sides with no capture or pawn promotion you may need to calculate in order to find if it is a win by mate in 5 that you have in tablebases or maybe a draw by the 50 move rule or draw by repetition and you cannot have a tablebase of all the possible stupid history of the game.

maybe white can mate in 5 but in order to do it white needs to allow a draw by 3-fold repetition when mate in 6 is not good enough because black can claim a draw by the 50 move rule earlier so it is a draw and you need to calculate to know it because a tablebases of all possible histories is not practical.

I think my answer was pretty clear. Any legal position and do you know if the position is W-L-D.
If you can not answer this question then chess is not solved.

And again it is not possible to even calculate this answer, so chess can not be solved. The speed of light, the quantum barrier, and the laws of thermodynamics, and information. Prevent you from calculating the answer, because the data set is too large.

If you tried to calculate this data set. You would not have enough storage to hold the information even if you could use every bit of matter in the universe. And if you still tried the laws of thermodynamics would scramble the information before you had time to access the data. And if that did not stop you quantum laws, and the 4 forces would destroy your machine and storage device before you were done calculating the information. And if you could somehow control all the above the universe would run out of energy trying to power your computer before the calculation could be completed.

Time, energy, and the laws of the universe can not be overcome to solve chess.

[Uri Blass]

The question is could chess be solved. And the answer is no. If solved means knowing the outcome of any possible position W-L-D. And to play perfect chess. You would also need to know a move that maintains the balance leading to the next position.

The question is what do you mean by position and what do you mean by knowing the outcome of any possible position W-L-D?

For the first question I assume that position include also history of moves that may be relevant for the question if the position is win for one side or maybe a forced draw by 3-fold repetition or 50 move rule.

For the second question
Suppose you do not have a database that give the result of any possible position but you have a program that can practically get a position and tell you after some time that is not very big if the position is win for white or draw or win for black.

Do you consider chess to be solved?

If not then even KQ vs K is not totally solved today.

KQ vs K is generally a win but if you have some history of 45 moves of both sides with no capture or pawn promotion you may need to calculate in order to find if it is a win by mate in 5 that you have in tablebases or maybe a draw by the 50 move rule or draw by repetition and you cannot have a tablebase of all the possible stupid history of the game.

maybe white can mate in 5 but in order to do it white needs to allow a draw by 3-fold repetition when mate in 6 is not good enough because black can claim a draw by the 50 move rule earlier so it is a draw and you need to calculate to know it because a tablebases of all possible histories is not practical.

I think my answer was pretty clear. Any legal position and do you know if the position is W-L-D.
If you can not answer this question then chess is not solved.

And again it is not possible to even calculate this answer, so chess can not be solved. The speed of light, the quantum barrier, and the laws of thermodynamics, and information. Prevent you from calculating the answer, because the data set is too large.

If you tried to calculate this data set. You would not have enough storage to hold the information even if you could use every bit of matter in the universe. And if you still tried the laws of thermodynamics would scramble the information before you had time to access the data. And if that did not stop you quantum laws, and the 4 forces would destroy your machine and storage device before you were done calculating the information. And if you could somehow control all the above the universe would run out of energy trying to power your computer before the calculation could be completed.

Time, energy, and the laws of the universe can not be overcome to solve chess.

I disagree that it is possible to prove that it is impossible to solve chess.
Maybe you may divide chess positions to classes of equivalent positions when the number of classes is small enough and if you know the solution to one position in the class you can translate it to another position.

For example if you know all the solutions for KQ vs K when the queen is white you can translate it to KQ vs K when the queen is black.

Edit:I can add that building the tablebases for a specific initial position in chess is not a problem that you need to memorize more than something in the order of 10^43 positions for it.

basically you start with the following information:
1)chess positions that you know that repeating them is a draw(less than 50 positions)
2)fifty move counter that is relevant only for the material configuration in the starting position(100 options) and I think that with a specific material configuration you have less than 10^30 options
3)chess positions(I think less than 10^43 options when only for less than 10^30 options the fifry move counter is relevant) so practically the number of chess positions when you do not care about the fifty move rule is the dominant factor.

Now the question if it is a possible to have a tool that can generate a tablebase of 10^43 positions in a short time.
I see no way to prove that it is impossible.

[M ANSARI]

I think that chess will be solved in that evaluations of engines will be so strong that all bad moves a culled out. Sort of like evolution ... a small fish that swims funny and slowly will immediately get gobbled up and to survive all the fish need to move fast and be accurate ... and only the fish that survive can pass on their genetic code. Time to play a move is not a constant with electronics like it is with humans ... today's engines playing with only 1 second a move will crush the best engines of 15 years ago with 10 minutes a move. This will continue as hardware and software improves and thus the ability of very very strong engines playing millions and billions and even trillion of games will weed out any moves that lose. This is how chess will be solved and not by 32 EGTB's.

[Dann Corbit]

This is pragmatically solving chess, and it is not the same as formally solving chess.
I believe that 32 man EGTB are probably not possible even as bitbase files

A Haskell program[*] has shown that the maximum number of possible board positions is:
45,193,640,626,062,205,213,735,739,171,550,309,047,984,050,718
(45 Quattuordecillion positions)
If we divide this by 4 (for bitbase, win/loss/draw needs 2 bits) we get:
1.1298410156515551303433934792887577262E46 bytes
If we divide this by 4 for left/right and color mirrors, we get:
5.6492050782577756517169673964437886310E45 bytes.
If we can store a bit of data onto ten atoms, that is
188,306,835,941,925,855,057,233 moles of atoms
About 5,272,591,406,373,923,941,602.5 KG of silicon
or
11,599,701,094,022,632,671,525.50 lbs
(11.6 sextillion pounds)
Now, the earth weights 6 sextillion tons, so there is probably enough silicon if we were to get all the silicon out of the earth and make it into storage.

I guess Mark is right that such a thing will never be built.
So the 32 man tablebase file is right out.

Storing all the positions in chess would not exhaust the universe of matter. Storing all the games would.

[*] https://tromp.github.io/chess/chess.html

[Uri Blass]

This is pragmatically solving chess, and it is not the same as formally solving chess.
I believe that 32 man EGTB are probably not possible even as bitbase files

A Haskell program[*] has shown that the maximum number of possible board positions is:
45,193,640,626,062,205,213,735,739,171,550,309,047,984,050,718
(45 Quattuordecillion positions)
If we divide this by 4 (for bitbase, win/loss/draw needs 2 bits) we get:
1.1298410156515551303433934792887577262E46 bytes
If we divide this by 4 for left/right and color mirrors, we get:
5.6492050782577756517169673964437886310E45 bytes.
If we can store a bit of data onto ten atoms, that is
188,306,835,941,925,855,057,233 moles of atoms
About 5,272,591,406,373,923,941,602.5 KG of silicon
or
11,599,701,094,022,632,671,525.50 lbs
(11.6 sextillion pounds)
Now, the earth weights 6 sextillion tons, so there is probably enough silicon if we were to get all the silicon out of the earth and make it into storage.

I guess Mark is right that such a thing will never be built.
So the 32 man tablebase file is right out.

Storing all the positions in chess would not exhaust the universe of matter. Storing all the games would.

[*] https://tromp.github.io/chess/chess.html

1)32 man tablebases is not exactly solution of chess if you include repetitions and 50 move rule because it does not tell us the expected result when the history is known.

2)I believe that you can get clearly less than the upper bound.
Maybe I will try to write a program to get a good estimate for it in the future.

The idea is simply to have some good upper bound first and to generate random positions based on random numbers and find how many of them you can reach.

I guess it is easy to find good upper bounds for 32 pieces less easy to find good upper bound for 31 pieces(there are more possible positions with 31 pieces than 32 pieces because with 32 pieces no promotion is possible)

It is harder to find a good upper bound for 30 pieces that I guess to be bigger than 31 pieces and later to have an upper bound for positions with 29 pieces or less than it that are probabily majority of the legal positions.

Note that I do not fully understand the link that you gave for the number of legal positions
maybe because I do not know haskell so I do not understand part of the code.