Chess solved?

[duncan]

It's surprising that a game designed so long ago has held out this long (but go will outlast chess).

Considering there are more possible games then atoms in the universe, it is not so surprising that the game has held out. I could argue that the fact that in 10 years or less we are approaching nearly 100% draws, despite our puny knowlege of the game is surprising.

[towforce]

It's surprising that a game designed so long ago has held out this long (but go will outlast chess).

Considering there are more possible games then atoms in the universe, it is not so surprising that the game has held out. I could argue that the fact that in 10 years or less we are approaching nearly 100% draws, despite our puny knowledge of the game is surprising.

IMO, we are all so used to looking at the game through human eyes that we've missed something which is "glaringly obvious". Even Donald Knuth in "The Art Of Programming" said that games like chess defy analytical solution - but how would he know?

In simple games, one can fairly easily write rules which will determine which side will win. It would be surprising if this wasn't true for chess as well - but it's going to be more difficult to do, and the method of cracking this will not be "chess experts provide rules for how to play good chess": that hasn't worked.

having a 1-ply chess competition would help - but what would help even more would be the right insight.

[syzygy]

IMO, we are all so used to looking at the game through human eyes that we've missed something which is "glaringly obvious". Even Donald Knuth in "The Art Of Programming" said that games like chess defy analytical solution - but how would he know?

I don't know what he writes exactly, but I suppose he just meant to say that it has defied our attempts at finding and proving a shortcut to applying the alpha-beta algorithm.

There is a trivial "analytical solution" that I can program in BASIC. It is one of these:

Code: Select all

10 PRINT "WHITE WINS"

Code: Select all

10 PRINT "DRAW"

Code: Select all

10 PRINT "BLACK WINS"

For each of these programs, I can write down a mathematical proof of correctness. It happens to be the same proof for each program. It consists of a reference to the alpha-beta algorithm described in Knuth's TAOCP and the sentence that it is left to the reader to verify that the outcome of the algorithm corresponds to the outcome of the program. This is a perfectly fine proof. (Except that it is wrong in two of the three cases and correct in one of the three cases.)

If you think these solutions are too trivial, I can dress them up a bit by coming up with three difficult-looking mathematical rules that take a bit of time to evaluate but give the same three outcomes.

The problem here is, of course, that nobody is actually able to run through the correctness proof in the time he/she has on this earth (even when using massive computing power).


The above shows that the fact that a simple rule may exist is not so interesting because it need not bring us any closer to being able to practically determine whether chess is a win for white, draw or win for black. If you find a rule that evaluates after one hour of calculation to "white wins", how do I know that the rule is correct?

[towforce]

The above shows that the fact that a simple rule may exist is not so interesting because it need not bring us any closer to being able to practically determine whether chess is a win for white, draw or win for black. If you find a rule that evaluates after one hour of calculation to "white wins", how do I know that the rule is correct?

You appear to be saying that chess cannot be solved without crunching out the entire game tree from the starting position. I think this assertion is wrong: IMO there are likely to exist rules about relationships between chess pieces that can provably tell us the outcome of a given position, and that discovering and documenting such rules will be many orders of magnitude easier than crunching out the game tree.

Can you prove that I am wrong? My evidence is that such rules can be provably demonstrated for easier games without crunching out the game tree.

[jp]

IMO, we are all so used to looking at the game through human eyes that we've missed something which is "glaringly obvious". Even Donald Knuth in "The Art Of Programming" said that games like chess defy analytical solution - but how would he know?

Can you give the exact quote and/or the page & volume numbers?

(Certainly, there's a sense in which that's a very safe claim.)

[mwyoung]

How many more elo until chesd considered solved?

It is possible that it is already weakly solved: Suppose we put the latest SFNNUE on a very powerful computer, give it a serious time control (maybe 2 hours plus one min inc or so), and the best/safest opening book available (people will argue over what that is of course!). Then see if any opponent, either the same or different engine on any hardware and with any book or even human assistance, can win even one game in a thousand from it. Of course this wouldn't be a "proof" that it can't lose, but no one would be able to prove that it hadn't solved chess weakly. I'm not saying that we are already at that point, only that it is possible that we are at that point now. Based on the high draw rates even with variety opening books, I can imagine that with a book that always plays the Berlin when possible and other draw-seeking defenses to other openings, it might never lose, or at least not within any number of games that can be practically tested. It could play Black every game to cut the number of games needed in half, since it is far easier to draw with White.

We have kind of already run this experiment. A0 vs SF. And what was the results....

It will be self evident when chess becomes weakly solved.

The development of chess engines will stop, as they did with checker engines, and other games.

[Milos]

Define 'solved'.

