7-pieces Syzygy tablebase support

This is the first patch teaching Stockfish how to use the 7-pieces
Syzygy tablebase currently calculated by Bujun Guo (@noobpwnftw) and
Ronald de Man (@syzygy1). The 7-pieces database are so big that they
required a change in the internal format of the files (technically,
some DTZ values are 16 bits long, so this had to be stored as wide
integers in the Huffman tree).

Here are the estimated file size for the 7-pieces Syzygy files,
compared to the 151G of the 6-pieces Syzygy:

```
7.1T    ./7men_testing/4v3_pawnful (ongoing, 120 of 325 sets remaining)
2.4T    ./7men_testing/4v3_pawnless
2.3T    ./7men_testing/5v2_pawnful
660G    ./7men_testing/5v2_pawnless
117G    ./7men_testing/6v1_pawnful
87G     ./7men_testing/6v1_pawnless
```
Some pointers to download or recalculate the tables:

Location of original files, by Bujun Guo:
ftp://ftp.chessdb.cn/pub/syzygy/

Mirrors:
http://tablebase.sesse.net/ (partial)
http://tablebase.lichess.ovh/tables/standard/7/

Generator code:
https://github.com/syzygy1/tb/

Closes https://github.com/official-stockfish/Stockfish/pull/1707

Bench: 5591925 (No functional change if SyzygyTB is not used)

----------------------

Comment by Leonardo Ljubičić (@DragonMist)

This is an amazing achievement, generating and being able to use 7 men syzygy
on the fly. Thank you for your efforts @noobpwnftw !! Looking forward how this
will work in real life, and expecting some trade off between gaining perfect
play and slow disc Access, but once the disc speed and space is not a problem,
I expect 7 men to yield something like 30 elo at least.

-----------------------

Comment by Michael Byrne (@MichaelB7)

This definitely has a bright future. I turned off the 50 move rule (ala ICCF
new rules) for the following position:  `[d]8/8/1b6/8/4N2r/1k6/7B/R1K5 w - - 0 1`
This position is a 451 ply win for white (sans the 50 move rule, this position
was identified by the generator as the longest cursed win for white in KRBN v KRB).

Now Stockfish finds it instantly (as it should), nice work 👊👍 .
```
dep score	    nodes	    time
  7	+132.79 	4339    	0:00.00	Rb1+ Kc4 Nd6+ Kc5 Bg1+ Kxd6 Rxb6+ Kc7 Be3 Rh2 Bd4
  6	+132.79 	1652    	0:00.00	Rb1+ Kc4 Nd2+ Kd5 Rxb6 Rxh2 Nf3 Rf2
  5	+132.79 	589      	0:00.00	Rb1+ Kc4 Rxb6 Rxh2 Nf6 Rh1+ Kb2
  4	+132.79 	308      	0:00.00	Rb1+ Kc4 Nd6+ Kc3 Rxb6 Rxh2
  3	+132.79 	88        	0:00.00	Rb1+ Ka4 Nc3+ Ka5 Ra1+ Kb4 Ra4+ Kxc3 Rxh4
  2	+132.79 	54        	0:00.00	Rb1+ Ka4 Nc3+ Ka5 Ra1+ Kb4
  1	+132.7
```

