What is the reason that table base files are so large?
I can't think of any other way to phrase that question - but the question alone is rejected by stackoverflow's gateway bot, hence this paragraph added to placate it.
1
-
2The gateway bot has a point, why would you expect them to be smaller? Are you asking why do tablebases contain so many combinations, or why storing it is so large on disk? Have you noticed an apparent overhead between the size you expect and the actual size? – Korone Jul 17 '15 at 15:15
Add a comment
|
For a simple numerical example, take the endgame of King + Rook + Pawn vs. King + Rook. The number of possible positions is 64 x 63 x 62 x 61 x 60. Of those, 25% is not valid because the pawn is at the first or last row, and because of the symmetry around the d/e file, we only need to store the positions where the pawn is on the a, b, c or d file. This leaves us with 64 x 63 x 62 x 61 x 60 x 0.75 x 0.5 = 343,103,040 positions*.
For every position, you need to know how many moves to mate or conversion, both with White to move and Black to move. You need 2 bytes for each position, so we get a total of 686,206,080 bytes which is about 654 MB. With ZIP-like algorithms, we can compress the size of the files by about 80%, which leaves us with around 150 MB. You can download the files here - note that the tablebases are split between White-to-move and Black-to-move.
For 6- and 7-man endgames, typical sizes are 60 resp. 3600 times as large, so 9 GB resp. 540 GB. Sometimes, symmetry can be exploited further (especially if there are no pawns involved), but this will result in a maximum reduction to 25% of sizes when pawns are involved.
*: actually, some positions are not valid because e.g. both kings attack each other. This number is rather small and if you would filter these, it would take much more time to lookup a certain position in the database.
answered Jul 17 '15 at 16:25
A tablebase contains information about every possible position with a certain material balance. The number of possible positions grows exponentially with the number of pieces. So while a tablebase covering King and Pawn vs King will not be large, if you add enough pieces the file size will grow out of bound for any storage medium you want to use. The number of all possible chess positions is something like the number of atoms of the sun, so storing everything does not seem to be workable with any concievable technology.
answered Jul 17 '15 at 15:17
In addition to the other fine answers, it is worth pointing out that tablebases contain every conceivable collection of pieces, even ones that don't make any sense. For example, I just asked about a position with king and three knights vs king and bishop, and was told that it was a mate in 30. And there are a lot of conceivable collections of six pieces, even if you know what two of those pieces are. (Not to mention that there are really two kinds of bishop.)
-
2Why does KNNNvKB not make sense? It is a perfectly reasonable possibility. I start with two knights and to avoid a stalemate when I promote I have to promote to a knight, say. – Brian Towers♦ Jul 17 '15 at 21:03
-
1If promoting to a queen or rook results in stalemate, you should give the king some escape squares and promote later. – limits Jul 17 '15 at 23:56
-
@BrianTowers Of course it is possible to reach such a scenario. On the other hand, I cannot imagine a position in which the best move is to promote to a third knight leading to a KNNNKB endgame, but perhaps that is a failure of my imagination. If you can produce one, I would be very interested to see it. – dfan Jul 18 '15 at 2:53
-
3
-
2Stalemate avoidance can figure too: kb6/2P3N1/K7/8/8/8/1N6/8 WTM wins only with 1 c8N (not 1 c8B? Be5! draw.) Also, "tablebases" are used also for analyzing composed studies, where exotic material configurations are much more common. – Noam D. Elkies Jan 22 '16 at 2:11
