16

I googled this question and ended up here. From previous questions, it seems Alpha Zero has not solved chess yet and if it does it will take a very long time. Nonetheless, it may be possible one day. I am wondering whether the programmers, or whichever title designers of the Alpha Zero system prefer to use, have built anything into Alpha Zero to detect if it discovers a solution. Also, even though the time required to solve chess is clearly enormous, even with the power of Alpha Zero has anyone attempted to calculate how long it might actually take? Is it likely to be more or less than 7.5 million years and is it possible it will involve the number 42? Perhaps all chess games can always be concluded in 42 moves with perfect play.

Improve this question
3
  • 8
    You have to commend the absolutely impressive marketing power of Google. By this point AlphaZero is a very mediocre engine, but because it was marked to well and tied to this whole AI idea people still think of it as the unreachable pinnacle of chess power. Good question btw, misconceptions should be cleared.
    – 12345ieee
    Nov 11, 2020 at 15:25
  • 2
    You've clearly put some deep thought into this question. ;)
    – Comic Sans Strikephim
    Nov 13, 2020 at 12:41
  • 1
    To add another point to the discussion in the answers below of what solving a game even means: Consider the game of Hex. Here we have a short and simple proof that the first player has a winning strategy, but (except for small boards) have no idea what should be the first move
    – Hagen von Eitzen
    Nov 14, 2020 at 11:10

6 Answers 6

Reset to default
48

No, it can't.

Even if you had it train on a zillion self-playing games and it miraculously achieved perfect play somehow, we would have no way of proving that it had achieved perfect play without first solving chess some other way and then comparing AlphaZero's play to perfect play in all possible positions.

Its approach simply doesn't result in a solution for chess, it's just a way to find good moves. A solution is a mathematical proof.

Improve this answer
8
  • Whether an algorithm can be a proof is a matter for debate in mathematics. For example, the proof of the four-color theorem is algorithmic. math.wustl.edu/~sk/4-color.pdf
    – Michael West
    Nov 11, 2020 at 13:36
  • 47
    @MichaelWest An algorithm can be a proof, but that doesn't mean that all algorithms are proofs. AlphaZero's algorithm isn't a proof.
    – HiddenWindshield
    Nov 11, 2020 at 14:15
  • 2
    I would say an algorithm can't be a proof: it can merely be the basis for a proof. The proof of the four-colour theorem isn't the algorithm alone, but also the justification that the algorithm is correct. And insofar as it's doubted, the doubt isn't whether it's a legitimate type of proof, but whether (in view of the enormous complexity) all the details are correct.
    – Especially Lime
    Nov 12, 2020 at 10:13
  • 3
    @EspeciallyLime an algorithm can be a proof alright, but only of the mathematical formulation of the problem description. The best theoretical framework for such problem descriptions is type theory, check out en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence. For machine learning systems however, the types are as a rule hilariously non-descriptive, like “the image classifier will output an image classification”, “AlphaZero will output a chess move”, at best perhaps “the training will with high probability not make the move suggestions worse”.
    – leftaroundabout
    Nov 12, 2020 at 12:25
  • 4
    @orlp In my opinion, a thing is solved when we know the correct answer and know that it is correct. Even if AlphaZero's current state is the correct answer, we do not know that, and so the problem is not solved.
    – Brilliand
    Nov 12, 2020 at 20:25
8

Nope. AlphaZero's entire architecture (and the architectures of most other engines) is such that it cannot "find a solution", and in any case, if a solution was to be found it would be through programs meant to do just that. Such programs do not exist, due to the absurd complexity. Also, note that AlphaZero (as far as I know) is no longer under active development.

As for how long, I will just quote from the fundamental paper Programming a Computer for Playing Chess by Claude Shannon

However, even at this figure [prior to this, he gave a conservative estimate of how much stuff is needed for solving chess], there will be 10^120 variations to be calculated from the initial position. A machine operating at the rate of one variation per micro-second would require over 10^90 years to calculate the first move!

Doubt it'd have 42, and I'd guess quicker than 7.5 mil

