From c0bb0415394179e9c771cc96a9da6724fc14c167 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 16 Jul 2016 08:10:45 +0200 Subject: [PATCH] Rewrite syzygy in C++ Rewrite the code in SF style, simplify and document it. Code is now much clear and bug free (no mem-leaks and other small issues) and is also smaller (more than 600 lines of code removed). All the code has been rewritten but root_probe() and root_probe_wdl() that are completely misplaced and should be retired altogheter. For now just leave them in the original version. Code is fully and deeply tested for equivalency both in functionality and in speed with hundreds of games and test positions and is guaranteed to be 100% equivalent to the original. Tested with tb_dbg branch for functional equivalency on more than 12M positions. stockfish.exe bench 128 1 16 syzygy.epd Position: 2016/2016 Total 12121156 Hits 0 hit rate (%) 0 Total time (ms) : 4417851 Nodes searched : 1100151204 Nodes/second : 249024 Tested with 5,000 games match against master, 1 Thread, 128 MB Hash each, tc 40+0.4, which is almost equivalent to LTC in Fishtest on this machine. 3-, 4- and 5-men syzygy bases on SSD, 12-moves opening book to emphasize mid- and endgame. Score of SF-SyzygyC++ vs SF-Master: 633 - 617 - 3750 [0.502] 5000 ELO difference: 1 No functional change. --- src/endgame.cpp | 25 +- src/position.cpp | 38 +- src/position.h | 3 +- src/search.cpp | 5 +- src/syzygy/tbcore.cpp | 1378 ------------------------- src/syzygy/tbcore.h | 169 --- src/syzygy/tbprobe.cpp | 2227 ++++++++++++++++++++++++++++------------ src/syzygy/tbprobe.h | 66 +- src/uci.cpp | 2 + 9 files changed, 1652 insertions(+), 2261 deletions(-) delete mode 100644 src/syzygy/tbcore.cpp delete mode 100644 src/syzygy/tbcore.h diff --git a/src/endgame.cpp b/src/endgame.cpp index cbca34be..61811390 100644 --- a/src/endgame.cpp +++ b/src/endgame.cpp @@ -83,26 +83,6 @@ namespace { return sq; } - // Get the material key of Position out of the given endgame key code - // like "KBPKN". The trick here is to first forge an ad-hoc FEN string - // and then let a Position object do the work for us. - Key key(const string& code, Color c) { - - assert(code.length() > 0 && code.length() < 8); - assert(code[0] == 'K'); - - string sides[] = { code.substr(code.find('K', 1)), // Weak - code.substr(0, code.find('K', 1)) }; // Strong - - std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower); - - string fen = sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/8/8/" - + sides[1] + char(8 - sides[1].length() + '0') + " w - - 0 10"; - - StateInfo st; - return Position().set(fen, false, &st, nullptr).material_key(); - } - } // namespace @@ -132,8 +112,9 @@ Endgames::Endgames() { template void Endgames::add(const string& code) { - map()[key(code, WHITE)] = std::unique_ptr>(new Endgame(WHITE)); - map()[key(code, BLACK)] = std::unique_ptr>(new Endgame(BLACK)); + StateInfo st; + map()[Position().set(code, WHITE, &st).material_key()] = std::unique_ptr>(new Endgame(WHITE)); + map()[Position().set(code, BLACK, &st).material_key()] = std::unique_ptr>(new Endgame(BLACK)); } diff --git a/src/position.cpp b/src/position.cpp index c09a953b..647f2bba 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -32,6 +32,7 @@ #include "thread.h" #include "tt.h" #include "uci.h" +#include "syzygy/tbprobe.h" using std::string; @@ -85,7 +86,7 @@ PieceType min_attacker(const Bitboard*, Square, Bitboard, Bitboard&, Bitbo /// operator<<(Position) returns an ASCII representation of the position -std::ostream& operator<<(std::ostream& os, const Position& pos) { +std::ostream& operator<<(std::ostream& os, Position& pos) { os << "\n +---+---+---+---+---+---+---+---+\n"; @@ -98,11 +99,22 @@ std::ostream& operator<<(std::ostream& os, const Position& pos) { } os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase - << std::setfill('0') << std::setw(16) << pos.key() << std::dec << "\nCheckers: "; + << std::setfill('0') << std::setw(16) << pos.key() + << std::setfill(' ') << std::dec << "\nCheckers: "; for (Bitboard b = pos.checkers(); b; ) os << UCI::square(pop_lsb(&b)) << " "; + if ( int(Tablebases::MaxCardinality) >= popcount(pos.pieces()) + && !pos.can_castle(ANY_CASTLING)) + { + Tablebases::ProbeState s1, s2; + Tablebases::WDLScore wdl = Tablebases::probe_wdl(pos, &s1); + int dtz = Tablebases::probe_dtz(pos, &s2); + os << "\nTablebases WDL: " << std::setw(4) << wdl << " (" << s1 << ")" + << "\nTablebases DTZ: " << std::setw(4) << dtz << " (" << s2 << ")"; + } + return os; } @@ -357,6 +369,28 @@ void Position::set_state(StateInfo* si) const { } +/// Position::set() is an overload to initialize the position object with +/// the given endgame code string like "KBPKN". It is manily an helper to +/// get the material key out of an endgame code. Position is not playable, +/// indeed is even not guaranteed to be legal. + +Position& Position::set(const string& code, Color c, StateInfo* si) { + + assert(code.length() > 0 && code.length() < 8); + assert(code[0] == 'K'); + + string sides[] = { code.substr(code.find('K', 1)), // Weak + code.substr(0, code.find('K', 1)) }; // Strong + + std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower); + + string fenStr = sides[0] + char(8 - sides[0].length() + '0') + "/8/8/8/8/8/8/" + + sides[1] + char(8 - sides[1].length() + '0') + " w - - 0 10"; + + return set(fenStr, false, si, nullptr); +} + + /// Position::fen() returns a FEN representation of the position. In case of /// Chess960 the Shredder-FEN notation is used. This is mainly a debugging function. diff --git a/src/position.h b/src/position.h index 9aa4c445..94e73086 100644 --- a/src/position.h +++ b/src/position.h @@ -76,6 +76,7 @@ public: // FEN string input/output Position& set(const std::string& fenStr, bool isChess960, StateInfo* si, Thread* th); + Position& set(const std::string& code, Color c, StateInfo* si); const std::string fen() const; // Position representation @@ -188,7 +189,7 @@ private: bool chess960; }; -extern std::ostream& operator<<(std::ostream& os, const Position& pos); +extern std::ostream& operator<<(std::ostream& os, Position& pos); inline Color Position::side_to_move() const { return sideToMove; diff --git a/src/search.cpp b/src/search.cpp index 19749b64..9c3e17b6 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -664,9 +664,10 @@ namespace { && pos.rule50_count() == 0 && !pos.can_castle(ANY_CASTLING)) { - int found, v = Tablebases::probe_wdl(pos, &found); + TB::ProbeState err; + TB::WDLScore v = Tablebases::probe_wdl(pos, &err); - if (found) + if (err != TB::ProbeState::FAIL) { thisThread->tbHits++; diff --git a/src/syzygy/tbcore.cpp b/src/syzygy/tbcore.cpp deleted file mode 100644 index f45da953..00000000 --- a/src/syzygy/tbcore.cpp +++ /dev/null @@ -1,1378 +0,0 @@ -/* - 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 too much adaptation to add tablebase probing to - a particular engine, provided the engine is written in C or C++. -*/ - -#include -#include -#include -#include -#include -#include -#ifndef _WIN32 -#include -#include -#endif -#include "tbcore.h" - -#define TBMAX_PIECE 254 -#define TBMAX_PAWN 256 -#define HSHMAX 5 - -#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 += (ubyte)pcs[i]; - entry->symmetric = (key == key2); - entry->has_pawns = (pcs[TB_WPAWN] + pcs[TB_BPAWN] > 0); - if (entry->num > Tablebases::MaxCardinality) - Tablebases::MaxCardinality = entry->num; - - if (entry->has_pawns) { - struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry; - ptr->pawns[0] = (ubyte)pcs[TB_WPAWN]; - ptr->pawns[1] = (ubyte)pcs[TB_BPAWN]; - if (pcs[TB_BPAWN] > 0 - && (pcs[TB_WPAWN] == 0 || pcs[TB_BPAWN] < pcs[TB_WPAWN])) { - ptr->pawns[0] = (ubyte)pcs[TB_BPAWN]; - ptr->pawns[1] = (ubyte)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 = ubyte(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, "")) 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; - MaxCardinality = 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 signed 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 -}; - -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 } -}; - -static int binomial[5][64]; -static int pawnidx[5][24]; -static int pfactor[5][4]; - -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; - } -} - -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; -} - -// 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; - static int pivfac[] = { 31332, 28056, 462 }; - - n = 64 - norm[0]; - - f = 1; - for (i = norm[0], k = 0; i < num || k == order; k++) { - if (k == order) { - factor[0] = static_cast(f); - f *= pivfac[enc_type]; - } else { - factor[i] = static_cast(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] = static_cast(f); - f *= pfactor[norm[0] - 1][file]; - } else if (k == order2) { - factor[norm[0]] = static_cast(f); - f *= subfactor(norm[norm[0]], 48 - norm[0]); - } else { - factor[i] = static_cast(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] = ubyte(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] = ubyte(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] = ubyte(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] = ubyte(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] = ubyte(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] = ubyte(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] = ubyte(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] = ubyte(d->symlen[s1] + d->symlen[s2] + 1); - } - tmp[s] = 1; -} - -ushort ReadUshort(ubyte* d) { - return ushort(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)]; - - uint64 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] = static_cast(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] = static_cast(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 -static ubyte decompress_pairs(struct PairsData *d, uint64 idx) -{ - if (!d->idxbits) - return ubyte(d->min_len); - - uint32 mainidx = static_cast(idx >> d->idxbits); - int litidx = (idx & ((1ULL << d->idxbits) - 1)) - (1ULL << (d->idxbits - 1)); - uint32 block = *(uint32 *)(d->indextable + 6 * mainidx); - if (!LittleEndian) - block = BSWAP32(block); - - ushort idxOffset = *(ushort *)(d->indextable + 6 * mainidx + 4); - if (!LittleEndian) - idxOffset = ushort((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 = 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 += static_cast((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 = 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 deleted file mode 100644 index cdaf2aca..00000000 --- a/src/syzygy/tbcore.h +++ /dev/null @@ -1,169 +0,0 @@ -/* - Copyright (c) 2011-2013 Ronald de Man -*/ - -#ifndef TBCORE_H -#define TBCORE_H - -#ifndef _WIN32 -#include -#define SEP_CHAR ':' -#define FD int -#define FD_ERR -1 -#else -#include -#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 - -#ifndef _MSC_VER -#define BSWAP32(v) __builtin_bswap32(v) -#define BSWAP64(v) __builtin_bswap64(v) -#else -#define BSWAP32(v) _byteswap_ulong(v) -#define BSWAP64(v) _byteswap_uint64(v) -#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; -} -#ifndef _WIN32 -__attribute__((__may_alias__)) -#endif -; - -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 index 0281ccc8..43fc0f1c 100644 --- a/src/syzygy/tbprobe.cpp +++ b/src/syzygy/tbprobe.cpp @@ -1,560 +1,1399 @@ /* + Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (c) 2013 Ronald de Man - This file may be redistributed and/or modified without restrictions. + Copyright (C) 2016 Marco Costalba, Lucas Braesch - 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. -*/ + Stockfish is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. -#define NOMINMAX + Stockfish is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ #include +#include +#include +#include // For std::memset +#include +#include +#include +#include +#include +#include -#include "../position.h" -#include "../movegen.h" #include "../bitboard.h" +#include "../movegen.h" +#include "../position.h" #include "../search.h" +#include "../thread_win32.h" +#include "../types.h" #include "tbprobe.h" -#include "tbcore.h" -#include "tbcore.cpp" +#ifndef _WIN32 +#include +#include +#include +#include +#else +#define WIN32_LEAN_AND_MEAN +#define NOMINMAX +#include +#endif + +using namespace Tablebases; -namespace Zobrist { - extern Key psq[PIECE_NB][SQUARE_NB]; -} +int Tablebases::MaxCardinality; -int Tablebases::MaxCardinality = 0; +namespace { -// 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(pos.pieces(color, pt)); i > 0; i--) - *str++ = pchr[6 - pt]; - *str++ = 'v'; - color = ~color; - for (pt = KING; pt >= PAWN; --pt) - for (i = popcount(pos.pieces(color, pt)); i > 0; i--) - *str++ = pchr[6 - pt]; - *str++ = 0; -} +// 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 }; -// 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(pos.pieces(color, pt)); i > 0; i--) - key ^= Zobrist::psq[make_piece(WHITE, pt)][i - 1]; - color = ~color; - for (pt = PAWN; pt <= KING; ++pt) - for (i = popcount(pos.pieces(color, pt)); i > 0; i--) - key ^= Zobrist::psq[make_piece(BLACK, pt)][i - 1]; - - return key; -} +inline WDLScore operator-(WDLScore d) { return WDLScore(-int(d)); } +inline Square operator^=(Square& s, int i) { return s = Square(int(s) ^ i); } +inline Square operator^(Square s, int i) { return Square(int(s) ^ i); } -// 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[make_piece(WHITE, pt)][i]; - color ^= 8; - for (pt = PAWN; pt <= KING; ++pt) - for (i = 0; i < pcs[color + pt]; i++) - key ^= Zobrist::psq[make_piece(BLACK, pt)][i]; - - return key; +// DTZ tables don't store valid scores for moves that reset the rule50 counter +// like captures and pawn moves but we can easily recover the correct dtz of the +// previous move if we know the position's WDL score. +int dtz_before_zeroing(WDLScore wdl) { + return wdl == WDLWin ? 1 : + wdl == WDLCursedWin ? 101 : + wdl == WDLCursedLoss ? -101 : + wdl == WDLLoss ? -1 : 0; } -bool is_little_endian() { - union { - int i; - char c[sizeof(int)]; - } x; - x.i = 1; - return x.c[0] == 1; +// Return the sign of a number (-1, 0, 1) +template int sign_of(T val) { + return (T(0) < val) - (val < T(0)); } -static ubyte decompress_pairs(struct PairsData *d, uint64 idx) +// Numbers in little endian used by sparseIndex[] to point into blockLength[] +struct SparseEntry { + char block[4]; // Number of block + char offset[2]; // Offset within the block +}; + +static_assert(sizeof(SparseEntry) == 6, "SparseEntry must be 6 bytes"); + +typedef uint16_t Sym; // Huffman symbol + +struct LR { + enum Side { Left, Right, Value }; + + 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. + template + 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)); + } +}; + +static_assert(sizeof(LR) == 3, "LR tree entry must be 3 bytes"); + +const int TBPIECES = 6; + +struct PairsData { + int flags; + size_t sizeofBlock; // Block size in bytes + size_t span; // About every span values there is a SparseIndex[] entry + int blocksNum; // Number of blocks in the TB file + int maxSymLen; // Maximum length in bits of the Huffman symbols + int minSymLen; // Minimum length in bits of the Huffman symbols + Sym* lowestSym; // lowestSym[l] is the symbol of length l with the lowest value + LR* btree; // btree[sym] stores the left and right symbols that expand sym + uint16_t* blockLength; // Number of stored positions (minus one) for each block: 1..65536 + int blockLengthSize; // Size of blockLength[] table: padded so it's bigger than blocksNum + SparseEntry* sparseIndex; // Partial indices into blockLength[] + size_t sparseIndexSize; // Size of SparseIndex[] table + uint8_t* data; // Start of Huffman compressed data + std::vector base64; // base64[l - min_sym_len] is the 64bit-padded lowest symbol of length l + std::vector symlen; // Number of values (-1) represented by a given Huffman symbol: 1..256 + Piece pieces[TBPIECES]; // Position pieces: the order of pieces defines the groups + uint64_t groupIdx[TBPIECES+1]; // Start index used for the encoding of the group's pieces + int groupLen[TBPIECES+1]; // Number of pieces in a given group: KRKN -> (3, 1) +}; + +// Helper struct to avoid to manually define entry copy c'tor as we should +// because default one is not compatible with std::atomic_bool. +struct Atomic { + Atomic() = default; + Atomic(const Atomic& e) { ready = e.ready.load(); } // MSVC 2013 wants assignment within body + std::atomic_bool ready; +}; + +struct WDLEntry : public Atomic { + WDLEntry(const std::string& code); + ~WDLEntry(); + + void* baseAddress; + uint64_t mapping; + Key key; + Key key2; + int pieceCount; + bool hasPawns; + bool hasUniquePieces; + union { + struct { + PairsData* precomp; + } pieceTable[2]; // [wtm / btm] + + struct { + uint8_t pawnCount[2]; // [Lead color / other color] + struct { + PairsData* precomp; + } file[2][4]; // [wtm / btm][FILE_A..FILE_D] + } pawnTable; + }; +}; + +struct DTZEntry : public Atomic { + DTZEntry(const WDLEntry& wdl); + ~DTZEntry(); + + void* baseAddress; + uint64_t mapping; + Key key; + Key key2; + int pieceCount; + bool hasPawns; + bool hasUniquePieces; + union { + struct { + PairsData* precomp; + uint16_t map_idx[4]; // WDLWin, WDLLoss, WDLCursedWin, WDLCursedLoss + uint8_t* map; + } pieceTable; + + struct { + uint8_t pawnCount[2]; + struct { + PairsData* precomp; + uint16_t map_idx[4]; + } file[4]; + uint8_t* map; + } pawnTable; + }; +}; + +typedef decltype(WDLEntry::pieceTable) WDLPieceTable; +typedef decltype(DTZEntry::pieceTable) DTZPieceTable; +typedef decltype(WDLEntry::pawnTable ) WDLPawnTable; +typedef decltype(DTZEntry::pawnTable ) DTZPawnTable; + +auto item(WDLPieceTable& e, int stm, int ) -> decltype(e[stm])& { return e[stm]; } +auto item(DTZPieceTable& e, int , int ) -> decltype(e)& { return e; } +auto item(WDLPawnTable& e, int stm, int f) -> decltype(e.file[stm][f])& { return e.file[stm][f]; } +auto item(DTZPawnTable& e, int , int f) -> decltype(e.file[f])& { return e.file[f]; } + +template struct Ret { typedef int type; }; +template<> struct Ret { typedef WDLScore type; }; + +int MapPawns[SQUARE_NB]; +int MapB1H1H7[SQUARE_NB]; +int MapA1D1D4[SQUARE_NB]; +int MapKK[10][SQUARE_NB]; // [MapA1D1D4][SQUARE_NB] + +// Comparison function to sort leading pawns in ascending MapPawns[] order +bool pawns_comp(Square i, Square j) { return MapPawns[i] < MapPawns[j]; } +int off_A1H8(Square sq) { return int(rank_of(sq)) - file_of(sq); } + +const Value WDL_to_value[] = { + -VALUE_MATE + MAX_PLY + 1, + VALUE_DRAW - 2, + VALUE_DRAW, + VALUE_DRAW + 2, + VALUE_MATE - MAX_PLY - 1 +}; + +const std::string PieceToChar = " PNBRQK pnbrqk"; + +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] + +enum { BigEndian, LittleEndian }; + +template +inline void swap_byte(T& x) { - static const bool isLittleEndian = is_little_endian(); - return isLittleEndian ? decompress_pairs(d, idx) - : decompress_pairs(d, idx); + char tmp, *c = (char*)&x; + if (Half) // Fix a MSVC 2015 warning + for (int i = 0; i < Half; ++i) + tmp = c[i], c[i] = c[End - i], c[End - i] = tmp; } -// probe_wdl_table and probe_dtz_table require similar adaptations. -static int probe_wdl_table(Position& pos, int *success) +template T number(void* addr) { - 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[W_KING][0] ^ Zobrist::psq[B_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; + const union { uint32_t i; char c[4]; } Le = { 0x01020304 }; + const bool IsLittleEndian = (Le.c[0] == 4); + + T v = *((T*)addr); + if (LE != IsLittleEndian) + swap_byte(v); + return v; +} + +class HashTable { + + typedef std::pair EntryPair; + typedef std::pair Entry; + + static const int TBHASHBITS = 10; + static const int HSHMAX = 5; + + Entry hashTable[1 << TBHASHBITS][HSHMAX]; + + std::deque wdlTable; + std::deque dtzTable; + + void insert(Key key, WDLEntry* wdl, DTZEntry* dtz) { + Entry* entry = hashTable[key >> (64 - TBHASHBITS)]; + + for (int i = 0; i < HSHMAX; ++i, ++entry) + if (!entry->second.first || entry->first == key) { + *entry = std::make_pair(key, std::make_pair(wdl, dtz)); + return; + } + + std::cerr << "HSHMAX too low!" << std::endl; + exit(1); + } + +public: + template::value ? 0 : 1> + E* get(Key key) { + Entry* entry = hashTable[key >> (64 - TBHASHBITS)]; + + for (int i = 0; i < HSHMAX; ++i, ++entry) + if (entry->first == key) + return std::get(entry->second); + + return nullptr; } - 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. -#ifdef _MSC_VER - _ReadWriteBarrier(); + void clear() { + std::memset(hashTable, 0, sizeof(hashTable)); + wdlTable.clear(); + dtzTable.clear(); + } + size_t size() const { return wdlTable.size(); } + void insert(const std::vector& pieces); +}; + +HashTable EntryTable; + +class TBFile : public std::ifstream { + + std::string fname; + +public: + // Look for and open the file among the Paths directories where the .rtbw + // and .rtbz files can be found. Multiple directories are separated by ";" + // on Windows and by ":" on Unix-based operating systems. + // + // Example: + // C:\tb\wdl345;C:\tb\wdl6;D:\tb\dtz345;D:\tb\dtz6 + static std::string Paths; + + TBFile(const std::string& f) { + +#ifndef _WIN32 + const char SepChar = ':'; #else - __asm__ __volatile__ ("" ::: "memory"); + const char SepChar = ';'; #endif - ptr->ready = 1; + std::stringstream ss(Paths); + std::string path; + + while (std::getline(ss, path, SepChar)) { + fname = path + "/" + f; + std::ifstream::open(fname); + if (is_open()) + return; + } } - 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); + // Memory map the file and check it. File should be already open and will be + // closed after mapping. + uint8_t* map(void** baseAddress, uint64_t* mapping, const uint8_t* TB_MAGIC) { + + assert(is_open()); + + close(); // Need to re-open to get native file descriptor + +#ifndef _WIN32 + struct stat statbuf; + int fd = ::open(fname.c_str(), O_RDONLY); + fstat(fd, &statbuf); + *mapping = statbuf.st_size; + *baseAddress = mmap(nullptr, statbuf.st_size, PROT_READ, MAP_SHARED, fd, 0); + ::close(fd); + + if (*baseAddress == MAP_FAILED) { + std::cerr << "Could not mmap() " << fname << std::endl; + exit(1); + } +#else + HANDLE fd = CreateFile(fname.c_str(), GENERIC_READ, FILE_SHARE_READ, nullptr, + OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, nullptr); + DWORD size_high; + DWORD size_low = GetFileSize(fd, &size_high); + HANDLE mmap = CreateFileMapping(fd, nullptr, PAGE_READONLY, size_high, size_low, nullptr); + CloseHandle(fd); + + if (!mmap) { + std::cerr << "CreateFileMapping() failed" << std::endl; + exit(1); + } + + *mapping = (uint64_t)mmap; + *baseAddress = MapViewOfFile(mmap, FILE_MAP_READ, 0, 0, 0); + + if (!*baseAddress) { + std::cerr << "MapViewOfFile() failed, name = " << fname + << ", error = " << GetLastError() << std::endl; + exit(1); + } +#endif + uint8_t* data = (uint8_t*)*baseAddress; + + if ( *data++ != *TB_MAGIC++ + || *data++ != *TB_MAGIC++ + || *data++ != *TB_MAGIC++ + || *data++ != *TB_MAGIC) { + std::cerr << "Corrupted table in file " << fname << std::endl; + unmap(*baseAddress, *mapping); + *baseAddress = nullptr; + return nullptr; + } + + return data; } - } 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); + static void unmap(void* baseAddress, uint64_t mapping) { + +#ifndef _WIN32 + munmap(baseAddress, mapping); +#else + UnmapViewOfFile(baseAddress); + CloseHandle((HANDLE)mapping); +#endif } - 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); +}; + +std::string TBFile::Paths; + +WDLEntry::WDLEntry(const std::string& code) { + + StateInfo st; + Position pos; + + memset(this, 0, sizeof(WDLEntry)); + + ready = false; + key = pos.set(code, WHITE, &st).material_key(); + pieceCount = popcount(pos.pieces()); + hasPawns = pos.pieces(PAWN); + + for (Color c = WHITE; c <= BLACK; ++c) + for (PieceType pt = PAWN; pt < KING; ++pt) + if (popcount(pos.pieces(c, pt)) == 1) + hasUniquePieces = true; + + if (hasPawns) { + // Set the leading color. In case both sides have pawns the leading color + // is the side with less pawns because this leads to better compression. + bool c = !pos.count(BLACK) + || ( pos.count(WHITE) + && pos.count(BLACK) >= pos.count(WHITE)); + + pawnTable.pawnCount[0] = pos.count(c ? WHITE : BLACK); + pawnTable.pawnCount[1] = pos.count(c ? BLACK : WHITE); } - 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; + key2 = pos.set(code, BLACK, &st).material_key(); } -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)); +WDLEntry::~WDLEntry() { + + if (baseAddress) + TBFile::unmap(baseAddress, mapping); + + for (int i = 0; i < 2; ++i) + if (hasPawns) + for (File f = FILE_A; f <= FILE_D; ++f) + delete pawnTable.file[i][f].precomp; + else + delete pieceTable[i].precomp; +} + +DTZEntry::DTZEntry(const WDLEntry& wdl) { + + memset(this, 0, sizeof(DTZEntry)); + + ready = false; + key = wdl.key; + key2 = wdl.key2; + pieceCount = wdl.pieceCount; + hasPawns = wdl.hasPawns; + hasUniquePieces = wdl.hasUniquePieces; + + if (hasPawns) { + pawnTable.pawnCount[0] = wdl.pawnTable.pawnCount[0]; + pawnTable.pawnCount[1] = wdl.pawnTable.pawnCount[1]; } - } +} - ptr = DTZ_table[0].entry; - if (!ptr) { - *success = 0; - return 0; - } +DTZEntry::~DTZEntry() { + + if (baseAddress) + TBFile::unmap(baseAddress, mapping); + + if (hasPawns) + for (File f = FILE_A; f <= FILE_D; ++f) + delete pawnTable.file[f].precomp; + else + delete pieceTable.precomp; +} + +void HashTable::insert(const std::vector& pieces) { - 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); + std::string code; + + for (PieceType pt : pieces) + code += PieceToChar[pt]; + + TBFile file(code.insert(code.find('K', 1), "v") + ".rtbw"); // KRK -> KRvK + + if (!file.is_open()) + return; + + file.close(); + + MaxCardinality = std::max((int)pieces.size(), MaxCardinality); + + wdlTable.push_back(WDLEntry(code)); + dtzTable.push_back(DTZEntry(wdlTable.back())); + + insert(wdlTable.back().key , &wdlTable.back(), &dtzTable.back()); + insert(wdlTable.back().key2, &wdlTable.back(), &dtzTable.back()); +} + +// TB tables are compressed with canonical Huffman code. The compressed data is divided into +// blocks of size d->sizeofBlock, and each block stores a variable number of symbols. +// Each symbol represents either a WDL or a (remapped) DTZ value, or a pair of other symbols +// (recursively). If you keep expanding the symbols in a block, you end up with up to 65536 +// WDL or DTZ values. Each symbol represents up to 256 values and will correspond after +// Huffman coding to at least 1 bit. So a block of 32 bytes corresponds to at most +// 32 x 8 x 256 = 65536 values. This maximum is only reached for tables that consist mostly +// of draws or mostly of wins, but such tables are actually quite common. In principle, the +// blocks in WDL tables are 64 bytes long (and will be aligned on cache lines). But for +// mostly-draw or mostly-win tables this can leave many 64-byte blocks only half-filled, so +// in such cases blocks are 32 bytes long. The blocks of DTZ tables are up to 1024 bytes long. +// The generator picks the size that leads to the smallest table. The "book" of symbols and +// Huffman codes is the same for all blocks in the table. A non-symmetric pawnless TB file +// will have one table for wtm and one for btm, a TB file with pawns will have tables per +// file a,b,c,d also in this case one set for wtm and one for btm. +int decompress_pairs(PairsData* d, uint64_t idx) { + + // Special case where all table positions store the same value + if (d->flags & TBFlag::SingleValue) + return d->minSymLen; + + // First we need to locate the right block that stores the value at index "idx". + // Because each block n stores blockLength[n] + 1 values, the index i of the block + // that contains the value at position idx is: + // + // for (i = -1, sum = 0; sum <= idx; i++) + // sum += blockLength[i + 1] + 1; + // + // This can be slow, so we use SparseIndex[] populated with a set of SparseEntry that + // point to known indices into blockLength[]. Namely SparseIndex[k] is a SparseEntry + // that stores the blockLength[] index and the offset within that block of the value + // with index I(k), where: + // + // I(k) = k * d->span + d->span / 2 (1) + + // First step is to get the 'k' of the I(k) nearest to our idx, using defintion (1) + uint32_t k = idx / d->span; + + // Then we read the corresponding SparseIndex[] entry + uint32_t block = number(&d->sparseIndex[k].block); + int offset = number(&d->sparseIndex[k].offset); + + // Now compute the difference idx - I(k). From defintion of k we know that + // + // idx = k * d->span + idx % d->span (2) + // + // So from (1) and (2) we can compute idx - I(K): + int diff = idx % d->span - d->span / 2; + + // Sum the above to offset to find the offset corresponding to our idx + offset += diff; + + // Move to previous/next block, until we reach the correct block that contains idx, + // that is when 0 <= offset <= d->blockLength[block] + while (offset < 0) + offset += d->blockLength[--block] + 1; + + while (offset > d->blockLength[block]) + 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); + + // 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 + // is at the beginning of this 64 bits sequence. + uint64_t buf64 = number(ptr); ptr += 2; + int buf64Size = 64; + Sym sym; + + while (true) { + int len = 0; // This is the symbol length - d->min_sym_len + + // Now get the symbol length. For any symbol s64 of length l right-padded + // to 64 bits we know that d->base64[l-1] >= s64 >= d->base64[l] so we + // can find the symbol length iterating through base64[]. + while (buf64 < d->base64[len]) + ++len; + + // All the symbols of a given length are consecutive integers (numerical + // sequence property), so we can compute the offset of our symbol of + // length len, stored at the beginning of buf64. + sym = (buf64 - d->base64[len]) >> (64 - len - d->minSymLen); + + // Now add the value of the lowest symbol of length len to get our symbol + sym += number(&d->lowestSym[len]); + + // If our offset is within the number of values represented by symbol sym + // we are done... + if (offset < d->symlen[sym] + 1) + break; + + // ...otherwise update the offset and continue to iterate + offset -= d->symlen[sym] + 1; + len += d->minSymLen; // Get the real length + buf64 <<= len; // Consume the just processed symbol + buf64Size -= len; + + if (buf64Size <= 32) { // Refill the buffer + buf64Size += 32; + buf64 |= (uint64_t)number(ptr++) << (64 - buf64Size); + } } - } 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; + // Ok, now we have our symbol that expands into d->symlen[sym] + 1 symbols. + // We binary-search for our value recursively expanding into the left and + // right child symbols until we reach a leaf node where symlen[sym] + 1 == 1 + // that will store the value we need. + while (d->symlen[sym]) { + + Sym left = d->btree[sym].get(); + + // If a symbol contains 36 sub-symbols (d->symlen[sym] + 1 = 36) and + // expands in a pair (d->symlen[left] = 23, d->symlen[right] = 11), then + // we know that, for instance the ten-th value (offset = 10) will be on + // the left side because in Recursive Pairing child symbols are adjacent. + if (offset < d->symlen[left] + 1) + sym = left; + else { + offset -= d->symlen[left] + 1; + sym = d->btree[sym].get(); + } + } + + return d->btree[sym].get(); +} + +bool check_dtz_stm(WDLEntry*, int, File) { return true; } + +bool check_dtz_stm(DTZEntry* entry, int stm, File f) { + + int flags = entry->hasPawns ? entry->pawnTable.file[f].precomp->flags + : entry->pieceTable.precomp->flags; + + return (flags & TBFlag::STM) == stm + || ((entry->key == entry->key2) && !entry->hasPawns); +} + +// DTZ scores are sorted by frequency of occurrence and then assigned the +// values 0, 1, 2, ... in order of decreasing frequency. This is done for each +// of the four WDLScore values. The mapping information necessary to reconstruct +// the original values is stored in the TB file and read during map[] init. +WDLScore map_score(WDLEntry*, File, int value, WDLScore) { return WDLScore(value - 2); } + +int map_score(DTZEntry* entry, File f, int value, WDLScore wdl) { + + const int WDLMap[] = { 1, 3, 0, 2, 0 }; + + int flags = entry->hasPawns ? entry->pawnTable.file[f].precomp->flags + : entry->pieceTable.precomp->flags; + + uint8_t* map = entry->hasPawns ? entry->pawnTable.map + : entry->pieceTable.map; + + uint16_t* idx = entry->hasPawns ? entry->pawnTable.file[f].map_idx + : entry->pieceTable.map_idx; + if (flags & TBFlag::Mapped) + 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. + if ( (wdl == WDLWin && !(flags & TBFlag::WinPlies)) + || (wdl == WDLLoss && !(flags & TBFlag::LossPlies)) + || wdl == WDLCursedWin + || wdl == WDLCursedLoss) + value *= 2; + + return value + 1; +} + +// Compute a unique index out of a position and use it to probe the TB file. To +// encode k pieces of same type and color, first sort the pieces by square in +// ascending order s1 <= s2 <= ... <= sk then compute the unique index as: +// +// idx = Binomial[1][s1] + Binomial[2][s2] + ... + Binomial[k][sk] +// +template::type> +T do_probe_table(const Position& pos, Entry* entry, WDLScore wdl, ProbeState* result) { + + const bool IsWDL = std::is_same::value; + + Square squares[TBPIECES]; + Piece pieces[TBPIECES]; + uint64_t idx; + int next = 0, size = 0, leadPawnsCnt = 0; + PairsData* d; + Bitboard b, leadPawns = 0; + File tbFile = FILE_A; + + // A given TB entry like KRK has associated two material keys: KRvk and Kvkr. + // If both sides have the same pieces keys are equal. In this case TB tables + // only store the 'white to move' case, so if the position to lookup has black + // to move, we need to switch the color and flip the squares before to lookup. + bool symmetricBlackToMove = (entry->key == entry->key2 && pos.side_to_move()); + + // TB files are calculated for white as stronger side. For instance we have + // KRvK, not KvKR. A position where stronger side is white will have its + // material key == entry->key, otherwise we have to switch the color and + // flip the squares before to lookup. + bool blackStronger = (pos.material_key() != entry->key); + + int flipColor = (symmetricBlackToMove || blackStronger) * 8; + int flipSquares = (symmetricBlackToMove || blackStronger) * 070; + int stm = (symmetricBlackToMove || blackStronger) ^ pos.side_to_move(); + + // For pawns, TB files store 4 separate tables according if leading pawn is on + // file a, b, c or d after reordering. The leading pawn is the one with maximum + // MapPawns[] value, that is the one most toward the edges and with lowest rank. + if (entry->hasPawns) { + + // In all the 4 tables, pawns are at the beginning of the piece sequence and + // their color is the reference one. So we just pick the first one. + Piece pc = Piece(item(entry->pawnTable, 0, 0).precomp->pieces[0] ^ flipColor); + + assert(type_of(pc) == PAWN); + + leadPawns = b = pos.pieces(color_of(pc), PAWN); + while (b) + squares[size++] = pop_lsb(&b) ^ flipSquares; + + leadPawnsCnt = size; + + std::swap(squares[0], *std::max_element(squares, squares + leadPawnsCnt, pawns_comp)); + + tbFile = file_of(squares[0]); + if (tbFile > FILE_D) + tbFile = file_of(squares[0] ^ 7); // Horizontal flip: SQ_H1 -> SQ_A1 + + d = item(entry->pawnTable , stm, tbFile).precomp; + } else + d = item(entry->pieceTable, stm, tbFile).precomp; + + // DTZ tables are one-sided, i.e. they store positions only for white to + // move or only for black to move, so check for side to move to be stm, + // early exit otherwise. + if (!IsWDL && !check_dtz_stm(entry, stm, tbFile)) + return *result = CHANGE_STM, T(); + + // Now we are ready to get all the position pieces (but the lead pawns) and + // directly map them to the correct color and square. + b = pos.pieces() ^ leadPawns; + while (b) { + Square s = pop_lsb(&b); + squares[size] = s ^ flipSquares; + pieces[size++] = Piece(pos.piece_on(s) ^ flipColor); } - 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); + + // Then we reorder the pieces to have the same sequence as the one stored + // in precomp->pieces[i]: the sequence that ensures the best compression. + for (int i = leadPawnsCnt; i < size; ++i) + for (int j = i; j < size; ++j) + if (d->pieces[i] == pieces[j]) + { + std::swap(pieces[i], pieces[j]); + std::swap(squares[i], squares[j]); + break; + } + + // Now we map again the squares so that the square of the lead piece is in + // the triangle A1-D1-D4. + if (file_of(squares[0]) > FILE_D) + for (int i = 0; i < size; ++i) + squares[i] ^= 7; // Horizontal flip: SQ_H1 -> SQ_A1 + + // Encode leading pawns starting with the one with minimum MapPawns[] and + // proceeding in ascending order. + if (entry->hasPawns) { + idx = LeadPawnIdx[leadPawnsCnt][squares[0]]; + + std::sort(squares + 1, squares + leadPawnsCnt, pawns_comp); + + for (int i = 1; i < leadPawnsCnt; ++i) + idx += Binomial[i][MapPawns[squares[i]]]; + + goto encode_remaining; // With pawns we have finished special treatments } - 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; + + // In positions withouth pawns, we further flip the squares to ensure leading + // piece is below RANK_5. + if (rank_of(squares[0]) > RANK_4) + for (int i = 0; i < size; ++i) + squares[i] ^= 070; // Vertical flip: SQ_A8 -> SQ_A1 + + // Look for the first piece of the leading group not on the A1-D4 diagonal + // and ensure it is mapped below the diagonal. + for (int i = 0; i < d->groupLen[0]; ++i) { + if (!off_A1H8(squares[i])) + continue; + + if (off_A1H8(squares[i]) > 0) // A1-H8 diagonal flip: SQ_A3 -> SQ_C3 + for (int j = i; j < size; ++j) + squares[j] = Square(((squares[j] >> 3) | (squares[j] << 3)) & 63); + break; } - 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); + + // Encode the leading group. + // + // Suppose we have KRvK. Let's say the pieces are on square numbers wK, wR + // and bK (each 0...63). The simplest way to map this position to an index + // is like this: + // + // index = wK * 64 * 64 + wR * 64 + bK; + // + // But this way the TB is going to have 64*64*64 = 262144 positions, with + // lots of positions being equivalent (because they are mirrors of each + // other) and lots of positions being invalid (two pieces on one square, + // adjacent kings, etc.). + // Usually the first step is to take the wK and bK together. There are just + // 462 ways legal and not-mirrored ways to place the wK and bK on the board. + // Once we have placed the wK and bK, there are 62 squares left for the wR + // Mapping its square from 0..63 to available squares 0..61 can be done like: + // + // wR -= (wR > wK) + (wR > bK); + // + // In words: if wR "comes later" than wK, we deduct 1, and the same if wR + // "comes later" than bK. In case of two same pieces like KRRvK we want to + // place the two Rs "together". If we have 62 squares left, we can place two + // Rs "together" in 62 * 61 / 2 ways (we divide by 2 because rooks can be + // swapped and still get the same position.) + // + // In case we have at least 3 unique pieces (inlcuded kings) we encode them + // together. + if (entry->hasUniquePieces) { + + int adjust1 = squares[1] > squares[0]; + int adjust2 = (squares[2] > squares[0]) + (squares[2] > squares[1]); + + // First piece is below a1-h8 diagonal. MapA1D1D4[] maps the b1-d1-d3 + // triangle to 0...5. There are 63 squares for second piece and and 62 + // (mapped to 0...61) for the third. + if (off_A1H8(squares[0])) + idx = ( MapA1D1D4[squares[0]] * 63 + + (squares[1] - adjust1)) * 62 + + squares[2] - adjust2; + + // First piece is on a1-h8 diagonal, second below: map this occurence to + // 6 to differentiate from the above case, rank_of() maps a1-d4 diagonal + // to 0...3 and finally MapB1H1H7[] maps the b1-h1-h7 triangle to 0..27. + else if (off_A1H8(squares[1])) + idx = ( 6 * 63 + rank_of(squares[0]) * 28 + + MapB1H1H7[squares[1]]) * 62 + + squares[2] - adjust2; + + // First two pieces are on a1-h8 diagonal, third below + else if (off_A1H8(squares[2])) + idx = 6 * 63 * 62 + 4 * 28 * 62 + + rank_of(squares[0]) * 7 * 28 + + (rank_of(squares[1]) - adjust1) * 28 + + MapB1H1H7[squares[2]]; + + // All 3 pieces on the diagonal a1-h8 + else + idx = 6 * 63 * 62 + 4 * 28 * 62 + 4 * 7 * 28 + + rank_of(squares[0]) * 7 * 6 + + (rank_of(squares[1]) - adjust1) * 6 + + (rank_of(squares[2]) - adjust2); + } else + // We don't have at least 3 unique pieces, like in KRRvKBB, just map + // the kings. + idx = MapKK[MapA1D1D4[squares[0]]][squares[1]]; + +encode_remaining: + idx *= d->groupIdx[0]; + Square* groupSq = squares + d->groupLen[0]; + + // Encode remainig pawns then pieces according to square, in ascending order + bool remainingPawns = entry->hasPawns && entry->pawnTable.pawnCount[1]; + + while (d->groupLen[++next]) + { + std::sort(groupSq, groupSq + d->groupLen[next]); + uint64_t n = 0; + + // Map down a square if "comes later" than a square in the previous + // groups (similar to what done earlier for leading group pieces). + for (int i = 0; i < d->groupLen[next]; ++i) + { + auto f = [&](Square s) { return groupSq[i] > s; }; + auto adjust = std::count_if(squares, groupSq, f); + n += Binomial[i + 1][groupSq[i] - adjust - 8 * remainingPawns]; + } + + remainingPawns = false; + idx += n * d->groupIdx[next]; + groupSq += d->groupLen[next]; } - 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]; + // Now that we have the index, decompress the pair and get the score + return map_score(entry, tbFile, decompress_pairs(d, idx), wdl); +} - if (!(entry->flags[f] & pa_flags[wdl + 2]) || (wdl & 1)) - res *= 2; - } +// Group together pieces that will be encoded together. The general rule is that +// a group contains pieces of same type and color. The exception is the leading +// group that, in case of positions withouth pawns, can be formed by 3 different +// pieces (default) or by the king pair when there is not a unique piece apart +// from the kings. When there are pawns, pawns are always first in pieces[]. +// +// As example KRKN -> KRK + N, KNNK -> KK + NN, KPPKP -> P + PP + K + K +// +// The actual grouping depends on the TB generator and can be inferred from the +// sequence of pieces in piece[] array. +template +void set_groups(T& e, PairsData* d, int order[], File f) { + + int n = 0, firstLen = e.hasPawns ? 0 : e.hasUniquePieces ? 3 : 2; + d->groupLen[n] = 1; + + // Number of pieces per group is stored in groupLen[], for instance in KRKN + // the encoder will default on '111', so groupLen[] will be (3, 1). + for (int i = 1; i < e.pieceCount; ++i) + if (--firstLen > 0 || d->pieces[i] == d->pieces[i - 1]) + d->groupLen[n]++; + else + d->groupLen[++n] = 1; + + d->groupLen[++n] = 0; // Zero-terminated + + // The sequence in pieces[] defines the groups, but not the order in which + // they are encoded. If the pieces in a group g can be combined on the board + // in N(g) different ways, then the position encoding will be of the form: + // + // g1 * N(g2) * N(g3) + g2 * N(g3) + g3 + // + // This ensures unique encoding for the whole position. The order of the + // groups is a per-table parameter and could not follow the canonical leading + // pawns/pieces -> remainig pawns -> remaining pieces. In particular the + // first group is at order[0] position and the remaining pawns, when present, + // are at order[1] position. + bool pp = e.hasPawns && e.pawnTable.pawnCount[1]; // Pawns on both sides + int next = pp ? 2 : 1; + int freeSquares = 64 - d->groupLen[0] - (pp ? d->groupLen[1] : 0); + uint64_t idx = 1; + + for (int k = 0; next < n || k == order[0] || k == order[1]; ++k) + if (k == order[0]) // Leading pawns or pieces + { + d->groupIdx[0] = idx; + idx *= e.hasPawns ? LeadPawnsSize[d->groupLen[0]][f] + : e.hasUniquePieces ? 31332 : 462; + } + else if (k == order[1]) // Remaining pawns + { + d->groupIdx[1] = idx; + idx *= Binomial[d->groupLen[1]][48 - d->groupLen[0]]; + } + else // Remainig pieces + { + d->groupIdx[next] = idx; + idx *= Binomial[d->groupLen[next]][freeSquares]; + freeSquares -= d->groupLen[next++]; + } - return res; + d->groupIdx[n] = idx; } -// 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)); +// In Recursive Pairing each symbol represents a pair of childern symbols. So +// read d->btree[] symbols data and expand each one in his left and right child +// symbol until reaching the leafs that represent the symbol value. +uint8_t set_symlen(PairsData* d, Sym s, std::vector& visited) { + + visited[s] = true; // We can set it now because tree is acyclic + Sym sr = d->btree[s].get(); + + if (sr == 0xFFF) + return 0; + + Sym sl = d->btree[s].get(); + + if (!visited[sl]) + d->symlen[sl] = set_symlen(d, sl, visited); + + if (!visited[sr]) + d->symlen[sr] = set_symlen(d, sr, visited); + + return d->symlen[sl] + d->symlen[sr] + 1; +} + +uint8_t* set_sizes(PairsData* d, uint8_t* data) { + + d->flags = *data++; + + if (d->flags & TBFlag::SingleValue) { + d->blocksNum = d->span = + d->blockLengthSize = d->sparseIndexSize = 0; // Broken MSVC zero-init + d->minSymLen = *data++; // Here we store the single value + return data; + } + + // groupLen[] is a zero-terminated list of group lengths, the last groupIdx[] + // element stores the biggest index that is the tb size. + uint64_t tbSize = d->groupIdx[std::find(d->groupLen, d->groupLen + 7, 0) - d->groupLen]; + + d->sizeofBlock = 1ULL << *data++; + d->span = 1ULL << *data++; + d->sparseIndexSize = (tbSize + d->span - 1) / d->span; // Round up + int padding = number(data++); + d->blocksNum = number(data); data += sizeof(uint32_t); + d->blockLengthSize = d->blocksNum + padding; // Padded to ensure SparseIndex[] + // does not point out of range. + d->maxSymLen = *data++; + d->minSymLen = *data++; + d->lowestSym = (Sym*)data; + d->base64.resize(d->maxSymLen - d->minSymLen + 1); + + // The canonical code is ordered such that longer symbols (in terms of + // the number of bits of their Huffman code) have lower numeric value, + // so that d->lowestSym[i] >= d->lowestSym[i+1] (when read as LittleEndian). + // Starting from this we compute a base64[] table indexed by symbol length + // and containing 64 bit values so that d->base64[i] >= d->base64[i+1]. + // See http://www.eecs.harvard.edu/~michaelm/E210/huffman.pdf + for (int i = d->base64.size() - 2; i >= 0; --i) { + d->base64[i] = (d->base64[i + 1] + number(&d->lowestSym[i]) + - number(&d->lowestSym[i + 1])) / 2; + + assert(d->base64[i] * 2 >= d->base64[i+1]); } - } - return extra; + // Now left-shift by an amount so that d->base64[i] gets shifted 1 bit more + // than d->base64[i+1] and given the above assert condition, we ensure that + // d->base64[i] >= d->base64[i+1]. Moreover for any symbol s64 of length i + // and right-padded to 64 bits holds d->base64[i-1] >= s64 >= d->base64[i]. + for (size_t i = 0; i < d->base64.size(); ++i) + d->base64[i] <<= 64 - i - d->minSymLen; // Right-padding to 64 bits + + data += d->base64.size() * sizeof(Sym); + d->symlen.resize(number(data)); data += sizeof(uint16_t); + d->btree = (LR*)data; + + // The comrpession scheme used is "Recursive Pairing", that replaces the most + // frequent adjacent pair of symbols in the source message by a new symbol, + // reevaluating the frequencies of all of the symbol pairs with respect to + // the extended alphabet, and then repeating the process. + // See http://www.larsson.dogma.net/dcc99.pdf + std::vector visited(d->symlen.size()); + + for (Sym sym = 0; sym < d->symlen.size(); ++sym) + if (!visited[sym]) + d->symlen[sym] = set_symlen(d, sym, visited); + + return data + d->symlen.size() * sizeof(LR) + (d->symlen.size() & 1); } -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(pos, stack); - // Since underpromotion captures are not included, we need to add them. - end = add_underprom_caps(pos, stack, end); - } else - end = generate(pos, stack); - - for (moves = stack; moves < end; moves++) { - Move capture = moves->move; - if (!pos.capture(capture) || type_of(capture) == ENPASSANT - || !pos.legal(capture)) - continue; - pos.do_move(capture, st, pos.gives_check(capture)); - 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; +template +uint8_t* set_dtz_map(WDLEntry&, T&, uint8_t*, File) { return nullptr; } + +template +uint8_t* set_dtz_map(DTZEntry&, T& p, uint8_t* data, File maxFile) { + + p.map = data; + + for (File f = FILE_A; f <= maxFile; ++f) { + if (item(p, 0, f).precomp->flags & TBFlag::Mapped) + for (int i = 0; i < 4; ++i) { // Sequence like 3,x,x,x,1,x,0,2,x,x + item(p, 0, f).map_idx[i] = (uint16_t)(data - p.map + 1); + data += *data + 1; + } } - } - 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; - } + return data += (uintptr_t)data & 1; // Word alignment } -// 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; +template +void do_init(Entry& e, T& p, uint8_t* data) { - *success = 1; - v = probe_ab(pos, -2, 2, success); + const bool IsWDL = std::is_same::value; - // 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(pos, stack); - else - end = generate(pos, stack); - - for (moves = stack; moves < end; moves++) { - Move capture = moves->move; - if (type_of(capture) != ENPASSANT - || !pos.legal(capture)) - continue; - pos.do_move(capture, st, pos.gives_check(capture)); - 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)) break; - } - if (moves == end && !pos.checkers()) { - end = generate(pos, end); - for (; moves < end; moves++) { - Move move = moves->move; - if (pos.legal(move)) - break; - } - } - // If not, then we are forced to play the losing ep capture. - if (moves == end) - v = v1; + PairsData* d; + + enum { Split = 1, HasPawns = 2 }; + + uint8_t flags = *data++; + + assert(e.hasPawns == !!(flags & HasPawns)); + assert((e.key != e.key2) == !!(flags & Split)); + + const int Sides = IsWDL && (e.key != e.key2) ? 2 : 1; + const File MaxFile = e.hasPawns ? FILE_D : FILE_A; + + bool pp = e.hasPawns && e.pawnTable.pawnCount[1]; // Pawns on both sides + + assert(!pp || e.pawnTable.pawnCount[0]); + + for (File f = FILE_A; f <= MaxFile; ++f) { + + for (int i = 0; i < Sides; i++) + item(p, i, f).precomp = new PairsData(); + + int order[][2] = { { *data & 0xF, pp ? *(data + 1) & 0xF : 0xF }, + { *data >> 4, pp ? *(data + 1) >> 4 : 0xF } }; + data += 1 + pp; + + for (int k = 0; k < e.pieceCount; ++k, ++data) + for (int i = 0; i < Sides; i++) + item(p, i, f).precomp->pieces[k] = Piece(i ? *data >> 4 : *data & 0xF); + + for (int i = 0; i < Sides; ++i) + set_groups(e, item(p, i, f).precomp, order[i], f); } - } - return v; + data += (uintptr_t)data & 1; // Word alignment + + for (File f = FILE_A; f <= MaxFile; ++f) + for (int i = 0; i < Sides; i++) + data = set_sizes(item(p, i, f).precomp, data); + + if (!IsWDL) + data = set_dtz_map(e, p, data, MaxFile); + + for (File f = FILE_A; f <= MaxFile; ++f) + for (int i = 0; i < Sides; i++) { + (d = item(p, i, f).precomp)->sparseIndex = (SparseEntry*)data; + data += d->sparseIndexSize * sizeof(SparseEntry) ; + } + + for (File f = FILE_A; f <= MaxFile; ++f) + for (int i = 0; i < Sides; i++) { + (d = item(p, i, f).precomp)->blockLength = (uint16_t*)data; + data += d->blockLengthSize * sizeof(uint16_t); + } + + for (File f = FILE_A; f <= MaxFile; ++f) + for (int i = 0; i < Sides; i++) { + data = (uint8_t*)(((uintptr_t)data + 0x3F) & ~0x3F); // 64 byte alignment + (d = item(p, i, f).precomp)->data = data; + data += d->blocksNum * d->sizeofBlock; + } } -// 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; +template +void* init(Entry& e, const Position& pos) { - wdl = probe_ab(pos, -2, 2, success); - if (*success == 0) return 0; + const bool IsWDL = std::is_same::value; - if (wdl == 0) return 0; + static Mutex mutex; - if (*success == 2) - return wdl == 2 ? 1 : 101; + // Avoid a thread reads 'ready' == true while another is still in do_init(), + // this could happen due to compiler reordering. + if (e.ready.load(std::memory_order_acquire)) + return e.baseAddress; - ExtMove stack[192]; - ExtMove *moves, *end = NULL; - StateInfo st; + std::unique_lock lk(mutex); - if (wdl > 0) { - // Generate at least all legal non-capturing pawn moves - // including non-capturing promotions. - if (!pos.checkers()) - end = generate(pos, stack); - else - end = generate(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)) - continue; - pos.do_move(move, st, pos.gives_check(move)); - int v = -Tablebases::probe_wdl(pos, success); - pos.undo_move(move); - if (*success == 0) return 0; - if (v == wdl) - return v == 2 ? 1 : 101; + if (e.ready.load(std::memory_order_relaxed)) // Recheck under lock + return e.baseAddress; + + // Pieces strings in decreasing order for each color, like ("KPP","KR") + std::string fname, w, b; + for (PieceType pt = KING; pt >= PAWN; --pt) { + w += std::string(popcount(pos.pieces(WHITE, pt)), PieceToChar[pt]); + b += std::string(popcount(pos.pieces(BLACK, pt)), PieceToChar[pt]); } - } - dtz = 1 + probe_dtz_table(pos, wdl, success); - if (*success >= 0) { - if (wdl & 1) dtz += 100; - return wdl >= 0 ? dtz : -dtz; - } + const uint8_t TB_MAGIC[][4] = { { 0xD7, 0x66, 0x0C, 0xA5 }, + { 0x71, 0xE8, 0x23, 0x5D } }; + + fname = (e.key == pos.material_key() ? w + 'v' + b : b + 'v' + w) + + (IsWDL ? ".rtbw" : ".rtbz"); + + uint8_t* data = TBFile(fname).map(&e.baseAddress, &e.mapping, TB_MAGIC[IsWDL]); + if (data) + e.hasPawns ? do_init(e, e.pawnTable, data) : do_init(e, e.pieceTable, data); + + e.ready.store(true, std::memory_order_release); + return e.baseAddress; +} + +template::type> +T probe_table(const Position& pos, ProbeState* result, WDLScore wdl = WDLDraw) { + + if (!(pos.pieces() ^ pos.pieces(KING))) + return T(WDLDraw); // KvK + + E* entry = EntryTable.get(pos.material_key()); + + if (!entry || !init(*entry, pos)) + return *result = FAIL, T(); + + return do_probe_table(pos, entry, wdl, result); +} - 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)) - continue; - pos.do_move(move, st, pos.gives_check(move)); - 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; +// For a position where the side to move has a winning capture it is not necessary +// to store a winning value so the generator treats such positions as "don't cares" +// and tries to assign to it a value that improves the compression ratio. Similarly, +// if the side to move has a drawing capture, then the position is at least drawn. +// If the position is won, then the TB needs to store a win value. But if the +// position is drawn, the TB may store a loss value if that is better for compression. +// All of this means that during probing, the engine must look at captures and probe +// their results and must probe the position itself. The "best" result of these +// probes is the correct result for the position. +// DTZ table don't store values when a following move is a zeroing winning move +// (winning capture or winning pawn move). Also DTZ store wrong values for positions +// where the best move is an ep-move (even if losing). So in all these cases set +// the state to ZEROING_BEST_MOVE. +template +WDLScore search(Position& pos, ProbeState* result) { + + WDLScore value, bestValue = WDLLoss; + StateInfo st; + + auto moveList = MoveList(pos); + size_t totalCount = moveList.size(), moveCount = 0; + + for (const Move& move : moveList) + { + if ( !pos.capture(move) + && (!CheckZeroingMoves || type_of(pos.moved_piece(move)) != PAWN)) + continue; + + moveCount++; + + pos.do_move(move, st, pos.gives_check(move)); + value = -search(pos, result); + pos.undo_move(move); + + if (*result == FAIL) + return WDLDraw; + + if (value > bestValue) + { + bestValue = value; + + if (value >= WDLWin) + { + *result = ZEROING_BEST_MOVE; // Winning DTZ-zeroing move + return value; + } + } } - return best; - } else { - int best = -1; - if (!pos.checkers()) - end = generate(pos, stack); + + // In case we have already searched all the legal moves we don't have to probe + // the TB because the stored score could be wrong. For instance TB tables + // do not contain information on position with ep rights, so in this case + // the result of probe_wdl_table is wrong. Also in case of only capture + // moves, for instance here 4K3/4q3/6p1/2k5/6p1/8/8/8 w - - 0 7, we have to + // return with ZEROING_BEST_MOVE set. + bool noMoreMoves = (moveCount && moveCount == totalCount); + + if (noMoreMoves) + value = bestValue; else - end = generate(pos, stack); - for (moves = stack; moves < end; moves++) { - int v; - Move move = moves->move; - if (!pos.legal(move)) - continue; - pos.do_move(move, st, pos.gives_check(move)); - if (st.rule50 == 0) { - if (wdl == -2) v = -1; - else { - v = probe_ab(pos, 1, 2, success); - v = (v == 2) ? 0 : -101; + { + value = probe_table(pos, result); + + if (*result == FAIL) + return WDLDraw; + } + + // DTZ stores a "don't care" value if bestValue is a win + if (bestValue >= value) + return *result = ( bestValue > WDLDraw + || noMoreMoves ? ZEROING_BEST_MOVE : OK), bestValue; + + return *result = OK, value; +} + +} // namespace + +void Tablebases::init(const std::string& paths) { + + EntryTable.clear(); + MaxCardinality = 0; + TBFile::Paths = paths; + + if (paths.empty() || paths == "") + return; + + // MapB1H1H7[] encodes a square below a1-h8 diagonal to 0..27 + int code = 0; + for (Square s = SQ_A1; s <= SQ_H8; ++s) + if (off_A1H8(s) < 0) + MapB1H1H7[s] = code++; + + // MapA1D1D4[] encodes a square in the a1-d1-d4 triangle to 0..9 + std::vector diagonal; + code = 0; + for (Square s = SQ_A1; s <= SQ_D4; ++s) + if (off_A1H8(s) < 0 && file_of(s) <= FILE_D) + MapA1D1D4[s] = code++; + + else if (!off_A1H8(s) && file_of(s) <= FILE_D) + diagonal.push_back(s); + + // Diagonal squares are encoded as last ones + for (auto s : diagonal) + MapA1D1D4[s] = code++; + + // MapKK[] encodes all the 461 possible legal positions of two kings where + // the first is in the a1-d1-d4 triangle. If the first king is on the a1-d4 + // diagonal, the other one shall not to be above the a1-h8 diagonal. + std::vector> bothOnDiagonal; + code = 0; + for (int idx = 0; idx < 10; idx++) + for (Square s1 = SQ_A1; s1 <= SQ_D4; ++s1) + if (MapA1D1D4[s1] == idx && (idx || s1 == SQ_B1)) // SQ_B1 is mapped to 0 + for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2) + if ((StepAttacksBB[KING][s1] | s1) & s2) + continue; // Illegal position + + else if (!off_A1H8(s1) && off_A1H8(s2) > 0) + continue; // First on diagonal, second above + + else if (!off_A1H8(s1) && !off_A1H8(s2)) + bothOnDiagonal.push_back(std::make_pair(idx, s2)); + + else + MapKK[idx][s2] = code++; + + // Legal positions with both kings on diagonal are encoded as last ones + for (auto p : bothOnDiagonal) + MapKK[p.first][p.second] = code++; + + // Binomial[] stores the Binomial Coefficents using Pascal rule. There + // are Binomial[k][n] ways to choose k elements from a set of n elements. + Binomial[0][0] = 1; + + for (int n = 1; n < 64; n++) // Squares + for (int k = 0; k < 6 && k <= n; ++k) // Pieces + Binomial[k][n] = (k > 0 ? Binomial[k - 1][n - 1] : 0) + + (k < n ? Binomial[k ][n - 1] : 0); + + // MapPawns[s] encodes squares a2-h7 to 0..47. This is the number of possible + // available squares when the leading one is in 's'. Moreover the pawn with + // highest MapPawns[] is the leading pawn, the one nearest the edge and, + // 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) + for (File f = FILE_A; f <= FILE_D; ++f) + { + // Restart the index at every file because TB table is splitted + // by file, so we can reuse the same index for different files. + int idx = 0; + + // Sum all possible combinations for a given file, starting with + // the leading pawn on rank 2 and increasing the rank. + for (Rank r = RANK_2; r <= RANK_7; ++r) + { + Square sq = make_square(f, r); + + // Compute MapPawns[] at first pass. + // If sq is the leading pawn square, any other pawn cannot be + // below or more toward the edge of sq. There are 47 available + // squares when sq = a2 and reduced by 2 for any rank increase + // due to mirroring: sq == a3 -> no a2, h2, so MapPawns[a3] = 45 + if (leadPawnsCnt == 1) + { + MapPawns[sq] = availableSquares--; + MapPawns[sq ^ 7] = availableSquares--; // Horizontal flip + } + LeadPawnIdx[leadPawnsCnt][sq] = idx; + idx += Binomial[leadPawnsCnt - 1][MapPawns[sq]]; + } + // After a file is traversed, store the cumulated per-file index + LeadPawnsSize[leadPawnsCnt][f] = idx; + } + + for (PieceType p1 = PAWN; p1 < KING; ++p1) { + EntryTable.insert({KING, p1, KING}); + + for (PieceType p2 = PAWN; p2 <= p1; ++p2) { + EntryTable.insert({KING, p1, p2, KING}); + EntryTable.insert({KING, p1, KING, p2}); + + for (PieceType p3 = PAWN; p3 < KING; ++p3) + EntryTable.insert({KING, p1, p2, KING, p3}); + + for (PieceType p3 = PAWN; p3 <= p2; ++p3) { + EntryTable.insert({KING, p1, p2, p3, KING}); + + for (PieceType p4 = PAWN; p4 <= p3; ++p4) + EntryTable.insert({KING, p1, p2, p3, p4, KING}); + + for (PieceType p4 = PAWN; p4 < KING; ++p4) + EntryTable.insert({KING, p1, p2, p3, KING, p4}); + } + + for (PieceType p3 = PAWN; p3 <= p1; ++p3) + for (PieceType p4 = PAWN; p4 <= (p1 == p3 ? p2 : p3); ++p4) + EntryTable.insert({KING, p1, p2, KING, p3, p4}); } - } else { - v = -Tablebases::probe_dtz(pos, success) - 1; - } - pos.undo_move(move); - if (*success == 0) return 0; - if (v < best) - best = v; } - return best; - } + + sync_cout << "info string Found " << EntryTable.size() << " tablebases" << sync_endl; } -static int wdl_to_dtz[] = { - -1, -101, 0, 101, 1 -}; +// Probe the WDL table for a particular position. +// If *result != FAIL, 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 +WDLScore Tablebases::probe_wdl(Position& pos, ProbeState* result) { + + *result = OK; + return search(pos, result); +} // Probe the DTZ table for a particular position. -// If *success != 0, the probe was successful. +// If *result != FAIL, 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) @@ -578,103 +1417,90 @@ static int wdl_to_dtz[] = { // // 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); +int Tablebases::probe_dtz(Position& pos, ProbeState* result) { - 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(pos, stack); - else - end = generate(pos, stack); - - for (moves = stack; moves < end; moves++) { - Move capture = moves->move; - if (type_of(capture) != ENPASSANT - || !pos.legal(capture)) - continue; - pos.do_move(capture, st, pos.gives_check(capture)); - 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)) break; - } - if (moves == end && !pos.checkers()) { - end = generate(pos, end); - for (; moves < end; moves++) { - Move move = moves->move; - if (pos.legal(move)) - break; - } - } - if (moves == end) - v = v1; + *result = OK; + WDLScore wdl = search(pos, result); + + if (*result == FAIL || wdl == WDLDraw) // DTZ tables don't store draws + return 0; + + // DTZ stores a 'don't care' value in this case, or even a plain wrong + // one as in case the best move is a losing ep, so it cannot be probed. + if (*result == ZEROING_BEST_MOVE) + return dtz_before_zeroing(wdl); + + int dtz = probe_table(pos, result, wdl); + + if (*result == FAIL) + return 0; + + if (*result != CHANGE_STM) + return (dtz + 100 * (wdl == WDLCursedLoss || wdl == WDLCursedWin)) * sign_of(wdl); + + // DTZ stores results for the other side, so we need to do a 1-ply search and + // find the winning move that minimizes DTZ. + StateInfo st; + int minDTZ = 0xFFFF; + + for (const Move& move : MoveList(pos)) + { + bool zeroing = pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN; + + pos.do_move(move, st, pos.gives_check(move)); + + // For zeroing moves we want the dtz of the move _before_ doing it, + // otherwise we will get the dtz of the next move sequence. Search the + // position after the move to get the score sign (because even in a + // winning position we could make a losing capture or going for a draw). + dtz = zeroing ? -dtz_before_zeroing(search(pos, result)) + : -probe_dtz(pos, result); + + pos.undo_move(move); + + if (*result == FAIL) + return 0; + + // Convert result from 1-ply search. Zeroing moves are already accounted + // by dtz_before_zeroing() that returns the DTZ of the previous move. + if (!zeroing) + dtz += sign_of(dtz); + + // Skip the draws and if we are winning only pick positive dtz + if (dtz < minDTZ && sign_of(dtz) == sign_of(wdl)) + minDTZ = dtz; } - } - return v; + // Special handle a mate position, when there are no legal moves, in this + // case return value is somewhat arbitrary, so stick to the original TB code + // that returns -1 in this case. + return minDTZ == 0xFFFF ? -1 : minDTZ; } // 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; - } -} + while (1) { + int i = 4, e = std::min(st->rule50, st->pliesFromNull); -static Value wdl_to_Value[5] = { - -VALUE_MATE + MAX_PLY + 1, - VALUE_DRAW - 2, - VALUE_DRAW, - VALUE_DRAW + 2, - VALUE_MATE - MAX_PLY - 1 -}; + 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; + } +} // 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 @@ -684,103 +1510,128 @@ static Value wdl_to_Value[5] = { // no moves were filtered out. bool Tablebases::root_probe(Position& pos, Search::RootMoves& rootMoves, Value& score) { - int success; - - int dtz = probe_dtz(pos, &success); - if (!success) return false; - - StateInfo st; - - // Probe each move. - for (size_t i = 0; i < rootMoves.size(); i++) { - Move move = rootMoves[i].pv[0]; - pos.do_move(move, st, pos.gives_check(move)); - int v = 0; - if (pos.checkers() && dtz > 0) { - ExtMove s[192]; - if (generate(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; - rootMoves[i].score = (Value)v; - } + ProbeState result; + int dtz = probe_dtz(pos, &result); - // 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. - score = 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) - score = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200); - else if (wdl == -1 && dtz >= -100) - score = -(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 < rootMoves.size(); i++) { - int v = 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 < rootMoves.size(); i++) { - int v = rootMoves[i].score; - if (v > 0 && v <= max) - rootMoves[j++] = rootMoves[i]; - } - } else if (dtz < 0) { // losing (or 50-move rule draw) - int best = 0; - for (size_t i = 0; i < rootMoves.size(); i++) { - int v = 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 < rootMoves.size(); i++) { - if (rootMoves[i].score == best) - rootMoves[j++] = rootMoves[i]; + if (result == FAIL) + return false; + + StateInfo st; + + // Probe each move + for (size_t i = 0; i < rootMoves.size(); ++i) { + Move move = rootMoves[i].pv[0]; + pos.do_move(move, st, pos.gives_check(move)); + int v = 0; + + if (pos.checkers() && dtz > 0) { + ExtMove s[MAX_MOVES]; + + if (generate(pos, s) == s) + v = 1; + } + + if (!v) { + if (st.rule50 != 0) { + v = -probe_dtz(pos, &result); + + if (v > 0) + ++v; + else if (v < 0) + --v; + } else { + v = -probe_wdl(pos, &result); + v = dtz_before_zeroing(WDLScore(v)); + } + } + + pos.undo_move(move); + + if (result == FAIL) + return false; + + rootMoves[i].score = (Value)v; } - } else { // drawing - // Try all moves that preserve the draw. - for (size_t i = 0; i < rootMoves.size(); i++) { - if (rootMoves[i].score == 0) - rootMoves[j++] = rootMoves[i]; + + // 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. + score = 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) + score = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200); + else if (wdl == -1 && dtz >= -100) + score = -(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 < rootMoves.size(); ++i) { + int v = 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 < rootMoves.size(); ++i) { + int v = rootMoves[i].score; + + if (v > 0 && v <= max) + rootMoves[j++] = rootMoves[i]; + } + } else if (dtz < 0) { // losing (or 50-move rule draw) + int best = 0; + + for (size_t i = 0; i < rootMoves.size(); ++i) { + int v = 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 < rootMoves.size(); ++i) { + if (rootMoves[i].score == best) + rootMoves[j++] = rootMoves[i]; + } + } else { // drawing + // Try all moves that preserve the draw. + for (size_t i = 0; i < rootMoves.size(); ++i) { + if (rootMoves[i].score == 0) + rootMoves[j++] = rootMoves[i]; + } } - } - rootMoves.resize(j, Search::RootMove(MOVE_NONE)); - return true; + 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. @@ -790,35 +1641,43 @@ bool Tablebases::root_probe(Position& pos, Search::RootMoves& rootMoves, Value& // no moves were filtered out. bool Tablebases::root_probe_wdl(Position& pos, Search::RootMoves& rootMoves, Value& score) { - int success; - - int wdl = Tablebases::probe_wdl(pos, &success); - if (!success) return false; - score = wdl_to_Value[wdl + 2]; - - StateInfo st; - - int best = -2; - - // Probe each move. - for (size_t i = 0; i < rootMoves.size(); i++) { - Move move = rootMoves[i].pv[0]; - pos.do_move(move, st, pos.gives_check(move)); - int v = -Tablebases::probe_wdl(pos, &success); - pos.undo_move(move); - if (!success) return false; - rootMoves[i].score = (Value)v; - if (v > best) - best = v; - } + ProbeState result; - size_t j = 0; - for (size_t i = 0; i < rootMoves.size(); i++) { - if (rootMoves[i].score == best) - rootMoves[j++] = rootMoves[i]; - } - rootMoves.resize(j, Search::RootMove(MOVE_NONE)); + WDLScore wdl = Tablebases::probe_wdl(pos, &result); - return true; -} + if (result == FAIL) + return false; + + score = WDL_to_value[wdl + 2]; + + StateInfo st; + + int best = WDLLoss; + // Probe each move + for (size_t i = 0; i < rootMoves.size(); ++i) { + Move move = rootMoves[i].pv[0]; + pos.do_move(move, st, pos.gives_check(move)); + WDLScore v = -Tablebases::probe_wdl(pos, &result); + pos.undo_move(move); + + if (result == FAIL) + return false; + + rootMoves[i].score = (Value)v; + + if (v > best) + best = v; + } + + size_t j = 0; + + for (size_t i = 0; i < rootMoves.size(); ++i) { + if (rootMoves[i].score == best) + rootMoves[j++] = rootMoves[i]; + } + + rootMoves.resize(j, Search::RootMove(MOVE_NONE)); + + return true; +} diff --git a/src/syzygy/tbprobe.h b/src/syzygy/tbprobe.h index b23fdf66..7cef6971 100644 --- a/src/syzygy/tbprobe.h +++ b/src/syzygy/tbprobe.h @@ -1,19 +1,79 @@ +/* + Stockfish, a UCI chess playing engine derived from Glaurung 2.1 + Copyright (c) 2013 Ronald de Man + Copyright (C) 2016 Marco Costalba, Lucas Braesch + + Stockfish is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + Stockfish is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + #ifndef TBPROBE_H #define TBPROBE_H +#include + #include "../search.h" namespace Tablebases { +enum WDLScore { + WDLLoss = -2, // Loss + WDLCursedLoss = -1, // Loss, but draw under 50-move rule + WDLDraw = 0, // Draw + WDLCursedWin = 1, // Win, but draw under 50-move rule + WDLWin = 2, // Win + + WDLScoreNone = -1000 +}; + +// Possible states after a probing operation +enum ProbeState { + FAIL = 0, // Probe failed (missing file table) + OK = 1, // Probe succesful + CHANGE_STM = -1, // DTZ should check the other side + ZEROING_BEST_MOVE = 2 // Best move zeroes DTZ (capture or pawn move) +}; + extern int MaxCardinality; -void init(const std::string& path); -int probe_wdl(Position& pos, int *success); -int probe_dtz(Position& pos, int *success); +void init(const std::string& paths); +WDLScore probe_wdl(Position& pos, ProbeState* result); +int probe_dtz(Position& pos, ProbeState* result); bool root_probe(Position& pos, Search::RootMoves& rootMoves, Value& score); bool root_probe_wdl(Position& pos, Search::RootMoves& rootMoves, Value& score); void filter_root_moves(Position& pos, Search::RootMoves& rootMoves); +inline std::ostream& operator<<(std::ostream& os, const WDLScore v) { + + os << (v == WDLLoss ? "Loss" : + v == WDLCursedLoss ? "Cursed loss" : + v == WDLDraw ? "Draw" : + v == WDLCursedWin ? "Cursed win" : + v == WDLWin ? "Win" : "None"); + + return os; +} + +inline std::ostream& operator<<(std::ostream& os, const ProbeState v) { + + os << (v == FAIL ? "Failed" : + v == OK ? "Success" : + v == CHANGE_STM ? "Probed opponent side" : + v == ZEROING_BEST_MOVE ? "Best move zeroes DTZ" : "None"); + + return os; +} + } #endif diff --git a/src/uci.cpp b/src/uci.cpp index b195b871..0b3e3a51 100644 --- a/src/uci.cpp +++ b/src/uci.cpp @@ -29,6 +29,7 @@ #include "thread.h" #include "timeman.h" #include "uci.h" +#include "syzygy/tbprobe.h" using namespace std; @@ -186,6 +187,7 @@ void UCI::loop(int argc, char* argv[]) { else if (token == "ucinewgame") { Search::clear(); + Tablebases::init(Options["SyzygyPath"]); Time.availableNodes = 0; } else if (token == "isready") sync_cout << "readyok" << sync_endl; -- 2.39.2