Answers.Body: <p>Since there is no single comprehensive publication this is based on the <a href="https://github.com/syzygy1/Cfish/blob/master/src/tbprobe.c" rel="noreferrer">probing code</a>, the <a href="https://github.com/syzygy1/tb" rel="noreferrer">generator</a> and <a href="https://www.chessprogramming.org/Syzygy_Bases#Forum_Posts" rel="noreferrer">various explanations</a> from Ronald de Man (the author of the generator).</p>
  
  <hr>
  
  <p>When probing pretty much any tablebase (aka huge compressed hash map):</p>
  
  <ol>
  <li>The position is normalized ...</li>
  <li>... mapped to an integer index.</li>
  <li>The index is looked up in a table that identifies which "block" it belongs to.</li>
  <li>The block is decompressed until the information for the index can be retrieved.</li>
  </ol>
  
  <p>Then there usually is some code "outside" of probing, at least to resolve en passant captures.</p>
  
  <hr>
  
  <p>Starting with the outside code for WDL. Syzygy tables use an optimization based on the following observation: If a position has a capture that achieves a particular value (e.g. is winning), then the position itself has at least that value (e.g. is winning). In this case the table can store an arbitrary lower value, whichever is best for compression, and this can be easily corrected by checking the subtables for captures.</p>
  
  <p>To get a DTZ, a WDL probe needs to be done first. If the position is drawn, then DTZ is 0 and the table can store anything, whichever is best for compression. If the best move was a capture (which we can remember from the WDL probe), then the DTZ is +/-1 or +/-101 depending on the WDL, and the table can again store anything, whichever is best for compression.</p>
  
  <p>Pawnful tables contain 4 subtables, one for each file of the "leading pawn" (after normalization).</p>
  
  <p>WDL (sub)tables are two-sided, i.e. they essentially contain two seperate tables for each side of the endgame (unless the material is symmetric).</p>
  
  <p>DTZ tables store only one side to move. So a brief 1-ply search may be required to compute the DTZ for the other side.</p>
  
  <hr>
  
  <p>(1) About the normalization: There are multiple ways this could be done and it is not easy to tell in advance which one will lead to the best compression. The generator just tries different permutations. The final order of the pieces is stored in the header of the table file.</p>
  
  <p>(2) Some combinatorics. The challenge is not to have large gaps for impossible positions. Although it is quite tricky, I don't think Syzygy does anything special here. Conceptually, pieces or groups of pieces are placed on the board in the order specified in the header.</p>
  
  <p>(3) Compressed values are stored in blocks. The block size is specified in the table header. The table mapping indexes to blocks is sparse, so it allows jumping very close to the correct block and then requires a brief forward or backward scan to find the exact block. A block can store values for at most 65536 positions.</p>
  
  <p>(4) Syzygy tables use custom compression based on <a href="http://www.larsson.dogma.net/dcc99.pdf" rel="noreferrer">RE-PAIR</a>. An important feature is that it actually allows taking advantage of the opportunities to store arbitrary values that were identified above. Decompression is very fast and can stop as soon as the value for the desired index is available.</p>
  
  <p>Optionally, DTZ tables can require another step f(wdl, stored value) = real value. This extra DTZ map is referenced in the table header and is itself a table with 8-bit entries. (Intrestingly this turned out to be insufficient for 7-piece endgames, even with pawns, so there is now another flag that enables 16-bit entries).</p>
  
  <p>For DTZ values, if the generator determined that all values for a table are less than 100, precise half-move counts are not required to guarantee perfect play. Instead it sets a flag in the table header and rounds half-moves to full-moves to save space.</p>
  
  <p>Also clearly there is no need to store the sign, or an additional offset of +/-100 for cursed endgames because this can be inferred from the WDL value.</p>
  
  <p>Since decompression is very fast, there is no need for a cache. Instead engines can rely on the operating systems page cache to store (still compressed) blocks.</p>
  
  <hr>
  
  <p>The 6 piece tables contain WDL and DTZ information for 3,787,154,440,416 <a href="https://kirill-kryukov.com/chess/nulp/results.html" rel="noreferrer">unique positions</a> in 150 Gigabytes, so ~0.3 bits per position.</p>
  
  <p>All in all Syzygy tables improved upon previous tablebase formats in at least 3 of these areas, making it a very compact and fast format. Amazingly the generator is quite fast as well.</p>
  
  <p>And of course using DTZ50 is a pragmatic choice, because this is just enough information to reliably make progress and allows perfect play (wrt. outcome) both with and without the 50-move rule. However based on the changes to Cfish that are published so far (RdM is now working on DTM tables), many of the techniques will apply to DTM as well.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-12T00:34:46.377Z
