Could chess be Solved using Summit plus Leela or AlphaZero

Discussion of computer chess matches and engine tournaments.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Chessqueen
Posts: 630
Joined: Wed Sep 05, 2018 12:16 am
Full name: Nancy M Pichardo

Could chess be Solved using Summit plus Leela or AlphaZero

Post by Chessqueen » Thu Feb 21, 2019 8:11 pm

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/thought-leadership/ ... rcomputer/

Dann Corbit
Posts: 10192
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by Dann Corbit » Thu Feb 21, 2019 8:40 pm

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

henk2
Posts: 30
Joined: Mon Jan 14, 2019 6:55 am
Full name: Henk Verbaasdonk

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by henk2 » Thu Feb 21, 2019 8:49 pm

Dann Corbit wrote:
Thu Feb 21, 2019 8:40 pm
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 if you only want a weak solution.
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.

mwyoung
Posts: 1642
Joined: Wed May 12, 2010 8:00 pm

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by mwyoung » Thu Feb 21, 2019 9:21 pm

Dann Corbit wrote:
Thu Feb 21, 2019 8:40 pm
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.
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.
Professing themselves to be wise, they became fools,
Take on me. foes 0

Dann Corbit
Posts: 10192
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by Dann Corbit » Thu Feb 21, 2019 9:46 pm

mwyoung wrote:
Thu Feb 21, 2019 9:21 pm
Dann Corbit wrote:
Thu Feb 21, 2019 8:40 pm
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.
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.
That assumes that the solutions are too distant for a depth first search.
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/ankan-ban/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.

henk2
Posts: 30
Joined: Mon Jan 14, 2019 6:55 am
Full name: Henk Verbaasdonk

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by henk2 » Thu Feb 21, 2019 9:57 pm

mwyoung wrote:
Thu Feb 21, 2019 9:21 pm
Dann Corbit wrote:
Thu Feb 21, 2019 8:40 pm
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.
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.
A weak solution doesn't require calculating all 10^120 game variations, nor does it require calculating all possible board positions.

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^18-10^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.

Dann Corbit
Posts: 10192
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by Dann Corbit » Thu Feb 21, 2019 10:06 pm

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.

mwyoung
Posts: 1642
Joined: Wed May 12, 2010 8:00 pm

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by mwyoung » Thu Feb 21, 2019 10:43 pm

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.
Professing themselves to be wise, they became fools,
Take on me. foes 0

Uri Blass
Posts: 8605
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by Uri Blass » Fri Feb 22, 2019 12:52 am

mwyoung wrote:
Thu Feb 21, 2019 10:43 pm
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.

Dann Corbit
Posts: 10192
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Could chess be Solved using Summit plus Leela or AlphaZero

Post by Dann Corbit » Fri Feb 22, 2019 1:16 am

mwyoung wrote:
Thu Feb 21, 2019 10:43 pm
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.
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.

Post Reply