Answers.Body: <p><em>Endgame tablebases</em> can be seen as such an effort, in that we started at few pieces and have increased the number. In 2012, <a href="http://tb7.chessok.com/" rel="noreferrer">7 piece tablebases -from Moscow state university</a> were generated, so chess is solved for positions of 7 or fewer pieces (including the kings).</p>
  <p>The problem is, the 7 piece tablebases take about 140 TB in storage. 8 piece tablebases would take about 10 petabyte of storage, and a computer with 50 TB of ram (<a href="http://tb7.chessok.com/articles/Top8DTM_eng" rel="noreferrer">source</a>) to keep hashes in memory to generate them in reasonable time (a few years?). I guess it would be doable these days if someone makes the millions of dollars available. 9 seems way out of reach.</p>
  <p>So it will take a while before we get to 32.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-21T16:25:33.987Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/121111/discussion-on-answer-by-remcogerlich-what-projects-have-been-undertaken-to-solve).
Answers.UserDisplayName: Brian Towers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T07:05:08.223Z
Answers.LastActivityDate: 2020-07-08T08:34:31.410Z
Answers.LastEditDate: 2020-07-08T08:34:31.410Z
Answers.UserDisplayName: RemcoGerlich
Answers.Body: <p><a href="http://tb7.chessok.com/" rel="nofollow noreferrer">7-piece endgame tablebases</a> were completed in 2012. 8-piece endgame tablebases is the next logical step. <a href="http://tb7.chessok.com/articles/Top8DTM_eng" rel="nofollow noreferrer">This page</a> says a little about how those are going (context is searching for the longest forced mate in pawnless positions):</p>
  <blockquote>
  <p>Many show interest in what is to expect from [8-piece] endings ... Unfortunately the size of [8-piece tablebases] will be 100 times larger than size of [7-piece] tablebases. To fully compute them, one will need about 10 PB (10000 TB) of disk space and 50 TB of RAM. Only top 10 supercomputers can solve [8-piece] problem in 2014. So don't hold your breath expecting new breakthroughs too soon - the first 1000-move mate is unlikely to be found until 2020 when a part of a TOP100 supercomputer may be allowed to be used for solving this task.</p>
  </blockquote>
  <p>If we get 8-piece tablebases one day (<em>if</em> we get them) that'll be the next step to solving chess, but we don't expect to get them for many years more at least. Even if they are created, they'll take huge amounts of disk space to store.</p>
  <p>In principle chess will be solved when we have 32-piece tablebases, but if 8-piece tablebases are this hard to create, we are not going to solve chess in the foreseeable future, AlphaZero or not.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T01:28:11.270Z
Answers.Text: In 2020 you can rent 10PB of disk and 50TB of RAM (and a few tens of thousands of CPU cores into the bargain) for maybe 5 million dollars per year.
Answers.UserDisplayName: hobbs
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T07:00:09.000Z
Answers.LastActivityDate: 2020-07-10T04:11:25.287Z
Answers.LastEditDate: 2020-07-10T04:11:25.287Z
Answers.UserDisplayName: Allure
Answers.Body: <p>AlphaZero has no intention of solving chess. It's just an engine that plays spectacularly well. The number of positions you'd have to evaluate in order to solve chess is larger than the number of atoms in the universe, so even if you could solve chess (which is nowhere near the capabilities of the current capability of all computers on Earth combined), you wouldn't be able to store the entire solution anywhere</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T15:24:37.820Z
Answers.Text: Well, you're assuming that you'd have to store every position. You could certainly discard the "worst" moves without storing them, or encode a "short" algorithm that works from a number of similar positions, avoiding the need to store them directly. Also, you can make the case that any chess-playing AI is a storage of the solution to every position it is able to win from, regardless of whether it had any a-priori knowledge of that position or not.
Answers.UserDisplayName: jpaugh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T16:53:35.750Z
Answers.Text: @jpaugh exactly . A0 does not "store" every position that is why i said that , that particular project  is particularly interesting  when it comes to solving chess. if we could follow A0 with big investment maybe it can take us very far into uncharted territories
Answers.UserDisplayName: shashank shekhar singh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T22:17:21.080Z
Answers.Text: @jpaugh in order to "solve" chess, you'd need to have the solution stored somewhere. Otherwise you'd have no way to know whether you solved it or not.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T22:47:17.293Z
Answers.Text: As I mentioned elsewhere, results like PSAPCE completeness of generalized chess suggests we should not expect to be able to compress a solution into sub-galactic size, even implicitly like in the guts of an engine. This contrasts with NP-complete problems whose solutions may be hard to find, but are small.
Answers.UserDisplayName: usul
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T00:55:07.737Z
Answers.Text: @David Nim with initial heaps of sizes {1,2,...,100} has a larger space of valid positions than chess, but it's solved. The solution consists of an algorithm that computes a move given a position, and a proof that the move it computes is always optimal. Chess is probably harder than Nim but the size of the position space by itself doesn't tell you much.
Answers.UserDisplayName: benrg
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T06:25:14.003Z
Answers.Text: @benrg sure, the argument about storage space implicitly assumes that you have to store a significant fraction of positions. However, no algorithm has been found for chess, and given the numerous attempts at finding one, it's likely that an implementable one exists. The chess computer community certainly has given up on finding one, anyway.
Answers.UserDisplayName: toolforger
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T12:19:01.487Z
Answers.Text: @David _"in order to "solve" chess, you'd need to have the solution stored somewhere"_ - yes, you would need to store _the_ solution, not all other non-solution positions, which essentially comes down to only 1 game of chess (the forcing solution).
Answers.UserDisplayName: gented
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T12:49:04.357Z
Answers.Text: @gented That wouldn't be a solution. For instnace on the first move you have 20 different alternatives, all of them leading to a draw (therefore equivalent), it's not enough to have analyzed one of them.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T15:16:05.230Z
Answers.Text: You can store it in a black hole:)
Answers.UserDisplayName: postoronnim
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T20:55:41.890Z
Answers.Text: @David That's not what we said (do you even read the comments?). You *do* analyse all of them, but you only *store* the one that is winning.
Answers.UserDisplayName: gented
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-12T09:23:04.150Z
Answers.Text: @gented Why do you expect any winning move to exist? Chess is more likely to be a draw with perfect play. Even after you only store the winning move (maybe 1.e4), then you have to store the answer to all twenty possible answers by Black, and after you store that you need to store the winning move against all 400+ combinations of moves (just by move two!)
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-14T09:50:33.997Z
Answers.Text: @David _"Why do you expect any winning move to exist?"_ I don't, that's not the point of what we are discussing, please read the comments above again.You don't need to store _anything_, that's exactly the point: searching a solution does NOT require storing the attempts of the search. _If_ and only _if_ you accidentally find a solution (you may or you may not) _then_ you store only that one chess game leading to that solution (which is 1 `.pgn` file only): all your previous attempts, however many numerous they are, need NOT be stored anywhere.
Answers.UserDisplayName: gented
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-14T10:35:00.763Z
Answers.Text: @pented It's a bit rude to assume that I hold the view I hold because of my ignorance or lack of reading comprehension rather than for the possibility that I may be right. The solution must include all answers to the alternative moves by the losing side (or both sides if the game is a draw). Sure you can store everything in a single .pgn file, of course! Only that .pgn file's size in TB will be several orders of magnitude beyond the number of atoms in the observable universe. But sure, it's still a single .pgn file
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-07T01:06:16.343Z
Answers.Text: @gented Typically in mathematics, when we "solve" something, we are expected not only to solve it, but to produce a way to verify that the solution was indeed found, without requiring the reader to solve it themselves.  This can be substantially smaller than "everything," but typically larger than "here's the best Chess game playable."
Answers.UserDisplayName: Cort Ammon
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-07T08:53:53.907Z
Answers.Text: @David _"The solution must include all answers to the alternative moves by the losing side. Only that .pgn file's size in TB will be several orders of magnitude beyond the number of atoms in the observable universe"_ This is false, see _all_ my comments above (you are in fact still not comprehending any of the comments). Other users in the comments have indicated this too (so I am really puzzled on why this discussion still continues).
Answers.UserDisplayName: gented
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T06:52:58.067Z
Answers.LastActivityDate: 2020-07-08T13:22:21.183Z
Answers.LastEditDate: 2020-07-08T13:22:21.183Z
Answers.UserDisplayName: David
Answers.Body: <p>Can't answer your main question, but to the point about alphazero: from my perspective, AlphaZero, although it may be a major step in superhuman performance in games, is not even a minor step towards solving chess.</p>
  <blockquote>
  <p>if we could follow A0 with big investment maybe it can take us very far into uncharted territories</p>
  </blockquote>
  <p>I don't think this is true. Its approach, which is to explore the game-tree by picking paths which have high probability of being good, doesn't seem to have much implication to fully solve chess.  Although it may be very very good at being very very good at chess, I think this heuristic-based approach is less viable to exactly solving chess than you think.</p>
  <p>To be very charitable, maybe... and by maybe I mean this is a pie-in-the-sky thought that just came from my dumb brain... maybe the AlphaZero work could someday lead to a proof that with training, the model converges to a model that plays correctly with probability 1 (and <code>1</code> in this case is aka 99.999...%), but even this may not be considered &quot;solving&quot; chess as we still cannot  not prove that any model we have trained in real life makes every move correctly.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T04:39:06.033Z
