Answers.Body: <p>If you don't mind approximate dates, 3-piece computer tablebase was solved in the 70's, 4-piece in the 80's and 5-piece in the late 80's. 6-piece took, I believe, until around 2005. 7-piece has been relatively faster (in terms of positions per year) mainly because it's been discovered people will pay for them, so more and faster computers have been dedicated to the task.</p>
  
  <p>As for 'solving' chess, as some posters have pointed out, it's the storage that will be the issue. With more pieces on the board, it will approach something on the order of 150 bits per position for storage, so a rough guess at legal positions with 32 pieces on the board would come in at around 10^13 or so bits. (1TB or thereabouts, and this doesn't include the bits necessary to indicate which two positions are linked and what the result would be.)</p>
  
  <p>It's funny, but for a short time as you decrease pieces you allow more combinations. Consider: with a the full complement of 32 pieces on the board, you can have no promoted pawns. (A pawn would have to capture in order to pass by the opposing pawn.) Allow one side to make captures, and suddenly you have to allow for positions with 7 queens, or 8 Bishops, etc. If you allow simply one capture (a 31-piece table -- for example a g-pawn capturing an f-pawn) you now can have both the g and f pawns of the majority side promoting, so the resulting 31-piece set must include provisions for as many as 4 minors or rooks or three queens on the 16-piece side.</p>
  
  <p>I suspect at some point the number of atoms in the universe may become a limiting factor. ;{>}</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-21T04:34:08.480Z
