Could chess be Solved using Summit plus Leela or AlphaZero

[Chessqueen]

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]

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.

[henk2]

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]

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.

[Dann Corbit]

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.

[henk2]

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]

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.

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

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

[Dann Corbit]

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.