Answers.Text: ".... Its approach, which is to explore the game-tree by picking paths which have high probability of being good" what is wrong with this approach?
Answers.UserDisplayName: shashank shekhar singh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T05:57:37.290Z
Answers.Text: @shashankshekharsingh I just don't see how it is related to the prospect of fully solving chess.  As I said, there's nothing "wrong" with it -- it's very very good at playing games better than anything we've seen before, but I don't see the connection to the goal at hand.
Answers.UserDisplayName: Kevin Wang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T10:00:44.293Z
Answers.Text: well lets say there are 10^40 [sensible positions](https://en.wikipedia.org/wiki/Shannon_number) , a0 can at least  bring that number further down without needing those humongous amounts of storage since it is the best at chess. and then maybe some other approach can be applied.
Answers.UserDisplayName: shashank shekhar singh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T10:08:29.407Z
Answers.Text: Is a0 even being used to solve chess , say the 8 piece table-bases ?
Answers.UserDisplayName: shashank shekhar singh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T18:56:30.560Z
Answers.Text: "Is a0 even being used to solve chess , say the 8 piece table-bases?"  That's a good question.  I don't know the answer to that.
Answers.UserDisplayName: Kevin Wang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-15T21:47:56.573Z
Answers.Text: @shashankshekharsingh Solving chess requires proof. High probability isn't the same as solving.
Answers.UserDisplayName: David Liu
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T18:39:19.553Z
Answers.LastActivityDate: 2020-07-09T06:46:53.143Z
Answers.LastEditDate: 2020-07-09T06:46:53.143Z
Answers.UserDisplayName: Kevin Wang
Answers.Body: <p>It is funny that you bring up mathematics and the universe as things we know quite a bit about.  Yet neither of these fields is 'solved'.  Moreover, neither ever can be.</p>
  <p>Mathematics can never be fully solved due to <a href="https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems" rel="nofollow noreferrer">Goedel's Incompleteness Theorems</a>.  There will always be true facts about numbers that we cannot find proofs of.</p>
  <p>As with the Universe, we can never know the full 'state' of the universe (eg what every atom and subatomic particle is doing) precisely due to the<a href="https://en.wikipedia.org/wiki/Uncertainty_principle" rel="nofollow noreferrer">Heisenberg's Uncertainty Principle</a>.  We can never hope to tell what is going on outside the <a href="https://en.wikipedia.org/wiki/Observable_universe" rel="nofollow noreferrer">observable universe</a> due to relativity.</p>
  <p>So in some sense, they are pretty fair comparisons to chess.  We know a lot, but due to universe we live in, we will never know it all.</p>
  <p>The best I believe we can hope for in terms of solving chess would be an ultra-weak solution (possibly involving some strategy stealing) that proves a eg a forced draw (or better) for white from the starting position without explicitly solving how.</p>
  <p>For an interesting article about endgame table-bases and methods for solving games, <em>check</em> out <a href="http://dit.unitn.it/%7Emontreso/asd/docs/checkers.pdf" rel="nofollow noreferrer">this</a>.  Checkers (a MUCH simpler game) was solved to be a draw over a decade ago</p>
  <p><strong>EDIT To clear up some confusion:</strong></p>
  <p>As pointed out in the comments, the unsolvability of these three systems are immensely and qualitatively different.  The incompleteness theorems derive from first principles and would hold up in ANY universe.  The unsolvability of the state of the universe is based on the physical laws of the one we live in.  The unsolvability of chess is only due to the fact that the universe we happen to live in is too small and chess is too large for a (strong) solution to be held inside it.  The reason they are similar here are pure coincidence, simply a by-product of universe we all happen to inhabit.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-21T16:26:36.920Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/121112/discussion-on-answer-by-dongky-what-projects-have-been-undertaken-to-solve-chess).
