4

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.

7
  • 2
    In fact, human had more or less solved 2 pieces and 3 pieces easily even before the computer was introduced. – SmallChess Jul 19 '15 at 2:37
  • 7-man tables are completed and available. – Tony Ennis Jul 19 '15 at 16:01
  • The topic is at odds with the question body. – Tony Ennis Jul 19 '15 at 16:02
  • +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. – Tony Ennis Jul 19 '15 at 16:05
  • 1
    @ETD, yup, exactly, I just want the dates. – Dan Sandberg Jul 19 '15 at 20:40
2

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. ;{>}

2
  • 1
    "4 minors or rooks or three queens".. ahhhh head explodes – Tony Ennis Jul 21 '15 at 4:34
  • 1
    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. – Arlen Jul 22 '15 at 20:02
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.

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.)

6
  • 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. – Tony Ennis Jul 19 '15 at 17:16
  • 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. – Dan Sandberg Jul 19 '15 at 20:45
  • I am making a LOT of assumptions. But I based my numbers on sizes of tables which have been compressed. – Tony Ennis Jul 19 '15 at 22:16
  • 1
    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. – Tony Ennis Jul 19 '15 at 22:30
  • 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. – RemcoGerlich Jul 20 '15 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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