Chess solved?

[Dann Corbit]

The checkers approach by the Chinook team was similar to what you are suggesting.
They analyzed openings and used tablebase files in combination.

[mmt]

You still need to store it, as it must know what it has calculated, and there is not enough matter in the universe to store the calculation. Even if you could somehow store each position as single bit of information.

There are easily enough atoms in the universe to store all possible chess positions, though. ~10^42 vs ~10^80.

[mwyoung]

You still need to store it, as it must know what it has calculated, and there is not enough matter in the universe to store the calculation. Even if you could somehow store each position as single bit of information.

There are easily enough atoms in the universe to store all possible chess positions, though. ~10^42 vs ~10^80.

The Shannon number which is the conservative lower bound and is 10^120, and assumes a game last 40 moves.

10^120 vs 10^80.

[Dann Corbit]

I guess that when checkers was solved, nobody bothered to store the 500,000,000,000,000,000,000 possible positions.

You don't have to examine every node to solve chess. If you were to solve by alpha-beta, you only have to examine (roughly) the square root of the nodes.

Now, that is a lot and I don't think you could solve chess by a pure alpha-beta search unless there is a forced conclusion (w/l/d) fairly close to the origin that nobody has seen. This would seem to me to be a very remote possibility.

So if there is a solution, I do not think it will be proven by simple alpha-beta search. But the gigantic numbers do assume that there is no solution nearby. This also has not been proven.

[mmt]

Interesting! Looks as though a single GPU can get 10^9 positions per second. With a million of them, and assuming "perfect efficiency", that would be 10^9 * 10^6 = 10^15 positions per second. If white does have a forced win, that might be enough - but if, as seems likely, chess is a draw, surely you won't be able to prove that? The chess tree is just too big.

So 1 year of running this setup gets us 3*10^22 positions. We should look at Koomey's Law more than Moore's Law to make guesses about future speed increases.

The problem will be not having enough RAM to store the hash table and not enough fast, non-volatile storage for the tablebases. There could be some tricks to cut down the storage requirements by not storing every position or by compression methods (e.g. could you train a smallish neural net on a W/D/L tablebase that would get you 99% accuracy plus have a list of positions where it fails). If we can't figure out the storage problem, it will take much more calculating. But actually, I wouldn't bet against chess getting solved in this century.

[mmt]

The Shannon number which is the conservative lower bound and is 10^120, and assumes a game last 40 moves.

10^120 vs 10^80.

Lower bound on the number of moves in the game tree, not on all possible positions. You definitely don't need to store 10^120 positions. The vast majority of moves at a given position would make this player lose, so their sub-trees are relatively small and you have transpositions. I think a factor of 3 sensible moves per position was used in the past.

[mwyoung]

The Shannon number which is the conservative lower bound and is 10^120, and assumes a game last 40 moves.

10^120 vs 10^80.

Lower bound on the number of moves in the game tree, not on all possible positions. You definitely don't need to store 10^120 positions.

You are correct on one thing, 10^120 is wrong and just a lower bound. The number will likely be larger.

[mmt]

You are correct on one thing, 10^120 is wrong and just a lower bound. The number will likely be larger.

https://en.wikipedia.org/wiki/Shannon_number

Shannon himself recognized that there are many fewer positions and made a rough estimate near what I mentioned.

And: "Recent results[3] improve that estimate, by proving an upper bound below 2^155, which is less than 10^46.7"

[mwyoung]

Interesting! Looks as though a single GPU can get 10^9 positions per second. With a million of them, and assuming "perfect efficiency", that would be 10^9 * 10^6 = 10^15 positions per second. If white does have a forced win, that might be enough - but if, as seems likely, chess is a draw, surely you won't be able to prove that? The chess tree is just too big.

So 1 year of running this setup gets us 3*10^22 positions. We should look at Koomey's Law more than Moore's Law to make guesses about future speed increases.

The problem will be not having enough RAM to store the hash table and not enough fast, non-volatile storage for the tablebases. There could be some tricks to cut down the storage requirements by not storing every position or by compression methods (e.g. could you train a smallish neural net on a W/D/L tablebase that would get you 99% accuracy plus have a list of positions where it fails). If we can't figure out the storage problem, it will take much more calculating. But actually, I wouldn't bet against chess getting solved in this century.

You do not need to guess about future speed. There is a limit to how fast you can make a computer. Using Moore's law that limit will be reached in 75 years. Just use the theoretical limit.

[mmt]

You do not need to guess about future speed. There is a limit to how fast you can make a computer. Using Moore's law that limit will be reached in 75 years. Just use the theoretical limit.

Moore's law is not about the speed of computers. Koomey's Law is not either but it's more relevant, since as was mentioned, the power use matters most at our current technological level.