Answers.Body: <p>No, it can't.</p>
  <p>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 <em>proving</em> 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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T13:36:07.853Z
Answers.Text: 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.  https://www.math.wustl.edu/~sk/4-color.pdf
Answers.UserDisplayName: Michael West
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T14:15:28.527Z
Answers.Text: @MichaelWest An algorithm can be a proof, but that doesn't mean that all algorithms are proofs. AlphaZero's algorithm isn't a proof.
Answers.UserDisplayName: HiddenWindshield
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T21:03:28.143Z
Answers.Text: @MichaelWest Do people doubt the proof of the 4-color theorem?
Answers.UserDisplayName: corsiKa
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T22:57:28.653Z
Answers.Text: @corsiKa, yes some doubt, see Phillip Roe's answer here.  Some also do not agree anything derived by proof by contradiction.  To bring this back to chess, G. H. Hardy said regarding proof by contradiction, ""It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."
Answers.UserDisplayName: Michael West
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T10:13:07.350Z
Answers.Text: 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.
Answers.UserDisplayName: Especially Lime
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T12:25:44.290Z
Answers.Text: @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 https://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”.
Answers.UserDisplayName: leftaroundabout
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T17:38:22.603Z
Answers.Text: -1 _"A solution is a mathematical proof."_ No it isn't. A solution is an optimal strategy. AlphaZero might (I'm not saying this is likely) be able to represent the perfect strategy using its neural networks, in which case it might be possible it converges on it. In that scenario, given infinite time, AlphaZero will solve chess. You won't know when it has solved it, but it will. And at some point in time, you will have a solution.
Answers.UserDisplayName: orlp
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T20:25:44.813Z
Answers.Text: @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.
Answers.UserDisplayName: Brilliand
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T08:40:27.407Z
Answers.LastActivityDate: 2020-11-11T08:40:27.407Z
Answers.UserDisplayName: RemcoGerlich
Answers.Body: <p>Nope. AlphaZero's entire architecture (and the architectures of most other engines) is such that it cannot &quot;find a solution&quot;, 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.</p>
  <p>As for how long, I will just quote from the fundamental paper Programming a Computer for Playing Chess by Claude Shannon</p>
  <blockquote>
  <p>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!</p>
  </blockquote>
  <p>Doubt it'd have 42, and I'd guess quicker than 7.5 mil</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T05:20:53.527Z
Answers.Text: 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.
Answers.UserDisplayName: D M
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T18:43:33.910Z
Answers.Text: @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.
Answers.UserDisplayName: Grade 'Eh' Bacon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-13T15:44:50.970Z
Answers.Text: @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.
Answers.UserDisplayName: Dan M.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-13T16:41:08.633Z
Answers.Text: @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...
Answers.UserDisplayName: Grade 'Eh' Bacon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-13T16:43:08.263Z
Answers.Text: ... 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
Answers.UserDisplayName: Grade 'Eh' Bacon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-13T16:43:34.667Z
Answers.Text: ... Anything less than waiting for this isn't "solving" chess, it is just "being a really good chess engine".
Answers.UserDisplayName: Grade 'Eh' Bacon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T04:45:27.517Z
Answers.LastActivityDate: 2020-11-11T14:11:00.890Z
Answers.LastEditDate: 2020-11-11T14:11:00.890Z
Answers.UserDisplayName: pulsar512b
Answers.Body: <p>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.</p>
  <p>It MIGHT be that Alpha Zero will not be beaten for centuries by man or engine. But that’s not solving chess.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T17:30:17.477Z