Answers.LastActivityDate: 2019-09-21T13:38:57.350Z
Answers.LastEditDate: 2019-09-21T13:38:57.350Z
Answers.UserDisplayName: Niklas
Body: <p>From reading everything I've found so far, I know that Syzygy uses both win/draw/loss files and distance-to-zero files, but I haven't found any information on the internal file format that these files use. I'm looking for the low level nitty gritty explanation.</p>
  
Tags: <engines><endgame><tablebases>
Title: How does Syzygy store its information?
ThreadText: # How does Syzygy store its information?
  
  (Asked by: username_0 on 2018-08-11)
  
  From reading everything I've found so far, I know that Syzygy uses both win/draw/loss files and distance-to-zero files, but I haven't found any information on the internal file format that these files use. I'm looking for the low level nitty gritty explanation.
  
  **Tags:** engines, endgame, tablebases
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-08-12. Score: 20 | Accepted answer
  
  Since there is no single comprehensive publication this is based on the [probing code](https://github.com/syzygy1/Cfish/blob/master/src/tbprobe.c), the [generator](https://github.com/syzygy1/tb) and [various explanations](https://www.chessprogramming.org/Syzygy_Bases#Forum_Posts) from Ronald de Man (the author of the generator).
  
  ---
  
  When probing pretty much any tablebase (aka huge compressed hash map):
  
  1. The position is normalized ...
  2. ... mapped to an integer index.
  3. The index is looked up in a table that identifies which "block" it belongs to.
  4. The block is decompressed until the information for the index can be retrieved.
  
  Then there usually is some code "outside" of probing, at least to resolve en passant captures.
  
  ---
  
  Starting with the outside code for WDL. Syzygy tables use an optimization based on the following observation: If a position has a capture that achieves a particular value (e.g. is winning), then the position itself has at least that value (e.g. is winning). In this case the table can store an arbitrary lower value, whichever is best for compression, and this can be easily corrected by checking the subtables for captures.
  
  To get a DTZ, a WDL probe needs to be done first. If the position is drawn, then DTZ is 0 and the table can store anything, whichever is best for compression. If the best move was a capture (which we can remember from the WDL probe), then the DTZ is +/-1 or +/-101 depending on the WDL, and the table can again store anything, whichever is best for compression.
  
  Pawnful tables contain 4 subtables, one for each file of the "leading pawn" (after normalization).
  
  WDL (sub)tables are two-sided, i.e. they essentially contain two seperate tables for each side of the endgame (unless the material is symmetric).
  
  DTZ tables store only one side to move. So a brief 1-ply search may be required to compute the DTZ for the other side.
  
  ---
  
  (1) About the normalization: There are multiple ways this could be done and it is not easy to tell in advance which one will lead to the best compression. The generator just tries different permutations. The final order of the pieces is stored in the header of the table file.
  
  (2) Some combinatorics. The challenge is not to have large gaps for impossible positions. Although it is quite tricky, I don't think Syzygy does anything special here. Conceptually, pieces or groups of pieces are placed on the board in the order specified in the header.
  
  (3) Compressed values are stored in blocks. The block size is specified in the table header. The table mapping indexes to blocks is sparse, so it allows jumping very close to the correct block and then requires a brief forward or backward scan to find the exact block. A block can store values for at most 65536 positions.
  
  (4) Syzygy tables use custom compression based on [RE-PAIR](http://www.larsson.dogma.net/dcc99.pdf). An important feature is that it actually allows taking advantage of the opportunities to store arbitrary values that were identified above. Decompression is very fast and can stop as soon as the value for the desired index is available.
  
  Optionally, DTZ tables can require another step f(wdl, stored value) = real value. This extra DTZ map is referenced in the table header and is itself a table with 8-bit entries. (Intrestingly this turned out to be insufficient for 7-piece endgames, even with pawns, so there is now another flag that enables 16-bit entries).
  
  For DTZ values, if the generator determined that all values for a table are less than 100, precise half-move counts are not required to guarantee perfect play. Instead it sets a flag in the table header and rounds half-moves to full-moves to save space.
  
  Also clearly there is no need to store the sign, or an additional offset of +/-100 for cursed endgames because this can be inferred from the WDL value.
  
  Since decompression is very fast, there is no need for a cache. Instead engines can rely on the operating systems page cache to store (still compressed) blocks.
  
  ---
  
  The 6 piece tables contain WDL and DTZ information for 3,787,154,440,416 [unique positions](https://kirill-kryukov.com/chess/nulp/results.html) in 150 Gigabytes, so ~0.3 bits per position.
  
  All in all Syzygy tables improved upon previous tablebase formats in at least 3 of these areas, making it a very compact and fast format. Amazingly the generator is quite fast as well.
  
  And of course using DTZ50 is a pragmatic choice, because this is just enough information to reliably make progress and allows perfect play (wrt. outcome) both with and without the 50-move rule. However based on the changes to Cfish that are published so far (RdM is now working on DTM tables), many of the techniques will apply to DTM as well.
  
  
  ---
  
  