Proving any given position is a win/loss/draw. We can do this with 7 man positions and below.

And this is the position you need to solve.

[d]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

That kind of solved (proving) is not achievable in practical sense.
For me solved means that if you played against perfect engine from any given position outcome wouldn't differ as if 2 perfect engines played from a given position (meaning moves could differ but outcome doesn't).

[mwyoung]

Define 'solved'.

Proving any given position is a win/loss/draw. We can do this with 7 man positions and below.

And this is the position you need to solve.

[d]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

That kind of solved (proving) is not achievable in practical sense.
For me solved means that if you played against perfect engine from any given position outcome wouldn't differ as if 2 perfect engines played from a given position (meaning moves could differ but outcome doesn't).

I like that the bar has been lowered on the what solved means. But that is a product of our day and age I guess. It is what ever I want it to mean. So I will point you to the post above.

"It will be self evident when chess becomes weakly solved.

The development of chess engines will stop, as they did with checker engines, and other games."

[Dann Corbit]

The above shows that the fact that a simple rule may exist is not so interesting because it need not bring us any closer to being able to practically determine whether chess is a win for white, draw or win for black. If you find a rule that evaluates after one hour of calculation to "white wins", how do I know that the rule is correct?

You appear to be saying that chess cannot be solved without crunching out the entire game tree from the starting position. I think this assertion is wrong: IMO there are likely to exist rules about relationships between chess pieces that can provably tell us the outcome of a given position, and that discovering and documenting such rules will be many orders of magnitude easier than crunching out the game tree.

Can you prove that I am wrong? My evidence is that such rules can be provably demonstrated for easier games without crunching out the game tree.

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.

[syzygy]

The above shows that the fact that a simple rule may exist is not so interesting because it need not bring us any closer to being able to practically determine whether chess is a win for white, draw or win for black. If you find a rule that evaluates after one hour of calculation to "white wins", how do I know that the rule is correct?

You appear to be saying that chess cannot be solved without crunching out the entire game tree from the starting position. I think this assertion is wrong: IMO there are likely to exist rules about relationships between chess pieces that can provably tell us the outcome of a given position, and that discovering and documenting such rules will be many orders of magnitude easier than crunching out the game tree.

Can you prove that I am wrong? My evidence is that such rules can be provably demonstrated for easier games without crunching out the game tree.

I am indeed personally convinced that there are at most insignificant shortcuts to a brute force approach. An example of a shortcut is showing that KBBBBvK with all Bs on the dark squares is a draw by observing that the Bs will always stay on the dark squares and that there is no mating position with all Bs on the dark squares. To make this shortcut complete, someone will have to provide a formal correctness proof, which will take a bit of effort.

You seem to think that there "should" exist a relatively simple proof that chess is a white win/draw/black win (pick your preferred option) which can be verified in a relatively small amount of computational steps.

It is certainly true that there is a relatively simple proof (based on mini-max or alpha-beta), but unfortunately it takes a very large amount of computational steps to verify.

Verification of the simple alpha-beta proof can be sped up very significantly by having a rule or oracle that picks the "best" move in each (non-losing) position. Unfortunately the resulting "accelerated" proof still takes too many steps to verify. In addition, it is extremely difficult to find/construct this accelerated proof because it requires you to determine an optimal move for each (non-losing) position. (If you just require a "good" move you can plug in SF in the formal alpha/beta-based proof to pick the first move to search. The resulting proof will of course be less accelerated.)

So it is not just about the existence of a computationally cheap proof, but also about the effort required to find/construct that proof. I am convinced that no proof exists that can be verified within 100 years using all of earth's current computational power, but if I am wrong, then I am convinced that no such proof can be constructed within those 100 years.

You seem to argue that since some games have simple solutions, chess must also have a simple solution. This argument of yours does not seem to be based on any particular property of chess, so I guess it should apply to all games in some appropriate class of (finite) games. It seems likely that the only structural property that the games in this class have in common is that they can be described by a game tree. In general, solving a game tree means coming up with a proof tree and verifying it.

Or have you identified anything in chess that makes it "special"?
If not, what makes you think chess is special?


Most games that have a simple solution are special in that an invariant can be identified that is respected by the rules of the game, much like KBBBBvK can be solved without brute force. There is no reason to think that such an invariant exists for chess as a whole. Certainly such invariants do not exist in general, and I see no reason to think that chess is special.

Draughts and suicide chess have been solved by constructing a proof tree. The proof tree is relatively small and can be verified in a relatively small amount of steps. In both cases the proof tree was constructed by a lot of computation aided by clever ideas. But these approaches are not going to work for reguar chess (within reasonable computational limits).


In short, my "proof" is based on the argument that chess is not special. Now please explain why chess is special.