Answers.UserDisplayName: Brian Towers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-08T15:36:00.910Z
Answers.LastActivityDate: 2020-07-09T16:37:41.373Z
Answers.LastEditDate: 2020-07-09T16:37:41.373Z
Answers.UserDisplayName: DongKy
Answers.Body: <p>Others have already mentioned tablebases and their development, but something that hasn't been touched on yet is the sheer space complexity of chess.</p>
  <p>In order to say that chess is solved, we need a function <code>gameState -&gt; move</code>, and that function needs to be defined for all possible states of the game, or at least all of the ones that are reachable within the rules of the game. <a href="https://en.wikipedia.org/wiki/Shannon_number" rel="nofollow noreferrer">There are vastly more of these than there are atoms in the observable universe.</a> So even if we could somehow encode each game state and its corresponding best move into a single atom, there isn't enough matter in the universe to build the server that would run the database.</p>
  <p>Endgame tablebases are interesting, but there's nobody who's seriously attempting to solve chess.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T01:49:18.923Z
Answers.Text: Who said that in order for a function to be defined, all possible inputs and their outputs need to be stored in a database? By this argument, the function `f(x, y) = x + y` cannot be defined, even for natural numbers, because there are more natural numbers than there are atoms in the universe.
Answers.UserDisplayName: LarsH
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T03:03:00.300Z
Answers.Text: @LarsH that's just what solving means in this context. If you're saying it can be a function that we compute on the fly... then we're right back to game tree search.
Answers.UserDisplayName: MattPutnam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T04:28:18.823Z
Answers.Text: @MattPutnam "....but there's nobody who's seriously attempting to solve chess." well that is the actual answer I guess. :)
Answers.UserDisplayName: shashank shekhar singh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T09:06:01.033Z
Answers.Text: A mathematical proof of whether the starting position is a win, or a forced draw, would be one kind of "solution" of chess without necessarily requiring a brute-force exhaustive tablebase.
Answers.UserDisplayName: nanoman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T10:32:08.610Z
Answers.Text: @nanoman yes exactly. i am more interested in that kind of solution rather than engine based brute force attempts. Chess theory has to be developed.
Answers.UserDisplayName: shashank shekhar singh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T14:15:35.863Z
Answers.Text: @Matt Not necessarily. There are many ways that functions can be computed on the fly, besides tree search.
Answers.UserDisplayName: LarsH
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T00:01:37.433Z
Answers.LastActivityDate: 2020-07-09T00:01:37.433Z
Answers.UserDisplayName: MattPutnam
Answers.Body: <p>Another line of attack is reducing dimension: Gardner's 5x5 <a href="https://en.wikipedia.org/wiki/Minichess#5%C3%975_chess" rel="nofollow noreferrer">minichess</a> has been <a href="https://arxiv.org/abs/1307.7118" rel="nofollow noreferrer">weakly solved</a> by Mehdi Mhalla and Frederic Prost in 2013. 3x3 and 3x4 boards have been <a href="http://kirr.homeunix.org/chess/3x3-chess/" rel="nofollow noreferrer">strongly</a> <a href="http://kirr.homeunix.org/chess/3x4-chess/" rel="nofollow noreferrer">solved</a> in the 2000s with complete tablebases for each position by Kirill Kryukov, and 9-men tablebases for <a href="http://kirill-kryukov.com/chess/4x4-chess/" rel="nofollow noreferrer">4x4 chess</a> have been completed in 2011 by the same author.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-11T05:54:16.193Z
Answers.LastActivityDate: 2020-07-11T07:27:47.473Z
Answers.LastEditDate: 2020-07-11T07:27:47.473Z
Answers.UserDisplayName: Federico Poloni
Answers.Body: <p>Shirish Chinchalkar has a <a href="https://www.semanticscholar.org/paper/An-Upper-Bound-for-the-Number-of-Reachable-Chinchalkar/9a5c2437d6f30c8281a8ee67cf9200cff7d06051" rel="nofollow noreferrer">paper</a> which calculates an upper bound of ~10^46 for the number of positions in chess (different from moves obviously). Arguments which talk about the number of atoms in the universe are very facetious on account of using position differences (we can only get to a position from another, so why not just store what piece moved instead of the whole new position?) as well as compression. IIRC, in the <a href="https://syzygy-tables.info/" rel="nofollow noreferrer">Syzygy endgame tables</a>,  each position can be represented by less than a single bit after taking into consideration compression.</p>
  <p>One thing that I personally wonder, and I could be completely wrong, is whether there would be at a certain point a relative small decrease in complexity as n -&gt; 32 as there will be less starting nodes.</p>
  <p>It's an amazing question though. I would love to see it (even weakly) solved in my lifetime.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T14:53:04.123Z
