/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
- Copyright (c) 2013 Ronald de Man
- Copyright (C) 2016-2018 Marco Costalba, Lucas Braesch
+ Copyright (C) 2004-2021 The Stockfish developers (see AUTHORS file)
Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
#include <list>
#include <sstream>
#include <type_traits>
+#include <mutex>
#include "../bitboard.h"
#include "../movegen.h"
#include "../position.h"
#include "../search.h"
-#include "../thread_win32.h"
#include "../types.h"
+#include "../uci.h"
#include "tbprobe.h"
#include <sys/stat.h>
#else
#define WIN32_LEAN_AND_MEAN
-#define NOMINMAX
+#ifndef NOMINMAX
+# define NOMINMAX // Disable macros min() and max()
+#endif
#include <windows.h>
#endif
-using namespace Tablebases;
+using namespace Stockfish::Tablebases;
+
+int Stockfish::Tablebases::MaxCardinality;
-int Tablebases::MaxCardinality;
+namespace Stockfish {
namespace {
-constexpr int TBPIECES = 6; // Max number of supported pieces
+constexpr int TBPIECES = 7; // Max number of supported pieces
enum { BigEndian, LittleEndian };
-enum TBType { KEY, WDL, DTZ }; // Used as template parameter
+enum TBType { WDL, DTZ }; // Used as template parameter
// Each table has a set of flags: all of them refer to DTZ tables, the last one to WDL tables
-enum TBFlag { STM = 1, Mapped = 2, WinPlies = 4, LossPlies = 8, SingleValue = 128 };
+enum TBFlag { STM = 1, Mapped = 2, WinPlies = 4, LossPlies = 8, Wide = 16, SingleValue = 128 };
inline WDLScore operator-(WDLScore d) { return WDLScore(-int(d)); }
-inline Square operator^=(Square& s, int i) { return s = Square(int(s) ^ i); }
inline Square operator^(Square s, int i) { return Square(int(s) ^ i); }
const std::string PieceToChar = " PNBRQK pnbrqk";
int MapKK[10][SQUARE_NB]; // [MapA1D1D4][SQUARE_NB]
int Binomial[6][SQUARE_NB]; // [k][n] k elements from a set of n elements
-int LeadPawnIdx[5][SQUARE_NB]; // [leadPawnsCnt][SQUARE_NB]
-int LeadPawnsSize[5][4]; // [leadPawnsCnt][FILE_A..FILE_D]
+int LeadPawnIdx[6][SQUARE_NB]; // [leadPawnsCnt][SQUARE_NB]
+int LeadPawnsSize[6][4]; // [leadPawnsCnt][FILE_A..FILE_D]
// Comparison function to sort leading pawns in ascending MapPawns[] order
bool pawns_comp(Square i, Square j) { return MapPawns[i] < MapPawns[j]; }
template<typename T, int LE> T number(void* addr)
{
- static const union { uint32_t i; char c[4]; } Le = { 0x01020304 };
- static const bool IsLittleEndian = (Le.c[0] == 4);
-
T v;
if ((uintptr_t)addr & (alignof(T) - 1)) // Unaligned pointer (very rare)
typedef uint16_t Sym; // Huffman symbol
struct LR {
- enum Side { Left, Right, Value };
+ enum Side { Left, Right };
uint8_t lr[3]; // The first 12 bits is the left-hand symbol, the second 12
// bits is the right-hand symbol. If symbol has length 1,
- // then the first byte is the stored value.
+ // then the left-hand symbol is the stored value.
template<Side S>
Sym get() {
return S == Left ? ((lr[1] & 0xF) << 8) | lr[0] :
- S == Right ? (lr[2] << 4) | (lr[1] >> 4) :
- S == Value ? lr[0] : (assert(false), Sym(-1));
+ S == Right ? (lr[2] << 4) | (lr[1] >> 4) : (assert(false), Sym(-1));
}
};
std::stringstream ss(Paths);
std::string path;
- while (std::getline(ss, path, SepChar)) {
+ while (std::getline(ss, path, SepChar))
+ {
fname = path + "/" + f;
std::ifstream::open(fname);
if (is_open())
return *baseAddress = nullptr, nullptr;
fstat(fd, &statbuf);
+
+ if (statbuf.st_size % 64 != 16)
+ {
+ std::cerr << "Corrupt tablebase file " << fname << std::endl;
+ exit(EXIT_FAILURE);
+ }
+
*mapping = statbuf.st_size;
*baseAddress = mmap(nullptr, statbuf.st_size, PROT_READ, MAP_SHARED, fd, 0);
+#if defined(MADV_RANDOM)
+ madvise(*baseAddress, statbuf.st_size, MADV_RANDOM);
+#endif
::close(fd);
- if (*baseAddress == MAP_FAILED) {
+ if (*baseAddress == MAP_FAILED)
+ {
std::cerr << "Could not mmap() " << fname << std::endl;
- exit(1);
+ exit(EXIT_FAILURE);
}
#else
+ // Note FILE_FLAG_RANDOM_ACCESS is only a hint to Windows and as such may get ignored.
HANDLE fd = CreateFile(fname.c_str(), GENERIC_READ, FILE_SHARE_READ, nullptr,
- OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, nullptr);
+ OPEN_EXISTING, FILE_FLAG_RANDOM_ACCESS, nullptr);
if (fd == INVALID_HANDLE_VALUE)
return *baseAddress = nullptr, nullptr;
DWORD size_high;
DWORD size_low = GetFileSize(fd, &size_high);
+
+ if (size_low % 64 != 16)
+ {
+ std::cerr << "Corrupt tablebase file " << fname << std::endl;
+ exit(EXIT_FAILURE);
+ }
+
HANDLE mmap = CreateFileMapping(fd, nullptr, PAGE_READONLY, size_high, size_low, nullptr);
CloseHandle(fd);
- if (!mmap) {
+ if (!mmap)
+ {
std::cerr << "CreateFileMapping() failed" << std::endl;
- exit(1);
+ exit(EXIT_FAILURE);
}
*mapping = (uint64_t)mmap;
*baseAddress = MapViewOfFile(mmap, FILE_MAP_READ, 0, 0, 0);
- if (!*baseAddress) {
+ if (!*baseAddress)
+ {
std::cerr << "MapViewOfFile() failed, name = " << fname
<< ", error = " << GetLastError() << std::endl;
- exit(1);
+ exit(EXIT_FAILURE);
}
#endif
uint8_t* data = (uint8_t*)*baseAddress;
constexpr uint8_t Magics[][4] = { { 0xD7, 0x66, 0x0C, 0xA5 },
{ 0x71, 0xE8, 0x23, 0x5D } };
- if (memcmp(data, Magics[type == WDL], 4)) {
+ if (memcmp(data, Magics[type == WDL], 4))
+ {
std::cerr << "Corrupted table in file " << fname << std::endl;
unmap(*baseAddress, *mapping);
return *baseAddress = nullptr, nullptr;
hasPawns = pos.pieces(PAWN);
hasUniquePieces = false;
- for (Color c = WHITE; c <= BLACK; ++c)
+ for (Color c : { WHITE, BLACK })
for (PieceType pt = PAWN; pt < KING; ++pt)
if (popcount(pos.pieces(c, pt)) == 1)
hasUniquePieces = true;
// at init time, accessed at probe time.
class TBTables {
- typedef std::tuple<Key, TBTable<WDL>*, TBTable<DTZ>*> Entry;
+ struct Entry
+ {
+ Key key;
+ TBTable<WDL>* wdl;
+ TBTable<DTZ>* dtz;
- static const int Size = 1 << 12; // 4K table, indexed by key's 12 lsb
+ template <TBType Type>
+ TBTable<Type>* get() const {
+ return (TBTable<Type>*)(Type == WDL ? (void*)wdl : (void*)dtz);
+ }
+ };
+
+ static constexpr int Size = 1 << 12; // 4K table, indexed by key's 12 lsb
+ static constexpr int Overflow = 1; // Number of elements allowed to map to the last bucket
- Entry hashTable[Size];
+ Entry hashTable[Size + Overflow];
std::deque<TBTable<WDL>> wdlTable;
std::deque<TBTable<DTZ>> dtzTable;
void insert(Key key, TBTable<WDL>* wdl, TBTable<DTZ>* dtz) {
- Entry* entry = &hashTable[(uint32_t)key & (Size - 1)];
+ uint32_t homeBucket = (uint32_t)key & (Size - 1);
+ Entry entry{ key, wdl, dtz };
// Ensure last element is empty to avoid overflow when looking up
- for ( ; entry - hashTable < Size - 1; ++entry)
- if (std::get<KEY>(*entry) == key || !std::get<WDL>(*entry)) {
- *entry = std::make_tuple(key, wdl, dtz);
+ for (uint32_t bucket = homeBucket; bucket < Size + Overflow - 1; ++bucket) {
+ Key otherKey = hashTable[bucket].key;
+ if (otherKey == key || !hashTable[bucket].get<WDL>()) {
+ hashTable[bucket] = entry;
return;
}
+
+ // Robin Hood hashing: If we've probed for longer than this element,
+ // insert here and search for a new spot for the other element instead.
+ uint32_t otherHomeBucket = (uint32_t)otherKey & (Size - 1);
+ if (otherHomeBucket > homeBucket) {
+ std::swap(entry, hashTable[bucket]);
+ key = otherKey;
+ homeBucket = otherHomeBucket;
+ }
+ }
std::cerr << "TB hash table size too low!" << std::endl;
- exit(1);
+ exit(EXIT_FAILURE);
}
public:
template<TBType Type>
TBTable<Type>* get(Key key) {
for (const Entry* entry = &hashTable[(uint32_t)key & (Size - 1)]; ; ++entry) {
- if (std::get<KEY>(*entry) == key || !std::get<Type>(*entry))
- return std::get<Type>(*entry);
+ if (entry->key == key || !entry->get<Type>())
+ return entry->get<Type>();
}
}
// 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 definition (1)
- uint32_t k = idx / d->span;
+ uint32_t k = uint32_t(idx / d->span);
// Then we read the corresponding SparseIndex[] entry
uint32_t block = number<uint32_t, LittleEndian>(&d->sparseIndex[k].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);
+ uint32_t* ptr = (uint32_t*)(d->data + ((uint64_t)block * d->sizeofBlock));
// Read the first 64 bits in our block, this is a (truncated) sequence of
// unknown number of symbols of unknown length but we know the first one
int buf64Size = 64;
Sym sym;
- while (true) {
+ 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
// 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);
+ sym = 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<Sym, LittleEndian>(&d->lowestSym[len]);
// 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]) {
-
+ while (d->symlen[sym])
+ {
Sym left = d->btree[sym].get<LR::Left>();
// If a symbol contains 36 sub-symbols (d->symlen[sym] + 1 = 36) and
}
}
- return d->btree[sym].get<LR::Value>();
+ return d->btree[sym].get<LR::Left>();
}
bool check_dtz_stm(TBTable<WDL>*, int, File) { return true; }
uint8_t* map = entry->map;
uint16_t* idx = entry->get(0, f)->map_idx;
- if (flags & TBFlag::Mapped)
- value = map[idx[WDLMap[wdl + 2]] + value];
+ if (flags & TBFlag::Mapped) {
+ if (flags & TBFlag::Wide)
+ value = ((uint16_t *)map)[idx[WDLMap[wdl + 2]] + value];
+ else
+ value = map[idx[WDLMap[wdl + 2]] + value];
+ }
// DTZ tables store distance to zero in number of moves or plies. We
// want to return plies, so we have convert to plies when needed.
bool blackStronger = (pos.material_key() != entry->key);
int flipColor = (symmetricBlackToMove || blackStronger) * 8;
- int flipSquares = (symmetricBlackToMove || blackStronger) * 070;
+ int flipSquares = (symmetricBlackToMove || blackStronger) * 56;
int stm = (symmetricBlackToMove || blackStronger) ^ pos.side_to_move();
// For pawns, TB files store 4 separate tables according if leading pawn is on
leadPawns = b = pos.pieces(color_of(pc), PAWN);
do
- squares[size++] = pop_lsb(&b) ^ flipSquares;
+ squares[size++] = pop_lsb(b) ^ flipSquares;
while (b);
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
+ tbFile = File(edge_distance(file_of(squares[0])));
}
// DTZ tables are one-sided, i.e. they store positions only for white to
// directly map them to the correct color and square.
b = pos.pieces() ^ leadPawns;
do {
- Square s = pop_lsb(&b);
+ Square s = pop_lsb(b);
squares[size] = s ^ flipSquares;
pieces[size++] = Piece(pos.piece_on(s) ^ flipColor);
} while (b);
// Then we reorder the pieces to have the same sequence as the one stored
// in pieces[i]: the sequence that ensures the best compression.
- for (int i = leadPawnsCnt; i < size; ++i)
- for (int j = i; j < size; ++j)
+ for (int i = leadPawnsCnt; i < size - 1; ++i)
+ for (int j = i + 1; j < size; ++j)
if (d->pieces[i] == pieces[j])
{
std::swap(pieces[i], pieces[j]);
// 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
+ squares[i] = flip_file(squares[i]);
// 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);
+ std::stable_sort(squares + 1, squares + leadPawnsCnt, pawns_comp);
for (int i = 1; i < leadPawnsCnt; ++i)
idx += Binomial[i][MapPawns[squares[i]]];
// 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
+ squares[i] = flip_rank(squares[i]);
// Look for the first piece of the leading group not on the A1-D4 diagonal
// and ensure it is mapped below the diagonal.
if (!off_A1H8(squares[i]))
continue;
- if (off_A1H8(squares[i]) > 0) // A1-H8 diagonal flip: SQ_A3 -> SQ_C3
+ if (off_A1H8(squares[i]) > 0) // A1-H8 diagonal flip: SQ_A3 -> SQ_C1
for (int j = i; j < size; ++j)
squares[j] = Square(((squares[j] >> 3) | (squares[j] << 3)) & 63);
break;
while (d->groupLen[++next])
{
- std::sort(groupSq, groupSq + d->groupLen[next]);
+ std::stable_sort(groupSq, groupSq + d->groupLen[next]);
uint64_t n = 0;
// Map down a square if "comes later" than a square in the previous
d->sizeofBlock = 1ULL << *data++;
d->span = 1ULL << *data++;
- d->sparseIndexSize = (tbSize + d->span - 1) / d->span; // Round up
+ d->sparseIndexSize = size_t((tbSize + d->span - 1) / d->span); // Round up
auto padding = number<uint8_t, LittleEndian>(data++);
d->blocksNum = number<uint32_t, LittleEndian>(data); data += sizeof(uint32_t);
d->blockLengthSize = d->blocksNum + padding; // Padded to ensure SparseIndex[]
// 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
+ // See https://en.wikipedia.org/wiki/Huffman_coding
for (int i = d->base64.size() - 2; i >= 0; --i) {
d->base64[i] = (d->base64[i + 1] + number<Sym, LittleEndian>(&d->lowestSym[i])
- number<Sym, LittleEndian>(&d->lowestSym[i + 1])) / 2;
d->symlen.resize(number<uint16_t, LittleEndian>(data)); data += sizeof(uint16_t);
d->btree = (LR*)data;
- // The comrpession scheme used is "Recursive Pairing", that replaces the most
+ // The compression 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.
e.map = data;
for (File f = FILE_A; f <= maxFile; ++f) {
- if (e.get(0, f)->flags & TBFlag::Mapped)
- for (int i = 0; i < 4; ++i) { // Sequence like 3,x,x,x,1,x,0,2,x,x
- e.get(0, f)->map_idx[i] = (uint16_t)(data - e.map + 1);
- data += *data + 1;
+ auto flags = e.get(0, f)->flags;
+ if (flags & TBFlag::Mapped) {
+ if (flags & TBFlag::Wide) {
+ data += (uintptr_t)data & 1; // Word alignment, we may have a mixed table
+ for (int i = 0; i < 4; ++i) { // Sequence like 3,x,x,x,1,x,0,2,x,x
+ e.get(0, f)->map_idx[i] = (uint16_t)((uint16_t *)data - (uint16_t *)e.map + 1);
+ data += 2 * number<uint16_t, LittleEndian>(data) + 2;
+ }
+ }
+ else {
+ for (int i = 0; i < 4; ++i) {
+ e.get(0, f)->map_idx[i] = (uint16_t)(data - e.map + 1);
+ data += *data + 1;
+ }
}
+ }
}
return data += (uintptr_t)data & 1; // Word alignment
enum { Split = 1, HasPawns = 2 };
- assert(e.hasPawns == !!(*data & HasPawns));
- assert((e.key != e.key2) == !!(*data & Split));
+ assert(e.hasPawns == bool(*data & HasPawns));
+ assert((e.key != e.key2) == bool(*data & Split));
data++; // First byte stores flags
template<TBType Type>
void* mapped(TBTable<Type>& e, const Position& pos) {
- static Mutex mutex;
+ static std::mutex mutex;
- // Use 'aquire' to avoid a thread reads 'ready' == true while another is
- // still working, this could happen due to compiler reordering.
+ // Use 'acquire' to avoid a thread reading 'ready' == true while
+ // another is still working. (compiler reordering may cause this).
if (e.ready.load(std::memory_order_acquire))
- return e.baseAddress; // Could be nullptr if file does not exsist
+ return e.baseAddress; // Could be nullptr if file does not exist
- std::unique_lock<Mutex> lk(mutex);
+ std::scoped_lock<std::mutex> lk(mutex);
if (e.ready.load(std::memory_order_relaxed)) // Recheck under lock
return e.baseAddress;
// 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
+// DTZ tables do not 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<bool CheckZeroingMoves = false>
+template<bool CheckZeroingMoves>
WDLScore search(Position& pos, ProbeState* result) {
WDLScore value, bestValue = WDLLoss;
auto moveList = MoveList<LEGAL>(pos);
size_t totalCount = moveList.size(), moveCount = 0;
- for (const Move& move : moveList)
+ for (const Move move : moveList)
{
if ( !pos.capture(move)
&& (!CheckZeroingMoves || type_of(pos.moved_piece(move)) != PAWN))
moveCount++;
pos.do_move(move, st);
- value = -search(pos, result);
+ value = -search<false>(pos, result);
pos.undo_move(move);
if (*result == FAIL)
continue; // First on diagonal, second above
else if (!off_A1H8(s1) && !off_A1H8(s2))
- bothOnDiagonal.push_back(std::make_pair(idx, s2));
+ bothOnDiagonal.emplace_back(idx, s2);
else
MapKK[idx][s2] = code++;
// among pawns with same file, the one with lowest rank.
int availableSquares = 47; // Available squares when lead pawn is in a2
- // Init the tables for the encoding of leading pawns group: with 6-men TB we
- // can have up to 4 leading pawns (KPPPPK).
- for (int leadPawnsCnt = 1; leadPawnsCnt <= 4; ++leadPawnsCnt)
+ // Init the tables for the encoding of leading pawns group: with 7-men TB we
+ // can have up to 5 leading pawns (KPPPPPK).
+ for (int leadPawnsCnt = 1; leadPawnsCnt <= 5; ++leadPawnsCnt)
for (File f = FILE_A; f <= FILE_D; ++f)
{
// Restart the index at every file because TB table is splitted
if (leadPawnsCnt == 1)
{
MapPawns[sq] = availableSquares--;
- MapPawns[sq ^ 7] = availableSquares--; // Horizontal flip
+ MapPawns[flip_file(sq)] = availableSquares--;
}
LeadPawnIdx[leadPawnsCnt][sq] = idx;
idx += Binomial[leadPawnsCnt - 1][MapPawns[sq]];
LeadPawnsSize[leadPawnsCnt][f] = idx;
}
- // Add entries in TB tables if the corresponding ".rtbw" file exsists
+ // Add entries in TB tables if the corresponding ".rtbw" file exists
for (PieceType p1 = PAWN; p1 < KING; ++p1) {
TBTables.add({KING, p1, KING});
for (PieceType p3 = PAWN; p3 <= p2; ++p3) {
TBTables.add({KING, p1, p2, p3, KING});
- for (PieceType p4 = PAWN; p4 <= p3; ++p4)
+ for (PieceType p4 = PAWN; p4 <= p3; ++p4) {
TBTables.add({KING, p1, p2, p3, p4, KING});
- for (PieceType p4 = PAWN; p4 < KING; ++p4)
+ for (PieceType p5 = PAWN; p5 <= p4; ++p5)
+ TBTables.add({KING, p1, p2, p3, p4, p5, KING});
+
+ for (PieceType p5 = PAWN; p5 < KING; ++p5)
+ TBTables.add({KING, p1, p2, p3, p4, KING, p5});
+ }
+
+ for (PieceType p4 = PAWN; p4 < KING; ++p4) {
TBTables.add({KING, p1, p2, p3, KING, p4});
+
+ for (PieceType p5 = PAWN; p5 <= p4; ++p5)
+ TBTables.add({KING, p1, p2, p3, KING, p4, p5});
+ }
}
for (PieceType p3 = PAWN; p3 <= p1; ++p3)
WDLScore Tablebases::probe_wdl(Position& pos, ProbeState* result) {
*result = OK;
- return search(pos, result);
+ return search<false>(pos, result);
}
// Probe the DTZ table for a particular position.
// 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)
+// -1 : loss, the side to move is mated
// 0 : draw
// 1 < n <= 100 : win in n ply (assuming 50-move counter == 0)
// 100 < n : win, but draw under 50-move rule
// If n = 100 immediately after a capture or pawn move, then the position
// is also certainly a win, and during the whole phase until the next
// capture or pawn move, the inequality to be preserved is
-// dtz + 50-movecounter <= 100.
+// dtz + 50-move-counter <= 100.
//
// In short, if a move is available resulting in dtz + 50-move-counter <= 99,
// then do not accept moves leading to dtz + 50-move-counter == 100.
StateInfo st;
int minDTZ = 0xFFFF;
- for (const Move& move : MoveList<LEGAL>(pos))
+ for (const Move move : MoveList<LEGAL>(pos))
{
bool zeroing = pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN;
// 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))
+ dtz = zeroing ? -dtz_before_zeroing(search<false>(pos, result))
: -probe_dtz(pos, result);
- pos.undo_move(move);
-
- if (*result == FAIL)
- return 0;
+ // If the move mates, force minDTZ to 1
+ if (dtz == 1 && pos.checkers() && MoveList<LEGAL>(pos).size() == 0)
+ minDTZ = 1;
// Convert result from 1-ply search. Zeroing moves are already accounted
// by dtz_before_zeroing() that returns the DTZ of the previous move.
// Skip the draws and if we are winning only pick positive dtz
if (dtz < minDTZ && sign_of(dtz) == sign_of(wdl))
minDTZ = dtz;
- }
- // 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);
+ pos.undo_move(move);
- if (e < i)
+ if (*result == FAIL)
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;
}
+
+ // When there are no legal moves, the position is mate: we return -1
+ return minDTZ == 0xFFFF ? -1 : minDTZ;
}
-// Use the DTZ tables to filter out moves that don't preserve the win or draw.
-// If the position is lost, but DTZ is fairly high, only keep moves that
-// maximise DTZ.
+
+// Use the DTZ tables to rank root moves.
//
-// A return value false indicates that not all probes were successful and that
-// no moves were filtered out.
-bool Tablebases::root_probe(Position& pos, Search::RootMoves& rootMoves, Value& score)
-{
- assert(rootMoves.size());
+// A return value false indicates that not all probes were successful.
+bool Tablebases::root_probe(Position& pos, Search::RootMoves& rootMoves) {
ProbeState result;
- int dtz = probe_dtz(pos, &result);
-
- 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);
- int v = 0;
-
- if (pos.checkers() && dtz > 0) {
- ExtMove s[MAX_MOVES];
-
- if (generate<LEGAL>(pos, s) == s)
- v = 1;
- }
+ // Obtain 50-move counter for the root position
+ int cnt50 = pos.rule50_count();
- 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));
- }
- }
+ // Check whether a position was repeated since the last zeroing move.
+ bool rep = pos.has_repeated();
- pos.undo_move(move);
-
- if (result == FAIL)
- return false;
+ int dtz, bound = Options["Syzygy50MoveRule"] ? 900 : 1;
- rootMoves[i].score = (Value)v;
- }
-
- // Obtain 50-move counter for the root position.
- // In Stockfish there seems to be no clean way, so we do it like this:
- int cnt50 = st.previous ? st.previous->rule50 : 0;
-
- // Use 50-move counter to determine whether the root position is
- // won, lost or drawn.
- WDLScore wdl = WDLDraw;
-
- if (dtz > 0)
- wdl = (dtz + cnt50 <= 100) ? WDLWin : WDLCursedWin;
- else if (dtz < 0)
- wdl = (-dtz + cnt50 <= 100) ? WDLLoss : WDLBlessedLoss;
-
- // 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 == WDLCursedWin && dtz <= 100)
- score = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200);
- else if (wdl == WDLBlessedLoss && 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;
+ // Probe and rank each move
+ for (auto& m : rootMoves)
+ {
+ pos.do_move(m.pv[0], st);
- if (v > 0 && v < best)
- best = v;
+ // Calculate dtz for the current move counting from the root position
+ if (pos.rule50_count() == 0)
+ {
+ // In case of a zeroing move, dtz is one of -101/-1/0/1/101
+ WDLScore wdl = -probe_wdl(pos, &result);
+ dtz = dtz_before_zeroing(wdl);
}
-
- 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 (pos.is_draw(1))
+ {
+ // In case a root move leads to a draw by repetition or
+ // 50-move rule, we set dtz to zero. Note: since we are
+ // only 1 ply from the root, this must be a true 3-fold
+ // repetition inside the game history.
+ dtz = 0;
+ }
+ else
+ {
+ // Otherwise, take dtz for the new position and correct by 1 ply
+ dtz = -probe_dtz(pos, &result);
+ dtz = dtz > 0 ? dtz + 1
+ : dtz < 0 ? dtz - 1 : dtz;
}
- } 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;
+ // Make sure that a mating move is assigned a dtz value of 1
+ if ( pos.checkers()
+ && dtz == 2
+ && MoveList<LEGAL>(pos).size() == 0)
+ dtz = 1;
- if (v < best)
- best = v;
- }
+ pos.undo_move(m.pv[0]);
- // Try all moves, unless we approach or have a 50-move rule draw.
- if (-best * 2 + cnt50 < 100)
- return true;
+ if (result == FAIL)
+ return false;
- 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];
- }
+ // Better moves are ranked higher. Certain wins are ranked equally.
+ // Losing moves are ranked equally unless a 50-move draw is in sight.
+ int r = dtz > 0 ? (dtz + cnt50 <= 99 && !rep ? 1000 : 1000 - (dtz + cnt50))
+ : dtz < 0 ? (-dtz * 2 + cnt50 < 100 ? -1000 : -1000 + (-dtz + cnt50))
+ : 0;
+ m.tbRank = r;
+
+ // Determine the score to be displayed for this move. Assign at least
+ // 1 cp to cursed wins and let it grow to 49 cp as the positions gets
+ // closer to a real win.
+ m.tbScore = r >= bound ? VALUE_MATE - MAX_PLY - 1
+ : r > 0 ? Value((std::max( 3, r - 800) * int(PawnValueEg)) / 200)
+ : r == 0 ? VALUE_DRAW
+ : r > -bound ? Value((std::min(-3, r + 800) * int(PawnValueEg)) / 200)
+ : -VALUE_MATE + MAX_PLY + 1;
}
- 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.
+
+// Use the WDL tables to rank root moves.
// This is a fallback for the case that some or all DTZ tables are missing.
//
-// A return value false indicates that not all probes were successful and that
-// no moves were filtered out.
-bool Tablebases::root_probe_wdl(Position& pos, Search::RootMoves& rootMoves, Value& score)
-{
- ProbeState result;
+// A return value false indicates that not all probes were successful.
+bool Tablebases::root_probe_wdl(Position& pos, Search::RootMoves& rootMoves) {
- WDLScore wdl = Tablebases::probe_wdl(pos, &result);
+ static const int WDL_to_rank[] = { -1000, -899, 0, 899, 1000 };
- if (result == FAIL)
- return false;
+ ProbeState result;
+ StateInfo st;
+ WDLScore wdl;
- score = WDL_to_value[wdl + 2];
+ bool rule50 = Options["Syzygy50MoveRule"];
- StateInfo st;
+ // Probe and rank each move
+ for (auto& m : rootMoves)
+ {
+ pos.do_move(m.pv[0], st);
- int best = WDLLoss;
+ if (pos.is_draw(1))
+ wdl = WDLDraw;
+ else
+ wdl = -probe_wdl(pos, &result);
- // Probe each move
- for (size_t i = 0; i < rootMoves.size(); ++i) {
- Move move = rootMoves[i].pv[0];
- pos.do_move(move, st);
- WDLScore v = -Tablebases::probe_wdl(pos, &result);
- pos.undo_move(move);
+ pos.undo_move(m.pv[0]);
if (result == FAIL)
return false;
- rootMoves[i].score = (Value)v;
-
- if (v > best)
- best = v;
- }
-
- size_t j = 0;
+ m.tbRank = WDL_to_rank[wdl + 2];
- for (size_t i = 0; i < rootMoves.size(); ++i) {
- if (rootMoves[i].score == best)
- rootMoves[j++] = rootMoves[i];
+ if (!rule50)
+ wdl = wdl > WDLDraw ? WDLWin
+ : wdl < WDLDraw ? WDLLoss : WDLDraw;
+ m.tbScore = WDL_to_value[wdl + 2];
}
- rootMoves.resize(j, Search::RootMove(MOVE_NONE));
-
return true;
}
+
+} // namespace Stockfish