Syzygy tablebases
authorRonald de Man <ronalddeman@gmail.com>
Tue, 25 Nov 2014 23:45:28 +0000 (07:45 +0800)
committerGary Linscott <glinscott@gmail.com>
Tue, 25 Nov 2014 23:49:58 +0000 (07:49 +0800)
Adds support for Syzygy tablebases to Stockfish.  See
the Readme for information on using the tablebases.

Tablebase support can be enabled/disabled at the Makefile
level as well, by setting syzygy=yes or syzygy=no.

Big/little endian are both supported.

No functional change (if Tablebases are not used).

Resolves #6

12 files changed:
Readme.md
src/Makefile
src/main.cpp
src/position.h
src/search.cpp
src/syzygy/tbcore.cpp [new file with mode: 0644]
src/syzygy/tbcore.h [new file with mode: 0644]
src/syzygy/tbprobe.cpp [new file with mode: 0644]
src/syzygy/tbprobe.h [new file with mode: 0644]
src/types.h
src/uci.cpp
src/ucioption.cpp

index d4ea7a0..319bca8 100644 (file)
--- a/Readme.md
+++ b/Readme.md
@@ -12,6 +12,8 @@ to one search thread, so it is therefore recommended to inspect the value of
 the *Threads* UCI parameter, and to make sure it equals the number of CPU
 cores on your computer.
 
+This version of Stockfish has support for Syzygybases.
+
 
 ### Files
 
@@ -25,6 +27,58 @@ This distribution of Stockfish consists of the following files:
     that can be used to compile Stockfish on Unix-like systems.
 
 
+### Syzygybases
+
+**Configuration**
+
+Syzygybases are configured using the UCI options "SyzygyPath",
+"SyzygyProbeDepth", "Syzygy50MoveRule" and "SyzygyProbeLimit".
+
+The option "SyzygyPath" should be set to the directory or directories that
+contain the .rtbw and .rtbz files. Multiple directories should be
+separated by ";" on Windows and by ":" on Unix-based operating systems.
+**Do not use spaces around the ";" or ":".**
+
+Example: `C:\tablebases\wdl345;C:\tablebases\wdl6;D:\tablebases\dtz345;D:\tablebases\dtz6`
+
+It is recommended to store .rtbw files on an SSD. There is no loss in
+storing the .rtbz files on a regular HD.
+
+Increasing the "SyzygyProbeDepth" option lets the engine probe less
+aggressively. Set this option to a higher value if you experience too much
+slowdown (in terms of nps) due to TB probing.
+
+Set the "Syzygy50MoveRule" option to false if you want tablebase positions
+that are drawn by the 50-move rule to count as win or loss. This may be useful
+for correspondence games (because of tablebase adjudication).
+
+The "SyzygyProbeLimit" option should normally be left at its default value.
+
+**What to expect**  
+If the engine is searching a position that is not in the tablebases (e.g.
+a position with 7 pieces), it will access the tablebases during the search.
+If the engine reports a very large score (typically 123.xx), this means
+that it has found a winning line into a tablebase position.
+
+If the engine is given a position to search that is in the tablebases, it
+will use the tablebases at the beginning of the search to preselect all
+good moves, i.e. all moves that preserve the win or preserve the draw while
+taking into account the 50-move rule.
+It will then perform a search only on those moves. **The engine will not move
+immediately**, unless there is only a single good move. **The engine likely
+will not report a mate score even if the position is known to be won.**
+
+It is therefore clear that behaviour is not identical to what one might
+be used to with Nalimov tablebases. There are technical reasons for this
+difference, the main technical reason being that Nalimov tablebases use the
+DTM metric (distance-to-mate), while Syzygybases use a variation of the
+DTZ metric (distance-to-zero, zero meaning any move that resets the 50-move
+counter). This special metric is one of the reasons that Syzygybases are
+more compact than Nalimov tablebases, while still storing all information
+needed for optimal play and in addition being able to take into account
+the 50-move rule.
+
+
 ### Compiling it yourself
 
 On Unix-like systems, it should be possible to compile Stockfish
index f183e4e..0b093c4 100644 (file)
@@ -75,6 +75,12 @@ bsfq = no
 popcnt = no
 sse = no
 pext = no
+syzygy = yes
+
+ifeq ($(syzygy),yes)
+       OBJS += syzygy/tbprobe.o
+       CXXFLAGS += -DSYZYGY
+endif
 
 ### 2.2 Architecture specific
 
@@ -398,7 +404,7 @@ install:
        -strip $(BINDIR)/$(EXE)
 
 clean:
-       $(RM) $(EXE) $(EXE).exe *.o .depend *~ core bench.txt *.gcda
+       $(RM) $(EXE) $(EXE).exe *.o .depend *~ core bench.txt *.gcda ./syzygy/*.o
 
 default:
        help
index 941e2be..528e609 100644 (file)
 #include "tt.h"
 #include "uci.h"
 
+#ifdef SYZYGY
+#include "syzygy/tbprobe.h"
+#endif
+
 int main(int argc, char* argv[]) {
 
   std::cout << engine_info() << std::endl;
@@ -40,6 +44,9 @@ int main(int argc, char* argv[]) {
   Pawns::init();
   Threads.init();
   TT.resize(Options["Hash"]);
+#ifdef SYZYGY
+  Tablebases::init(Options["SyzygyPath"]);
+#endif
 
   UCI::loop(argc, argv);
 
index c39f847..6667de7 100644 (file)
@@ -24,9 +24,9 @@
 #include <cstddef>
 
 #include "bitboard.h"
+#include "bitcount.h"
 #include "types.h"
 
-
 /// The checkInfo struct is initialized at c'tor time and keeps info used
 /// to detect if a move gives check.
 class Position;
@@ -100,6 +100,7 @@ public:
   bool empty(Square s) const;
   template<PieceType Pt> int count(Color c) const;
   template<PieceType Pt> const Square* list(Color c) const;
+  int total_piece_count() const;
 
   // Castling
   int can_castle(Color c) const;
@@ -166,6 +167,7 @@ public:
   uint64_t nodes_searched() const;
   void set_nodes_searched(uint64_t n);
   bool is_draw() const;
+  int rule50_count() const;
 
   // Position consistency check, for debugging
   bool pos_is_ok(int* step = NULL) const;
@@ -352,6 +354,14 @@ inline int Position::game_ply() const {
   return gamePly;
 }
 
+inline int Position::rule50_count() const {
+  return st->rule50;
+}
+
+inline int Position::total_piece_count() const {
+  return HasPopCnt ? popcount<Full>(pieces()) : pieceCount[WHITE][ALL_PIECES];
+}
+
 inline bool Position::opposite_bishops() const {
 
   return   pieceCount[WHITE][BISHOP] == 1
@@ -402,6 +412,8 @@ inline void Position::put_piece(Square s, Color c, PieceType pt) {
   byColorBB[c] |= s;
   index[s] = pieceCount[c][pt]++;
   pieceList[c][pt][index[s]] = s;
+  if (!HasPopCnt)
+      pieceCount[WHITE][ALL_PIECES]++;
 }
 
 inline void Position::move_piece(Square from, Square to, Color c, PieceType pt) {
@@ -432,6 +444,8 @@ inline void Position::remove_piece(Square s, Color c, PieceType pt) {
   index[lastSquare] = index[s];
   pieceList[c][pt][index[lastSquare]] = lastSquare;
   pieceList[c][pt][pieceCount[c][pt]] = SQ_NONE;
+  if (!HasPopCnt)
+      pieceCount[WHITE][ALL_PIECES]--;
 }
 
 #endif // #ifndef POSITION_H_INCLUDED
index 11ba939..7116808 100644 (file)
 #include "tt.h"
 #include "uci.h"
 
+#ifdef SYZYGY
+#include "syzygy/tbprobe.h"
+#endif
+
 namespace Search {
 
   volatile SignalsType Signals;
@@ -42,6 +46,12 @@ namespace Search {
   Position RootPos;
   Time::point SearchTime;
   StateStackPtr SetupStates;
+  int TBCardinality;
+  uint64_t TBHits;
+  bool RootInTB;
+  bool TB50MoveRule;
+  Depth TBProbeDepth;
+  Value TBScore;
 }
 
 using std::string;
@@ -181,6 +191,8 @@ template uint64_t Search::perft<true>(Position& pos, Depth depth);
 void Search::think() {
 
   TimeMgr.init(Limits, RootPos.game_ply(), RootPos.side_to_move());
+  TBHits = TBCardinality = 0;
+  RootInTB = false;
 
   int cf = Options["Contempt"] * PawnValueEg / 100; // From centipawns
   DrawValue[ RootPos.side_to_move()] = VALUE_DRAW - Value(cf);
@@ -195,6 +207,60 @@ void Search::think() {
   }
   else
   {
+#ifdef SYZYGY
+      // Check Tablebases at root
+      int piecesCnt = RootPos.total_piece_count();
+      TBCardinality = Options["SyzygyProbeLimit"];
+      TBProbeDepth = Options["SyzygyProbeDepth"] * ONE_PLY;
+      if (TBCardinality > Tablebases::TBLargest)
+      {
+          TBCardinality = Tablebases::TBLargest;
+          TBProbeDepth = 0 * ONE_PLY;
+      }
+      TB50MoveRule = Options["Syzygy50MoveRule"];
+
+      if (piecesCnt <= TBCardinality)
+      {
+          TBHits = RootMoves.size();
+
+          // If the current root position is in the tablebases then RootMoves
+          // contains only moves that preserve the draw or win.
+          RootInTB = Tablebases::root_probe(RootPos, TBScore);
+
+          if (RootInTB)
+          {
+              TBCardinality = 0; // Do not probe tablebases during the search
+
+              // It might be a good idea to mangle the hash key (xor it
+              // with a fixed value) in order to "clear" the hash table of
+              // the results of previous probes. However, that would have to
+              // be done from within the Position class, so we skip it for now.
+
+              // Optional: decrease target time.
+          }
+          else // If DTZ tables are missing, use WDL tables as a fallback
+          {
+              // Filter out moves that do not preserve a draw or win
+              RootInTB = Tablebases::root_probe_wdl(RootPos, TBScore);
+
+              // Only probe during search if winning
+              if (TBScore <= VALUE_DRAW)
+                  TBCardinality = 0;
+          }
+
+          if (!RootInTB)
+          {
+              TBHits = 0;
+          }
+          else if (!TB50MoveRule)
+          {
+              TBScore = TBScore > VALUE_DRAW ? VALUE_MATE - MAX_PLY - 1
+                      : TBScore < VALUE_DRAW ? -VALUE_MATE + MAX_PLY + 1
+                      : TBScore;
+          }
+      }
+#endif
+
       for (size_t i = 0; i < Threads.size(); ++i)
           Threads[i]->maxPly = 0;
 
@@ -486,6 +552,39 @@ namespace {
         return ttValue;
     }
 
+#ifdef SYZYGY
+    // Step 4a. Tablebase probe
+    if (   !RootNode
+        && pos.total_piece_count() <= TBCardinality
+        && ( pos.total_piece_count() < TBCardinality || depth >= TBProbeDepth )
+        && pos.rule50_count() == 0)
+    {
+        int found, v = Tablebases::probe_wdl(pos, &found);
+
+        if (found)
+        {
+            TBHits++;
+
+            if (TB50MoveRule) {
+                value = v < -1 ? -VALUE_MATE + MAX_PLY + ss->ply
+                      : v >  1 ?  VALUE_MATE - MAX_PLY - ss->ply
+                      : VALUE_DRAW + 2 * v;
+            }
+            else
+            {
+                value = v < 0 ? -VALUE_MATE + MAX_PLY + ss->ply
+                      : v > 0 ?  VALUE_MATE - MAX_PLY - ss->ply
+                      : VALUE_DRAW;
+            }
+
+            TT.store(posKey, value_to_tt(value, ss->ply), BOUND_EXACT,
+                     std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY), MOVE_NONE, VALUE_NONE);
+
+            return value;
+        }
+    }
+#endif
+
     // Step 5. Evaluate the position statically and update parent's gain statistics
     if (inCheck)
     {
@@ -1352,15 +1451,25 @@ moves_loop: // When in check and at SpNode search starts from here
         Depth d = updated ? depth : depth - ONE_PLY;
         Value v = updated ? RootMoves[i].score : RootMoves[i].prevScore;
 
+        bool tb = RootInTB;
+        if (tb)
+        {
+            if (abs(v) >= VALUE_MATE - MAX_PLY)
+                tb = false;
+            else
+                v = TBScore;
+        }
+
         if (ss.rdbuf()->in_avail()) // Not at first line
             ss << "\n";
 
         ss << "info depth " << d / ONE_PLY
            << " seldepth "  << selDepth
            << " multipv "   << i + 1
-           << " score "     << (i == PVIdx ? UCI::format_value(v, alpha, beta) : UCI::format_value(v))
+           << " score "     << ((!tb && i == PVIdx) ? UCI::format_value(v, alpha, beta) : UCI::format_value(v))
            << " nodes "     << pos.nodes_searched()
            << " nps "       << pos.nodes_searched() * 1000 / elapsed
+           << " tbhits "    << TBHits
            << " time "      << elapsed
            << " pv";
 
diff --git a/src/syzygy/tbcore.cpp b/src/syzygy/tbcore.cpp
new file mode 100644 (file)
index 0000000..436f9ae
--- /dev/null
@@ -0,0 +1,1630 @@
+/*
+  Copyright (c) 2011-2013 Ronald de Man
+  This file may be redistributed and/or modified without restrictions.
+
+  tbcore.c contains engine-independent routines of the tablebase probing code.
+  This file should not need to much adaptation to add tablebase probing to
+  a particular engine, provided the engine is written in C or C++.
+*/
+
+#include <stdio.h>
+#include <unistd.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#ifndef __WIN32__
+#include <sys/mman.h>
+#endif
+#include "tbcore.h"
+
+#define TBMAX_PIECE 254
+#define TBMAX_PAWN 256
+#define HSHMAX 5
+
+// for variants where kings can connect and/or captured
+// #define CONNECTED_KINGS
+
+#define Swap(a,b) {int tmp=a;a=b;b=tmp;}
+
+#define TB_PAWN 1
+#define TB_KNIGHT 2
+#define TB_BISHOP 3
+#define TB_ROOK 4
+#define TB_QUEEN 5
+#define TB_KING 6
+
+#define TB_WPAWN TB_PAWN
+#define TB_BPAWN (TB_PAWN | 8)
+
+static LOCK_T TB_mutex;
+
+static bool initialized = false;
+static int num_paths = 0;
+static char *path_string = NULL;
+static char **paths = NULL;
+
+static int TBnum_piece, TBnum_pawn;
+static struct TBEntry_piece TB_piece[TBMAX_PIECE];
+static struct TBEntry_pawn TB_pawn[TBMAX_PAWN];
+
+static struct TBHashEntry TB_hash[1 << TBHASHBITS][HSHMAX];
+
+#define DTZ_ENTRIES 64
+
+static struct DTZTableEntry DTZ_table[DTZ_ENTRIES];
+
+static void init_indices(void);
+static uint64 calc_key_from_pcs(int *pcs, int mirror);
+static void free_wdl_entry(struct TBEntry *entry);
+static void free_dtz_entry(struct TBEntry *entry);
+
+static FD open_tb(const char *str, const char *suffix)
+{
+  int i;
+  FD fd;
+  char file[256];
+
+  for (i = 0; i < num_paths; i++) {
+    strcpy(file, paths[i]);
+    strcat(file, "/");
+    strcat(file, str);
+    strcat(file, suffix);
+#ifndef __WIN32__
+    fd = open(file, O_RDONLY);
+#else
+    fd = CreateFile(file, GENERIC_READ, FILE_SHARE_READ, NULL,
+                          OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
+#endif
+    if (fd != FD_ERR) return fd;
+  }
+  return FD_ERR;
+}
+
+static void close_tb(FD fd)
+{
+#ifndef __WIN32__
+  close(fd);
+#else
+  CloseHandle(fd);
+#endif
+}
+
+static char *map_file(const char *name, const char *suffix, uint64 *mapping)
+{
+  FD fd = open_tb(name, suffix);
+  if (fd == FD_ERR)
+    return NULL;
+#ifndef __WIN32__
+  struct stat statbuf;
+  fstat(fd, &statbuf);
+  *mapping = statbuf.st_size;
+  char *data = (char *)mmap(NULL, statbuf.st_size, PROT_READ,
+                              MAP_SHARED, fd, 0);
+  if (data == (char *)(-1)) {
+    printf("Could not mmap() %s.\n", name);
+    exit(1);
+  }
+#else
+  DWORD size_low, size_high;
+  size_low = GetFileSize(fd, &size_high);
+//  *size = ((uint64)size_high) << 32 | ((uint64)size_low);
+  HANDLE map = CreateFileMapping(fd, NULL, PAGE_READONLY, size_high, size_low,
+                                  NULL);
+  if (map == NULL) {
+    printf("CreateFileMapping() failed.\n");
+    exit(1);
+  }
+  *mapping = (uint64)map;
+  char *data = (char *)MapViewOfFile(map, FILE_MAP_READ, 0, 0, 0);
+  if (data == NULL) {
+    printf("MapViewOfFile() failed, name = %s%s, error = %lu.\n", name, suffix, GetLastError());
+    exit(1);
+  }
+#endif
+  close_tb(fd);
+  return data;
+}
+
+#ifndef __WIN32__
+static void unmap_file(char *data, uint64 size)
+{
+  if (!data) return;
+  munmap(data, size);
+}
+#else
+static void unmap_file(char *data, uint64 mapping)
+{
+  if (!data) return;
+  UnmapViewOfFile(data);
+  CloseHandle((HANDLE)mapping);
+}
+#endif
+
+static void add_to_hash(struct TBEntry *ptr, uint64 key)
+{
+  int i, hshidx;
+
+  hshidx = key >> (64 - TBHASHBITS);
+  i = 0;
+  while (i < HSHMAX && TB_hash[hshidx][i].ptr)
+    i++;
+  if (i == HSHMAX) {
+    printf("HSHMAX too low!\n");
+    exit(1);
+  } else {
+    TB_hash[hshidx][i].key = key;
+    TB_hash[hshidx][i].ptr = ptr;
+  }
+}
+
+static char pchr[] = {'K', 'Q', 'R', 'B', 'N', 'P'};
+
+static void init_tb(char *str)
+{
+  FD fd;
+  struct TBEntry *entry;
+  int i, j, pcs[16];
+  uint64 key, key2;
+  int color;
+  char *s;
+
+  fd = open_tb(str, WDLSUFFIX);
+  if (fd == FD_ERR) return;
+  close_tb(fd);
+
+  for (i = 0; i < 16; i++)
+    pcs[i] = 0;
+  color = 0;
+  for (s = str; *s; s++)
+    switch (*s) {
+    case 'P':
+      pcs[TB_PAWN | color]++;
+      break;
+    case 'N':
+      pcs[TB_KNIGHT | color]++;
+      break;
+    case 'B':
+      pcs[TB_BISHOP | color]++;
+      break;
+    case 'R':
+      pcs[TB_ROOK | color]++;
+      break;
+    case 'Q':
+      pcs[TB_QUEEN | color]++;
+      break;
+    case 'K':
+      pcs[TB_KING | color]++;
+      break;
+    case 'v':
+      color = 0x08;
+      break;
+    }
+  for (i = 0; i < 8; i++)
+    if (pcs[i] != pcs[i+8])
+      break;
+  key = calc_key_from_pcs(pcs, 0);
+  key2 = calc_key_from_pcs(pcs, 1);
+  if (pcs[TB_WPAWN] + pcs[TB_BPAWN] == 0) {
+    if (TBnum_piece == TBMAX_PIECE) {
+      printf("TBMAX_PIECE limit too low!\n");
+      exit(1);
+    }
+    entry = (struct TBEntry *)&TB_piece[TBnum_piece++];
+  } else {
+    if (TBnum_pawn == TBMAX_PAWN) {
+      printf("TBMAX_PAWN limit too low!\n");
+      exit(1);
+    }
+    entry = (struct TBEntry *)&TB_pawn[TBnum_pawn++];
+  }
+  entry->key = key;
+  entry->ready = 0;
+  entry->num = 0;
+  for (i = 0; i < 16; i++)
+    entry->num += pcs[i];
+  entry->symmetric = (key == key2);
+  entry->has_pawns = (pcs[TB_WPAWN] + pcs[TB_BPAWN] > 0);
+  if (entry->num > Tablebases::TBLargest)
+    Tablebases::TBLargest = entry->num;
+
+  if (entry->has_pawns) {
+    struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
+    ptr->pawns[0] = pcs[TB_WPAWN];
+    ptr->pawns[1] = pcs[TB_BPAWN];
+    if (pcs[TB_BPAWN] > 0
+              && (pcs[TB_WPAWN] == 0 || pcs[TB_BPAWN] < pcs[TB_WPAWN])) {
+      ptr->pawns[0] = pcs[TB_BPAWN];
+      ptr->pawns[1] = pcs[TB_WPAWN];
+    }
+  } else {
+    struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
+    for (i = 0, j = 0; i < 16; i++)
+      if (pcs[i] == 1) j++;
+    if (j >= 3) ptr->enc_type = 0;
+    else if (j == 2) ptr->enc_type = 2;
+    else { /* only for suicide */
+      j = 16;
+      for (i = 0; i < 16; i++) {
+        if (pcs[i] < j && pcs[i] > 1) j = pcs[i];
+        ptr->enc_type = 1 + j;
+      }
+    }
+  }
+  add_to_hash(entry, key);
+  if (key2 != key) add_to_hash(entry, key2);
+}
+
+void Tablebases::init(const std::string& path)
+{
+  char str[16];
+  int i, j, k, l;
+
+  if (initialized) {
+    free(path_string);
+    free(paths);
+    struct TBEntry *entry;
+    for (i = 0; i < TBnum_piece; i++) {
+      entry = (struct TBEntry *)&TB_piece[i];
+      free_wdl_entry(entry);
+    }
+    for (i = 0; i < TBnum_pawn; i++) {
+      entry = (struct TBEntry *)&TB_pawn[i];
+      free_wdl_entry(entry);
+    }
+    for (i = 0; i < DTZ_ENTRIES; i++)
+      if (DTZ_table[i].entry)
+        free_dtz_entry(DTZ_table[i].entry);
+  } else {
+    init_indices();
+    initialized = true;
+  }
+
+  const char *p = path.c_str();
+  if (strlen(p) == 0 || !strcmp(p, "<empty>")) return;
+  path_string = (char *)malloc(strlen(p) + 1);
+  strcpy(path_string, p);
+  num_paths = 0;
+  for (i = 0;; i++) {
+    if (path_string[i] != SEP_CHAR)
+      num_paths++;
+    while (path_string[i] && path_string[i] != SEP_CHAR)
+      i++;
+    if (!path_string[i]) break;
+    path_string[i] = 0;
+  }
+  paths = (char **)malloc(num_paths * sizeof(char *));
+  for (i = j = 0; i < num_paths; i++) {
+    while (!path_string[j]) j++;
+    paths[i] = &path_string[j];
+    while (path_string[j]) j++;
+  }
+
+  LOCK_INIT(TB_mutex);
+
+  TBnum_piece = TBnum_pawn = 0;
+  TBLargest = 0;
+
+  for (i = 0; i < (1 << TBHASHBITS); i++)
+    for (j = 0; j < HSHMAX; j++) {
+      TB_hash[i][j].key = 0ULL;
+      TB_hash[i][j].ptr = NULL;
+    }
+
+  for (i = 0; i < DTZ_ENTRIES; i++)
+    DTZ_table[i].entry = NULL;
+
+  for (i = 1; i < 6; i++) {
+    sprintf(str, "K%cvK", pchr[i]);
+    init_tb(str);
+  }
+
+  for (i = 1; i < 6; i++)
+    for (j = i; j < 6; j++) {
+      sprintf(str, "K%cvK%c", pchr[i], pchr[j]);
+      init_tb(str);
+    }
+
+  for (i = 1; i < 6; i++)
+    for (j = i; j < 6; j++) {
+      sprintf(str, "K%c%cvK", pchr[i], pchr[j]);
+      init_tb(str);
+    }
+
+  for (i = 1; i < 6; i++)
+    for (j = i; j < 6; j++)
+      for (k = 1; k < 6; k++) {
+        sprintf(str, "K%c%cvK%c", pchr[i], pchr[j], pchr[k]);
+        init_tb(str);
+      }
+
+  for (i = 1; i < 6; i++)
+    for (j = i; j < 6; j++)
+      for (k = j; k < 6; k++) {
+        sprintf(str, "K%c%c%cvK", pchr[i], pchr[j], pchr[k]);
+        init_tb(str);
+      }
+
+  for (i = 1; i < 6; i++)
+    for (j = i; j < 6; j++)
+      for (k = i; k < 6; k++)
+        for (l = (i == k) ? j : k; l < 6; l++) {
+          sprintf(str, "K%c%cvK%c%c", pchr[i], pchr[j], pchr[k], pchr[l]);
+          init_tb(str);
+        }
+
+  for (i = 1; i < 6; i++)
+    for (j = i; j < 6; j++)
+      for (k = j; k < 6; k++)
+        for (l = 1; l < 6; l++) {
+          sprintf(str, "K%c%c%cvK%c", pchr[i], pchr[j], pchr[k], pchr[l]);
+          init_tb(str);
+        }
+
+  for (i = 1; i < 6; i++)
+    for (j = i; j < 6; j++)
+      for (k = j; k < 6; k++)
+        for (l = k; l < 6; l++) {
+          sprintf(str, "K%c%c%c%cvK", pchr[i], pchr[j], pchr[k], pchr[l]);
+          init_tb(str);
+        }
+
+  printf("info string Found %d tablebases.\n", TBnum_piece + TBnum_pawn);
+}
+
+static const char offdiag[] = {
+  0,-1,-1,-1,-1,-1,-1,-1,
+  1, 0,-1,-1,-1,-1,-1,-1,
+  1, 1, 0,-1,-1,-1,-1,-1,
+  1, 1, 1, 0,-1,-1,-1,-1,
+  1, 1, 1, 1, 0,-1,-1,-1,
+  1, 1, 1, 1, 1, 0,-1,-1,
+  1, 1, 1, 1, 1, 1, 0,-1,
+  1, 1, 1, 1, 1, 1, 1, 0
+};
+
+static const ubyte triangle[] = {
+  6, 0, 1, 2, 2, 1, 0, 6,
+  0, 7, 3, 4, 4, 3, 7, 0,
+  1, 3, 8, 5, 5, 8, 3, 1,
+  2, 4, 5, 9, 9, 5, 4, 2,
+  2, 4, 5, 9, 9, 5, 4, 2,
+  1, 3, 8, 5, 5, 8, 3, 1,
+  0, 7, 3, 4, 4, 3, 7, 0,
+  6, 0, 1, 2, 2, 1, 0, 6
+};
+
+static const ubyte invtriangle[] = {
+  1, 2, 3, 10, 11, 19, 0, 9, 18, 27
+};
+
+static const ubyte invdiag[] = {
+  0, 9, 18, 27, 36, 45, 54, 63,
+  7, 14, 21, 28, 35, 42, 49, 56
+};
+
+static const ubyte flipdiag[] = {
+   0,  8, 16, 24, 32, 40, 48, 56,
+   1,  9, 17, 25, 33, 41, 49, 57,
+   2, 10, 18, 26, 34, 42, 50, 58,
+   3, 11, 19, 27, 35, 43, 51, 59,
+   4, 12, 20, 28, 36, 44, 52, 60,
+   5, 13, 21, 29, 37, 45, 53, 61,
+   6, 14, 22, 30, 38, 46, 54, 62,
+   7, 15, 23, 31, 39, 47, 55, 63
+};
+
+static const ubyte lower[] = {
+  28,  0,  1,  2,  3,  4,  5,  6,
+   0, 29,  7,  8,  9, 10, 11, 12,
+   1,  7, 30, 13, 14, 15, 16, 17,
+   2,  8, 13, 31, 18, 19, 20, 21,
+   3,  9, 14, 18, 32, 22, 23, 24,
+   4, 10, 15, 19, 22, 33, 25, 26,
+   5, 11, 16, 20, 23, 25, 34, 27,
+   6, 12, 17, 21, 24, 26, 27, 35
+};
+
+static const ubyte diag[] = {
+   0,  0,  0,  0,  0,  0,  0,  8,
+   0,  1,  0,  0,  0,  0,  9,  0,
+   0,  0,  2,  0,  0, 10,  0,  0,
+   0,  0,  0,  3, 11,  0,  0,  0,
+   0,  0,  0, 12,  4,  0,  0,  0,
+   0,  0, 13,  0,  0,  5,  0,  0,
+   0, 14,  0,  0,  0,  0,  6,  0,
+  15,  0,  0,  0,  0,  0,  0,  7
+};
+
+static const ubyte flap[] = {
+  0, 0, 0, 0, 0, 0, 0, 0,
+  0, 6, 12, 18, 18, 12, 6, 0,
+  1, 7, 13, 19, 19, 13, 7, 1,
+  2, 8, 14, 20, 20, 14, 8, 2,
+  3, 9, 15, 21, 21, 15, 9, 3,
+  4, 10, 16, 22, 22, 16, 10, 4,
+  5, 11, 17, 23, 23, 17, 11, 5,
+  0, 0, 0, 0, 0, 0, 0, 0
+};
+
+static const ubyte ptwist[] = {
+  0, 0, 0, 0, 0, 0, 0, 0,
+  47, 35, 23, 11, 10, 22, 34, 46,
+  45, 33, 21, 9, 8, 20, 32, 44,
+  43, 31, 19, 7, 6, 18, 30, 42,
+  41, 29, 17, 5, 4, 16, 28, 40,
+  39, 27, 15, 3, 2, 14, 26, 38,
+  37, 25, 13, 1, 0, 12, 24, 36,
+  0, 0, 0, 0, 0, 0, 0, 0
+};
+
+static const ubyte invflap[] = {
+  8, 16, 24, 32, 40, 48,
+  9, 17, 25, 33, 41, 49,
+  10, 18, 26, 34, 42, 50,
+  11, 19, 27, 35, 43, 51
+};
+
+static const ubyte invptwist[] = {
+  52, 51, 44, 43, 36, 35, 28, 27, 20, 19, 12, 11,
+  53, 50, 45, 42, 37, 34, 29, 26, 21, 18, 13, 10,
+  54, 49, 46, 41, 38, 33, 30, 25, 22, 17, 14, 9,
+  55, 48, 47, 40, 39, 32, 31, 24, 23, 16, 15, 8
+};
+
+static const ubyte file_to_file[] = {
+  0, 1, 2, 3, 3, 2, 1, 0
+};
+
+#ifndef CONNECTED_KINGS
+static const short KK_idx[10][64] = {
+  { -1, -1, -1,  0,  1,  2,  3,  4,
+    -1, -1, -1,  5,  6,  7,  8,  9,
+    10, 11, 12, 13, 14, 15, 16, 17,
+    18, 19, 20, 21, 22, 23, 24, 25,
+    26, 27, 28, 29, 30, 31, 32, 33,
+    34, 35, 36, 37, 38, 39, 40, 41,
+    42, 43, 44, 45, 46, 47, 48, 49,
+    50, 51, 52, 53, 54, 55, 56, 57 },
+  { 58, -1, -1, -1, 59, 60, 61, 62,
+    63, -1, -1, -1, 64, 65, 66, 67,
+    68, 69, 70, 71, 72, 73, 74, 75,
+    76, 77, 78, 79, 80, 81, 82, 83,
+    84, 85, 86, 87, 88, 89, 90, 91,
+    92, 93, 94, 95, 96, 97, 98, 99,
+   100,101,102,103,104,105,106,107,
+   108,109,110,111,112,113,114,115},
+  {116,117, -1, -1, -1,118,119,120,
+   121,122, -1, -1, -1,123,124,125,
+   126,127,128,129,130,131,132,133,
+   134,135,136,137,138,139,140,141,
+   142,143,144,145,146,147,148,149,
+   150,151,152,153,154,155,156,157,
+   158,159,160,161,162,163,164,165,
+   166,167,168,169,170,171,172,173 },
+  {174, -1, -1, -1,175,176,177,178,
+   179, -1, -1, -1,180,181,182,183,
+   184, -1, -1, -1,185,186,187,188,
+   189,190,191,192,193,194,195,196,
+   197,198,199,200,201,202,203,204,
+   205,206,207,208,209,210,211,212,
+   213,214,215,216,217,218,219,220,
+   221,222,223,224,225,226,227,228 },
+  {229,230, -1, -1, -1,231,232,233,
+   234,235, -1, -1, -1,236,237,238,
+   239,240, -1, -1, -1,241,242,243,
+   244,245,246,247,248,249,250,251,
+   252,253,254,255,256,257,258,259,
+   260,261,262,263,264,265,266,267,
+   268,269,270,271,272,273,274,275,
+   276,277,278,279,280,281,282,283 },
+  {284,285,286,287,288,289,290,291,
+   292,293, -1, -1, -1,294,295,296,
+   297,298, -1, -1, -1,299,300,301,
+   302,303, -1, -1, -1,304,305,306,
+   307,308,309,310,311,312,313,314,
+   315,316,317,318,319,320,321,322,
+   323,324,325,326,327,328,329,330,
+   331,332,333,334,335,336,337,338 },
+  { -1, -1,339,340,341,342,343,344,
+    -1, -1,345,346,347,348,349,350,
+    -1, -1,441,351,352,353,354,355,
+    -1, -1, -1,442,356,357,358,359,
+    -1, -1, -1, -1,443,360,361,362,
+    -1, -1, -1, -1, -1,444,363,364,
+    -1, -1, -1, -1, -1, -1,445,365,
+    -1, -1, -1, -1, -1, -1, -1,446 },
+  { -1, -1, -1,366,367,368,369,370,
+    -1, -1, -1,371,372,373,374,375,
+    -1, -1, -1,376,377,378,379,380,
+    -1, -1, -1,447,381,382,383,384,
+    -1, -1, -1, -1,448,385,386,387,
+    -1, -1, -1, -1, -1,449,388,389,
+    -1, -1, -1, -1, -1, -1,450,390,
+    -1, -1, -1, -1, -1, -1, -1,451 },
+  {452,391,392,393,394,395,396,397,
+    -1, -1, -1, -1,398,399,400,401,
+    -1, -1, -1, -1,402,403,404,405,
+    -1, -1, -1, -1,406,407,408,409,
+    -1, -1, -1, -1,453,410,411,412,
+    -1, -1, -1, -1, -1,454,413,414,
+    -1, -1, -1, -1, -1, -1,455,415,
+    -1, -1, -1, -1, -1, -1, -1,456 },
+  {457,416,417,418,419,420,421,422,
+    -1,458,423,424,425,426,427,428,
+    -1, -1, -1, -1, -1,429,430,431,
+    -1, -1, -1, -1, -1,432,433,434,
+    -1, -1, -1, -1, -1,435,436,437,
+    -1, -1, -1, -1, -1,459,438,439,
+    -1, -1, -1, -1, -1, -1,460,440,
+    -1, -1, -1, -1, -1, -1, -1,461 }
+};
+#else
+static const short PP_idx[10][64] = {
+  {  0, -1,  1,  2,  3,  4,  5,  6,
+     7,  8,  9, 10, 11, 12, 13, 14,
+    15, 16, 17, 18, 19, 20, 21, 22,
+    23, 24, 25, 26, 27, 28, 29, 30,
+    31, 32, 33, 34, 35, 36, 37, 38,
+    39, 40, 41, 42, 43, 44, 45, 46,
+    -1, 47, 48, 49, 50, 51, 52, 53,
+    54, 55, 56, 57, 58, 59, 60, 61 },
+  { 62, -1, -1, 63, 64, 65, -1, 66,
+    -1, 67, 68, 69, 70, 71, 72, -1,
+    73, 74, 75, 76, 77, 78, 79, 80,
+    81, 82, 83, 84, 85, 86, 87, 88,
+    89, 90, 91, 92, 93, 94, 95, 96,
+    -1, 97, 98, 99,100,101,102,103,
+    -1,104,105,106,107,108,109, -1,
+   110, -1,111,112,113,114, -1,115 },
+  {116, -1, -1, -1,117, -1, -1,118,
+    -1,119,120,121,122,123,124, -1,
+    -1,125,126,127,128,129,130, -1,
+   131,132,133,134,135,136,137,138,
+    -1,139,140,141,142,143,144,145,
+    -1,146,147,148,149,150,151, -1,
+    -1,152,153,154,155,156,157, -1,
+   158, -1, -1,159,160, -1, -1,161 },
+  {162, -1, -1, -1, -1, -1, -1,163,
+    -1,164, -1,165,166,167,168, -1,
+    -1,169,170,171,172,173,174, -1,
+    -1,175,176,177,178,179,180, -1,
+    -1,181,182,183,184,185,186, -1,
+    -1, -1,187,188,189,190,191, -1,
+    -1,192,193,194,195,196,197, -1,
+   198, -1, -1, -1, -1, -1, -1,199 },
+  {200, -1, -1, -1, -1, -1, -1,201,
+    -1,202, -1, -1,203, -1,204, -1,
+    -1, -1,205,206,207,208, -1, -1,
+    -1,209,210,211,212,213,214, -1,
+    -1, -1,215,216,217,218,219, -1,
+    -1, -1,220,221,222,223, -1, -1,
+    -1,224, -1,225,226, -1,227, -1,
+   228, -1, -1, -1, -1, -1, -1,229 },
+  {230, -1, -1, -1, -1, -1, -1,231,
+    -1,232, -1, -1, -1, -1,233, -1,
+    -1, -1,234, -1,235,236, -1, -1,
+    -1, -1,237,238,239,240, -1, -1,
+    -1, -1, -1,241,242,243, -1, -1,
+    -1, -1,244,245,246,247, -1, -1,
+    -1,248, -1, -1, -1, -1,249, -1,
+   250, -1, -1, -1, -1, -1, -1,251 },
+  { -1, -1, -1, -1, -1, -1, -1,259,
+    -1,252, -1, -1, -1, -1,260, -1,
+    -1, -1,253, -1, -1,261, -1, -1,
+    -1, -1, -1,254,262, -1, -1, -1,
+    -1, -1, -1, -1,255, -1, -1, -1,
+    -1, -1, -1, -1, -1,256, -1, -1,
+    -1, -1, -1, -1, -1, -1,257, -1,
+    -1, -1, -1, -1, -1, -1, -1,258 },
+  { -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1,268, -1,
+    -1, -1,263, -1, -1,269, -1, -1,
+    -1, -1, -1,264,270, -1, -1, -1,
+    -1, -1, -1, -1,265, -1, -1, -1,
+    -1, -1, -1, -1, -1,266, -1, -1,
+    -1, -1, -1, -1, -1, -1,267, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1 },
+  { -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1,274, -1, -1,
+    -1, -1, -1,271,275, -1, -1, -1,
+    -1, -1, -1, -1,272, -1, -1, -1,
+    -1, -1, -1, -1, -1,273, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1 },
+  { -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1,277, -1, -1, -1,
+    -1, -1, -1, -1,276, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1,
+    -1, -1, -1, -1, -1, -1, -1, -1 }
+};
+
+static const ubyte test45[] = {
+  0, 0, 0, 0, 0, 0, 0, 0,
+  0, 0, 0, 0, 0, 0, 0, 0,
+  0, 0, 0, 0, 0, 0, 0, 0,
+  0, 0, 0, 0, 0, 0, 0, 0,
+  1, 1, 1, 0, 0, 0, 0, 0,
+  1, 1, 0, 0, 0, 0, 0, 0,
+  1, 0, 0, 0, 0, 0, 0, 0,
+  0, 0, 0, 0, 0, 0, 0, 0
+};
+
+static const ubyte mtwist[] = {
+  15, 63, 55, 47, 40, 48, 56, 12,
+  62, 11, 39, 31, 24, 32,  8, 57,
+  54, 38,  7, 23, 16,  4, 33, 49,
+  46, 30, 22,  3,  0, 17, 25, 41,
+  45, 29, 21,  2,  1, 18, 26, 42,
+  53, 37,  6, 20, 19,  5, 34, 50,
+  61, 10, 36, 28, 27, 35,  9, 58,
+  14, 60, 52, 44, 43, 51, 59, 13
+};
+#endif
+
+static int binomial[5][64];
+static int pawnidx[5][24];
+static int pfactor[5][4];
+#ifdef CONNECTED_KINGS
+static int multidx[5][10];
+static int mfactor[5];
+#endif
+
+static void init_indices(void)
+{
+  int i, j, k;
+
+// binomial[k-1][n] = Bin(n, k)
+  for (i = 0; i < 5; i++)
+    for (j = 0; j < 64; j++) {
+      int f = j;
+      int l = 1;
+      for (k = 1; k <= i; k++) {
+        f *= (j - k);
+        l *= (k + 1);
+      }
+      binomial[i][j] = f / l;
+    }
+
+  for (i = 0; i < 5; i++) {
+    int s = 0;
+    for (j = 0; j < 6; j++) {
+      pawnidx[i][j] = s;
+      s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
+    }
+    pfactor[i][0] = s;
+    s = 0;
+    for (; j < 12; j++) {
+      pawnidx[i][j] = s;
+      s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
+    }
+    pfactor[i][1] = s;
+    s = 0;
+    for (; j < 18; j++) {
+      pawnidx[i][j] = s;
+      s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
+    }
+    pfactor[i][2] = s;
+    s = 0;
+    for (; j < 24; j++) {
+      pawnidx[i][j] = s;
+      s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
+    }
+    pfactor[i][3] = s;
+  }
+
+#ifdef CONNECTED_KINGS
+  for (i = 0; i < 5; i++) {
+    int s = 0;
+    for (j = 0; j < 10; j++) {
+      multidx[i][j] = s;
+      s += (i == 0) ? 1 : binomial[i - 1][mtwist[invtriangle[j]]];
+    }
+    mfactor[i] = s;
+  }
+#endif
+}
+
+#ifndef CONNECTED_KINGS
+static uint64 encode_piece(struct TBEntry_piece *ptr, ubyte *norm, int *pos, int *factor)
+{
+  uint64 idx;
+  int i, j, k, m, l, p;
+  int n = ptr->num;
+
+  if (pos[0] & 0x04) {
+    for (i = 0; i < n; i++)
+      pos[i] ^= 0x07;
+  }
+  if (pos[0] & 0x20) {
+    for (i = 0; i < n; i++)
+      pos[i] ^= 0x38;
+  }
+
+  for (i = 0; i < n; i++)
+    if (offdiag[pos[i]]) break;
+  if (i < (ptr->enc_type == 0 ? 3 : 2) && offdiag[pos[i]] > 0)
+    for (i = 0; i < n; i++)
+      pos[i] = flipdiag[pos[i]];
+
+  switch (ptr->enc_type) {
+
+  case 0: /* 111 */
+    i = (pos[1] > pos[0]);
+    j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
+
+    if (offdiag[pos[0]])
+      idx = triangle[pos[0]] * 63*62 + (pos[1] - i) * 62 + (pos[2] - j);
+    else if (offdiag[pos[1]])
+      idx = 6*63*62 + diag[pos[0]] * 28*62 + lower[pos[1]] * 62 + pos[2] - j;
+    else if (offdiag[pos[2]])
+      idx = 6*63*62 + 4*28*62 + (diag[pos[0]]) * 7*28 + (diag[pos[1]] - i) * 28 + lower[pos[2]];
+    else
+      idx = 6*63*62 + 4*28*62 + 4*7*28 + (diag[pos[0]] * 7*6) + (diag[pos[1]] - i) * 6 + (diag[pos[2]] - j);
+    i = 3;
+    break;
+
+  case 1: /* K3 */
+    j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
+
+    idx = KK_idx[triangle[pos[0]]][pos[1]];
+    if (idx < 441)
+      idx = idx + 441 * (pos[2] - j);
+    else {
+      idx = 441*62 + (idx - 441) + 21 * lower[pos[2]];
+      if (!offdiag[pos[2]])
+        idx -= j * 21;
+    }
+    i = 3;
+    break;
+
+  default: /* K2 */
+    idx = KK_idx[triangle[pos[0]]][pos[1]];
+    i = 2;
+    break;
+  }
+  idx *= factor[0];
+
+  for (; i < n;) {
+    int t = norm[i];
+    for (j = i; j < i + t; j++)
+      for (k = j + 1; k < i + t; k++)
+        if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
+    int s = 0;
+    for (m = i; m < i + t; m++) {
+      p = pos[m];
+      for (l = 0, j = 0; l < i; l++)
+        j += (p > pos[l]);
+      s += binomial[m - i][p - j];
+    }
+    idx += ((uint64)s) * ((uint64)factor[i]);
+    i += t;
+  }
+
+  return idx;
+}
+#else
+static uint64 encode_piece(struct TBEntry_piece *ptr, ubyte *norm, int *pos, int *factor)
+{
+  uint64 idx;
+  int i, j, k, m, l, p;
+  int n = ptr->num;
+
+  if (ptr->enc_type < 3) {
+    if (pos[0] & 0x04) {
+      for (i = 0; i < n; i++)
+        pos[i] ^= 0x07;
+    }
+    if (pos[0] & 0x20) {
+      for (i = 0; i < n; i++)
+        pos[i] ^= 0x38;
+    }
+
+    for (i = 0; i < n; i++)
+      if (offdiag[pos[i]]) break;
+    if (i < (ptr->enc_type == 0 ? 3 : 2) && offdiag[pos[i]] > 0)
+      for (i = 0; i < n; i++)
+        pos[i] = flipdiag[pos[i]];
+
+    switch (ptr->enc_type) {
+
+    case 0: /* 111 */
+      i = (pos[1] > pos[0]);
+      j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
+
+      if (offdiag[pos[0]])
+        idx = triangle[pos[0]] * 63*62 + (pos[1] - i) * 62 + (pos[2] - j);
+      else if (offdiag[pos[1]])
+        idx = 6*63*62 + diag[pos[0]] * 28*62 + lower[pos[1]] * 62 + pos[2] - j;
+      else if (offdiag[pos[2]])
+        idx = 6*63*62 + 4*28*62 + (diag[pos[0]]) * 7*28 + (diag[pos[1]] - i) * 28 + lower[pos[2]];
+      else
+        idx = 6*63*62 + 4*28*62 + 4*7*28 + (diag[pos[0]] * 7*6) + (diag[pos[1]] - i) * 6 + (diag[pos[2]] - j);
+      i = 3;
+      break;
+
+    case 2: /* 11 */
+      i = (pos[1] > pos[0]);
+
+      if (offdiag[pos[0]])
+        idx = triangle[pos[0]] * 63 + (pos[1] - i);
+      else if (offdiag[pos[1]])
+        idx = 6*63 + diag[pos[0]] * 28 + lower[pos[1]];
+      else
+        idx = 6*63 + 4*28 + (diag[pos[0]]) * 7 + (diag[pos[1]] - i);
+      i = 2;
+      break;
+
+    }
+  } else if (ptr->enc_type == 3) { /* 2, e.g. KKvK */
+    if (triangle[pos[0]] > triangle[pos[1]])
+      Swap(pos[0], pos[1]);
+    if (pos[0] & 0x04)
+      for (i = 0; i < n; i++)
+        pos[i] ^= 0x07;
+    if (pos[0] & 0x20)
+      for (i = 0; i < n; i++)
+        pos[i] ^= 0x38;
+    if (offdiag[pos[0]] > 0 || (offdiag[pos[0]] == 0 && offdiag[pos[1]] > 0))
+      for (i = 0; i < n; i++)
+        pos[i] = flipdiag[pos[i]];
+    if (test45[pos[1]] && triangle[pos[0]] == triangle[pos[1]]) {
+      Swap(pos[0], pos[1]);
+      for (i = 0; i < n; i++)
+        pos[i] = flipdiag[pos[i] ^ 0x38];
+    }
+    idx = PP_idx[triangle[pos[0]]][pos[1]];
+    i = 2;
+  } else { /* 3 and higher, e.g. KKKvK and KKKKvK */
+    for (i = 1; i < norm[0]; i++)
+      if (triangle[pos[0]] > triangle[pos[i]])
+        Swap(pos[0], pos[i]);
+    if (pos[0] & 0x04)
+      for (i = 0; i < n; i++)
+        pos[i] ^= 0x07;
+    if (pos[0] & 0x20)
+      for (i = 0; i < n; i++)
+        pos[i] ^= 0x38;
+    if (offdiag[pos[0]] > 0)
+      for (i = 0; i < n; i++)
+        pos[i] = flipdiag[pos[i]];
+    for (i = 1; i < norm[0]; i++)
+      for (j = i + 1; j < norm[0]; j++)
+        if (mtwist[pos[i]] > mtwist[pos[j]])
+          Swap(pos[i], pos[j]);
+
+    idx = multidx[norm[0] - 1][triangle[pos[0]]];
+    for (i = 1; i < norm[0]; i++)
+      idx += binomial[i - 1][mtwist[pos[i]]];
+  }
+  idx *= factor[0];
+
+  for (; i < n;) {
+    int t = norm[i];
+    for (j = i; j < i + t; j++)
+      for (k = j + 1; k < i + t; k++)
+        if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
+    int s = 0;
+    for (m = i; m < i + t; m++) {
+      p = pos[m];
+      for (l = 0, j = 0; l < i; l++)
+        j += (p > pos[l]);
+      s += binomial[m - i][p - j];
+    }
+    idx += ((uint64)s) * ((uint64)factor[i]);
+    i += t;
+  }
+
+  return idx;
+}
+#endif
+
+// determine file of leftmost pawn and sort pawns
+static int pawn_file(struct TBEntry_pawn *ptr, int *pos)
+{
+  int i;
+
+  for (i = 1; i < ptr->pawns[0]; i++)
+    if (flap[pos[0]] > flap[pos[i]])
+      Swap(pos[0], pos[i]);
+
+  return file_to_file[pos[0] & 0x07];
+}
+
+static uint64 encode_pawn(struct TBEntry_pawn *ptr, ubyte *norm, int *pos, int *factor)
+{
+  uint64 idx;
+  int i, j, k, m, s, t;
+  int n = ptr->num;
+
+  if (pos[0] & 0x04)
+    for (i = 0; i < n; i++)
+      pos[i] ^= 0x07;
+
+  for (i = 1; i < ptr->pawns[0]; i++)
+    for (j = i + 1; j < ptr->pawns[0]; j++)
+      if (ptwist[pos[i]] < ptwist[pos[j]])
+        Swap(pos[i], pos[j]);
+
+  t = ptr->pawns[0] - 1;
+  idx = pawnidx[t][flap[pos[0]]];
+  for (i = t; i > 0; i--)
+    idx += binomial[t - i][ptwist[pos[i]]];
+  idx *= factor[0];
+
+// remaining pawns
+  i = ptr->pawns[0];
+  t = i + ptr->pawns[1];
+  if (t > i) {
+    for (j = i; j < t; j++)
+      for (k = j + 1; k < t; k++)
+        if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
+    s = 0;
+    for (m = i; m < t; m++) {
+      int p = pos[m];
+      for (k = 0, j = 0; k < i; k++)
+        j += (p > pos[k]);
+      s += binomial[m - i][p - j - 8];
+    }
+    idx += ((uint64)s) * ((uint64)factor[i]);
+    i = t;
+  }
+
+  for (; i < n;) {
+    t = norm[i];
+    for (j = i; j < i + t; j++)
+      for (k = j + 1; k < i + t; k++)
+        if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
+    s = 0;
+    for (m = i; m < i + t; m++) {
+      int p = pos[m];
+      for (k = 0, j = 0; k < i; k++)
+        j += (p > pos[k]);
+      s += binomial[m - i][p - j];
+    }
+    idx += ((uint64)s) * ((uint64)factor[i]);
+    i += t;
+  }
+
+  return idx;
+}
+
+// place k like pieces on n squares
+static int subfactor(int k, int n)
+{
+  int i, f, l;
+
+  f = n;
+  l = 1;
+  for (i = 1; i < k; i++) {
+    f *= n - i;
+    l *= i + 1;
+  }
+
+  return f / l;
+}
+
+static uint64 calc_factors_piece(int *factor, int num, int order, ubyte *norm, ubyte enc_type)
+{
+  int i, k, n;
+  uint64 f;
+#ifndef CONNECTED_KINGS
+  static int pivfac[] = { 31332, 28056, 462 };
+#else
+  static int pivfac[] = { 31332, 0, 518, 278 };
+#endif
+
+  n = 64 - norm[0];
+
+  f = 1;
+  for (i = norm[0], k = 0; i < num || k == order; k++) {
+    if (k == order) {
+      factor[0] = f;
+#ifndef CONNECTED_KINGS
+      f *= pivfac[enc_type];
+#else
+      if (enc_type < 4)
+        f *= pivfac[enc_type];
+      else
+        f *= mfactor[enc_type - 2];
+#endif
+    } else {
+      factor[i] = f;
+      f *= subfactor(norm[i], n);
+      n -= norm[i];
+      i += norm[i];
+    }
+  }
+
+  return f;
+}
+
+static uint64 calc_factors_pawn(int *factor, int num, int order, int order2, ubyte *norm, int file)
+{
+  int i, k, n;
+  uint64 f;
+
+  i = norm[0];
+  if (order2 < 0x0f) i += norm[i];
+  n = 64 - i;
+
+  f = 1;
+  for (k = 0; i < num || k == order || k == order2; k++) {
+    if (k == order) {
+      factor[0] = f;
+      f *= pfactor[norm[0] - 1][file];
+    } else if (k == order2) {
+      factor[norm[0]] = f;
+      f *= subfactor(norm[norm[0]], 48 - norm[0]);
+    } else {
+      factor[i] = f;
+      f *= subfactor(norm[i], n);
+      n -= norm[i];
+      i += norm[i];
+    }
+  }
+
+  return f;
+}
+
+static void set_norm_piece(struct TBEntry_piece *ptr, ubyte *norm, ubyte *pieces)
+{
+  int i, j;
+
+  for (i = 0; i < ptr->num; i++)
+    norm[i] = 0;
+
+  switch (ptr->enc_type) {
+  case 0:
+    norm[0] = 3;
+    break;
+  case 2:
+    norm[0] = 2;
+    break;
+  default:
+    norm[0] = ptr->enc_type - 1;
+    break;
+  }
+
+  for (i = norm[0]; i < ptr->num; i += norm[i])
+    for (j = i; j < ptr->num && pieces[j] == pieces[i]; j++)
+      norm[i]++;
+}
+
+static void set_norm_pawn(struct TBEntry_pawn *ptr, ubyte *norm, ubyte *pieces)
+{
+  int i, j;
+
+  for (i = 0; i < ptr->num; i++)
+    norm[i] = 0;
+
+  norm[0] = ptr->pawns[0];
+  if (ptr->pawns[1]) norm[ptr->pawns[0]] = ptr->pawns[1];
+
+  for (i = ptr->pawns[0] + ptr->pawns[1]; i < ptr->num; i += norm[i])
+    for (j = i; j < ptr->num && pieces[j] == pieces[i]; j++)
+      norm[i]++;
+}
+
+static void setup_pieces_piece(struct TBEntry_piece *ptr, unsigned char *data, uint64 *tb_size)
+{
+  int i;
+  int order;
+
+  for (i = 0; i < ptr->num; i++)
+    ptr->pieces[0][i] = data[i + 1] & 0x0f;
+  order = data[0] & 0x0f;
+  set_norm_piece(ptr, ptr->norm[0], ptr->pieces[0]);
+  tb_size[0] = calc_factors_piece(ptr->factor[0], ptr->num, order, ptr->norm[0], ptr->enc_type);
+
+  for (i = 0; i < ptr->num; i++)
+    ptr->pieces[1][i] = data[i + 1] >> 4;
+  order = data[0] >> 4;
+  set_norm_piece(ptr, ptr->norm[1], ptr->pieces[1]);
+  tb_size[1] = calc_factors_piece(ptr->factor[1], ptr->num, order, ptr->norm[1], ptr->enc_type);
+}
+
+static void setup_pieces_piece_dtz(struct DTZEntry_piece *ptr, unsigned char *data, uint64 *tb_size)
+{
+  int i;
+  int order;
+
+  for (i = 0; i < ptr->num; i++)
+    ptr->pieces[i] = data[i + 1] & 0x0f;
+  order = data[0] & 0x0f;
+  set_norm_piece((struct TBEntry_piece *)ptr, ptr->norm, ptr->pieces);
+  tb_size[0] = calc_factors_piece(ptr->factor, ptr->num, order, ptr->norm, ptr->enc_type);
+}
+
+static void setup_pieces_pawn(struct TBEntry_pawn *ptr, unsigned char *data, uint64 *tb_size, int f)
+{
+  int i, j;
+  int order, order2;
+
+  j = 1 + (ptr->pawns[1] > 0);
+  order = data[0] & 0x0f;
+  order2 = ptr->pawns[1] ? (data[1] & 0x0f) : 0x0f;
+  for (i = 0; i < ptr->num; i++)
+    ptr->file[f].pieces[0][i] = data[i + j] & 0x0f;
+  set_norm_pawn(ptr, ptr->file[f].norm[0], ptr->file[f].pieces[0]);
+  tb_size[0] = calc_factors_pawn(ptr->file[f].factor[0], ptr->num, order, order2, ptr->file[f].norm[0], f);
+
+  order = data[0] >> 4;
+  order2 = ptr->pawns[1] ? (data[1] >> 4) : 0x0f;
+  for (i = 0; i < ptr->num; i++)
+    ptr->file[f].pieces[1][i] = data[i + j] >> 4;
+  set_norm_pawn(ptr, ptr->file[f].norm[1], ptr->file[f].pieces[1]);
+  tb_size[1] = calc_factors_pawn(ptr->file[f].factor[1], ptr->num, order, order2, ptr->file[f].norm[1], f);
+}
+
+static void setup_pieces_pawn_dtz(struct DTZEntry_pawn *ptr, unsigned char *data, uint64 *tb_size, int f)
+{
+  int i, j;
+  int order, order2;
+
+  j = 1 + (ptr->pawns[1] > 0);
+  order = data[0] & 0x0f;
+  order2 = ptr->pawns[1] ? (data[1] & 0x0f) : 0x0f;
+  for (i = 0; i < ptr->num; i++)
+    ptr->file[f].pieces[i] = data[i + j] & 0x0f;
+  set_norm_pawn((struct TBEntry_pawn *)ptr, ptr->file[f].norm, ptr->file[f].pieces);
+  tb_size[0] = calc_factors_pawn(ptr->file[f].factor, ptr->num, order, order2, ptr->file[f].norm, f);
+}
+
+static void calc_symlen(struct PairsData *d, int s, char *tmp)
+{
+  int s1, s2;
+
+  ubyte* w = d->sympat + 3 * s;
+  s2 = (w[2] << 4) | (w[1] >> 4);
+  if (s2 == 0x0fff)
+    d->symlen[s] = 0;
+  else {
+    s1 = ((w[1] & 0xf) << 8) | w[0];
+    if (!tmp[s1]) calc_symlen(d, s1, tmp);
+    if (!tmp[s2]) calc_symlen(d, s2, tmp);
+    d->symlen[s] = d->symlen[s1] + d->symlen[s2] + 1;
+  }
+  tmp[s] = 1;
+}
+
+ushort ReadUshort(ubyte* d) {
+  return d[0] | (d[1] << 8);
+}
+
+uint32 ReadUint32(ubyte* d) {
+  return d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24);
+}
+
+static struct PairsData *setup_pairs(unsigned char *data, uint64 tb_size, uint64 *size, unsigned char **next, ubyte *flags, int wdl)
+{
+  struct PairsData *d;
+  int i;
+
+  *flags = data[0];
+  if (data[0] & 0x80) {
+    d = (struct PairsData *)malloc(sizeof(struct PairsData));
+    d->idxbits = 0;
+    if (wdl)
+      d->min_len = data[1];
+    else
+      d->min_len = 0;
+    *next = data + 2;
+    size[0] = size[1] = size[2] = 0;
+    return d;
+  }
+
+  int blocksize = data[1];
+  int idxbits = data[2];
+  int real_num_blocks = ReadUint32(&data[4]);
+  int num_blocks = real_num_blocks + *(ubyte *)(&data[3]);
+  int max_len = data[8];
+  int min_len = data[9];
+  int h = max_len - min_len + 1;
+  int num_syms = ReadUshort(&data[10 + 2 * h]);
+  d = (struct PairsData *)malloc(sizeof(struct PairsData) + (h - 1) * sizeof(base_t) + num_syms);
+  d->blocksize = blocksize;
+  d->idxbits = idxbits;
+  d->offset = (ushort*)(&data[10]);
+  d->symlen = ((ubyte *)d) + sizeof(struct PairsData) + (h - 1) * sizeof(base_t);
+  d->sympat = &data[12 + 2 * h];
+  d->min_len = min_len;
+  *next = &data[12 + 2 * h + 3 * num_syms + (num_syms & 1)];
+
+  int num_indices = (tb_size + (1ULL << idxbits) - 1) >> idxbits;
+  size[0] = 6ULL * num_indices;
+  size[1] = 2ULL * num_blocks;
+  size[2] = (1ULL << blocksize) * real_num_blocks;
+
+  // char tmp[num_syms];
+  char tmp[4096];
+  for (i = 0; i < num_syms; i++)
+    tmp[i] = 0;
+  for (i = 0; i < num_syms; i++)
+    if (!tmp[i])
+      calc_symlen(d, i, tmp);
+
+  d->base[h - 1] = 0;
+  for (i = h - 2; i >= 0; i--)
+    d->base[i] = (d->base[i + 1] + ReadUshort((ubyte*)(d->offset + i)) - ReadUshort((ubyte*)(d->offset + i + 1))) / 2;
+  for (i = 0; i < h; i++)
+    d->base[i] <<= 64 - (min_len + i);
+
+  d->offset -= d->min_len;
+
+  return d;
+}
+
+static int init_table_wdl(struct TBEntry *entry, char *str)
+{
+  ubyte *next;
+  int f, s;
+  uint64 tb_size[8];
+  uint64 size[8 * 3];
+  ubyte flags;
+
+  // first mmap the table into memory
+
+  entry->data = map_file(str, WDLSUFFIX, &entry->mapping);
+  if (!entry->data) {
+    printf("Could not find %s" WDLSUFFIX, str);
+    return 0;
+  }
+
+  ubyte *data = (ubyte *)entry->data;
+  if (data[0] != WDL_MAGIC[0] ||
+      data[1] != WDL_MAGIC[1] ||
+      data[2] != WDL_MAGIC[2] ||
+      data[3] != WDL_MAGIC[3]) {
+    printf("Corrupted table.\n");
+    unmap_file(entry->data, entry->mapping);
+    entry->data = 0;
+    return 0;
+  }
+
+  int split = data[4] & 0x01;
+  int files = data[4] & 0x02 ? 4 : 1;
+
+  data += 5;
+
+  if (!entry->has_pawns) {
+    struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
+    setup_pieces_piece(ptr, data, &tb_size[0]);
+    data += ptr->num + 1;
+    data += ((uintptr_t)data) & 0x01;
+
+    ptr->precomp[0] = setup_pairs(data, tb_size[0], &size[0], &next, &flags, 1);
+    data = next;
+    if (split) {
+      ptr->precomp[1] = setup_pairs(data, tb_size[1], &size[3], &next, &flags, 1);
+      data = next;
+    } else
+      ptr->precomp[1] = NULL;
+
+    ptr->precomp[0]->indextable = (char *)data;
+    data += size[0];
+    if (split) {
+      ptr->precomp[1]->indextable = (char *)data;
+      data += size[3];
+    }
+
+    ptr->precomp[0]->sizetable = (ushort *)data;
+    data += size[1];
+    if (split) {
+      ptr->precomp[1]->sizetable = (ushort *)data;
+      data += size[4];
+    }
+
+    data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
+    ptr->precomp[0]->data = data;
+    data += size[2];
+    if (split) {
+      data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
+      ptr->precomp[1]->data = data;
+    }
+  } else {
+    struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
+    s = 1 + (ptr->pawns[1] > 0);
+    for (f = 0; f < 4; f++) {
+      setup_pieces_pawn((struct TBEntry_pawn *)ptr, data, &tb_size[2 * f], f);
+      data += ptr->num + s;
+    }
+    data += ((uintptr_t)data) & 0x01;
+
+    for (f = 0; f < files; f++) {
+      ptr->file[f].precomp[0] = setup_pairs(data, tb_size[2 * f], &size[6 * f], &next, &flags, 1);
+      data = next;
+      if (split) {
+        ptr->file[f].precomp[1] = setup_pairs(data, tb_size[2 * f + 1], &size[6 * f + 3], &next, &flags, 1);
+        data = next;
+      } else
+        ptr->file[f].precomp[1] = NULL;
+    }
+
+    for (f = 0; f < files; f++) {
+      ptr->file[f].precomp[0]->indextable = (char *)data;
+      data += size[6 * f];
+      if (split) {
+        ptr->file[f].precomp[1]->indextable = (char *)data;
+        data += size[6 * f + 3];
+      }
+    }
+
+    for (f = 0; f < files; f++) {
+      ptr->file[f].precomp[0]->sizetable = (ushort *)data;
+      data += size[6 * f + 1];
+      if (split) {
+        ptr->file[f].precomp[1]->sizetable = (ushort *)data;
+        data += size[6 * f + 4];
+      }
+    }
+
+    for (f = 0; f < files; f++) {
+      data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
+      ptr->file[f].precomp[0]->data = data;
+      data += size[6 * f + 2];
+      if (split) {
+        data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
+        ptr->file[f].precomp[1]->data = data;
+        data += size[6 * f + 5];
+      }
+    }
+  }
+
+  return 1;
+}
+
+static int init_table_dtz(struct TBEntry *entry)
+{
+  ubyte *data = (ubyte *)entry->data;
+  ubyte *next;
+  int f, s;
+  uint64 tb_size[4];
+  uint64 size[4 * 3];
+
+  if (!data)
+    return 0;
+
+  if (data[0] != DTZ_MAGIC[0] ||
+      data[1] != DTZ_MAGIC[1] ||
+      data[2] != DTZ_MAGIC[2] ||
+      data[3] != DTZ_MAGIC[3]) {
+    printf("Corrupted table.\n");
+    return 0;
+  }
+
+  int files = data[4] & 0x02 ? 4 : 1;
+
+  data += 5;
+
+  if (!entry->has_pawns) {
+    struct DTZEntry_piece *ptr = (struct DTZEntry_piece *)entry;
+    setup_pieces_piece_dtz(ptr, data, &tb_size[0]);
+    data += ptr->num + 1;
+    data += ((uintptr_t)data) & 0x01;
+
+    ptr->precomp = setup_pairs(data, tb_size[0], &size[0], &next, &(ptr->flags), 0);
+    data = next;
+
+    ptr->map = data;
+    if (ptr->flags & 2) {
+      int i;
+      for (i = 0; i < 4; i++) {
+        ptr->map_idx[i] = (data + 1 - ptr->map);
+        data += 1 + data[0];
+      }
+      data += ((uintptr_t)data) & 0x01;
+    }
+
+    ptr->precomp->indextable = (char *)data;
+    data += size[0];
+
+    ptr->precomp->sizetable = (ushort *)data;
+    data += size[1];
+
+    data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
+    ptr->precomp->data = data;
+    data += size[2];
+  } else {
+    struct DTZEntry_pawn *ptr = (struct DTZEntry_pawn *)entry;
+    s = 1 + (ptr->pawns[1] > 0);
+    for (f = 0; f < 4; f++) {
+      setup_pieces_pawn_dtz(ptr, data, &tb_size[f], f);
+      data += ptr->num + s;
+    }
+    data += ((uintptr_t)data) & 0x01;
+
+    for (f = 0; f < files; f++) {
+      ptr->file[f].precomp = setup_pairs(data, tb_size[f], &size[3 * f], &next, &(ptr->flags[f]), 0);
+      data = next;
+    }
+
+    ptr->map = data;
+    for (f = 0; f < files; f++) {
+      if (ptr->flags[f] & 2) {
+        int i;
+        for (i = 0; i < 4; i++) {
+          ptr->map_idx[f][i] = (data + 1 - ptr->map);
+          data += 1 + data[0];
+        }
+      }
+    }
+    data += ((uintptr_t)data) & 0x01;
+
+    for (f = 0; f < files; f++) {
+      ptr->file[f].precomp->indextable = (char *)data;
+      data += size[3 * f];
+    }
+
+    for (f = 0; f < files; f++) {
+      ptr->file[f].precomp->sizetable = (ushort *)data;
+      data += size[3 * f + 1];
+    }
+
+    for (f = 0; f < files; f++) {
+      data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
+      ptr->file[f].precomp->data = data;
+      data += size[3 * f + 2];
+    }
+  }
+
+  return 1;
+}
+
+template<bool LittleEndian>
+static ubyte decompress_pairs(struct PairsData *d, uint64 idx)
+{
+  if (!d->idxbits)
+    return d->min_len;
+
+  uint32 mainidx = idx >> d->idxbits;
+  int litidx = (idx & ((1 << d->idxbits) - 1)) - (1 << (d->idxbits - 1));
+  uint32 block = *(uint32 *)(d->indextable + 6 * mainidx);
+  if (!LittleEndian)
+    block = __builtin_bswap32(block);
+
+  ushort idxOffset = *(ushort *)(d->indextable + 6 * mainidx + 4);
+  if (!LittleEndian)
+    idxOffset = (idxOffset << 8) | (idxOffset >> 8);
+  litidx += idxOffset;
+
+  if (litidx < 0) {
+    do {
+      litidx += d->sizetable[--block] + 1;
+    } while (litidx < 0);
+  } else {
+    while (litidx > d->sizetable[block])
+      litidx -= d->sizetable[block++] + 1;
+  }
+
+  uint32 *ptr = (uint32 *)(d->data + (block << d->blocksize));
+
+  int m = d->min_len;
+  ushort *offset = d->offset;
+  base_t *base = d->base - m;
+  ubyte *symlen = d->symlen;
+  int sym, bitcnt;
+
+  uint64 code = *((uint64 *)ptr);
+  if (LittleEndian)
+    code = __builtin_bswap64(code);
+
+  ptr += 2;
+  bitcnt = 0; // number of "empty bits" in code
+  for (;;) {
+    int l = m;
+    while (code < base[l]) l++;
+    sym = offset[l];
+    if (!LittleEndian)
+      sym = ((sym & 0xff) << 8) | (sym >> 8);
+    sym += ((code - base[l]) >> (64 - l));
+    if (litidx < (int)symlen[sym] + 1) break;
+    litidx -= (int)symlen[sym] + 1;
+    code <<= l;
+    bitcnt += l;
+    if (bitcnt >= 32) {
+      bitcnt -= 32;
+      uint32 tmp = *ptr++;
+      if (LittleEndian)
+        tmp = __builtin_bswap32(tmp);
+      code |= ((uint64)tmp) << bitcnt;
+     }
+   }
+
+  ubyte *sympat = d->sympat;
+  while (symlen[sym] != 0) {
+    ubyte* w = sympat + (3 * sym);
+    int s1 = ((w[1] & 0xf) << 8) | w[0];
+    if (litidx < (int)symlen[s1] + 1)
+      sym = s1;
+    else {
+      litidx -= (int)symlen[s1] + 1;
+      sym = (w[2] << 4) | (w[1] >> 4);
+    }
+  }
+
+  return sympat[3 * sym];
+}
+
+void load_dtz_table(char *str, uint64 key1, uint64 key2)
+{
+  int i;
+  struct TBEntry *ptr, *ptr3;
+  struct TBHashEntry *ptr2;
+
+  DTZ_table[0].key1 = key1;
+  DTZ_table[0].key2 = key2;
+  DTZ_table[0].entry = NULL;
+
+  // find corresponding WDL entry
+  ptr2 = TB_hash[key1 >> (64 - TBHASHBITS)];
+  for (i = 0; i < HSHMAX; i++)
+    if (ptr2[i].key == key1) break;
+  if (i == HSHMAX) return;
+  ptr = ptr2[i].ptr;
+
+  ptr3 = (struct TBEntry *)malloc(ptr->has_pawns
+                                ? sizeof(struct DTZEntry_pawn)
+                                : sizeof(struct DTZEntry_piece));
+
+  ptr3->data = map_file(str, DTZSUFFIX, &ptr3->mapping);
+  ptr3->key = ptr->key;
+  ptr3->num = ptr->num;
+  ptr3->symmetric = ptr->symmetric;
+  ptr3->has_pawns = ptr->has_pawns;
+  if (ptr3->has_pawns) {
+    struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *)ptr3;
+    entry->pawns[0] = ((struct TBEntry_pawn *)ptr)->pawns[0];
+    entry->pawns[1] = ((struct TBEntry_pawn *)ptr)->pawns[1];
+  } else {
+    struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr3;
+    entry->enc_type = ((struct TBEntry_piece *)ptr)->enc_type;
+  }
+  if (!init_table_dtz(ptr3))
+    free(ptr3);
+  else
+    DTZ_table[0].entry = ptr3;
+}
+
+static void free_wdl_entry(struct TBEntry *entry)
+{
+  unmap_file(entry->data, entry->mapping);
+  if (!entry->has_pawns) {
+    struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
+    free(ptr->precomp[0]);
+    if (ptr->precomp[1])
+      free(ptr->precomp[1]);
+  } else {
+    struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
+    int f;
+    for (f = 0; f < 4; f++) {
+      free(ptr->file[f].precomp[0]);
+      if (ptr->file[f].precomp[1])
+        free(ptr->file[f].precomp[1]);
+    }
+  }
+}
+
+static void free_dtz_entry(struct TBEntry *entry)
+{
+  unmap_file(entry->data, entry->mapping);
+  if (!entry->has_pawns) {
+    struct DTZEntry_piece *ptr = (struct DTZEntry_piece *)entry;
+    free(ptr->precomp);
+  } else {
+    struct DTZEntry_pawn *ptr = (struct DTZEntry_pawn *)entry;
+    int f;
+    for (f = 0; f < 4; f++)
+      free(ptr->file[f].precomp);
+  }
+  free(entry);
+}
+
+static int wdl_to_map[5] = { 1, 3, 0, 2, 0 };
+static ubyte pa_flags[5] = { 8, 0, 0, 0, 4 };
+
diff --git a/src/syzygy/tbcore.h b/src/syzygy/tbcore.h
new file mode 100644 (file)
index 0000000..b80298e
--- /dev/null
@@ -0,0 +1,157 @@
+/*
+  Copyright (c) 2011-2013 Ronald de Man
+*/
+
+#ifndef TBCORE_H
+#define TBCORE_H
+
+#ifndef __WIN32__
+#include <pthread.h>
+#define SEP_CHAR ':'
+#define FD int
+#define FD_ERR -1
+#else
+#include <windows.h>
+#define SEP_CHAR ';'
+#define FD HANDLE
+#define FD_ERR INVALID_HANDLE_VALUE
+#endif
+
+#ifndef __WIN32__
+#define LOCK_T pthread_mutex_t
+#define LOCK_INIT(x) pthread_mutex_init(&(x), NULL)
+#define LOCK(x) pthread_mutex_lock(&(x))
+#define UNLOCK(x) pthread_mutex_unlock(&(x))
+#else
+#define LOCK_T HANDLE
+#define LOCK_INIT(x) do { x = CreateMutex(NULL, FALSE, NULL); } while (0)
+#define LOCK(x) WaitForSingleObject(x, INFINITE)
+#define UNLOCK(x) ReleaseMutex(x)
+#endif
+
+#define WDLSUFFIX ".rtbw"
+#define DTZSUFFIX ".rtbz"
+#define WDLDIR "RTBWDIR"
+#define DTZDIR "RTBZDIR"
+#define TBPIECES 6
+
+typedef unsigned long long uint64;
+typedef unsigned int uint32;
+typedef unsigned char ubyte;
+typedef unsigned short ushort;
+
+const ubyte WDL_MAGIC[4] = { 0x71, 0xe8, 0x23, 0x5d };
+const ubyte DTZ_MAGIC[4] = { 0xd7, 0x66, 0x0c, 0xa5 };
+
+#define TBHASHBITS 10
+
+struct TBHashEntry;
+
+typedef uint64 base_t;
+
+struct PairsData {
+  char *indextable;
+  ushort *sizetable;
+  ubyte *data;
+  ushort *offset;
+  ubyte *symlen;
+  ubyte *sympat;
+  int blocksize;
+  int idxbits;
+  int min_len;
+  base_t base[1]; // C++ complains about base[]...
+};
+
+struct TBEntry {
+  char *data;
+  uint64 key;
+  uint64 mapping;
+  ubyte ready;
+  ubyte num;
+  ubyte symmetric;
+  ubyte has_pawns;
+} __attribute__((__may_alias__));
+
+struct TBEntry_piece {
+  char *data;
+  uint64 key;
+  uint64 mapping;
+  ubyte ready;
+  ubyte num;
+  ubyte symmetric;
+  ubyte has_pawns;
+  ubyte enc_type;
+  struct PairsData *precomp[2];
+  int factor[2][TBPIECES];
+  ubyte pieces[2][TBPIECES];
+  ubyte norm[2][TBPIECES];
+};
+
+struct TBEntry_pawn {
+  char *data;
+  uint64 key;
+  uint64 mapping;
+  ubyte ready;
+  ubyte num;
+  ubyte symmetric;
+  ubyte has_pawns;
+  ubyte pawns[2];
+  struct {
+    struct PairsData *precomp[2];
+    int factor[2][TBPIECES];
+    ubyte pieces[2][TBPIECES];
+    ubyte norm[2][TBPIECES];
+  } file[4];
+};
+
+struct DTZEntry_piece {
+  char *data;
+  uint64 key;
+  uint64 mapping;
+  ubyte ready;
+  ubyte num;
+  ubyte symmetric;
+  ubyte has_pawns;
+  ubyte enc_type;
+  struct PairsData *precomp;
+  int factor[TBPIECES];
+  ubyte pieces[TBPIECES];
+  ubyte norm[TBPIECES];
+  ubyte flags; // accurate, mapped, side
+  ushort map_idx[4];
+  ubyte *map;
+};
+
+struct DTZEntry_pawn {
+  char *data;
+  uint64 key;
+  uint64 mapping;
+  ubyte ready;
+  ubyte num;
+  ubyte symmetric;
+  ubyte has_pawns;
+  ubyte pawns[2];
+  struct {
+    struct PairsData *precomp;
+    int factor[TBPIECES];
+    ubyte pieces[TBPIECES];
+    ubyte norm[TBPIECES];
+  } file[4];
+  ubyte flags[4];
+  ushort map_idx[4][4];
+  ubyte *map;
+};
+
+struct TBHashEntry {
+  uint64 key;
+  struct TBEntry *ptr;
+};
+
+struct DTZTableEntry {
+  uint64 key1;
+  uint64 key2;
+  struct TBEntry *entry;
+};
+
+#endif
+
diff --git a/src/syzygy/tbprobe.cpp b/src/syzygy/tbprobe.cpp
new file mode 100644 (file)
index 0000000..de437d7
--- /dev/null
@@ -0,0 +1,825 @@
+/*
+  Copyright (c) 2013 Ronald de Man
+  This file may be redistributed and/or modified without restrictions.
+
+  tbprobe.cpp contains the Stockfish-specific routines of the
+  tablebase probing code. It should be relatively easy to adapt
+  this code to other chess engines.
+*/
+
+#include "../position.h"
+#include "../movegen.h"
+#include "../bitboard.h"
+#include "../search.h"
+#include "../bitcount.h"
+
+#include "tbprobe.h"
+#include "tbcore.h"
+
+#include "tbcore.cpp"
+
+namespace Zobrist {
+  extern Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
+}
+
+int Tablebases::TBLargest = 0;
+
+// Given a position with 6 or fewer pieces, produce a text string
+// of the form KQPvKRP, where "KQP" represents the white pieces if
+// mirror == 0 and the black pieces if mirror == 1.
+static void prt_str(Position& pos, char *str, int mirror)
+{
+  Color color;
+  PieceType pt;
+  int i;
+  
+  color = !mirror ? WHITE : BLACK;
+  for (pt = KING; pt >= PAWN; --pt)
+    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
+      *str++ = pchr[6 - pt];
+  *str++ = 'v';
+  color = ~color;
+  for (pt = KING; pt >= PAWN; --pt)
+    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
+      *str++ = pchr[6 - pt];
+  *str++ = 0;
+}
+
+// Given a position, produce a 64-bit material signature key.
+// If the engine supports such a key, it should equal the engine's key.
+static uint64 calc_key(Position& pos, int mirror)
+{
+  Color color;
+  PieceType pt;
+  int i;
+  uint64 key = 0;
+
+  color = !mirror ? WHITE : BLACK;
+  for (pt = PAWN; pt <= KING; ++pt)
+    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
+      key ^= Zobrist::psq[WHITE][pt][i - 1];
+  color = ~color;
+  for (pt = PAWN; pt <= KING; ++pt)
+    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
+      key ^= Zobrist::psq[BLACK][pt][i - 1];
+
+  return key;
+}
+
+// Produce a 64-bit material key corresponding to the material combination
+// defined by pcs[16], where pcs[1], ..., pcs[6] is the number of white
+// pawns, ..., kings and pcs[9], ..., pcs[14] is the number of black
+// pawns, ..., kings.
+static uint64 calc_key_from_pcs(int *pcs, int mirror)
+{
+  int color;
+  PieceType pt;
+  int i;
+  uint64 key = 0;
+
+  color = !mirror ? 0 : 8;
+  for (pt = PAWN; pt <= KING; ++pt)
+    for (i = 0; i < pcs[color + pt]; i++)
+      key ^= Zobrist::psq[WHITE][pt][i];
+  color ^= 8;
+  for (pt = PAWN; pt <= KING; ++pt)
+    for (i = 0; i < pcs[color + pt]; i++)
+      key ^= Zobrist::psq[BLACK][pt][i];
+
+  return key;
+}
+
+bool is_little_endian() {
+  union {
+    int i;
+    char c[sizeof(int)];
+  } x;
+  x.i = 1;
+  return x.c[0] == 1;
+}
+
+static ubyte decompress_pairs(struct PairsData *d, uint64 idx)
+{
+  static const bool isLittleEndian = is_little_endian();
+  return isLittleEndian ? decompress_pairs<true >(d, idx)
+                        : decompress_pairs<false>(d, idx);
+}
+
+// probe_wdl_table and probe_dtz_table require similar adaptations.
+static int probe_wdl_table(Position& pos, int *success)
+{
+  struct TBEntry *ptr;
+  struct TBHashEntry *ptr2;
+  uint64 idx;
+  uint64 key;
+  int i;
+  ubyte res;
+  int p[TBPIECES];
+
+  // Obtain the position's material signature key.
+  key = pos.material_key();
+
+  // Test for KvK.
+  if (key == (Zobrist::psq[WHITE][KING][0] ^ Zobrist::psq[BLACK][KING][0]))
+    return 0;
+
+  ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
+  for (i = 0; i < HSHMAX; i++)
+    if (ptr2[i].key == key) break;
+  if (i == HSHMAX) {
+    *success = 0;
+    return 0;
+  }
+
+  ptr = ptr2[i].ptr;
+  if (!ptr->ready) {
+    LOCK(TB_mutex);
+    if (!ptr->ready) {
+      char str[16];
+      prt_str(pos, str, ptr->key != key);
+      if (!init_table_wdl(ptr, str)) {
+        ptr2[i].key = 0ULL;
+        *success = 0;
+        UNLOCK(TB_mutex);
+        return 0;
+      }
+      // Memory barrier to ensure ptr->ready = 1 is not reordered.
+      __asm__ __volatile__ ("" ::: "memory");
+      ptr->ready = 1;
+    }
+    UNLOCK(TB_mutex);
+  }
+
+  int bside, mirror, cmirror;
+  if (!ptr->symmetric) {
+    if (key != ptr->key) {
+      cmirror = 8;
+      mirror = 0x38;
+      bside = (pos.side_to_move() == WHITE);
+    } else {
+      cmirror = mirror = 0;
+      bside = !(pos.side_to_move() == WHITE);
+    }
+  } else {
+    cmirror = pos.side_to_move() == WHITE ? 0 : 8;
+    mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
+    bside = 0;
+  }
+
+  // p[i] is to contain the square 0-63 (A1-H8) for a piece of type
+  // pc[i] ^ cmirror, where 1 = white pawn, ..., 14 = black king.
+  // Pieces of the same type are guaranteed to be consecutive.
+  if (!ptr->has_pawns) {
+    struct TBEntry_piece *entry = (struct TBEntry_piece *)ptr;
+    ubyte *pc = entry->pieces[bside];
+    for (i = 0; i < entry->num;) {
+      Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
+                                      (PieceType)(pc[i] & 0x07));
+      do {
+        p[i++] = pop_lsb(&bb);
+      } while (bb);
+    }
+    idx = encode_piece(entry, entry->norm[bside], p, entry->factor[bside]);
+    res = decompress_pairs(entry->precomp[bside], idx);
+  } else {
+    struct TBEntry_pawn *entry = (struct TBEntry_pawn *)ptr;
+    int k = entry->file[0].pieces[0][0] ^ cmirror;
+    Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));
+    i = 0;
+    do {
+      p[i++] = pop_lsb(&bb) ^ mirror;
+    } while (bb);
+    int f = pawn_file(entry, p);
+    ubyte *pc = entry->file[f].pieces[bside];
+    for (; i < entry->num;) {
+      bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
+                                    (PieceType)(pc[i] & 0x07));
+      do {
+        p[i++] = pop_lsb(&bb) ^ mirror;
+      } while (bb);
+    }
+    idx = encode_pawn(entry, entry->file[f].norm[bside], p, entry->file[f].factor[bside]);
+    res = decompress_pairs(entry->file[f].precomp[bside], idx);
+  }
+
+  return ((int)res) - 2;
+}
+
+static int probe_dtz_table(Position& pos, int wdl, int *success)
+{
+  struct TBEntry *ptr;
+  uint64 idx;
+  int i, res;
+  int p[TBPIECES];
+
+  // Obtain the position's material signature key.
+  uint64 key = pos.material_key();
+
+  if (DTZ_table[0].key1 != key && DTZ_table[0].key2 != key) {
+    for (i = 1; i < DTZ_ENTRIES; i++)
+      if (DTZ_table[i].key1 == key) break;
+    if (i < DTZ_ENTRIES) {
+      struct DTZTableEntry table_entry = DTZ_table[i];
+      for (; i > 0; i--)
+        DTZ_table[i] = DTZ_table[i - 1];
+      DTZ_table[0] = table_entry;
+    } else {
+      struct TBHashEntry *ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
+      for (i = 0; i < HSHMAX; i++)
+        if (ptr2[i].key == key) break;
+      if (i == HSHMAX) {
+        *success = 0;
+        return 0;
+      }
+      ptr = ptr2[i].ptr;
+      char str[16];
+      int mirror = (ptr->key != key);
+      prt_str(pos, str, mirror);
+      if (DTZ_table[DTZ_ENTRIES - 1].entry)
+        free_dtz_entry(DTZ_table[DTZ_ENTRIES-1].entry);
+      for (i = DTZ_ENTRIES - 1; i > 0; i--)
+        DTZ_table[i] = DTZ_table[i - 1];
+      load_dtz_table(str, calc_key(pos, mirror), calc_key(pos, !mirror));
+    }
+  }
+
+  ptr = DTZ_table[0].entry;
+  if (!ptr) {
+    *success = 0;
+    return 0;
+  }
+
+  int bside, mirror, cmirror;
+  if (!ptr->symmetric) {
+    if (key != ptr->key) {
+      cmirror = 8;
+      mirror = 0x38;
+      bside = (pos.side_to_move() == WHITE);
+    } else {
+      cmirror = mirror = 0;
+      bside = !(pos.side_to_move() == WHITE);
+    }
+  } else {
+    cmirror = pos.side_to_move() == WHITE ? 0 : 8;
+    mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
+    bside = 0;
+  }
+
+  if (!ptr->has_pawns) {
+    struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr;
+    if ((entry->flags & 1) != bside && !entry->symmetric) {
+      *success = -1;
+      return 0;
+    }
+    ubyte *pc = entry->pieces;
+    for (i = 0; i < entry->num;) {
+      Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
+                                    (PieceType)(pc[i] & 0x07));
+      do {
+        p[i++] = pop_lsb(&bb);
+      } while (bb);
+    }
+    idx = encode_piece((struct TBEntry_piece *)entry, entry->norm, p, entry->factor);
+    res = decompress_pairs(entry->precomp, idx);
+
+    if (entry->flags & 2)
+      res = entry->map[entry->map_idx[wdl_to_map[wdl + 2]] + res];
+
+    if (!(entry->flags & pa_flags[wdl + 2]) || (wdl & 1))
+      res *= 2;
+  } else {
+    struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *)ptr;
+    int k = entry->file[0].pieces[0] ^ cmirror;
+    Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));
+    i = 0;
+    do {
+      p[i++] = pop_lsb(&bb) ^ mirror;
+    } while (bb);
+    int f = pawn_file((struct TBEntry_pawn *)entry, p);
+    if ((entry->flags[f] & 1) != bside) {
+      *success = -1;
+      return 0;
+    }
+    ubyte *pc = entry->file[f].pieces;
+    for (; i < entry->num;) {
+      bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
+                            (PieceType)(pc[i] & 0x07));
+      do {
+        p[i++] = pop_lsb(&bb) ^ mirror;
+      } while (bb);
+    }
+    idx = encode_pawn((struct TBEntry_pawn *)entry, entry->file[f].norm, p, entry->file[f].factor);
+    res = decompress_pairs(entry->file[f].precomp, idx);
+
+    if (entry->flags[f] & 2)
+      res = entry->map[entry->map_idx[f][wdl_to_map[wdl + 2]] + res];
+
+    if (!(entry->flags[f] & pa_flags[wdl + 2]) || (wdl & 1))
+      res *= 2;
+  }
+
+  return res;
+}
+
+// Add underpromotion captures to list of captures.
+static ExtMove *add_underprom_caps(Position& pos, ExtMove *stack, ExtMove *end)
+{
+  ExtMove *moves, *extra = end;
+
+  for (moves = stack; moves < end; moves++) {
+    Move move = moves->move;
+    if (type_of(move) == PROMOTION && !pos.empty(to_sq(move))) {
+      (*extra++).move = (Move)(move - (1 << 12));
+      (*extra++).move = (Move)(move - (2 << 12));
+      (*extra++).move = (Move)(move - (3 << 12));
+    }
+  }
+
+  return extra;
+}
+
+static int probe_ab(Position& pos, int alpha, int beta, int *success)
+{
+  int v;
+  ExtMove stack[64];
+  ExtMove *moves, *end;
+  StateInfo st;
+
+  // Generate (at least) all legal non-ep captures including (under)promotions.
+  // It is OK to generate more, as long as they are filtered out below.
+  if (!pos.checkers()) {
+    end = generate<CAPTURES>(pos, stack);
+    // Since underpromotion captures are not included, we need to add them.
+    end = add_underprom_caps(pos, stack, end);
+  } else
+    end = generate<EVASIONS>(pos, stack);
+
+  CheckInfo ci(pos);
+
+  for (moves = stack; moves < end; moves++) {
+    Move capture = moves->move;
+    if (!pos.capture(capture) || type_of(capture) == ENPASSANT
+                        || !pos.legal(capture, ci.pinned))
+      continue;
+    pos.do_move(capture, st, ci, pos.gives_check(capture, ci));
+    v = -probe_ab(pos, -beta, -alpha, success);
+    pos.undo_move(capture);
+    if (*success == 0) return 0;
+    if (v > alpha) {
+      if (v >= beta) {
+        *success = 2;
+        return v;
+      }
+      alpha = v;
+    }
+  }
+
+  v = probe_wdl_table(pos, success);
+  if (*success == 0) return 0;
+  if (alpha >= v) {
+    *success = 1 + (alpha > 0);
+    return alpha;
+  } else {
+    *success = 1;
+    return v;
+  }
+}
+
+// Probe the WDL table for a particular position.
+// If *success != 0, the probe was successful.
+// The return value is from the point of view of the side to move:
+// -2 : loss
+// -1 : loss, but draw under 50-move rule
+//  0 : draw
+//  1 : win, but draw under 50-move rule
+//  2 : win
+int Tablebases::probe_wdl(Position& pos, int *success)
+{
+  int v;
+
+  *success = 1;
+  v = probe_ab(pos, -2, 2, success);
+
+  // If en passant is not possible, we are done.
+  if (pos.ep_square() == SQ_NONE)
+    return v;
+  if (!(*success)) return 0;
+
+  // Now handle en passant.
+  int v1 = -3;
+  // Generate (at least) all legal en passant captures.
+  ExtMove stack[192];
+  ExtMove *moves, *end;
+  StateInfo st;
+
+  if (!pos.checkers())
+    end = generate<CAPTURES>(pos, stack);
+  else
+    end = generate<EVASIONS>(pos, stack);
+
+  CheckInfo ci(pos);
+
+  for (moves = stack; moves < end; moves++) {
+    Move capture = moves->move;
+    if (type_of(capture) != ENPASSANT
+          || !pos.legal(capture, ci.pinned))
+      continue;
+    pos.do_move(capture, st, ci, pos.gives_check(capture, ci));
+    int v0 = -probe_ab(pos, -2, 2, success);
+    pos.undo_move(capture);
+    if (*success == 0) return 0;
+    if (v0 > v1) v1 = v0;
+  }
+  if (v1 > -3) {
+    if (v1 >= v) v = v1;
+    else if (v == 0) {
+      // Check whether there is at least one legal non-ep move.
+      for (moves = stack; moves < end; moves++) {
+        Move capture = moves->move;
+        if (type_of(capture) == ENPASSANT) continue;
+        if (pos.legal(capture, ci.pinned)) break;
+      }
+      if (moves == end && !pos.checkers()) {
+        end = generate<QUIETS>(pos, end);
+        for (; moves < end; moves++) {
+          Move move = moves->move;
+          if (pos.legal(move, ci.pinned))
+            break;
+        }
+      }
+      // If not, then we are forced to play the losing ep capture.
+      if (moves == end)
+        v = v1;
+    }
+  }
+
+  return v;
+}
+
+// This routine treats a position with en passant captures as one without.
+static int probe_dtz_no_ep(Position& pos, int *success)
+{
+  int wdl, dtz;
+
+  wdl = probe_ab(pos, -2, 2, success);
+  if (*success == 0) return 0;
+
+  if (wdl == 0) return 0;
+
+  if (*success == 2)
+    return wdl == 2 ? 1 : 101;
+
+  ExtMove stack[192];
+  ExtMove *moves, *end = NULL;
+  StateInfo st;
+  CheckInfo ci(pos);
+
+  if (wdl > 0) {
+    // Generate at least all legal non-capturing pawn moves
+    // including non-capturing promotions.
+    if (!pos.checkers())
+      end = generate<NON_EVASIONS>(pos, stack);
+    else
+      end = generate<EVASIONS>(pos, stack);
+
+    for (moves = stack; moves < end; moves++) {
+      Move move = moves->move;
+      if (type_of(pos.moved_piece(move)) != PAWN || pos.capture(move)
+                || !pos.legal(move, ci.pinned))
+        continue;
+      pos.do_move(move, st, ci, pos.gives_check(move, ci));
+      int v = -probe_ab(pos, -2, -wdl + 1, success);
+      pos.undo_move(move);
+      if (*success == 0) return 0;
+      if (v == wdl)
+        return v == 2 ? 1 : 101;
+    }
+  }
+
+  dtz = 1 + probe_dtz_table(pos, wdl, success);
+  if (*success >= 0) {
+    if (wdl & 1) dtz += 100;
+    return wdl >= 0 ? dtz : -dtz;
+  }
+
+  if (wdl > 0) {
+    int best = 0xffff;
+    for (moves = stack; moves < end; moves++) {
+      Move move = moves->move;
+      if (pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN
+                || !pos.legal(move, ci.pinned))
+        continue;
+      pos.do_move(move, st, ci, pos.gives_check(move, ci));
+      int v = -Tablebases::probe_dtz(pos, success);
+      pos.undo_move(move);
+      if (*success == 0) return 0;
+      if (v > 0 && v + 1 < best)
+        best = v + 1;
+    }
+    return best;
+  } else {
+    int best = -1;
+    if (!pos.checkers())
+      end = generate<NON_EVASIONS>(pos, stack);
+    else
+      end = generate<EVASIONS>(pos, stack);
+    for (moves = stack; moves < end; moves++) {
+      int v;
+      Move move = moves->move;
+      if (!pos.legal(move, ci.pinned))
+        continue;
+      pos.do_move(move, st, ci, pos.gives_check(move, ci));
+      if (st.rule50 == 0) {
+        if (wdl == -2) v = -1;
+        else {
+          v = probe_ab(pos, 1, 2, success);
+          v = (v == 2) ? 0 : -101;
+        }
+      } else {
+        v = -Tablebases::probe_dtz(pos, success) - 1;
+      }
+      pos.undo_move(move);
+      if (*success == 0) return 0;
+      if (v < best)
+        best = v;
+    }
+    return best;
+  }
+}
+
+static int wdl_to_dtz[] = {
+  -1, -101, 0, 101, 1
+};
+
+// Probe the DTZ table for a particular position.
+// If *success != 0, the probe was successful.
+// The return value is from the point of view of the side to move:
+//         n < -100 : loss, but draw under 50-move rule
+// -100 <= n < -1   : loss in n ply (assuming 50-move counter == 0)
+//         0        : draw
+//     1 < n <= 100 : win in n ply (assuming 50-move counter == 0)
+//   100 < n        : win, but draw under 50-move rule
+//
+// The return value n can be off by 1: a return value -n can mean a loss
+// in n+1 ply and a return value +n can mean a win in n+1 ply. This
+// cannot happen for tables with positions exactly on the "edge" of
+// the 50-move rule.
+//
+// This implies that if dtz > 0 is returned, the position is certainly
+// a win if dtz + 50-move-counter <= 99. Care must be taken that the engine
+// picks moves that preserve dtz + 50-move-counter <= 99.
+//
+// If n = 100 immediately after a capture or pawn move, then the position
+// is also certainly a win, and during the whole phase until the next
+// capture or pawn move, the inequality to be preserved is
+// dtz + 50-movecounter <= 100.
+//
+// In short, if a move is available resulting in dtz + 50-move-counter <= 99,
+// then do not accept moves leading to dtz + 50-move-counter == 100.
+//
+int Tablebases::probe_dtz(Position& pos, int *success)
+{
+  *success = 1;
+  int v = probe_dtz_no_ep(pos, success);
+
+  if (pos.ep_square() == SQ_NONE)
+    return v;
+  if (*success == 0) return 0;
+
+  // Now handle en passant.
+  int v1 = -3;
+
+  ExtMove stack[192];
+  ExtMove *moves, *end;
+  StateInfo st;
+
+  if (!pos.checkers())
+    end = generate<CAPTURES>(pos, stack);
+  else
+    end = generate<EVASIONS>(pos, stack);
+  CheckInfo ci(pos);
+
+  for (moves = stack; moves < end; moves++) {
+    Move capture = moves->move;
+    if (type_of(capture) != ENPASSANT
+                || !pos.legal(capture, ci.pinned))
+      continue;
+    pos.do_move(capture, st, ci, pos.gives_check(capture, ci));
+    int v0 = -probe_ab(pos, -2, 2, success);
+    pos.undo_move(capture);
+    if (*success == 0) return 0;
+    if (v0 > v1) v1 = v0;
+  }
+  if (v1 > -3) {
+    v1 = wdl_to_dtz[v1 + 2];
+    if (v < -100) {
+      if (v1 >= 0)
+        v = v1;
+    } else if (v < 0) {
+      if (v1 >= 0 || v1 < 100)
+        v = v1;
+    } else if (v > 100) {
+      if (v1 > 0)
+        v = v1;
+    } else if (v > 0) {
+      if (v1 == 1)
+        v = v1;
+    } else if (v1 >= 0) {
+      v = v1;
+    } else {
+      for (moves = stack; moves < end; moves++) {
+        Move move = moves->move;
+        if (type_of(move) == ENPASSANT) continue;
+        if (pos.legal(move, ci.pinned)) break;
+      }
+      if (moves == end && !pos.checkers()) {
+        end = generate<QUIETS>(pos, end);
+        for (; moves < end; moves++) {
+          Move move = moves->move;
+          if (pos.legal(move, ci.pinned))
+            break;
+        }
+      }
+      if (moves == end)
+        v = v1;
+    }
+  }
+
+  return v;
+}
+
+// Check whether there has been at least one repetition of positions
+// since the last capture or pawn move.
+static int has_repeated(StateInfo *st)
+{
+  while (1) {
+    int i = 4, e = std::min(st->rule50, st->pliesFromNull);
+    if (e < i)
+      return 0;
+    StateInfo *stp = st->previous->previous;
+    do {
+      stp = stp->previous->previous;
+      if (stp->key == st->key)
+        return 1;
+      i += 2;
+    } while (i <= e);
+    st = st->previous;
+  }
+}
+
+static Value wdl_to_Value[5] = {
+  -VALUE_MATE + MAX_PLY + 1,
+  VALUE_DRAW - 2,
+  VALUE_DRAW,
+  VALUE_DRAW + 2,
+  VALUE_MATE - MAX_PLY - 1
+};
+
+// Use the DTZ tables to filter out moves that don't preserve the win or draw.
+// If the position is lost, but DTZ is fairly high, only keep moves that
+// maximise DTZ.
+//
+// A return value false indicates that not all probes were successful and that
+// no moves were filtered out.
+bool Tablebases::root_probe(Position& pos, Value& TBScore)
+{
+  int success;
+
+  int dtz = probe_dtz(pos, &success);
+  if (!success) return false;
+
+  StateInfo st;
+  CheckInfo ci(pos);
+
+  // Probe each move.
+  for (size_t i = 0; i < Search::RootMoves.size(); i++) {
+    Move move = Search::RootMoves[i].pv[0];
+    pos.do_move(move, st, ci, pos.gives_check(move, ci));
+    int v = 0;
+    if (pos.checkers() && dtz > 0) {
+      ExtMove s[192];
+      if (generate<LEGAL>(pos, s) == s)
+        v = 1;
+    }
+    if (!v) {
+      if (st.rule50 != 0) {
+        v = -Tablebases::probe_dtz(pos, &success);
+        if (v > 0) v++;
+        else if (v < 0) v--;
+      } else {
+        v = -Tablebases::probe_wdl(pos, &success);
+        v = wdl_to_dtz[v + 2];
+      }
+    }
+    pos.undo_move(move);
+    if (!success) return false;
+    Search::RootMoves[i].score = (Value)v;
+  }
+
+  // Obtain 50-move counter for the root position.
+  // In Stockfish there seems to be no clean way, so we do it like this:
+  int cnt50 = st.previous->rule50;
+
+  // Use 50-move counter to determine whether the root position is
+  // won, lost or drawn.
+  int wdl = 0;
+  if (dtz > 0)
+    wdl = (dtz + cnt50 <= 100) ? 2 : 1;
+  else if (dtz < 0)
+    wdl = (-dtz + cnt50 <= 100) ? -2 : -1;
+
+  // Determine the score to report to the user.
+  TBScore = wdl_to_Value[wdl + 2];
+  // If the position is winning or losing, but too few moves left, adjust the
+  // score to show how close it is to winning or losing.
+  // NOTE: int(PawnValueEg) is used as scaling factor in score_to_uci().
+  if (wdl == 1 && dtz <= 100)
+    TBScore = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200);
+  else if (wdl == -1 && dtz >= -100)
+    TBScore = -(Value)(((200 + dtz - cnt50) * int(PawnValueEg)) / 200);
+
+  // Now be a bit smart about filtering out moves.
+  size_t j = 0;
+  if (dtz > 0) { // winning (or 50-move rule draw)
+    int best = 0xffff;
+    for (size_t i = 0; i < Search::RootMoves.size(); i++) {
+      int v = Search::RootMoves[i].score;
+      if (v > 0 && v < best)
+        best = v;
+    }
+    int max = best;
+    // If the current phase has not seen repetitions, then try all moves
+    // that stay safely within the 50-move budget, if there are any.
+    if (!has_repeated(st.previous) && best + cnt50 <= 99)
+      max = 99 - cnt50;
+    for (size_t i = 0; i < Search::RootMoves.size(); i++) {
+      int v = Search::RootMoves[i].score;
+      if (v > 0 && v <= max)
+        Search::RootMoves[j++] = Search::RootMoves[i];
+    }
+  } else if (dtz < 0) { // losing (or 50-move rule draw)
+    int best = 0;
+    for (size_t i = 0; i < Search::RootMoves.size(); i++) {
+      int v = Search::RootMoves[i].score;
+      if (v < best)
+        best = v;
+    }
+    // Try all moves, unless we approach or have a 50-move rule draw.
+    if (-best * 2 + cnt50 < 100)
+      return true;
+    for (size_t i = 0; i < Search::RootMoves.size(); i++) {
+      if (Search::RootMoves[i].score == best)
+        Search::RootMoves[j++] = Search::RootMoves[i];
+    }
+  } else { // drawing
+    // Try all moves that preserve the draw.
+    for (size_t i = 0; i < Search::RootMoves.size(); i++) {
+      if (Search::RootMoves[i].score == 0)
+        Search::RootMoves[j++] = Search::RootMoves[i];
+    }
+  }
+  Search::RootMoves.resize(j, Search::RootMove(MOVE_NONE));
+
+  return true;
+}
+
+// Use the WDL tables to filter out moves that don't preserve the win or draw.
+// This is a fallback for the case that some or all DTZ tables are missing.
+//
+// A return value false indicates that not all probes were successful and that
+// no moves were filtered out.
+bool Tablebases::root_probe_wdl(Position& pos, Value& TBScore)
+{
+  int success;
+
+  int wdl = Tablebases::probe_wdl(pos, &success);
+  if (!success) return false;
+  TBScore = wdl_to_Value[wdl + 2];
+
+  StateInfo st;
+  CheckInfo ci(pos);
+
+  int best = -2;
+
+  // Probe each move.
+  for (size_t i = 0; i < Search::RootMoves.size(); i++) {
+    Move move = Search::RootMoves[i].pv[0];
+    pos.do_move(move, st, ci, pos.gives_check(move, ci));
+    int v = -Tablebases::probe_wdl(pos, &success);
+    pos.undo_move(move);
+    if (!success) return false;
+    Search::RootMoves[i].score = (Value)v;
+    if (v > best)
+      best = v;
+  }
+
+  size_t j = 0;
+  for (size_t i = 0; i < Search::RootMoves.size(); i++) {
+    if (Search::RootMoves[i].score == best)
+      Search::RootMoves[j++] = Search::RootMoves[i];
+  }
+  Search::RootMoves.resize(j, Search::RootMove(MOVE_NONE));
+
+  return true;
+}
+
diff --git a/src/syzygy/tbprobe.h b/src/syzygy/tbprobe.h
new file mode 100644 (file)
index 0000000..9ed6f0a
--- /dev/null
@@ -0,0 +1,16 @@
+#ifndef TBPROBE_H
+#define TBPROBE_H
+
+namespace Tablebases {
+
+extern int TBLargest;
+
+void init(const std::string& path);
+int probe_wdl(Position& pos, int *success);
+int probe_dtz(Position& pos, int *success);
+bool root_probe(Position& pos, Value& TBScore);
+bool root_probe_wdl(Position& pos, Value& TBScore);
+
+}
+
+#endif
index d725c13..43f2d4e 100644 (file)
@@ -175,8 +175,8 @@ enum Value {
   VALUE_INFINITE  = 32001,
   VALUE_NONE      = 32002,
 
-  VALUE_MATE_IN_MAX_PLY  =  VALUE_MATE - MAX_PLY,
-  VALUE_MATED_IN_MAX_PLY = -VALUE_MATE + MAX_PLY,
+  VALUE_MATE_IN_MAX_PLY  =  VALUE_MATE - 2 * MAX_PLY,
+  VALUE_MATED_IN_MAX_PLY = -VALUE_MATE + 2 * MAX_PLY,
 
   VALUE_ENSURE_INTEGER_SIZE_P = INT_MAX,
   VALUE_ENSURE_INTEGER_SIZE_N = INT_MIN,
index 0f67c44..876bb1d 100644 (file)
@@ -227,7 +227,7 @@ string UCI::format_value(Value v, Value alpha, Value beta) {
 
   stringstream ss;
 
-  if (abs(v) < VALUE_MATE_IN_MAX_PLY)
+  if (abs(v) < VALUE_MATE - MAX_PLY)
       ss << "cp " << v * 100 / PawnValueEg;
   else
       ss << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2;
index 1d61d07..b2096f5 100644 (file)
 #include "tt.h"
 #include "uci.h"
 
+#ifdef SYZYGY
+#include "syzygy/tbprobe.h"
+#endif
+
 using std::string;
 
 UCI::OptionsMap Options; // Global object
@@ -38,6 +42,9 @@ void on_logger(const Option& o) { start_logger(o); }
 void on_threads(const Option&) { Threads.read_uci_options(); }
 void on_hash_size(const Option& o) { TT.resize(o); }
 void on_clear_hash(const Option&) { TT.clear(); }
+#ifdef SYZYGY
+void on_tb_path(const Option& o) { Tablebases::init(o); }
+#endif
 
 
 /// Our case insensitive less() function as required by UCI protocol
@@ -65,6 +72,12 @@ void init(OptionsMap& o) {
   o["Minimum Thinking Time"] << Option(20, 0, 5000);
   o["Slow Mover"]            << Option(80, 10, 1000);
   o["UCI_Chess960"]          << Option(false);
+#ifdef SYZYGY
+  o["SyzygyPath"]            << Option("<empty>", on_tb_path);
+  o["SyzygyProbeDepth"]      << Option(1, 1, 100);
+  o["Syzygy50MoveRule"]      << Option(true);
+  o["SyzygyProbeLimit"]      << Option(6, 0, 6);
+#endif
 }