Answers.Text: A quick calculation shows 3x10^23 possible positions, of which some number are unreachable.  There are 13 possible states for each square - 6 pieces on each side - pawn, rook, knight, bishop, queen, king plus 1 empty space.  There are 64 squares - so 64^13 possible positions.  This seems much more reasonable than 10^46, though still a very large number.  the fact that the game-tree has 10^120 moves (shannon number) is irrelevant.  you only need to keep 'the one winning move' for each of these 10^23 states.
Answers.UserDisplayName: Jim
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T15:19:19.400Z
Answers.Text: the unreachable states would take into account that there are only ever 2 kings on a board with 2048 total positions of them, instead of up to 64 kings.  it would also limit to a maximum of 8 pawns each (again down from 64), and have a maximum bounds on the other pieces due to promotion - say, 4 queens, 6 rooks, 6 bishops, and 6 knights.  my math is too rusty to calculate this, but i expect orders of magnitudes of possible positions can be discarded.
Answers.UserDisplayName: Jim
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T15:54:12.087Z
Answers.Text: one final note on unreachable states - there has to be a minimum of 32 empty spaces, up to 61.  so, again, anything outside this range can be excluded.
Answers.UserDisplayName: Jim
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T16:40:33.817Z
Answers.Text: Hi Jim, it's actually 13^64 (~10^71) according to your reasoning. So using the different pieces of information you've given you could look to reduce it. However, positions also take account of whether castling is possible for either side and if there are any en-passant squares. See here for position vs diagram: http://wismuth.com/chess/statistics-positions.html
Answers.UserDisplayName: Colin McDonagh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-14T15:12:29.273Z
Answers.Text: Colin, that's embarassing.  like i said, my math is rusty.  what is the etiquette for a wrong post?  should i delete it or leave it up? i think the follow-on posts are valid.  one more interesting limiter - with 8 pawns in row 2, there are only 16 possible states of row 1, 4 on each side with the rook & knight possibly switching places or the knight not being there.
Answers.UserDisplayName: Jim
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-14T15:21:52.743Z
Answers.Text: @Jim haha don't worry, we all make mistakes. I've looked at all of this in the past hence anything less than 10^46 would arouse my suspicions. If you're too embarrassed you can delete it, but I don't think there's any reason to hide mistakes. Yeah, one of my friends once wrote up a little article on the same! Having a lot of pawns on their starting positions really restricts the possible positions of pieces
Answers.UserDisplayName: Colin McDonagh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-14T15:23:03.383Z
Answers.Text: @Jim I'm currently trying to publish a small paper on pawn positions. I'll post it here if it ever gets published!
Answers.UserDisplayName: Colin McDonagh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-10T11:05:11.547Z
Answers.LastActivityDate: 2020-07-10T14:08:19.200Z
Answers.LastEditDate: 2020-07-10T14:08:19.200Z
Answers.UserDisplayName: Colin McDonagh
Answers.Body: <p>Nice question. The wikipedia page <a href="https://en.wikipedia.org/wiki/Solving_chess" rel="nofollow noreferrer">Solving chess</a> also report only endgame tables as partial results.</p>
  <p>Personally, I believe that tools from <strong>combinatorial game theory</strong> are essential to solve chess completely (unless by something similar to an exhaustive search; I would argue that the machine learning method is under the hood an exhaustive search [plus some pruning-type techniques]). Don't expect the the machine learning tools to be of help here if you think the solution should build a chess theory. Combinatorial Game Theory (CGT) is the study of combinatorial games. Chess is not a combinatorial game. But, tools from CGT sometimes do a good job of (partially) solving games which are not combinatorial (e.g.: dots and boxes).</p>
  <p>See papers <a href="http://web.stanford.edu/%7Ewqy/research/Math%20191-%20Chess.pdf" rel="nofollow noreferrer">[1]</a> and <a href="http://library.msri.org/books/Book29/files/elkies.pdf" rel="nofollow noreferrer">[2]</a> for a taste of what to expect.</p>
  <p>By the way, the fact that generalized chess is computationally hard says practically nothing about chess.</p>
  <p>Linked resources:<br />
  [1] Qingyun Wu, Frank Yu, Michael Landry, A combinatorial game theoretic analysis of chessendgames.<br />
  [2] Noam D. Elkies, On numbers and endgames: Combinatorial game theory in chess endgames.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-03T09:16:20.833Z
Answers.Text: Also see this: https://chess.stackexchange.com/a/27267/14678
Answers.UserDisplayName: Cyriac Antony
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-03T07:58:51.470Z
Answers.LastActivityDate: 2021-04-03T08:15:48.673Z
Answers.LastEditDate: 2021-04-03T08:15:48.673Z
Answers.UserDisplayName: Cyriac Antony
Answers.Body: <p>I think the other answers and comment have made it clear that this is a really complex problem. So complex, that no classic computer will ever come close to solving it.</p>
  <p>But I have asked myself the same question. Isn't chess a perfect example to use a quantum computer? Although quantum computers are not yet fully ready for use there do exist &quot;programming languages&quot;, and there are already many algorithms for a quantum computer described this way. There actually even exist simulators for running these quantum computer &quot;programs&quot; on classic computers.</p>
  <p>I wonder how feasible it would be to write an algorithm for solving chess on a quantum computer. Or would that require so many qbits, that we can never expect an actual quantum computer that could run this algorithm? But if it would once exist, shouldn't it be able to answer the question within a second?</p>
  <p>Just to clarify, since I mentioned the possibility to simulate these algorithms on classic computers. This simulation of course only makes this very complex problem solved even less performant, so those simulators could only be used for testing of the algorithm, not for really using it.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-11T04:11:24.953Z
Answers.Text: there are no actual quantum computers as of now hence those algorithms don't mean much as you still don't get the time advantage of quantum computers. so we have to wait for that
Answers.UserDisplayName: shashank shekhar singh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-11T00:39:07.147Z
Answers.LastActivityDate: 2020-07-11T00:39:07.147Z
Answers.UserDisplayName: Claus
Answers.Body: <p>I think everyone here has a good and necessary point with the space complexity of chess being larger than the number of atoms in the observable universe.  However, I think I can add some additional points onto that.</p>
  <ol>
  <li><p>As others have pointed out, the definition of &quot;solved&quot; is not super clear.  If &quot;solved&quot; means &quot;find the optimal move from any possible game state&quot;, solving chess is impossible.  However, if we take solved to mean that we just want to play the single &quot;perfect&quot; game of chess we may be able to reduce space complexity.</p>
  </li>
  <li><p>The problem with point one is that chess does not have a single perfect game.  A perfect game of chess implies that you are always making the move that leaves you with the highest chance of winning.  It also implies that you are accounting for your opponent making optimal moves, as otherwise it would not be a perfect game (and would also break the previous space complexity issues).  However, chess is a well balanced game and any game perfectly played would necessarily end in a draw.</p>
  </li>
  <li><p>There are likely a near-infinite number of optimally played games that end in a draw.  While the number of optimal moves from any position is much smaller than the number of possible moves, according to the best chess engines we have today there are many moves that have near-optimal results from the starting position and in the first few moves.  Because a significant advantage is needed to win any game of chess, many of these moves would likely be included in a &quot;perfect&quot; or solved game.</p>
  </li>
  <li><p>Lastly, how would you prove my points 2 and 3 right or wrong? You can't.  Again, you run into the space complexity issue.  To prove any position is either winnable or unwinnable if both players play optimally, you need to diagram out every single possible move from a given position.  As we have shown earlier, this is impossible until we are below a certain piece number.</p>
  </li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T21:13:03.317Z
