Chess solved?

[syzygy]

Draughts and suicide chess have been solved ...

I probably should have written "checkers" instead of draughts.

[towforce]

It is, of course, possible to find a forced win, forced loss, or forced draw from the opening (if, indeed, one exists). But it clearly can't be easy to find that if it exists, because nobody has found it.
It' possible, for instance, that chess is a mate in 192 for white that involves several piece sacrifices and the win is forced.
I think it extremely unlikely, however.

Science has many cases where it was really difficult to work out what was going on, and then an underlying discovery was made which suddenly made the whole thing seem simple.

An example of how it might be possible (this is pure speculation: the actual route to solving chess might be completely different):

* we know that CAS tools can solve algebra extremely well

* somebody could break down the chess positions in which the outcome is known into tiny steps to get to that knowledge

* it is reasonable to suppose that having this list of tiny steps, more steps could be added

* having this solving toolkit as a software package, it's entirely possible that the time it takes to resolve a position doesn't increase exponentially with the complexity of the position

There are many (if not most) examples of complex maths solutions that have been built by building on what has gone before: our problem in chess computing has basically been that there are three ways of looking at the subject:

1. as a gateway to AI

2. as a route to solving chess

3. as a new type of chess in its own right - one where it's 100% down to preparation and 0% down to anything other than preparation

Most of what happens at talkchess is very clearly category 3 activity - but my interest is mainly in categories 1 and 2. I accept that there's no hard proof that solving chess like algebra is possible, but I think that the balance of evidence is that it can be: people have written theorem proving software, so why wouldn't chess theorem proving software be possible?

[Dann Corbit]

One method that seems interesting to me is an AND/OR proof search using move generators on an array of GPUs using the internet.
Since you only need to know won/lost/drawn and a move generator can tell you all three of those things, you do not even need an eval function.
Ankan has already written an obscenely fast move generator:
https://github.com/ankan-ban/perft_gpu
Imagine if you had a million GPUs cooperating in an AND/OR proof search.
Sounds like a lot but I imagine it is less than 1/1000th of the GPUs on the planet, and the quality of the GPUs continues to rise exponentially.
A cooperative effort might say that Chess is a mate in 3,827 for white. Or some other such interesting nonsense.
Of course, we would want some way to record the solution. That is the hard part.

[towforce]

One method that seems interesting to me is an AND/OR proof search using move generators on an array of GPUs using the internet.
Since you only need to know won/lost/drawn and a move generator can tell you all three of those things, you do not even need an eval function.
Ankan has already written an obscenely fast move generator:
https://github.com/ankan-ban/perft_gpu
Imagine if you had a million GPUs cooperating in an AND/OR proof search.
Sounds like a lot but I imagine it is less than 1/1000th of the GPUs on the planet, and the quality of the GPUs continues to rise exponentially.
A cooperative effort might say that Chess is a mate in 3,827 for white. Or some other such interesting nonsense.
Of course, we would want some way to record the solution. That is the hard part.

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.

[mwyoung]

One method that seems interesting to me is an AND/OR proof search using move generators on an array of GPUs using the internet.
Since you only need to know won/lost/drawn and a move generator can tell you all three of those things, you do not even need an eval function.
Ankan has already written an obscenely fast move generator:
https://github.com/ankan-ban/perft_gpu
Imagine if you had a million GPUs cooperating in an AND/OR proof search.
Sounds like a lot but I imagine it is less than 1/1000th of the GPUs on the planet, and the quality of the GPUs continues to rise exponentially.
A cooperative effort might say that Chess is a mate in 3,827 for white. Or some other such interesting nonsense.
Of course, we would want some way to record the solution. That is the hard part.

"Since the laws of physics would prevent any kind of machine to be built to achieve this calculation. Let alone the energy needed to power such a device. All the stars in the universe would not be enough. The calculation is that BIG."

You don't understand the scale of the calculation. You need the power to run it under your method. And there is not enough energy to even get close to completing the calculation. 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. And then you are breaking the laws of physics again, Information theory.

[Dann Corbit]

Proving a forced draw is also possible.
While the tree is absurdly huge (embarrasingly enormous?) it is possible that there is a forced draw within a certain distance just as it is possible that there is a forced mate for one side or the other.
You could prove it branch by branch. Once you have proven the outcome of a branch, you don't have to explore it again, just use the root value.
While 12,000 ply games are possible, I suspect that these really would require cooperation of both parties to achieve. But that's just a guess.

Let's suppose that we have divided chess into a million branches and tried to explore them.
Perhaps some large percentage might be resolved to a known outcome.
Then the remaining usolved parts could be divided recursively and examined.

[mmt]

Imagine if you had a million GPUs cooperating in an AND/OR proof search.

You could generate 1 million openings from the starting position for which evals of SF, LC0, and Komodo are between -1 and 1 at the leaf nodes. Choose a few at random and try to solve them using this method. If you can solve them all, it would be worth it to investigate further. My guess is that even at 1 trillion openings, it won't be possible.

[Dann Corbit]

You don't have to solve them all.
Suppose that you solve 60%.
Those are done.
Now, subdivide the reamainder and repeat the process.

Without knowing how effective the and/or proof search is at a billion nodes per second, it is hard to say anything about feasibility.
It's really just talking about how many angels can dance on the head of a pin at this point.
But I think it is an interesting idea.

{edit: and every ten years it will be 1000x faster}
Yes, I know Moore's law says transistors are on their last legs. That just means we won't be using transistors 50 years from now.

[mwyoung]

Proving a forced draw is also possible.
While the tree is absurdly huge (embarrasingly enormous?) it is possible that there is a forced draw within a certain distance just as it is possible that there is a forced mate for one side or the other.
You could prove it branch by branch. Once you have proven the outcome of a branch, you don't have to explore it again, just use the root value.
While 12,000 ply games are possible, I suspect that these really would require cooperation of both parties to achieve. But that's just a guess.

Let's suppose that we have divided chess into a million branches and tried to explore them.
Perhaps some large percentage might be resolved to a known outcome.
Then the remaining usolved parts could be divided recursively and examined.

You are forgetting the power needed to run your method. You still need the power to complete the calculation no matter how you sub divide the calculation. Information theory is a bitch Maxwell's demon!

[mmt]

Goi opening book by Massimiliano Goi has 16.7 million positions. I think we could learn quite a bit by choosing leaf nodes at random from it and evaluating them deeply.

The ratios between sizes of tablebases seem to be:
5 to 4: 207
6 to 5: 146
7 to 6: 112
8 to 7: 90

An 8-piece tablebase is possible to create today with existing (but very expensive) hardware. If we can expect them to keep getting smaller, we could make some conservative guesses on what it would take.