diff --git a/src/syzygy/tbprobe.cpp b/src/syzygy/tbprobe.cpp
index da6dc49f7bbd3f07d77672ff789c265844f8a354..dc7c523ae79900e5cc0634926596db6303743b9a 100644 (file)
--- a/src/syzygy/tbprobe.cpp
+++ b/src/syzygy/tbprobe.cpp
@@ -55,13 +55,13 @@ int Tablebases::MaxCardinality;
 
 namespace {
 
 
 namespace {
 

-constexpr int TBPIECES = 6; // Max number of supported pieces
+constexpr int TBPIECES = 7; // Max number of supported pieces

 
 enum { BigEndian, LittleEndian };
 enum TBType { KEY, WDL, DTZ }; // Used as template parameter
 
 // Each table has a set of flags: all of them refer to DTZ tables, the last one to WDL tables
 
 enum { BigEndian, LittleEndian };
 enum TBType { KEY, WDL, DTZ }; // Used as template parameter
 
 // Each table has a set of flags: all of them refer to DTZ tables, the last one to WDL tables

-enum TBFlag { STM = 1, Mapped = 2, WinPlies = 4, LossPlies = 8, SingleValue = 128 };
+enum TBFlag { STM = 1, Mapped = 2, WinPlies = 4, LossPlies = 8, Wide = 16, SingleValue = 128 };

 
 inline WDLScore operator-(WDLScore d) { return WDLScore(-int(d)); }
 inline Square operator^=(Square& s, int i) { return s = Square(int(s) ^ i); }
 
 inline WDLScore operator-(WDLScore d) { return WDLScore(-int(d)); }
 inline Square operator^=(Square& s, int i) { return s = Square(int(s) ^ i); }


@@ -75,8 +75,8 @@ int MapA1D1D4[SQUARE_NB];
 int MapKK[10][SQUARE_NB]; // [MapA1D1D4][SQUARE_NB]
 
 int Binomial[6][SQUARE_NB];    // [k][n] k elements from a set of n elements
 int MapKK[10][SQUARE_NB]; // [MapA1D1D4][SQUARE_NB]
 
 int Binomial[6][SQUARE_NB];    // [k][n] k elements from a set of n elements

-int LeadPawnIdx[5][SQUARE_NB]; // [leadPawnsCnt][SQUARE_NB]
-int LeadPawnsSize[5][4];       // [leadPawnsCnt][FILE_A..FILE_D]
+int LeadPawnIdx[6][SQUARE_NB]; // [leadPawnsCnt][SQUARE_NB]
+int LeadPawnsSize[6][4];       // [leadPawnsCnt][FILE_A..FILE_D]

 
 // Comparison function to sort leading pawns in ascending MapPawns[] order
 bool pawns_comp(Square i, Square j) { return MapPawns[i] < MapPawns[j]; }
 
 // Comparison function to sort leading pawns in ascending MapPawns[] order
 bool pawns_comp(Square i, Square j) { return MapPawns[i] < MapPawns[j]; }


@@ -144,16 +144,15 @@ static_assert(sizeof(SparseEntry) == 6, "SparseEntry must be 6 bytes");
 typedef uint16_t Sym; // Huffman symbol
 
 struct LR {
 typedef uint16_t Sym; // Huffman symbol
 
 struct LR {

-    enum Side { Left, Right, Value };
+    enum Side { Left, Right };

 
     uint8_t lr[3]; // The first 12 bits is the left-hand symbol, the second 12
                    // bits is the right-hand symbol. If symbol has length 1,
 
     uint8_t lr[3]; // The first 12 bits is the left-hand symbol, the second 12
                    // bits is the right-hand symbol. If symbol has length 1,

-                   // then the first byte is the stored value.
+                   // then the left-hand symbol is the stored value.

     template<Side S>
     Sym get() {
         return S == Left  ? ((lr[1] & 0xF) << 8) | lr[0] :
     template<Side S>
     Sym get() {
         return S == Left  ? ((lr[1] & 0xF) << 8) | lr[0] :

-               S == Right ?  (lr[2] << 4) | (lr[1] >> 4) :
-               S == Value ?   lr[0] : (assert(false), Sym(-1));
+               S == Right ?  (lr[2] << 4) | (lr[1] >> 4) : (assert(false), Sym(-1));

     }
 };
 
     }
 };
 


@@ -385,7 +384,7 @@ class TBTables {
 
     typedef std::tuple<Key, TBTable<WDL>*, TBTable<DTZ>*> Entry;
 
 
     typedef std::tuple<Key, TBTable<WDL>*, TBTable<DTZ>*> Entry;
 

-    static const int Size = 1 << 12; // 4K table, indexed by key's 12 lsb
+    static const int Size = 1 << 16; // 64K table, indexed by key's 16 lsb

 
     Entry hashTable[Size];
 
 
     Entry hashTable[Size];
 


@@ -512,7 +511,7 @@ int decompress_pairs(PairsData* d, uint64_t idx) {
         offset -= d->blockLength[block++] + 1;
 
     // Finally, we find the start address of our block of canonical Huffman symbols
         offset -= d->blockLength[block++] + 1;
 
     // Finally, we find the start address of our block of canonical Huffman symbols

-    uint32_t* ptr = (uint32_t*)(d->data + block * d->sizeofBlock);
+    uint32_t* ptr = (uint32_t*)(d->data + ((uint64_t)block * d->sizeofBlock));

 
     // Read the first 64 bits in our block, this is a (truncated) sequence of
     // unknown number of symbols of unknown length but we know the first one
 
     // Read the first 64 bits in our block, this is a (truncated) sequence of
     // unknown number of symbols of unknown length but we know the first one


@@ -575,7 +574,7 @@ int decompress_pairs(PairsData* d, uint64_t idx) {
         }
     }
 
         }
     }
 

-    return d->btree[sym].get<LR::Value>();
+    return d->btree[sym].get<LR::Left>();

 }
 
 bool check_dtz_stm(TBTable<WDL>*, int, File) { return true; }
 }
 
 bool check_dtz_stm(TBTable<WDL>*, int, File) { return true; }


