14

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 information about this theme.

6
  • 13
    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, 2016 at 21:11
  • 3
    @dfan Your comments should be an answer.
    – SmallChess
    Jul 25, 2016 at 1:15
  • 1
    @StudentT I didn't think it was definitive enough.
    – dfan
    Jul 25, 2016 at 1:37
  • 1
    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. Jul 25, 2016 at 6:28
  • 1
    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, 2016 at 22:52

2 Answers 2

9

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.

Edit

Since this answer is getting a lot of traffic and I re-read my answer, I feel the need to add some clarification. Endgame tablebases are created with retrograde analysis, so deterministically calculating the outcome of one position requires knowledge of enough possible successor positions. As we know, this graph mushrooms quickly. While retrograde analysis is definitely parallelizable, one needs an enormous amount of working memory. However, it is common practice to allocate only 10s of GB of RAM to a single processor, so positions must be communicated over a network. This would require a lot of bandwidth, and multiple processors contending to make changes to the same table state would create synchronization problems that add overhead. Positions must be stored in RAM because disk read latency is horrendous (on the order of milliseconds instead of nanoseconds for cache or microseconds for RAM). It's possible some amount of pipelining or caching could amortize poor latency, but this is still a hard problem to solve at the required scale.

Tl;dr even with a big supercomputer, modern computer architecture is not amenable to this type of problem.

3

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
  • 4
    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, 2016 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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