7

Due to Wikipedia: Endgame tablebase the Lomonosov endgame tablebase is still the biggest tablebase (with a size of 140TB). Now this tablebase was computed in the year 2012 with the Lomonosov 1 (Top500-list November 2012, rank 26). The Lomonosov 1 had 78.660 cores with ~900 TFlop/s (peak: 1.700 TFlop/s). When I have a look on the most recent Top500-List (June 2016) I see that the Lomonosov 2 is ranked 41 in the world with ~2.100 TFlop/s (peak: ~2.900 TFlop/s), the No1-ranked super-computer has 93.000 TFlop/s.

So I wonder why the Lomonosov-tablebase after 4 years still is the biggest tablebase. Shouldn't it be easy with the growing computer-power to calculate an 8-men-tablebase? Or is the step from 7 to 8 just too big? Maybe the size would go up exponentially so that standard-storage-systems just cannot handle this?

Would appreciate all informations about this theme. Thanks in advance!

  • 10
    The step from 7 to 8 is just too big. According to that Wikipedia article, it takes 7 GB to store the tablebases up to 5 men (in Nalimov format), 1.2 TB to store the tablebases up to 6 men, and 140 TB to store the tablebases up to 7 men. So storing an 8-man tablebase will require well over a petabyte of storage. – dfan Jul 24 '16 at 21:11
  • 2
    @dfan Your comments should be an answer. – SmallChess Jul 25 '16 at 1:15
  • 1
    @StudentT I didn't think it was definitive enough. – dfan Jul 25 '16 at 1:37
  • They could do 7-men with opposing pawns on same file configs counted as "1" rather than "2", or something. This would only about 3x as large as current. Also, memory (across all nodes) is more important than speed ("TFlops", not precisely the best measure) I think. – Post-It-Note Jul 25 '16 at 6:28
  • according to this page it's estimated that computing 8-man TB will require 10PB of storage and 50TB of RAM. That's not to mention the time required -- with that volume of storage and random access requirements, much technology is needed to manage the storage access times. – M.M Aug 31 '16 at 22:52
3

I am a developer currently working on software to compute endgame tablebases. The real bottleneck with calculating positions is not memory per se but the working memory and computing cycles needed to calculate a network for an exponentially-growing set of positions.

The number of positions grows exponentially according to the number of men on the board; this means that the working memory needed (whether it be RAM or hard drive reads, which are less expensive and more scalable but significantly slower) increases proportionately to A^N where A is a scaling constant (somewhat less than 64) and N is the number of men in the tablebase. The Lomonosov Supercomputer used 92 TiB of RAM, which is sufficient for a 7-man tablebase; as dfan said in his comment, the jump is too big.

Furthermore, as more nodes are added to the tablebase the number of calculations increases faster than linearly to the number of nodes. For instance, accessing data in a Binary Search Tree (BST) is proportional to ln(M) where M is the number of nodes in the tree; since M = A^N, to access each node of the tree once, A^N * ln(A^N) operations are needed. There are several steps in the tablebase retrograde evaluation algorithm that scale similarly.

In short, memory increases exponentially and the number of operations increases faster than exponentially as more men are added. Computing has not advanced this far in (at the time of writing) 6 years.

2

I'm unable to comment as I don't have "50 reputation", but I was wondering if one could use the 7 tablebase as part of the answer for an 8 tablebase. Did they do that for the 7 tablebase?

That is, when determining the solution for 8 pieces, stop if you get to 7 pieces and just refer to the 7 tablebase. Granted, even with that it would be huge because there would still be a lot of combinations before getting to 7 pieces, but less than it would if you wanted to figure it out without referencing the 7 tablebase?

If the solution used a method of going in the other direction, then maybe it doesn't help?

  • 1
    The tablebase stores whether a position is Win , Draw or Loss; and also a metric (e.g. DTC - meaning number of moves until the position moves into another category). It doesn't store "a solution" as you suggest, instead the engine that uses the tablebase will look at all possible moves in a position, rank the metrics for each resulting position, and select a move based on the best metric. If the best move was a capture then the engine will look up the base for the new position to work out its next move – M.M Aug 31 '16 at 22:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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