Improve this answer
6
  • 9
    1090 years? You're missing an exponent. 10^90 years. And it's a bit misleading to say it would take that long to "calculate the first move" since at that point it's calculated ALL the moves.
    – D M
    Nov 11, 2020 at 5:20
  • 4
    @DM To make a 1st move before calculating the entire move tree would not be possible. Being certain of the first move would require the computer to be certain about the final move. Otherwise, what if it later becomes clear, once the final tabulation is complete, that 1. Nc3 is the only winning move? In theory, if a computer had mapped out everything except 1. Nc3 as losing eventually, then it could perform that move before completing 1.Nc3 (which might also be losing, but no harm in trying), but that would be a weird edge case. The way the statement is listed in the answer is correct enough.
    – Grade 'Eh' Bacon
    Nov 11, 2020 at 18:43
  • @Grade'Eh'Bacon is there a proof for that statement? It's intuitively plausible, but certainly games exist (usually much simpler) that require only the state in some (practical) local area to make a "perfect" decision. At least when "strong solvability is not required.
    – Dan M.
    Nov 13, 2020 at 15:44
  • @DanM. Proving the statement would require me to solve chess, but in a simplistic fashion, consider as analogy how a current engine works: assign values to pieces and positional advantages, then brute force a first move evaluate using defined metrics, then prune the move 'tree' of what seems promising, brute force a second move from what seems good, evaluate, prune, brute force, etc. etc. until it runs out of time (move 5-7 would be a common end point for non-high end engines). But bad / old engines, or those which have a quick timer to evaluate only a couple moves, might miss...
    – Grade 'Eh' Bacon
    Nov 13, 2020 at 16:41
  • ... a queen sac that leads to a mate in 8 further moves. In such a case, without solving to 8 moves out, the engine doesn't know that the queen sac is valuable, because its defined 'value' metrics weigh the loss of the queen heavily, and must eliminate it from consideration. So while 'pruning' a move tree is necessary for efficient calculation, it also drops off possible moves from consideration. To actually 'solve' chess would require a 100% complete listing of all possible games, to know for certain whether an initial move accidentally eliminates what might be the only 'forced' win for white
    – Grade 'Eh' Bacon
    Nov 13, 2020 at 16:43
6

No, it is impossible, even for Alpha Zero. Solving chess in a scientific sense means to prove the value of every possible move in every possible position. Without a mathematic model still to be found, that means: brute force calculation from the regular starting position (or even all 960 starting positions of Chess960) to a regular end: mate, stalemate, dead position; including the tournament rules: 5fold repetition, 75 moves rule. There will be not enough time to do this. And this is not the task Alpha Zero is created for.

It MIGHT be that Alpha Zero will not be beaten for centuries by man or engine. But that’s not solving chess.

Improve this answer
3
  • 1
    "It MIGHT be that Alpha Zero will not be beaten for centuries by man or engine. But that’s not solving chess." You dodge the crucial question here. What if AlphaZero's state space includes 'the perfect agent', one that cannot be beaten? We can all agree on that AlphaZero can't prove it has solved chess, but it very well might do so, given enough time (and luck). In order to answer negatively you'd need to show that the solution to chess can not be represented by AZ's neural networks. And since neural networks are universal approximators, that only meant it didn't have enough neurons.
    – orlp
    Nov 12, 2020 at 17:30
  • @orlp Did you ever have a math test and wrote down the correct answer, but not how you arrived at it? You gave a correct answer but didn't solve the problem (and had points deducted with a "show your works!" comment by the teacher). Same her: Solving chess is not just exhibiting perfect play, but proving that the play is perfect.
    – Hagen von Eitzen
    Nov 14, 2020 at 10:54
  • @Hagen von Eitzen Minimax exhibits perfect play, and is proven to. It's trivial to modify the inner MCTS of AlphaZero such that you can prove it will fully explore the game tree within a constant overhead over minimax, in which case it also exhibits perfect play. Now apply this to my previous argument. Your qualms about requiring proof have been satisfied from iteration one. What now?
    – orlp
    Nov 14, 2020 at 12:18
5

Compressibility

