What are the dates each of the endgame tablebases were completed?

Question

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.

Answer 1

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

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