Answers.Text: I'm not sure you understand what "solving" a game means. Once you "solve" a game you have a strategy by which you always win (as with checkers, which has been solved), or for some games, always tie (as in tic-tac-toe). It isn't just playing "a single perfect game"
Answers.UserDisplayName: Kevin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-11T01:33:40.917Z
Answers.Text: "There are likely a near-infinite number of optimally played games that end in a draw.": It is *believed* that an optimally played chess game is a draw. *proving* it would be a huge step toward solving chess.
Answers.UserDisplayName: Bit Chaser
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-14T22:27:13.860Z
Answers.Text: @KevinWells That definition of "solving" is not available to chess, so it makes the conversation much less interesting. (You can't force a win from every possible game position, and it isn't clear that you could force a win from the starting position, either.)
Answers.UserDisplayName: jpaugh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-15T14:27:37.027Z
Answers.Text: @jpaugh What other definition of "solving" are you using then? The whole point of this question is if we are able to move towards that goal, and if so what efforts are being made to do so. The real answer is that solving chess is certainly out of reach currently, and may never be in reach, but there are still efforts to be made to improve our knowledge of solving increasingly complex starting positions
Answers.UserDisplayName: Kevin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-15T14:36:20.497Z
Answers.Text: @KevinWells How about, being able to know the outcome of any game, given the starting position, and two opponents who play perfectly? Solving chess is not about winning an *individual* game, but predicting the outcome of every game well enough to give yourself the best chance of winning.
Answers.UserDisplayName: jpaugh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-15T15:27:46.993Z
Answers.Text: @jpaugh Your question is answered by my point four.  You can't know the outcome of any game from a given starting position because that would be equivalent in complexity to knowing the outcome of all the possible games that could be played.  As has been discussed in the other answers, this is impossible.
Answers.UserDisplayName: Richard Boone
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-15T18:44:55.330Z
Answers.Text: @jpaugh Solving for every possible game from the starting position is exactly what I'm talking about. I even said that solving a game isn't about playing a single perfect game, which is exactly what you're saying, so I don't understand your criticism. You said that that is a bad definition because it's out of reach for chess, but that doesn't make it a bad definition, it just makes the answer kind of boring
Answers.UserDisplayName: Kevin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-09T13:02:16.707Z
Answers.LastActivityDate: 2020-07-09T13:02:16.707Z
Answers.UserDisplayName: Richard Boone
Body: <p>Chess is not completely solved yet but what efforts have been undertaken to solve it? Has there been a large project like the HGP or is something like that even worth pursuing? What failed efforts have been there if any? I am speculating that the the Alpha Zero project must have taken some steps towards that end.</p>
  <p>EDIT:-Answers ponder on the point that is extremely difficult to solve chess which i have clearly indicated in the first line in the question. What I would like to know that are there or have there been any projects that try to solve chess. Like that Moscow university 7-piece tablebases and any efforts like that. It is clearly an expensive problem to solve but who is doing it and what approaches are being taken? It is often said that there are more chess combinations than atoms in the universe (probably because of that ad) but so are the real numbers but we have a rich theory about that. We also know a great deal about the universe as well but we had to try hard to get to that point. Is chess being treated the same is my question.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-21T16:25:17.737Z