@@ -601,8 +600,12 @@ int map_score(TBTable<DTZ>* entry, File f, int value, WDLScore wdl) {
 
     uint8_t* map = entry->map;
     uint16_t* idx = entry->get(0, f)->map_idx;
 
     uint8_t* map = entry->map;
     uint16_t* idx = entry->get(0, f)->map_idx;

-    if (flags & TBFlag::Mapped)
-        value = map[idx[WDLMap[wdl + 2]] + value];
+    if (flags & TBFlag::Mapped) {
+        if (flags & TBFlag::Wide)
+            value = ((uint16_t *)map)[idx[WDLMap[wdl + 2]] + value];
+        else
+            value = map[idx[WDLMap[wdl + 2]] + value];
+    }

 
     // DTZ tables store distance to zero in number of moves or plies. We
     // want to return plies, so we have convert to plies when needed.
 
     // DTZ tables store distance to zero in number of moves or plies. We
     // want to return plies, so we have convert to plies when needed.


@@ -994,11 +997,22 @@ uint8_t* set_dtz_map(TBTable<DTZ>& e, uint8_t* data, File maxFile) {
     e.map = data;
 
     for (File f = FILE_A; f <= maxFile; ++f) {
     e.map = data;
 
     for (File f = FILE_A; f <= maxFile; ++f) {

-        if (e.get(0, f)->flags & TBFlag::Mapped)
-            for (int i = 0; i < 4; ++i) { // Sequence like 3,x,x,x,1,x,0,2,x,x
-                e.get(0, f)->map_idx[i] = (uint16_t)(data - e.map + 1);
-                data += *data + 1;
+        auto flags = e.get(0, f)->flags;
+        if (flags & TBFlag::Mapped) {
+            if (flags & TBFlag::Wide) {
+                data += (uintptr_t)data & 1;  // Word alignment, we may have a mixed table
+                for (int i = 0; i < 4; ++i) { // Sequence like 3,x,x,x,1,x,0,2,x,x
+                    e.get(0, f)->map_idx[i] = (uint16_t)((uint16_t *)data - (uint16_t *)e.map + 1);
+                    data += 2 * number<uint16_t, LittleEndian>(data) + 2;
+                }

             }
             }

+            else {
+                for (int i = 0; i < 4; ++i) {
+                    e.get(0, f)->map_idx[i] = (uint16_t)(data - e.map + 1);
+                    data += *data + 1;
+                }
+            }
+        }

     }
 
     return data += (uintptr_t)data & 1; // Word alignment
     }
 
     return data += (uintptr_t)data & 1; // Word alignment


@@ -1274,9 +1288,9 @@ void Tablebases::init(const std::string& paths) {
     // among pawns with same file, the one with lowest rank.
     int availableSquares = 47; // Available squares when lead pawn is in a2
 
     // among pawns with same file, the one with lowest rank.
     int availableSquares = 47; // Available squares when lead pawn is in a2
 

-    // Init the tables for the encoding of leading pawns group: with 6-men TB we
-    // can have up to 4 leading pawns (KPPPPK).
-    for (int leadPawnsCnt = 1; leadPawnsCnt <= 4; ++leadPawnsCnt)
+    // Init the tables for the encoding of leading pawns group: with 7-men TB we
+    // can have up to 5 leading pawns (KPPPPPK).
+    for (int leadPawnsCnt = 1; leadPawnsCnt <= 5; ++leadPawnsCnt)

         for (File f = FILE_A; f <= FILE_D; ++f)
         {
             // Restart the index at every file because TB table is splitted
         for (File f = FILE_A; f <= FILE_D; ++f)
         {
             // Restart the index at every file because TB table is splitted


@@ -1320,11 +1334,22 @@ void Tablebases::init(const std::string& paths) {
             for (PieceType p3 = PAWN; p3 <= p2; ++p3) {
                 TBTables.add({KING, p1, p2, p3, KING});
 
             for (PieceType p3 = PAWN; p3 <= p2; ++p3) {
                 TBTables.add({KING, p1, p2, p3, KING});
 

-                for (PieceType p4 = PAWN; p4 <= p3; ++p4)
+                for (PieceType p4 = PAWN; p4 <= p3; ++p4) {

                     TBTables.add({KING, p1, p2, p3, p4, KING});
 
                     TBTables.add({KING, p1, p2, p3, p4, KING});
 

-                for (PieceType p4 = PAWN; p4 < KING; ++p4)
+                    for (PieceType p5 = PAWN; p5 <= p4; ++p5)
+                        TBTables.add({KING, p1, p2, p3, p4, p5, KING});
+
+                    for (PieceType p5 = PAWN; p5 < KING; ++p5)
+                        TBTables.add({KING, p1, p2, p3, p4, KING, p5});
+                }
+
+                for (PieceType p4 = PAWN; p4 < KING; ++p4) {

                     TBTables.add({KING, p1, p2, p3, KING, p4});
                     TBTables.add({KING, p1, p2, p3, KING, p4});

+
+                    for (PieceType p5 = PAWN; p5 <= p4; ++p5)
+                        TBTables.add({KING, p1, p2, p3, KING, p4, p5});
+                }

             }
 
             for (PieceType p3 = PAWN; p3 <= p1; ++p3)
             }
 
             for (PieceType p3 = PAWN; p3 <= p1; ++p3)

diff --git a/src/ucioption.cpp b/src/ucioption.cpp
index 1f120e11120b1034b3175d84a686b4512ea33668..ed68027de720ec2d86bb49fb3c7d0afbb6ca6b17 100644 (file)
--- a/src/ucioption.cpp
+++ b/src/ucioption.cpp
@@ -76,7 +76,7 @@ void init(OptionsMap& o) {
   o["SyzygyPath"]            << Option("<empty>", on_tb_path);
   o["SyzygyProbeDepth"]      << Option(1, 1, 100);
   o["Syzygy50MoveRule"]      << Option(true);
   o["SyzygyPath"]            << Option("<empty>", on_tb_path);
   o["SyzygyProbeDepth"]      << Option(1, 1, 100);
   o["Syzygy50MoveRule"]      << Option(true);

-  o["SyzygyProbeLimit"]      << Option(6, 0, 6);
+  o["SyzygyProbeLimit"]      << Option(7, 0, 7);

 }
 
 
 }