Answers.Text: _"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.
Answers.UserDisplayName: orlp
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-14T10:54:28.513Z
Answers.Text: @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.
Answers.UserDisplayName: Hagen von Eitzen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-14T12:18:41.187Z
Answers.Text: @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?
Answers.UserDisplayName: orlp
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T13:36:52.387Z
Answers.LastActivityDate: 2020-11-11T13:36:52.387Z
Answers.UserDisplayName: Christian H. Kuhn
Answers.Body: <h1>Compressibility</h1>
  <p>When we talk about chess, we almost always talk about <em>time</em>, because for humans, that is the relevant variable.  But when you talk about <em>the space of all games</em>, time suddenly shrinks into the background, and you suddenly realize: &quot;this is an enormous <em>space</em>&quot;.  When we talk about &quot;proofs&quot;, 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 &quot;Build a Snowflake&quot;.  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 &quot;Build a Snowflake&quot;?</p>
  <p>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 &quot;snowflake images&quot;.  But what if we didn't trust this program?  What if we said: &quot;This program is so far removed from human experience that I reject the notion that it is even a proof.&quot;  What if we demanded that this program actually provide a &quot;constructive proof&quot; 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 &quot;proof&quot;.</p>
  <h1>Chess Proof</h1>
  <p>So suppose that I show you this program, and I call it a &quot;Chess Oracle&quot;.  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 &quot;solved chess&quot;?  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 <em>extremely</em> unlikely that such a proof exists.</p>
  <p>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 <em>generate</em> 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 <em>extremely compressible</em>, that it has a compact representation as code that fits into a human-understandable space (so, not &gt; 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.</p>
  <p>Most likely, any &quot;chess solution&quot; 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 &quot;play lots of games and remember the outcome, sorta&quot; system, then AlphaGo could theoretically perform this task.</p>
  <h1>Memory Alpha?</h1>
  <p>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: &quot;Hmm...in virtually every game, strong development of the queen predicts the winner.&quot;  And this becomes a high-level principle which characterizes much of the game tree without telling you which move to make.  Whereas: &quot;don't trade your queen for a pawn&quot; 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 &quot;exceptions&quot;.</p>
  <p>This tactic described above basically says: &quot;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.&quot;  And thus, it &quot;prunes&quot; all of those subtrees, which compresses the &quot;proof&quot;.  The exceptions allow you to develop the tactics above, while saying: &quot;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.&quot;  Whereas, there may be 10^30 board states downstream of a &quot;bad QxP&quot;, which we can basically ignore because of the tactic.  This reduces the size of the proof dramatically.</p>
  <p>So if all this is possible, AlphaZero will eventually solve chess, right?  Nope.  While AlphaZero does &quot;remember&quot; the games it plays (including games it doesn't actually play, but only &quot;imagines&quot; playing), it does so in a sloppy way, not unlike human memory.  AlphaZero &quot;remembers&quot; 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 <em>play</em> every possible chess game, there is no way it could <em>remember</em> all of them, even if you kept expanding the size of its neural network.  On the one hand, the neural network <em>does</em> perform the &quot;compression&quot; described above...in an indirect way.  And so, it is trying very hard to build that ultimate &quot;chess proof&quot;.  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%.</p>
  <p>Furthermore, we know that while neural networks are very powerful optimization engines, they can get &quot;stuck&quot; in a non-optimal part of the search space.  It's entirely possible that instances of AlphaZero running today are already stuck in a &quot;local maximum&quot;, 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 &quot;final proof&quot; of chess (nor was that ever a design goal).</p>
  <h1>Big Numbers</h1>
  <p>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.</p>
  <p>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 <a href="https://math.stackexchange.com/questions/1406919/how-many-legal-states-of-chess-exists">legal chess board states</a>.  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 <a href="https://www.livescience.com/54094-how-big-is-the-internet.html" rel="noreferrer">2^83 bits</a>.  So let's say in a century, we increase storage by 1000x.  Furthermore, let's say that our &quot;chess proof&quot; can compress the full game tree by a factor of a billion.  It would still take a <em>billion</em> earth-interwebs to store the <em>compressed</em> game tree.</p>
  <p>Needless to say, AlphaZero is not getting close to that any time soon.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T19:11:49.673Z
Answers.Text: 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!"
Answers.UserDisplayName: Philip Roe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T22:03:10.877Z
Answers.Text: @user253751 I *do* believe that chess is compressible. But a "solution" to chess would have to describe the winning moves for every possible game. I suspect that this description is not "compact" for most reasonable definitions of the term. Rules as compact as Stockfish are obviously quite limited. AZ's "rule set" is much larger, but do you believe it is even within 10 orders of magnitude of the "solution"?
Answers.UserDisplayName: Lawnmower Man
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-13T19:05:12.773Z
Answers.Text: @user253751 if we consider spacetime as a unified whole, then the traditional space/time tradeoff is just a rotation in this space. In that case, the brute force solution is very "large", and not at all compressed.
Answers.UserDisplayName: Lawnmower Man
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-14T11:06:00.173Z
Answers.Text: If there are 2^150 legal game states, then each of these can (theoretically) be described/identified by 150 bits - but definitely not less. Perhaps 200 is a good heuristic, but the actual bound is 150
Answers.UserDisplayName: Hagen von Eitzen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-14T21:27:18.970Z
Answers.Text: @HagenvonEitzen that's only true if you define the bitmap for the game state with an exact 1:1 match. However, that can produce a very non-intuitive mapping whose description increases the total size. A naive mapping takes 64 squares and stores a 4-bit value at each indicating piece type and color. That's 256 bits already. You can use run-length encoding to compress the blank squares for some boards, but it will cause others to get bigger. Or you can take 32 pieces x 6 bits to indicate their square, for 186 bits. This is how I created my estimate. See if you can describe your mapping. ;)
Answers.UserDisplayName: Lawnmower Man
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T20:32:37.650Z
Answers.LastActivityDate: 2020-11-11T20:32:37.650Z
Answers.UserDisplayName: Lawnmower Man
Answers.Body: <p>We can start by asking what it means to &quot;solve&quot; a problem. It seems to me that this is almost an unanswerable question. It means in practice that a sufficient number of &quot;experts&quot; are convinced by the &quot;proof&quot; 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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T17:25:50.507Z
Answers.Text: @user253751 What if the shortest valid proof is longer than a human can read in his/her lifetime?
Answers.UserDisplayName: orlp
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-12T18:31:58.743Z
Answers.Text: @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?
Answers.UserDisplayName: Philip Roe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T20:53:00.927Z
Answers.LastActivityDate: 2020-11-11T20:53:00.927Z
Answers.UserDisplayName: Philip Roe
Answers.Body: <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-02T21:36:50.523Z
Answers.Text: The problem with filtering out obviously bad lines is that an obviously bad move such as the uncompensated loss of a queen could turn out to instead have a payoff too far in the future to see.
Answers.UserDisplayName: Mark
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-11T04:35:56.300Z
Answers.LastActivityDate: 2020-11-11T13:16:37.830Z
Answers.LastEditDate: 2020-11-11T13:16:37.830Z
Answers.UserDisplayName: user25233
Body: <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-11T15:25:48.437Z
Comments.Text: 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.
Comments.UserDisplayName: 12345ieee
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-13T12:41:02.833Z
Comments.Text: You've clearly put some deep thought into this question. ;)
Comments.UserDisplayName: Comic Sans Seraphim
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-11-14T11:10:45.583Z
Comments.Text: To add another point to the discussion in the answers below of what solving a game even *means*: Consider the game of [Hex](https://en.wikipedia.org/wiki/Hex_(board_game)). 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
Comments.UserDisplayName: Hagen von Eitzen
Tags: <alphazero><solving>
Title: Is it possible Alpha Zero will eventually solve chess?
ThreadText: # Is it possible Alpha Zero will eventually solve chess?
  
  (Asked by: username_0 on 2020-11-11)
  
  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.
  
  **Tags:** alphazero, solving
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_2**: You've clearly put some deep thought into this question. ;)  
  > **username_3**: To add another point to the discussion in the answers below of what solving a game even *means*: Consider the game of [Hex](https://en.wikipedia.org/wiki/Hex_(board_game)). 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  
  
  ---
  
  ## 6 answers
  
  ### Answer by username_4 on 2020-11-11. Score: 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.
  
  > **Comments:**
  > **username_5**: 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.  https://www.math.wustl.edu/~sk/4-color.pdf  
  > **username_6**: @username_5 An algorithm can be a proof, but that doesn't mean that all algorithms are proofs. AlphaZero's algorithm isn't a proof.  
  > **username_7**: @username_5 Do people doubt the proof of the 4-color theorem?  
  > **username_5**: @username_7, yes some doubt, see Phillip Roe's answer here.  Some also do not agree anything derived by proof by contradiction.  To bring this back to chess, G. H. Hardy said regarding proof by contradiction, ""It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."  
  > **username_8**: 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.  
  > **username_9**: @username_8 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 https://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”.  
  > **username_10**: -1 _"A solution is a mathematical proof."_ No it isn't. A solution is an optimal strategy. AlphaZero might (I'm not saying this is likely) be able to represent the perfect strategy using its neural networks, in which case it might be possible it converges on it. In that scenario, given infinite time, AlphaZero will solve chess. You won't know when it has solved it, but it will. And at some point in time, you will have a solution.  
  > **username_11**: @username_10 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.  
  
  ---
  
  ### Answer by username_12 on 2020-11-11. Score: 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
  
  > **Comments:**
  > **username_13**: 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.  
  > **username_14**: @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.  
  > **username_15**: @username_14'Eh'username_14 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.  
  > **username_14**: @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...  
  > **username_14**: ... 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  
  > **username_14**: ... Anything less than waiting for this isn't "solving" chess, it is just "being a really good chess engine".  
  
  ---
  
  ### Answer by username_16 on 2020-11-11. Score: 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.
  
  > **Comments:**
  > **username_10**: _"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.  
  > **username_3**: @username_10 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.  
  > **username_10**: @username_3 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?  
  
  ---
  
  ### Answer by username_17 on 2020-11-11. Score: 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](https://math.stackexchange.com/questions/1406919/how-many-legal-states-of-chess-exists). 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](https://www.livescience.com/54094-how-big-is-the-internet.html). 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.
  
  > **Comments:**
  > **username_18**: 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!"  
  > **username_17**: @user253751 I *do* believe that chess is compressible. But a "solution" to chess would have to describe the winning moves for every possible game. I suspect that this description is not "compact" for most reasonable definitions of the term. Rules as compact as Stockfish are obviously quite limited. AZ's "rule set" is much larger, but do you believe it is even within 10 orders of magnitude of the "solution"?  
  > **username_17**: @user253751 if we consider spacetime as a unified whole, then the traditional space/time tradeoff is just a rotation in this space. In that case, the brute force solution is very "large", and not at all compressed.  
  > **username_3**: If there are 2^150 legal game states, then each of these can (theoretically) be described/identified by 150 bits - but definitely not less. Perhaps 200 is a good heuristic, but the actual bound is 150  
  > **username_17**: @username_3 that's only true if you define the bitmap for the game state with an exact 1:1 match. However, that can produce a very non-intuitive mapping whose description increases the total size. A naive mapping takes 64 squares and stores a 4-bit value at each indicating piece type and color. That's 256 bits already. You can use run-length encoding to compress the blank squares for some boards, but it will cause others to get bigger. Or you can take 32 pieces x 6 bits to indicate their square, for 186 bits. This is how I created my estimate. See if you can describe your mapping. ;)  
  
  ---
  
  ### Answer by username_18 on 2020-11-11. Score: 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.
  
  > **Comments:**
  > **username_10**: @user253751 What if the shortest valid proof is longer than a human can read in his/her lifetime?  
  > **username_18**: @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?  
  
  ---
  
  ### Answer by username_19 on 2020-11-11. Score: 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.
  
  > **Comments:**
  > **username_20**: The problem with filtering out obviously bad lines is that an obviously bad move such as the uncompensated loss of a queen could turn out to instead have a payoff too far in the future to see.  
  
  ---
  
  