Could chess be Solved using Summit plus Leela or AlphaZero
Moderators: bob, hgm, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

 Posts: 881
 Joined: Wed Sep 05, 2018 12:16 am
 Full name: Nancy M Pichardo
Could chess be Solved using Summit plus Leela or AlphaZero
If by any chance either LC0 or Alpha Zero can use Summit Supercomputer for one day, can Chess be Solved or NOT?
https://www.ibm.com/thoughtleadership/ ... rcomputer/
https://www.ibm.com/thoughtleadership/ ... rcomputer/

 Posts: 10811
 Joined: Wed Mar 08, 2006 7:57 pm
 Location: Redmond, WA USA
 Contact:
Re: Could chess be Solved using Summit plus Leela or AlphaZero
No.
Not by that means.
To solve a game means that you know a perfect game theoretical outcome from any position.
Any engine that uses unsound pruning cannot do this.
That includes null move pruning, LMR pruning, and all the other wonderful pruning that gives branching factors of around one and a half.
As to whether chess can be solved, that is an open question but it seems likely.
I think it is much more probable that it would be solved using AND/OR proof search on a few million GPU cards.
But that is just a guess.
Not by that means.
To solve a game means that you know a perfect game theoretical outcome from any position.
Any engine that uses unsound pruning cannot do this.
That includes null move pruning, LMR pruning, and all the other wonderful pruning that gives branching factors of around one and a half.
As to whether chess can be solved, that is an open question but it seems likely.
I think it is much more probable that it would be solved using AND/OR proof search on a few million GPU cards.
But that is just a guess.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Re: Could chess be Solved using Summit plus Leela or AlphaZero
Not if you only want a weak solution.Dann Corbit wrote: ↑Thu Feb 21, 2019 8:40 pmNo.
Not by that means.
To solve a game means that you know a perfect game theoretical outcome from any position.
Any engine that uses unsound pruning cannot do this.
That includes null move pruning, LMR pruning, and all the other wonderful pruning that gives branching factors of around one and a half.
As to whether chess can be solved, that is an open question but it seems likely.
I think it is much more probable that it would be solved using AND/OR proof search on a few million GPU cards.
But that is just a guess.
Optimal play from starting position is enough for a weak solution.
Either way to answer OP, MCTS is one of the worse options to try and solve a game with. I'm not sure if Lc0 or A0 are lossy or lossless engines, pure MCTS should converge to minimax eventually but does it much slower than traditional methods. If Lc0 or A0 are lossy then they'll never be able to solve any game.
Re: Could chess be Solved using Summit plus Leela or AlphaZero
It is not possible to solve chess. With 10^120 possible game variations, and 10^43 possible board positions and these are conservative numbers. The laws of physics stop you from solving chess. You are limited by the speed of light, and other barriers. And the Universe does not contain enough matter and energy for you to complete this calculation. The universe contains about 10^80 particles in the observable universe.Dann Corbit wrote: ↑Thu Feb 21, 2019 8:40 pmNo.
Not by that means.
To solve a game means that you know a perfect game theoretical outcome from any position.
Any engine that uses unsound pruning cannot do this.
That includes null move pruning, LMR pruning, and all the other wonderful pruning that gives branching factors of around one and a half.
As to whether chess can be solved, that is an open question but it seems likely.
I think it is much more probable that it would be solved using AND/OR proof search on a few million GPU cards.
But that is just a guess.
Professing themselves to be wise, they became fools,
take on me. Foes 0.
take on me. Foes 0.

 Posts: 10811
 Joined: Wed Mar 08, 2006 7:57 pm
 Location: Redmond, WA USA
 Contact:
Re: Could chess be Solved using Summit plus Leela or AlphaZero
That assumes that the solutions are too distant for a depth first search.mwyoung wrote: ↑Thu Feb 21, 2019 9:21 pmIt is not possible to solve chess. With 10^120 possible game variations, and 10^43 possible board positions and these are conservative numbers. The laws of physics stop you from solving chess. You are limited by the speed of light, and other barriers. And the Universe does not contain enough matter and energy for you to complete this calculation. The universe contains about 10^80 particles in the observable universe.Dann Corbit wrote: ↑Thu Feb 21, 2019 8:40 pmNo.
Not by that means.
To solve a game means that you know a perfect game theoretical outcome from any position.
Any engine that uses unsound pruning cannot do this.
That includes null move pruning, LMR pruning, and all the other wonderful pruning that gives branching factors of around one and a half.
As to whether chess can be solved, that is an open question but it seems likely.
I think it is much more probable that it would be solved using AND/OR proof search on a few million GPU cards.
But that is just a guess.
A GPU move generator can give perfect information about wins, losses and draws.
We do not need any information for the value of the position other than this with AND/OR dfps.
We do not have to store the information, only the outcome of the search.
This thing can do perft(11) from a chess position in one hour on an old GPU card:
https://github.com/ankanban/perft_gpu
I guess that in 5 years it can be perft(16) in an hour, assuming GPUs continue to grow in strength exponentially.
Sounds like a long way from solution, but if you have millions of GPUs cooperating, and they are doing a depth first proof search, it is not impossible that they can find a solution for an arbitrary position in a reasonable time.
Keep in mind that we can spend the effort in promising branches, and that the searches are perfect (unlike null move searches and the like).
Consider the count for perft(15) which is 2,015,099,950,053,364,471,960 nodes examined from the root.
About 2 sextillion nodes calculated.
So my estimate for 100 million computers performing a perft(16) search given an hour is 6,561,568,064,234,610,949,676,300,000,000 nodes.
So about 6 decillion nodes.
Given we are performing a depth first search, it is possible that due to the actual outcomes of the moves, that is enough to solve.
And if that is not enough, then ten years later we have 1000 times more nodes.
And ten years later we have 1000 times more than that, etc.
6.5615680642346109496763e+42 is after 5 cycles of ten years, and we are approximately at the number of possible chess positions.
In a hundred years, that gives 30 more digits, or 6.5e60 nodes, which is far more than the 10^43 possible positions in the game.
And I also expect that new technologies will be invented to allow Moore's law to continue to grow exponentially.
History has shown us that this is what happens.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Re: Could chess be Solved using Summit plus Leela or AlphaZero
A weak solution doesn't require calculating all 10^120 game variations, nor does it require calculating all possible board positions.mwyoung wrote: ↑Thu Feb 21, 2019 9:21 pmIt is not possible to solve chess. With 10^120 possible game variations, and 10^43 possible board positions and these are conservative numbers. The laws of physics stop you from solving chess. You are limited by the speed of light, and other barriers. And the Universe does not contain enough matter and energy for you to complete this calculation. The universe contains about 10^80 particles in the observable universe.Dann Corbit wrote: ↑Thu Feb 21, 2019 8:40 pmNo.
Not by that means.
To solve a game means that you know a perfect game theoretical outcome from any position.
Any engine that uses unsound pruning cannot do this.
That includes null move pruning, LMR pruning, and all the other wonderful pruning that gives branching factors of around one and a half.
As to whether chess can be solved, that is an open question but it seems likely.
I think it is much more probable that it would be solved using AND/OR proof search on a few million GPU cards.
But that is just a guess.
Gardner's minichess has 9*10^18 legal positions and yet it was trivially solved with a weak laptop (and Stockfish) while Checkers with comparable "complexity" (10^1810^20) required 2 decades of number crunching and even with a modern laptop would take 2 years to solve.
You only need to prove if one side can force a win, or if both can force a draw. That's all you need for a weak solution.
If hypothetically white can force a win in 18 turns, then you can throw the overwhelming majority of 10^43 positions away because they aren't needed. as they'll never be reached.

 Posts: 10811
 Joined: Wed Mar 08, 2006 7:57 pm
 Location: Redmond, WA USA
 Contact:
Re: Could chess be Solved using Summit plus Leela or AlphaZero
But to mwyoung's point, we must accede that even a weak solution is a pretty big job that could not be solved today (at least not by the method I described). It is (of course) possible that someone has a 64 qbit quantum computer somewhere which might solve it today, but I am guessing if it exists, only the military would have access to it.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Re: Could chess be Solved using Summit plus Leela or AlphaZero
The question is could chess be solved. And the answer is no. If solved means knowing the outcome of any possible position WLD. And to play perfect chess. You would also need to know a move that maintains the balance leading to the next position.
Professing themselves to be wise, they became fools,
take on me. Foes 0.
take on me. Foes 0.
Re: Could chess be Solved using Summit plus Leela or AlphaZero
The question is what do you mean by position and what do you mean by knowing the outcome of any possible position WLD?
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 3fold 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 3fold 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.

 Posts: 10811
 Joined: Wed Mar 08, 2006 7:57 pm
 Location: Redmond, WA USA
 Contact:
Re: Could chess be Solved using Summit plus Leela or AlphaZero
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 tictactoe).
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.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.