When we talk about chess, we almost always talk about time, because for humans, that is the relevant variable. But when you talk about the space of all games, time suddenly shrinks into the background, and you suddenly realize: "this is an enormous space". When we talk about "proofs", we think of things which are a few to a few hundred pages long. So space is rarely an issue. But suppose we played a game called "Build a Snowflake". The snowflake has to be less than 1 cm in its largest dimension (so it's finite, and realistically so). It follows the physical laws of snowflake construction, so solutions to this game must be physically realizable. What kind of program could solve "Build a Snowflake"?

If we encoded quantum mechanics in a way that only allows the exact set of atomic combinations which result in a snowflake, we could likely produce a program that, while large, is much smaller than, say, the set of all "snowflake images". But what if we didn't trust this program? What if we said: "This program is so far removed from human experience that I reject the notion that it is even a proof." What if we demanded that this program actually provide a "constructive proof" of the set of all snowflakes? Well, it couldn't do it. There are too many ways to build a snowflake, and not enough fundamental particles in the universe. Nor would we live long enough to examine the boundaries of such a "proof".

Chess Proof

So suppose that I show you this program, and I call it a "Chess Oracle". I tell you that it has solved chess, and to demonstrate, I offer to let you challenge it with any combination of human and non-human chess players you can muster. What would it take for you to accept that it has "solved chess"? The answer is: it depends on the nature of the proof. If chess turns out to have a subtle and deep symmetry which admits for a compact and comprehensible algorithm that could be described in, say, a few pages, then probably most mathematicians would ultimately accept such a proof, after analyzing it carefully. However, it seems extremely unlikely that such a proof exists.

But if it does, what exactly does that mean? Well, it means that, like the number pi, while the set of all chess games is extremely large, the space required to generate the set of all chess games is rather modest (just like many algorithms to compute the digits of pi are just a few lines long). It would mean that chess is extremely compressible, that it has a compact representation as code that fits into a human-understandable space (so, not > 1 million pages of code). Given the variety of chess games we know about, I think that almost nobody believes that chess can be compressed in this way.

Most likely, any "chess solution" will be a mix of high-level principles, medium-level tactics, and fine-grained exceptions. But let's think about what this means. Ultimately, a chess solution could simply be a collection of the set of all legal chess board states along with a set of best next moves for white or black, along with an indication of whether white or black can force a win with perfect play. And, it is theoretically possible to construct such a solution. You just need to play every possible chess game, and write down the results as you go. Since AlphaGo is just a very fancy "play lots of games and remember the outcome, sorta" system, then AlphaGo could theoretically perform this task.

Memory Alpha?

The reason all the other answers say this is impossible is because the number of games you or AlphaGo would have to play to draw out the full game tree is beyond astronomical. Even if every star in every galaxy had 10 planets full of 10 billion chess players cooperatively building this chess proof non-stop, they would not finish in the lifetime of the universe. Also, they would not have enough space to write it down. But let's say that somehow, they did! When they are all finished, they wouldn't just leave it as one giant game tree. They would look for structure. They would say: "Hmm...in virtually every game, strong development of the queen predicts the winner." And this becomes a high-level principle which characterizes much of the game tree without telling you which move to make. Whereas: "don't trade your queen for a pawn" is a tactic which would appear in nearly every game. And the games where trading your queen for a pawn actually leads to a win would appear as the lowest-level "exceptions".

This tactic described above basically says: "the game tree below the point at which you foolishly traded your queen for a pawn is not worth exploring, because in most branches it leads to a loss with perfect play." And thus, it "prunes" all of those subtrees, which compresses the "proof". The exceptions allow you to develop the tactics above, while saying: "There are 3,284 games in which trading your queen for a pawn leads to a win. These are the board states in which you may make this trade for perfect play." Whereas, there may be 10^30 board states downstream of a "bad QxP", which we can basically ignore because of the tactic. This reduces the size of the proof dramatically.

So if all this is possible, AlphaZero will eventually solve chess, right? Nope. While AlphaZero does "remember" the games it plays (including games it doesn't actually play, but only "imagines" playing), it does so in a sloppy way, not unlike human memory. AlphaZero "remembers" its chess performance via a neural network, which has a rather small capacity compared to the total number of chess games. So even if it were somehow possible for AlphaZero to play every possible chess game, there is no way it could remember all of them, even if you kept expanding the size of its neural network. On the one hand, the neural network does perform the "compression" described above...in an indirect way. And so, it is trying very hard to build that ultimate "chess proof". On the other hand, its ability to distill chess knowledge is quite limited, and it appears that it isn't getting much better than it already is. Perhaps with a larger NN, its play could improve, but most likely there are strongly diminishing returns. At some point, you may need to give it 1000x more memory to increase its win rate against, say, Stockfish by 1%.

Furthermore, we know that while neural networks are very powerful optimization engines, they can get "stuck" in a non-optimal part of the search space. It's entirely possible that instances of AlphaZero running today are already stuck in a "local maximum", and would improve more if they could be nudged out of it. So the architecture of AlphaZero itself is not really conducive to finding a "final proof" of chess (nor was that ever a design goal).

Big Numbers

At the end of the day, the real problem here is Very Big Numbers(TM). Our cave man brains are simply not equipped to reason well about numbers much bigger than a few hundred. For instance, if I told you that the majority of orderings of a standard deck of 52 playing cards has never been shuffled in the entire history of playing cards, would you believe me? There are almost 10^68 possible orderings. If the standard card deck has been shuffled a billion billion times since cards have been invented, then we have gone through no more than 10^18 such orderings. That means we would need to do that billion billion shuffles about 10^50 more times to have any chance of seeing all possible orderings. You cannot even intuit how large 10^50 is.

The number of possible chess games is also incomprehensibly large. Just storing the information about which board states lead to a win for white or black or a draw is incomprehensibly large. There are about 2^150 legal chess board states. Each board state can be encoded in about 200 bits, which is about 2^8. So it takes about 2^158 bits to represent every legal chess board state. Way back in 2014, the global computer memory storage was estimated at a ballpark of 2^83 bits. So let's say in a century, we increase storage by 1000x. Furthermore, let's say that our "chess proof" can compress the full game tree by a factor of a billion. It would still take a billion earth-interwebs to store the compressed game tree.

Needless to say, AlphaZero is not getting close to that any time soon.

Improve this answer
9
  • 1
    A constructive proof is one that gives you an algorithm to construct every possible snowflake. You don't have to actually construct all those snowflakes in order to have a constructive proof. You just have to prove that the algorithm constructs them all. i.e. you have to prove that if something is a snowflake, the algorithm constructs it, and that if there is something the algorithm does not construct, it is not a snowflake.
    – user253751
    Nov 12, 2020 at 14:14
  • 1
    And why don't you believe chess is compressible? It can be explained to a human in a few pages of writing. That's much shorter than writing out every possible game.
    – user253751
    Nov 12, 2020 at 14:17
  • 1
    And we can also prove things about card shuffles just fine.
    – user253751
    Nov 12, 2020 at 14:19
  • I love the word compressibility. Did you make it up? It is how we know there are infinitely many primes without being able to write them all down, And it is always at least a remote possibility that some given problem is more compressible that we realize. "aha, we don't need to do all this stuff!"
    – Philip Roe
    Nov 12, 2020 at 19:11
  • 1
    @LawnmowerMan Actually we have a highly compressed solution: an algorithm to play all possible games starting from this point and see which one guarantees you a win. It's not useful though because it takes too long.
    – user253751
    Nov 13, 2020 at 14:07
1

We can start by asking what it means to "solve" a problem. It seems to me that this is almost an unanswerable question. It means in practice that a sufficient number of "experts" are convinced by the "proof" We have this situation in Mathematics, with the famous Haken-Appel computer proof of the four-color theorem, where a computer essentially reduces a problem about an infinite number of possibilities to a finite (but still huge) number of special cases. The role of the experts in this is to confirm that nothing has been forgotten. AFAIK the jury has almost decided that the proof is OK but slight doubt remains.

If there is to be agreement that chess has been solved, it will have to be arrived at by some process like this. At present we cannot imagine what that process could be, but never is a long time.

Improve this answer
4
  • 1
    Agreement about the proof is almost irrelevant. If the proof is really a proof, experts will agree. If it's a very very long proof, it might take them a long time to understand it well enough, but they will still agree in the end. If one person disagrees, then either the proof is not a proof, or that person's objection is objectively wrong. The hard part is writing the proof, not getting people to agree on it!
    – user253751
    Nov 12, 2020 at 14:20
  • @user253751 What if the shortest valid proof is longer than a human can read in his/her lifetime?
    – orlp
    Nov 12, 2020 at 17:25
  • @user 253751 That does not seem to have been the case with Haken-Appel (although I am not qualified to judge) And the definition of experts may simply be those who agree about something. So experts will agree by definition. @orlp1; I like your point. And what if the shortest valid proof is longer than a human being can write in their lifetime?
    – Philip Roe
    Nov 12, 2020 at 18:31
  • @orlp Then it can be written in a form which a computer can check. Also, how did someone write it? Writing it surely takes longer than reading it.
    – user253751
    Nov 13, 2020 at 14:09
0

It seems quite improbable. The number of moves in the largest chess game possible is in the 5000s, and the number of possible positions even larger than 10^16! Alpha Xero can filter our obviously bad lines, but even afterwards, it has to get to an extremely high depth, which I estimate to be around 200.

My theory is that it is a win for White with perfect play. Black can neutralize white's opening advantage with the move. so White always plays perfectly and gains the small advantage of the tempo.

Improve this answer
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.