Comments.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/121110/discussion-on-question-by-shashank-shekhar-singh-what-projects-have-been-underta).
Comments.UserDisplayName: Brian Towers
Tags: <theory>
Title: What projects have been undertaken to solve chess completely?
ThreadText: # What projects have been undertaken to solve chess completely?
  
  (Asked by: username_0 on 2020-07-08)
  
  Chess is not completely solved yet but what efforts have been undertaken to solve it? Has there been a large project like the HGP or is something like that even worth pursuing? What failed efforts have been there if any? I am speculating that the the Alpha Zero project must have taken some steps towards that end.
  
  EDIT:-Answers ponder on the point that is extremely difficult to solve chess which i have clearly indicated in the first line in the question. What I would like to know that are there or have there been any projects that try to solve chess. Like that Moscow university 7-piece tablebases and any efforts like that. It is clearly an expensive problem to solve but who is doing it and what approaches are being taken? It is often said that there are more chess combinations than atoms in the universe (probably because of that ad) but so are the real numbers but we have a rich theory about that. We also know a great deal about the universe as well but we had to try hard to get to that point. Is chess being treated the same is my question.
  
  **Tags:** theory
  
  > **Comments:**
  > **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/121110/discussion-on-question-by-username_0-shekhar-username_0-what-projects-have-been-underta).  
  
  ---
  
  ## 11 answers
  
  ### Answer by username_2 on 2020-07-08. Score: 43
  
  *Endgame tablebases* can be seen as such an effort, in that we started at few pieces and have increased the number. In 2012, [7 piece tablebases -from Moscow state university](http://tb7.chessok.com/) were generated, so chess is solved for positions of 7 or fewer pieces (including the kings).
  
  The problem is, the 7 piece tablebases take about 140 TB in storage. 8 piece tablebases would take about 10 petabyte of storage, and a computer with 50 TB of ram ([source](http://tb7.chessok.com/articles/Top8DTM_eng)) to keep hashes in memory to generate them in reasonable time (a few years?). I guess it would be doable these days if someone makes the millions of dollars available. 9 seems way out of reach.
  
  So it will take a while before we get to 32.
  
  > **Comments:**
  > **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/121111/discussion-on-answer-by-username_2-what-projects-have-been-undertaken-to-solve).  
  
  ---
  
  ### Answer by username_3 on 2020-07-08. Score: 19
  
  [7-piece endgame tablebases](http://tb7.chessok.com/) were completed in 2012. 8-piece endgame tablebases is the next logical step. [This page](http://tb7.chessok.com/articles/Top8DTM_eng) says a little about how those are going (context is searching for the longest forced mate in pawnless positions):
  
  > Many show interest in what is to expect from [8-piece] endings ... Unfortunately the size of [8-piece tablebases] will be 100 times larger than size of [7-piece] tablebases. To fully compute them, one will need about 10 PB (10000 TB) of disk space and 50 TB of RAM. Only top 10 supercomputers can solve [8-piece] problem in 2014. So don't hold your breath expecting new breakthroughs too soon - the first 1000-move mate is unlikely to be found until 2020 when a part of a TOP100 supercomputer may be allowed to be used for solving this task.
  
  If we get 8-piece tablebases one day (*if* we get them) that'll be the next step to solving chess, but we don't expect to get them for many years more at least. Even if they are created, they'll take huge amounts of disk space to store.
  
  In principle chess will be solved when we have 32-piece tablebases, but if 8-piece tablebases are this hard to create, we are not going to solve chess in the foreseeable future, AlphaZero or not.
  
  > **Comments:**
  > **username_4**: In 2020 you can rent 10PB of disk and 50TB of RAM (and a few tens of thousands of CPU cores into the bargain) for maybe 5 million dollars per year.  
  
  ---
  
  ### Answer by username_5 on 2020-07-08. Score: 15
  
  AlphaZero has no intention of solving chess. It's just an engine that plays spectacularly well. The number of positions you'd have to evaluate in order to solve chess is larger than the number of atoms in the universe, so even if you could solve chess (which is nowhere near the capabilities of the current capability of all computers on Earth combined), you wouldn't be able to store the entire solution anywhere
  
  > **Comments:**
  > **username_6**: Well, you're assuming that you'd have to store every position. You could certainly discard the "worst" moves without storing them, or encode a "short" algorithm that works from a number of similar positions, avoiding the need to store them directly. Also, you can make the case that any chess-playing AI is a storage of the solution to every position it is able to win from, regardless of whether it had any a-priori knowledge of that position or not.  
  > **username_0**: @username_6 exactly . A0 does not "store" every position that is why i said that , that particular project  is particularly interesting  when it comes to solving chess. if we could follow A0 with big investment maybe it can take us very far into uncharted territories  
  > **username_5**: @username_6 in order to "solve" chess, you'd need to have the solution stored somewhere. Otherwise you'd have no way to know whether you solved it or not.  
  > **username_7**: As I mentioned elsewhere, results like PSAPCE completeness of generalized chess suggests we should not expect to be able to compress a solution into sub-galactic size, even implicitly like in the guts of an engine. This contrasts with NP-complete problems whose solutions may be hard to find, but are small.  
  > **username_8**: @username_5 Nim with initial heaps of sizes {1,2,...,100} has a larger space of valid positions than chess, but it's solved. The solution consists of an algorithm that computes a move given a position, and a proof that the move it computes is always optimal. Chess is probably harder than Nim but the size of the position space by itself doesn't tell you much.  
  > **username_9**: @username_8 sure, the argument about storage space implicitly assumes that you have to store a significant fraction of positions. However, no algorithm has been found for chess, and given the numerous attempts at finding one, it's likely that an implementable one exists. The chess computer community certainly has given up on finding one, anyway.  
  > **username_10**: @username_5 _"in order to "solve" chess, you'd need to have the solution stored somewhere"_ - yes, you would need to store _the_ solution, not all other non-solution positions, which essentially comes down to only 1 game of chess (the forcing solution).  
  > **username_5**: @username_10 That wouldn't be a solution. For instnace on the first move you have 20 different alternatives, all of them leading to a draw (therefore equivalent), it's not enough to have analyzed one of them.  
  > **username_11**: You can store it in a black hole:)  
  > **username_10**: @username_5 That's not what we said (do you even read the comments?). You *do* analyse all of them, but you only *store* the one that is winning.  
  > **username_5**: @username_10 Why do you expect any winning move to exist? Chess is more likely to be a draw with perfect play. Even after you only store the winning move (maybe 1.e4), then you have to store the answer to all twenty possible answers by Black, and after you store that you need to store the winning move against all 400+ combinations of moves (just by move two!)  
  > **username_10**: @username_5 _"Why do you expect any winning move to exist?"_ I don't, that's not the point of what we are discussing, please read the comments above again.You don't need to store _anything_, that's exactly the point: searching a solution does NOT require storing the attempts of the search. _If_ and only _if_ you accidentally find a solution (you may or you may not) _then_ you store only that one chess game leading to that solution (which is 1 `.pgn` file only): all your previous attempts, however many numerous they are, need NOT be stored anywhere.  
  > **username_5**: @pented It's a bit rude to assume that I hold the view I hold because of my ignorance or lack of reading comprehension rather than for the possibility that I may be right. The solution must include all answers to the alternative moves by the losing side (or both sides if the game is a draw). Sure you can store everything in a single .pgn file, of course! Only that .pgn file's size in TB will be several orders of magnitude beyond the number of atoms in the observable universe. But sure, it's still a single .pgn file  
  > **username_12**: @username_10 Typically in mathematics, when we "solve" something, we are expected not only to solve it, but to produce a way to verify that the solution was indeed found, without requiring the reader to solve it themselves.  This can be substantially smaller than "everything," but typically larger than "here's the best Chess game playable."  
  > **username_10**: @username_5 _"The solution must include all answers to the alternative moves by the losing side. Only that .pgn file's size in TB will be several orders of magnitude beyond the number of atoms in the observable universe"_ This is false, see _all_ my comments above (you are in fact still not comprehending any of the comments). Other users in the comments have indicated this too (so I am really puzzled on why this discussion still continues).  
  
  ---
  
  ### Answer by username_13 on 2020-07-08. Score: 6
  
  Can't answer your main question, but to the point about alphazero: from my perspective, AlphaZero, although it may be a major step in superhuman performance in games, is not even a minor step towards solving chess.
  
  > if we could follow A0 with big investment maybe it can take us very far into uncharted territories
  
  I don't think this is true. Its approach, which is to explore the game-tree by picking paths which have high probability of being good, doesn't seem to have much implication to fully solve chess. Although it may be very very good at being very very good at chess, I think this heuristic-based approach is less viable to exactly solving chess than you think.
  
  To be very charitable, maybe... and by maybe I mean this is a pie-in-the-sky thought that just came from my dumb brain... maybe the AlphaZero work could someday lead to a proof that with training, the model converges to a model that plays correctly with probability 1 (and `1` in this case is aka 99.999...%), but even this may not be considered "solving" chess as we still cannot not prove that any model we have trained in real life makes every move correctly.
  
  > **Comments:**
  > **username_0**: ".... Its approach, which is to explore the game-tree by picking paths which have high probability of being good" what is wrong with this approach?  
  > **username_13**: @username_0 I just don't see how it is related to the prospect of fully solving chess.  As I said, there's nothing "wrong" with it -- it's very very good at playing games better than anything we've seen before, but I don't see the connection to the goal at hand.  
  > **username_0**: well lets say there are 10^40 [sensible positions](https://en.wikipedia.org/wiki/Shannon_number) , a0 can at least  bring that number further down without needing those humongous amounts of storage since it is the best at chess. and then maybe some other approach can be applied.  
  > **username_0**: Is a0 even being used to solve chess , say the 8 piece table-bases ?  
  > **username_13**: "Is a0 even being used to solve chess , say the 8 piece table-bases?"  That's a good question.  I don't know the answer to that.  
  > **username_14**: @username_0 Solving chess requires proof. High probability isn't the same as solving.  
  
  ---
  
  ### Answer by username_15 on 2020-07-08. Score: 6
  
  It is funny that you bring up mathematics and the universe as things we know quite a bit about. Yet neither of these fields is 'solved'. Moreover, neither ever can be.
  
  Mathematics can never be fully solved due to [Goedel's Incompleteness Theorems](https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems). There will always be true facts about numbers that we cannot find proofs of.
  
  As with the Universe, we can never know the full 'state' of the universe (eg what every atom and subatomic particle is doing) precisely due to the[Heisenberg's Uncertainty Principle](https://en.wikipedia.org/wiki/Uncertainty_principle). We can never hope to tell what is going on outside the [observable universe](https://en.wikipedia.org/wiki/Observable_universe) due to relativity.
  
  So in some sense, they are pretty fair comparisons to chess. We know a lot, but due to universe we live in, we will never know it all.
  
  The best I believe we can hope for in terms of solving chess would be an ultra-weak solution (possibly involving some strategy stealing) that proves a eg a forced draw (or better) for white from the starting position without explicitly solving how.
  
  For an interesting article about endgame table-bases and methods for solving games, *check* out [this](http://dit.unitn.it/%7Emontreso/asd/docs/checkers.pdf). Checkers (a MUCH simpler game) was solved to be a draw over a decade ago
  
  **EDIT To clear up some confusion:**
  
  As pointed out in the comments, the unsolvability of these three systems are immensely and qualitatively different. The incompleteness theorems derive from first principles and would hold up in ANY universe. The unsolvability of the state of the universe is based on the physical laws of the one we live in. The unsolvability of chess is only due to the fact that the universe we happen to live in is too small and chess is too large for a (strong) solution to be held inside it. The reason they are similar here are pure coincidence, simply a by-product of universe we all happen to inhabit.
  
  > **Comments:**
  > **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/121112/discussion-on-answer-by-username_15-what-projects-have-been-undertaken-to-solve-chess).  
  
  ---
  
  ### Answer by username_16 on 2020-07-09. Score: 4
  
  Others have already mentioned tablebases and their development, but something that hasn't been touched on yet is the sheer space complexity of chess.
  
  In order to say that chess is solved, we need a function `gameState -> move`, and that function needs to be defined for all possible states of the game, or at least all of the ones that are reachable within the rules of the game. [There are vastly more of these than there are atoms in the observable universe.](https://en.wikipedia.org/wiki/Shannon_number) So even if we could somehow encode each game state and its corresponding best move into a single atom, there isn't enough matter in the universe to build the server that would run the database.
  
  Endgame tablebases are interesting, but there's nobody who's seriously attempting to solve chess.
  
  > **Comments:**
  > **username_17**: Who said that in order for a function to be defined, all possible inputs and their outputs need to be stored in a database? By this argument, the function `f(x, y) = x + y` cannot be defined, even for natural numbers, because there are more natural numbers than there are atoms in the universe.  
  > **username_16**: @username_17 that's just what solving means in this context. If you're saying it can be a function that we compute on the fly... then we're right back to game tree search.  
  > **username_0**: @username_16 "....but there's nobody who's seriously attempting to solve chess." well that is the actual answer I guess. :)  
  > **username_18**: A mathematical proof of whether the starting position is a win, or a forced draw, would be one kind of "solution" of chess without necessarily requiring a brute-force exhaustive tablebase.  
  > **username_0**: @username_18 yes exactly. i am more interested in that kind of solution rather than engine based brute force attempts. Chess theory has to be developed.  
  > **username_17**: @Matt Not necessarily. There are many ways that functions can be computed on the fly, besides tree search.  
  
  ---
  
  ### Answer by username_19 on 2020-07-11. Score: 2
  
  Another line of attack is reducing dimension: Gardner's 5x5 [minichess](https://en.wikipedia.org/wiki/Minichess#5%C3%975_chess) has been [weakly solved](https://arxiv.org/abs/1307.7118) by Mehdi Mhalla and Frederic Prost in 2013. 3x3 and 3x4 boards have been [strongly](http://kirr.homeunix.org/chess/3x3-chess/) [solved](http://kirr.homeunix.org/chess/3x4-chess/) in the 2000s with complete tablebases for each position by Kirill Kryukov, and 9-men tablebases for [4x4 chess](http://kirill-kryukov.com/chess/4x4-chess/) have been completed in 2011 by the same author.
  
  
  ---
  
  ### Answer by username_20 on 2020-07-10. Score: 2
  
  Shirish Chinchalkar has a [paper](https://www.semanticscholar.org/paper/An-Upper-Bound-for-the-Number-of-Reachable-Chinchalkar/9a5c2437d6f30c8281a8ee67cf9200cff7d06051) which calculates an upper bound of ~10^46 for the number of positions in chess (different from moves obviously). Arguments which talk about the number of atoms in the universe are very facetious on account of using position differences (we can only get to a position from another, so why not just store what piece moved instead of the whole new position?) as well as compression. IIRC, in the [Syzygy endgame tables](https://syzygy-tables.info/), each position can be represented by less than a single bit after taking into consideration compression.
  
  One thing that I personally wonder, and I could be completely wrong, is whether there would be at a certain point a relative small decrease in complexity as n -> 32 as there will be less starting nodes.
  
  It's an amazing question though. I would love to see it (even weakly) solved in my lifetime.
  
  > **Comments:**
  > **username_21**: A quick calculation shows 3x10^23 possible positions, of which some number are unreachable.  There are 13 possible states for each square - 6 pieces on each side - pawn, rook, knight, bishop, queen, king plus 1 empty space.  There are 64 squares - so 64^13 possible positions.  This seems much more reasonable than 10^46, though still a very large number.  the fact that the game-tree has 10^120 moves (shannon number) is irrelevant.  you only need to keep 'the one winning move' for each of these 10^23 states.  
  > **username_21**: the unreachable states would take into account that there are only ever 2 kings on a board with 2048 total positions of them, instead of up to 64 kings.  it would also limit to a maximum of 8 pawns each (again down from 64), and have a maximum bounds on the other pieces due to promotion - say, 4 queens, 6 rooks, 6 bishops, and 6 knights.  my math is too rusty to calculate this, but i expect orders of magnitudes of possible positions can be discarded.  
  > **username_21**: one final note on unreachable states - there has to be a minimum of 32 empty spaces, up to 61.  so, again, anything outside this range can be excluded.  
  > **username_20**: Hi Jim, it's actually 13^64 (~10^71) according to your reasoning. So using the different pieces of information you've given you could look to reduce it. However, positions also take account of whether castling is possible for either side and if there are any en-passant squares. See here for position vs diagram: http://wismuth.com/chess/statistics-positions.html  
  > **username_21**: username_20, that's embarassing.  like i said, my math is rusty.  what is the etiquette for a wrong post?  should i delete it or leave it up? i think the follow-on posts are valid.  one more interesting limiter - with 8 pawns in row 2, there are only 16 possible states of row 1, 4 on each side with the rook & knight possibly switching places or the knight not being there.  
  > **username_20**: @username_21 haha don't worry, we all make mistakes. I've looked at all of this in the past hence anything less than 10^46 would arouse my suspicions. If you're too embarrassed you can delete it, but I don't think there's any reason to hide mistakes. Yeah, one of my friends once wrote up a little article on the same! Having a lot of pawns on their starting positions really restricts the possible positions of pieces  
  > **username_20**: @username_21 I'm currently trying to publish a small paper on pawn positions. I'll post it here if it ever gets published!  
  
  ---
  
  ### Answer by username_22 on 2021-04-03. Score: 1
  
  Nice question. The wikipedia page [Solving chess](https://en.wikipedia.org/wiki/Solving_chess) also report only endgame tables as partial results.
  
  Personally, I believe that tools from **combinatorial game theory** are essential to solve chess completely (unless by something similar to an exhaustive search; I would argue that the machine learning method is under the hood an exhaustive search [plus some pruning-type techniques]). Don't expect the the machine learning tools to be of help here if you think the solution should build a chess theory. Combinatorial Game Theory (CGT) is the study of combinatorial games. Chess is not a combinatorial game. But, tools from CGT sometimes do a good job of (partially) solving games which are not combinatorial (e.g.: dots and boxes).
  
  See papers [[1]](http://web.stanford.edu/%7Ewqy/research/Math%20191-%20Chess.pdf) and [[2]](http://library.msri.org/books/Book29/files/elkies.pdf) for a taste of what to expect.
  
  By the way, the fact that generalized chess is computationally hard says practically nothing about chess.
  
  Linked resources:  
  [1] Qingyun Wu, Frank Yu, Michael Landry, A combinatorial game theoretic analysis of chessendgames.  
  [2] Noam D. Elkies, On numbers and endgames: Combinatorial game theory in chess endgames.
  
  > **Comments:**
  > **username_22**: Also see this: https://chess.stackexchange.com/a/27267/14678  
  
  ---
  
  ### Answer by username_23 on 2020-07-11. Score: 0
  
  I think the other answers and comment have made it clear that this is a really complex problem. So complex, that no classic computer will ever come close to solving it.
  
  But I have asked myself the same question. Isn't chess a perfect example to use a quantum computer? Although quantum computers are not yet fully ready for use there do exist "programming languages", and there are already many algorithms for a quantum computer described this way. There actually even exist simulators for running these quantum computer "programs" on classic computers.
  
  I wonder how feasible it would be to write an algorithm for solving chess on a quantum computer. Or would that require so many qbits, that we can never expect an actual quantum computer that could run this algorithm? But if it would once exist, shouldn't it be able to answer the question within a second?
  
  Just to clarify, since I mentioned the possibility to simulate these algorithms on classic computers. This simulation of course only makes this very complex problem solved even less performant, so those simulators could only be used for testing of the algorithm, not for really using it.
  
  > **Comments:**
  > **username_0**: there are no actual quantum computers as of now hence those algorithms don't mean much as you still don't get the time advantage of quantum computers. so we have to wait for that  
  
  ---
  
  ### Answer by username_24 on 2020-07-09. Score: -1
  
  I think everyone here has a good and necessary point with the space complexity of chess being larger than the number of atoms in the observable universe. However, I think I can add some additional points onto that.
  
  1. As others have pointed out, the definition of "solved" is not super clear. If "solved" means "find the optimal move from any possible game state", solving chess is impossible. However, if we take solved to mean that we just want to play the single "perfect" game of chess we may be able to reduce space complexity.
  2. The problem with point one is that chess does not have a single perfect game. A perfect game of chess implies that you are always making the move that leaves you with the highest chance of winning. It also implies that you are accounting for your opponent making optimal moves, as otherwise it would not be a perfect game (and would also break the previous space complexity issues). However, chess is a well balanced game and any game perfectly played would necessarily end in a draw.
  3. There are likely a near-infinite number of optimally played games that end in a draw. While the number of optimal moves from any position is much smaller than the number of possible moves, according to the best chess engines we have today there are many moves that have near-optimal results from the starting position and in the first few moves. Because a significant advantage is needed to win any game of chess, many of these moves would likely be included in a "perfect" or solved game.
  4. Lastly, how would you prove my points 2 and 3 right or wrong? You can't. Again, you run into the space complexity issue. To prove any position is either winnable or unwinnable if both players play optimally, you need to diagram out every single possible move from a given position. As we have shown earlier, this is impossible until we are below a certain piece number.
  
  > **Comments:**
  > **username_25**: I'm not sure you understand what "solving" a game means. Once you "solve" a game you have a strategy by which you always win (as with checkers, which has been solved), or for some games, always tie (as in tic-tac-toe). It isn't just playing "a single perfect game"  
  > **username_26**: "There are likely a near-infinite number of optimally played games that end in a draw.": It is *believed* that an optimally played chess game is a draw. *proving* it would be a huge step toward solving chess.  
  > **username_6**: @KevinWells That definition of "solving" is not available to chess, so it makes the conversation much less interesting. (You can't force a win from every possible game position, and it isn't clear that you could force a win from the starting position, either.)  
  > **username_25**: @username_6 What other definition of "solving" are you using then? The whole point of this question is if we are able to move towards that goal, and if so what efforts are being made to do so. The real answer is that solving chess is certainly out of reach currently, and may never be in reach, but there are still efforts to be made to improve our knowledge of solving increasingly complex starting positions  
  > **username_6**: @KevinWells How about, being able to know the outcome of any game, given the starting position, and two opponents who play perfectly? Solving chess is not about winning an *individual* game, but predicting the outcome of every game well enough to give yourself the best chance of winning.  
  > **username_24**: @username_6 Your question is answered by my point four.  You can't know the outcome of any game from a given starting position because that would be equivalent in complexity to knowing the outcome of all the possible games that could be played.  As has been discussed in the other answers, this is impossible.  
  > **username_25**: @username_6 Solving for every possible game from the starting position is exactly what I'm talking about. I even said that solving a game isn't about playing a single perfect game, which is exactly what you're saying, so I don't understand your criticism. You said that that is a bad definition because it's out of reach for chess, but that doesn't make it a bad definition, it just makes the answer kind of boring  
  
  ---
  
  