Answers.Text: "4 minors or rooks or three queens"..   ahhhh *head explodes*
Answers.UserDisplayName: Tony Ennis
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-22T20:02:45.400Z
Answers.Text: And I forgot that the g-pawn of the minority side could also promote, potentially yielding 3Q vs 2Q positions, or 4B vs 3R, etc.
Answers.UserDisplayName: Arlen
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-20T18:54:38.587Z
Answers.LastActivityDate: 2015-07-20T18:54:38.587Z
Answers.UserDisplayName: Arlen
Answers.Body: <p>Endgame tables require enormous amounts of storage. According to <a href="https://chess.stackexchange.com/questions/351/what-is-the-status-for-seven-man-end-game-table-bases">this post</a>, the 7-man tables are 140 terabytes.  The 8-man tables will be many petabytes.</p>
  
  <p>Each iteration of the tablebases grows exponentially in size. Moore's Law says that transistor density doubles every 18 months.  Moore's Law is starting to falter now. But assuming it is not, the question becomes:</p>
  
  <pre><code>140 terabytes for 7 man = 20 terabytes per man 'of density units', aka 20 DU
  Assume X terabytes for a 32 man.
  X/20 -&gt; number of currently available units needed
  2^Y = X/20 -&gt; Y is how many times the current density would have to double
  Y * 18 = months for the doubling to occur if Moore's Law holds.
  </code></pre>
  
  <p>The trick, obviously, is knowing how large the final table would be.</p>
  
  <ul>
  <li>5-man 7 Gb
  (<a href="http://www.cruxis.com/chess/manual/index.html?end_game_table_base_support.htm" rel="nofollow noreferrer">http://www.cruxis.com/chess/manual/index.html?end_game_table_base_support.htm</a>)</li>
  <li>6-man 1.2 Tb
  (<a href="http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380" rel="nofollow noreferrer">http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380</a>)</li>
  <li>7-man (140 Tb)</li>
  </ul>
  
  <p>Soooo... using no math except simple division, I decided each iteration is 100x bigger than the previous. This is conservative according to simple division from the above. This also assumes that the rate of growth is linear. That is, each iteration is 100x, and that this rate doesn't change.</p>
  
  <p>The result is that the 32 man table base would consume 6.6 x 10^53 terabytes of storage. That is, X = 6.6E53 Tb</p>
  
  <pre><code>6.6E53/20 = 3.3E52 DU
  2^Y = 3.3E52, Y = 179
  months = 18 * 179 = 3218 months
  years = 153
  </code></pre>
  
  <p>So, my best guess is the 153 years, lol.  I can only imagine what the error on that is.</p>
  
  <p>What this really is, however, is the estimate on when the storage density will be possible according to Moore's Law. It says nothing about our ability to actually calculate the tables. But it seems logical that we'd have to be able to store the result first, so 153 years it is.  At a minimum.</p>
  
  <p>This is very silly as it turns out.  So going back to the X number, 6.6E53... converting it to bytes gives 6.6E65. Converting this to bits gives 8.25E64</p>
  
  <p>So to store this table requires 8E64 bits, give or take (heh)</p>
  
  <p>According to <a href="http://www.madsci.org/posts/archives/1998-05/892502124.Ph.r.html" rel="nofollow noreferrer">this web site</a>, the solar system is made up of 1.2E57 atoms (assuming it is all hydrogen!)</p>
  
  <p>So if we store each bit as an atom, we'd require about <strong>69 million</strong> of our solar systems, in atoms, to store the 32-man table.</p>
  
  <p>I'm a computer programmer by trade. I'll get right on this.</p>
  
  <p>(I assumed Moore's Law holds. This is optimistic. I assumed each iteration of the table base was 100x larger then the previous. I actually don't know. However, I am confident that the result is actually... <strong>never</strong>. We will never 'solve' chess exhaustively. <strong>Because of a lack of atoms.</strong>)</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-19T17:16:16.163Z
Answers.Text: As an aside, adding more pieces might decrease the rate of space consumption since the pieces start constraining the other pieces.  That is, there are more pieces but on average they can move to fewer squares. The problem is mind-bogglingly complex.
Answers.UserDisplayName: Tony Ennis
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-19T20:45:22.227Z
Answers.Text: I'm a computer programmer as well.  You're assuming that the table isn't massively compressible.  Given how well humans play chess via intuition, I'd imagine there are many, many patterns that lead to an extremely compressible end-table.
Answers.UserDisplayName: Dan Sandberg
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-19T22:16:46.937Z
Answers.Text: I am making a LOT of assumptions. But I based my numbers on sizes of tables which *have* been compressed.
Answers.UserDisplayName: Tony Ennis
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-19T22:30:54.687Z
Answers.Text: It occurs to me that normal compression for text yields a 10x reduction in size.  So if the same compression win were applied here, we'd only need 7 million of our solar systems for storage.
Answers.UserDisplayName: Tony Ennis
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-20T20:23:35.973Z
Answers.Text: A minimum factor 100 in size growth also sounds reasonable when you consider that there are 10 different pieces (white and black rook, knight, bishop, queen, pawn) that could be added at one of 57 empty squares for each existing position in the 7-man bases to get the positions for the 8-mans, minus some proportion of illegal positions. That's a factor of 570, so if 80% of those are illegal, that's still more than a factor 100.
Answers.UserDisplayName: RemcoGerlich
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-20T20:26:03.653Z
Answers.Text: @DanSandberg: given how compressed the format already is, I find that claim rather frivolous.
Answers.UserDisplayName: RemcoGerlich
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2015-07-19T16:52:18.823Z
Answers.LastActivityDate: 2015-07-19T17:03:07.527Z
Answers.LastEditDate: 2017-04-13T12:48:53.737Z
Answers.UserDisplayName: Tony Ennis
Body: <p>I'm curious to get a rough sense for when chess could be solved if Moore's law, and algorithm improvements continue, and I thought a good way to get a rough idea would be to extrapolate based on when the endgame tablebases for 2 to 7 pieces was completed.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-07-19T02:37:11.093Z
Comments.Text: In fact, human had more or less solved 2 pieces and 3 pieces easily even before the computer was introduced.
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-07-19T16:01:18.967Z
Comments.Text: 7-man tables are completed and available.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-07-19T16:02:28.803Z
Comments.Text: The topic is at odds with the question body.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-07-19T16:05:08.343Z
Comments.Text: +1 for the idea that tablebases solve chess, not brute calculation of moves during a game which implies a more-or-less realtime solution.  I have never heard it expressed that way.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-07-19T17:04:05.290Z
Comments.Text: @TonyEnnis, the way I read the question, the topic isn't at odds with the question body. Rather, the question body is just the OP explaining his motivation for asking the question in the title. That is, he wants to extrapolate from the dates of completion of tablebases up to 7-man in order to have a guess (assuming Moore's Law) of when chess could be completely solved. *If I'm reading it correctly, the OP doesn't seek answers concerning when such a final solution might be found, but is rather just after the historical timeline for what has been completed to date.* (Perhaps Dan can clarify.)
Comments.UserDisplayName: ETD
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-07-19T17:10:10.543Z
Comments.Text: @ETD I believe my answer went that way as a matter of course.
Comments.UserDisplayName: Tony Ennis
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2015-07-19T20:40:53.887Z
Comments.Text: @ETD, yup, exactly, I just want the dates.
Comments.UserDisplayName: Dan Sandberg
Tags: <history><tablebases>
Title: What are the dates each of the endgame tablebases were completed?
ThreadText: # What are the dates each of the endgame tablebases were completed?
  
  (Asked by: username_0 on 2015-07-19)
  
  I'm curious to get a rough sense for when chess could be solved if Moore's law, and algorithm improvements continue, and I thought a good way to get a rough idea would be to extrapolate based on when the endgame tablebases for 2 to 7 pieces was completed.
  
  **Tags:** history, tablebases
  
  > **Comments:**
  > **username_1**: In fact, human had more or less solved 2 pieces and 3 pieces easily even before the computer was introduced.  
  > **username_2**: 7-man tables are completed and available.  
  > **username_2**: The topic is at odds with the question body.  
  > **username_2**: +1 for the idea that tablebases solve chess, not brute calculation of moves during a game which implies a more-or-less realtime solution.  I have never heard it expressed that way.  
  > **username_3**: @TonyEnnis, the way I read the question, the topic isn't at odds with the question body. Rather, the question body is just the OP explaining his motivation for asking the question in the title. That is, he wants to extrapolate from the dates of completion of tablebases up to 7-man in order to have a guess (assuming Moore's Law) of when chess could be completely solved. *If I'm reading it correctly, the OP doesn't seek answers concerning when such a final solution might be found, but is rather just after the historical timeline for what has been completed to date.* (Perhaps Dan can clarify.)  
  > **username_2**: @username_3 I believe my answer went that way as a matter of course.  
  > **username_0**: @username_3, yup, exactly, I just want the dates.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2015-07-20. Score: 2 | Accepted answer
  
  If you don't mind approximate dates, 3-piece computer tablebase was solved in the 70's, 4-piece in the 80's and 5-piece in the late 80's. 6-piece took, I believe, until around 2005. 7-piece has been relatively faster (in terms of positions per year) mainly because it's been discovered people will pay for them, so more and faster computers have been dedicated to the task.
  
  As for 'solving' chess, as some posters have pointed out, it's the storage that will be the issue. With more pieces on the board, it will approach something on the order of 150 bits per position for storage, so a rough guess at legal positions with 32 pieces on the board would come in at around 10^13 or so bits. (1TB or thereabouts, and this doesn't include the bits necessary to indicate which two positions are linked and what the result would be.)
  
  It's funny, but for a short time as you decrease pieces you allow more combinations. Consider: with a the full complement of 32 pieces on the board, you can have no promoted pawns. (A pawn would have to capture in order to pass by the opposing pawn.) Allow one side to make captures, and suddenly you have to allow for positions with 7 queens, or 8 Bishops, etc. If you allow simply one capture (a 31-piece table -- for example a g-pawn capturing an f-pawn) you now can have both the g and f pawns of the majority side promoting, so the resulting 31-piece set must include provisions for as many as 4 minors or rooks or three queens on the 16-piece side.
  
  I suspect at some point the number of atoms in the universe may become a limiting factor. ;{>}
  
  > **Comments:**
  > **username_2**: "4 minors or rooks or three queens"..   ahhhh *head explodes*  
  > **username_4**: And I forgot that the g-pawn of the minority side could also promote, potentially yielding 3Q vs 2Q positions, or 4B vs 3R, etc.  
  
  ---
  
  ### Answer by username_2 on 2015-07-19. Score: 2
  
  Endgame tables require enormous amounts of storage. According to this post, the 7-man tables are 140 terabytes.  The 8-man tables will be many petabytes.
  Each iteration of the tablebases grows exponentially in size. Moore's Law says that transistor density doubles every 18 months.  Moore's Law is starting to falter now. But assuming it is not, the question becomes:
  140 terabytes for 7 man = 20 terabytes per man 'of density units', aka 20 DU
  Assume X terabytes for a 32 man.
  X/20 -> number of currently available units needed
  2^Y = X/20 -> Y is how many times the current density would have to double
  Y * 18 = months for the doubling to occur if Moore's Law holds.
  
  The trick, obviously, is knowing how large the final table would be.
  
  5-man 7 Gb
  (http://www.cruxis.com/chess/manual/index.html?end_game_table_base_support.htm)
  6-man 1.2 Tb
  (http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380)
  7-man (140 Tb)
  
  Soooo... using no math except simple division, I decided each iteration is 100x bigger than the previous. This is conservative according to simple division from the above. This also assumes that the rate of growth is linear. That is, each iteration is 100x, and that this rate doesn't change.
  The result is that the 32 man table base would consume 6.6 x 10^53 terabytes of storage. That is, X = 6.6E53 Tb
  6.6E53/20 = 3.3E52 DU
  2^Y = 3.3E52, Y = 179
  months = 18 * 179 = 3218 months
  years = 153
  
  So, my best guess is the 153 years, lol.  I can only imagine what the error on that is.
  What this really is, however, is the estimate on when the storage density will be possible according to Moore's Law. It says nothing about our ability to actually calculate the tables. But it seems logical that we'd have to be able to store the result first, so 153 years it is.  At a minimum.
  This is very silly as it turns out.  So going back to the X number, 6.6E53... converting it to bytes gives 6.6E65. Converting this to bits gives 8.25E64
  So to store this table requires 8E64 bits, give or take (heh)
  According to this web site, the solar system is made up of 1.2E57 atoms (assuming it is all hydrogen!)
  So if we store each bit as an atom, we'd require about 69 million of our solar systems, in atoms, to store the 32-man table.
  I'm a computer programmer by trade. I'll get right on this.
  (I assumed Moore's Law holds. This is optimistic. I assumed each iteration of the table base was 100x larger then the previous. I actually don't know. However, I am confident that the result is actually... never. We will never 'solve' chess exhaustively. Because of a lack of atoms.)
  
  > **Comments:**
  > **username_2**: As an aside, adding more pieces might decrease the rate of space consumption since the pieces start constraining the other pieces.  That is, there are more pieces but on average they can move to fewer squares. The problem is mind-bogglingly complex.  
  > **username_0**: I'm a computer programmer as well.  You're assuming that the table isn't massively compressible.  Given how well humans play chess via intuition, I'd imagine there are many, many patterns that lead to an extremely compressible end-table.  
  > **username_2**: I am making a LOT of assumptions. But I based my numbers on sizes of tables which *have* been compressed.  
  > **username_2**: It occurs to me that normal compression for text yields a 10x reduction in size.  So if the same compression win were applied here, we'd only need 7 million of our solar systems for storage.  
  > **username_5**: A minimum factor 100 in size growth also sounds reasonable when you consider that there are 10 different pieces (white and black rook, knight, bishop, queen, pawn) that could be added at one of 57 empty squares for each existing position in the 7-man bases to get the positions for the 8-mans, minus some proportion of illegal positions. That's a factor of 570, so if 80% of those are illegal, that's still more than a factor 100.  
  > **username_5**: @DanSandberg: given how compressed the format already is, I find that claim rather frivolous.  
  
  ---
  
  