+
+ // 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<LR::Left>();
+
+ // 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<LR::Right>();
+ }
+ }
+
+ return d->btree[sym].get<LR::Value>();
+}
+
+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 == WDLBlessedLoss)
+ 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<typename Entry, typename T = typename Ret<Entry>::type>
+T do_probe_table(const Position& pos, Entry* entry, WDLScore wdl, ProbeState* result) {
+
+ const bool IsWDL = std::is_same<Entry, WDLEntry>::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);
+ do
+ 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
+
+ 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;