2 Copyright (c) 2013 Ronald de Man
3 This file may be redistributed and/or modified without restrictions.
5 tbprobe.cpp contains the Stockfish-specific routines of the
6 tablebase probing code. It should be relatively easy to adapt
7 this code to other chess engines.
12 #include "../position.h"
13 #include "../movegen.h"
14 #include "../bitboard.h"
15 #include "../search.h"
16 #include "../bitcount.h"
24 extern Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
27 int Tablebases::MaxCardinality = 0;
29 // Given a position with 6 or fewer pieces, produce a text string
30 // of the form KQPvKRP, where "KQP" represents the white pieces if
31 // mirror == 0 and the black pieces if mirror == 1.
32 static void prt_str(Position& pos, char *str, int mirror)
38 color = !mirror ? WHITE : BLACK;
39 for (pt = KING; pt >= PAWN; --pt)
40 for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
41 *str++ = pchr[6 - pt];
44 for (pt = KING; pt >= PAWN; --pt)
45 for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
46 *str++ = pchr[6 - pt];
50 // Given a position, produce a 64-bit material signature key.
51 // If the engine supports such a key, it should equal the engine's key.
52 static uint64 calc_key(Position& pos, int mirror)
59 color = !mirror ? WHITE : BLACK;
60 for (pt = PAWN; pt <= KING; ++pt)
61 for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
62 key ^= Zobrist::psq[WHITE][pt][i - 1];
64 for (pt = PAWN; pt <= KING; ++pt)
65 for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
66 key ^= Zobrist::psq[BLACK][pt][i - 1];
71 // Produce a 64-bit material key corresponding to the material combination
72 // defined by pcs[16], where pcs[1], ..., pcs[6] is the number of white
73 // pawns, ..., kings and pcs[9], ..., pcs[14] is the number of black
75 static uint64 calc_key_from_pcs(int *pcs, int mirror)
82 color = !mirror ? 0 : 8;
83 for (pt = PAWN; pt <= KING; ++pt)
84 for (i = 0; i < pcs[color + pt]; i++)
85 key ^= Zobrist::psq[WHITE][pt][i];
87 for (pt = PAWN; pt <= KING; ++pt)
88 for (i = 0; i < pcs[color + pt]; i++)
89 key ^= Zobrist::psq[BLACK][pt][i];
94 bool is_little_endian() {
103 static ubyte decompress_pairs(struct PairsData *d, uint64 idx)
105 static const bool isLittleEndian = is_little_endian();
106 return isLittleEndian ? decompress_pairs<true >(d, idx)
107 : decompress_pairs<false>(d, idx);
110 // probe_wdl_table and probe_dtz_table require similar adaptations.
111 static int probe_wdl_table(Position& pos, int *success)
114 struct TBHashEntry *ptr2;
121 // Obtain the position's material signature key.
122 key = pos.material_key();
125 if (key == (Zobrist::psq[WHITE][KING][0] ^ Zobrist::psq[BLACK][KING][0]))
128 ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
129 for (i = 0; i < HSHMAX; i++)
130 if (ptr2[i].key == key) break;
141 prt_str(pos, str, ptr->key != key);
142 if (!init_table_wdl(ptr, str)) {
148 // Memory barrier to ensure ptr->ready = 1 is not reordered.
152 __asm__ __volatile__ ("" ::: "memory");
159 int bside, mirror, cmirror;
160 if (!ptr->symmetric) {
161 if (key != ptr->key) {
164 bside = (pos.side_to_move() == WHITE);
166 cmirror = mirror = 0;
167 bside = !(pos.side_to_move() == WHITE);
170 cmirror = pos.side_to_move() == WHITE ? 0 : 8;
171 mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
175 // p[i] is to contain the square 0-63 (A1-H8) for a piece of type
176 // pc[i] ^ cmirror, where 1 = white pawn, ..., 14 = black king.
177 // Pieces of the same type are guaranteed to be consecutive.
178 if (!ptr->has_pawns) {
179 struct TBEntry_piece *entry = (struct TBEntry_piece *)ptr;
180 ubyte *pc = entry->pieces[bside];
181 for (i = 0; i < entry->num;) {
182 Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
183 (PieceType)(pc[i] & 0x07));
185 p[i++] = pop_lsb(&bb);
188 idx = encode_piece(entry, entry->norm[bside], p, entry->factor[bside]);
189 res = decompress_pairs(entry->precomp[bside], idx);
191 struct TBEntry_pawn *entry = (struct TBEntry_pawn *)ptr;
192 int k = entry->file[0].pieces[0][0] ^ cmirror;
193 Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));
196 p[i++] = pop_lsb(&bb) ^ mirror;
198 int f = pawn_file(entry, p);
199 ubyte *pc = entry->file[f].pieces[bside];
200 for (; i < entry->num;) {
201 bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
202 (PieceType)(pc[i] & 0x07));
204 p[i++] = pop_lsb(&bb) ^ mirror;
207 idx = encode_pawn(entry, entry->file[f].norm[bside], p, entry->file[f].factor[bside]);
208 res = decompress_pairs(entry->file[f].precomp[bside], idx);
211 return ((int)res) - 2;
214 static int probe_dtz_table(Position& pos, int wdl, int *success)
221 // Obtain the position's material signature key.
222 uint64 key = pos.material_key();
224 if (DTZ_table[0].key1 != key && DTZ_table[0].key2 != key) {
225 for (i = 1; i < DTZ_ENTRIES; i++)
226 if (DTZ_table[i].key1 == key) break;
227 if (i < DTZ_ENTRIES) {
228 struct DTZTableEntry table_entry = DTZ_table[i];
230 DTZ_table[i] = DTZ_table[i - 1];
231 DTZ_table[0] = table_entry;
233 struct TBHashEntry *ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
234 for (i = 0; i < HSHMAX; i++)
235 if (ptr2[i].key == key) break;
242 int mirror = (ptr->key != key);
243 prt_str(pos, str, mirror);
244 if (DTZ_table[DTZ_ENTRIES - 1].entry)
245 free_dtz_entry(DTZ_table[DTZ_ENTRIES-1].entry);
246 for (i = DTZ_ENTRIES - 1; i > 0; i--)
247 DTZ_table[i] = DTZ_table[i - 1];
248 load_dtz_table(str, calc_key(pos, mirror), calc_key(pos, !mirror));
252 ptr = DTZ_table[0].entry;
258 int bside, mirror, cmirror;
259 if (!ptr->symmetric) {
260 if (key != ptr->key) {
263 bside = (pos.side_to_move() == WHITE);
265 cmirror = mirror = 0;
266 bside = !(pos.side_to_move() == WHITE);
269 cmirror = pos.side_to_move() == WHITE ? 0 : 8;
270 mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
274 if (!ptr->has_pawns) {
275 struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr;
276 if ((entry->flags & 1) != bside && !entry->symmetric) {
280 ubyte *pc = entry->pieces;
281 for (i = 0; i < entry->num;) {
282 Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
283 (PieceType)(pc[i] & 0x07));
285 p[i++] = pop_lsb(&bb);
288 idx = encode_piece((struct TBEntry_piece *)entry, entry->norm, p, entry->factor);
289 res = decompress_pairs(entry->precomp, idx);
291 if (entry->flags & 2)
292 res = entry->map[entry->map_idx[wdl_to_map[wdl + 2]] + res];
294 if (!(entry->flags & pa_flags[wdl + 2]) || (wdl & 1))
297 struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *)ptr;
298 int k = entry->file[0].pieces[0] ^ cmirror;
299 Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));
302 p[i++] = pop_lsb(&bb) ^ mirror;
304 int f = pawn_file((struct TBEntry_pawn *)entry, p);
305 if ((entry->flags[f] & 1) != bside) {
309 ubyte *pc = entry->file[f].pieces;
310 for (; i < entry->num;) {
311 bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
312 (PieceType)(pc[i] & 0x07));
314 p[i++] = pop_lsb(&bb) ^ mirror;
317 idx = encode_pawn((struct TBEntry_pawn *)entry, entry->file[f].norm, p, entry->file[f].factor);
318 res = decompress_pairs(entry->file[f].precomp, idx);
320 if (entry->flags[f] & 2)
321 res = entry->map[entry->map_idx[f][wdl_to_map[wdl + 2]] + res];
323 if (!(entry->flags[f] & pa_flags[wdl + 2]) || (wdl & 1))
330 // Add underpromotion captures to list of captures.
331 static ExtMove *add_underprom_caps(Position& pos, ExtMove *stack, ExtMove *end)
333 ExtMove *moves, *extra = end;
335 for (moves = stack; moves < end; moves++) {
336 Move move = moves->move;
337 if (type_of(move) == PROMOTION && !pos.empty(to_sq(move))) {
338 (*extra++).move = (Move)(move - (1 << 12));
339 (*extra++).move = (Move)(move - (2 << 12));
340 (*extra++).move = (Move)(move - (3 << 12));
347 static int probe_ab(Position& pos, int alpha, int beta, int *success)
351 ExtMove *moves, *end;
354 // Generate (at least) all legal non-ep captures including (under)promotions.
355 // It is OK to generate more, as long as they are filtered out below.
356 if (!pos.checkers()) {
357 end = generate<CAPTURES>(pos, stack);
358 // Since underpromotion captures are not included, we need to add them.
359 end = add_underprom_caps(pos, stack, end);
361 end = generate<EVASIONS>(pos, stack);
365 for (moves = stack; moves < end; moves++) {
366 Move capture = moves->move;
367 if (!pos.capture(capture) || type_of(capture) == ENPASSANT
368 || !pos.legal(capture, ci.pinned))
370 pos.do_move(capture, st, pos.gives_check(capture, ci));
371 v = -probe_ab(pos, -beta, -alpha, success);
372 pos.undo_move(capture);
373 if (*success == 0) return 0;
383 v = probe_wdl_table(pos, success);
384 if (*success == 0) return 0;
386 *success = 1 + (alpha > 0);
394 // Probe the WDL table for a particular position.
395 // If *success != 0, the probe was successful.
396 // The return value is from the point of view of the side to move:
398 // -1 : loss, but draw under 50-move rule
400 // 1 : win, but draw under 50-move rule
402 int Tablebases::probe_wdl(Position& pos, int *success)
407 v = probe_ab(pos, -2, 2, success);
409 // If en passant is not possible, we are done.
410 if (pos.ep_square() == SQ_NONE)
412 if (!(*success)) return 0;
414 // Now handle en passant.
416 // Generate (at least) all legal en passant captures.
418 ExtMove *moves, *end;
422 end = generate<CAPTURES>(pos, stack);
424 end = generate<EVASIONS>(pos, stack);
428 for (moves = stack; moves < end; moves++) {
429 Move capture = moves->move;
430 if (type_of(capture) != ENPASSANT
431 || !pos.legal(capture, ci.pinned))
433 pos.do_move(capture, st, pos.gives_check(capture, ci));
434 int v0 = -probe_ab(pos, -2, 2, success);
435 pos.undo_move(capture);
436 if (*success == 0) return 0;
437 if (v0 > v1) v1 = v0;
442 // Check whether there is at least one legal non-ep move.
443 for (moves = stack; moves < end; moves++) {
444 Move capture = moves->move;
445 if (type_of(capture) == ENPASSANT) continue;
446 if (pos.legal(capture, ci.pinned)) break;
448 if (moves == end && !pos.checkers()) {
449 end = generate<QUIETS>(pos, end);
450 for (; moves < end; moves++) {
451 Move move = moves->move;
452 if (pos.legal(move, ci.pinned))
456 // If not, then we are forced to play the losing ep capture.
465 // This routine treats a position with en passant captures as one without.
466 static int probe_dtz_no_ep(Position& pos, int *success)
470 wdl = probe_ab(pos, -2, 2, success);
471 if (*success == 0) return 0;
473 if (wdl == 0) return 0;
476 return wdl == 2 ? 1 : 101;
479 ExtMove *moves, *end = NULL;
484 // Generate at least all legal non-capturing pawn moves
485 // including non-capturing promotions.
487 end = generate<NON_EVASIONS>(pos, stack);
489 end = generate<EVASIONS>(pos, stack);
491 for (moves = stack; moves < end; moves++) {
492 Move move = moves->move;
493 if (type_of(pos.moved_piece(move)) != PAWN || pos.capture(move)
494 || !pos.legal(move, ci.pinned))
496 pos.do_move(move, st, pos.gives_check(move, ci));
497 int v = -probe_ab(pos, -2, -wdl + 1, success);
499 if (*success == 0) return 0;
501 return v == 2 ? 1 : 101;
505 dtz = 1 + probe_dtz_table(pos, wdl, success);
507 if (wdl & 1) dtz += 100;
508 return wdl >= 0 ? dtz : -dtz;
513 for (moves = stack; moves < end; moves++) {
514 Move move = moves->move;
515 if (pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN
516 || !pos.legal(move, ci.pinned))
518 pos.do_move(move, st, pos.gives_check(move, ci));
519 int v = -Tablebases::probe_dtz(pos, success);
521 if (*success == 0) return 0;
522 if (v > 0 && v + 1 < best)
529 end = generate<NON_EVASIONS>(pos, stack);
531 end = generate<EVASIONS>(pos, stack);
532 for (moves = stack; moves < end; moves++) {
534 Move move = moves->move;
535 if (!pos.legal(move, ci.pinned))
537 pos.do_move(move, st, pos.gives_check(move, ci));
538 if (st.rule50 == 0) {
539 if (wdl == -2) v = -1;
541 v = probe_ab(pos, 1, 2, success);
542 v = (v == 2) ? 0 : -101;
545 v = -Tablebases::probe_dtz(pos, success) - 1;
548 if (*success == 0) return 0;
556 static int wdl_to_dtz[] = {
560 // Probe the DTZ table for a particular position.
561 // If *success != 0, the probe was successful.
562 // The return value is from the point of view of the side to move:
563 // n < -100 : loss, but draw under 50-move rule
564 // -100 <= n < -1 : loss in n ply (assuming 50-move counter == 0)
566 // 1 < n <= 100 : win in n ply (assuming 50-move counter == 0)
567 // 100 < n : win, but draw under 50-move rule
569 // The return value n can be off by 1: a return value -n can mean a loss
570 // in n+1 ply and a return value +n can mean a win in n+1 ply. This
571 // cannot happen for tables with positions exactly on the "edge" of
574 // This implies that if dtz > 0 is returned, the position is certainly
575 // a win if dtz + 50-move-counter <= 99. Care must be taken that the engine
576 // picks moves that preserve dtz + 50-move-counter <= 99.
578 // If n = 100 immediately after a capture or pawn move, then the position
579 // is also certainly a win, and during the whole phase until the next
580 // capture or pawn move, the inequality to be preserved is
581 // dtz + 50-movecounter <= 100.
583 // In short, if a move is available resulting in dtz + 50-move-counter <= 99,
584 // then do not accept moves leading to dtz + 50-move-counter == 100.
586 int Tablebases::probe_dtz(Position& pos, int *success)
589 int v = probe_dtz_no_ep(pos, success);
591 if (pos.ep_square() == SQ_NONE)
593 if (*success == 0) return 0;
595 // Now handle en passant.
599 ExtMove *moves, *end;
603 end = generate<CAPTURES>(pos, stack);
605 end = generate<EVASIONS>(pos, stack);
608 for (moves = stack; moves < end; moves++) {
609 Move capture = moves->move;
610 if (type_of(capture) != ENPASSANT
611 || !pos.legal(capture, ci.pinned))
613 pos.do_move(capture, st, pos.gives_check(capture, ci));
614 int v0 = -probe_ab(pos, -2, 2, success);
615 pos.undo_move(capture);
616 if (*success == 0) return 0;
617 if (v0 > v1) v1 = v0;
620 v1 = wdl_to_dtz[v1 + 2];
625 if (v1 >= 0 || v1 < 100)
627 } else if (v > 100) {
633 } else if (v1 >= 0) {
636 for (moves = stack; moves < end; moves++) {
637 Move move = moves->move;
638 if (type_of(move) == ENPASSANT) continue;
639 if (pos.legal(move, ci.pinned)) break;
641 if (moves == end && !pos.checkers()) {
642 end = generate<QUIETS>(pos, end);
643 for (; moves < end; moves++) {
644 Move move = moves->move;
645 if (pos.legal(move, ci.pinned))
657 // Check whether there has been at least one repetition of positions
658 // since the last capture or pawn move.
659 static int has_repeated(StateInfo *st)
662 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
665 StateInfo *stp = st->previous->previous;
667 stp = stp->previous->previous;
668 if (stp->key == st->key)
676 static Value wdl_to_Value[5] = {
677 -VALUE_MATE + MAX_PLY + 1,
681 VALUE_MATE - MAX_PLY - 1
684 // Use the DTZ tables to filter out moves that don't preserve the win or draw.
685 // If the position is lost, but DTZ is fairly high, only keep moves that
688 // A return value false indicates that not all probes were successful and that
689 // no moves were filtered out.
690 bool Tablebases::root_probe(Position& pos, Search::RootMoveVector& rootMoves, Value& score)
694 int dtz = probe_dtz(pos, &success);
695 if (!success) return false;
701 for (size_t i = 0; i < rootMoves.size(); i++) {
702 Move move = rootMoves[i].pv[0];
703 pos.do_move(move, st, pos.gives_check(move, ci));
705 if (pos.checkers() && dtz > 0) {
707 if (generate<LEGAL>(pos, s) == s)
711 if (st.rule50 != 0) {
712 v = -Tablebases::probe_dtz(pos, &success);
716 v = -Tablebases::probe_wdl(pos, &success);
717 v = wdl_to_dtz[v + 2];
721 if (!success) return false;
722 rootMoves[i].score = (Value)v;
725 // Obtain 50-move counter for the root position.
726 // In Stockfish there seems to be no clean way, so we do it like this:
727 int cnt50 = st.previous->rule50;
729 // Use 50-move counter to determine whether the root position is
730 // won, lost or drawn.
733 wdl = (dtz + cnt50 <= 100) ? 2 : 1;
735 wdl = (-dtz + cnt50 <= 100) ? -2 : -1;
737 // Determine the score to report to the user.
738 score = wdl_to_Value[wdl + 2];
739 // If the position is winning or losing, but too few moves left, adjust the
740 // score to show how close it is to winning or losing.
741 // NOTE: int(PawnValueEg) is used as scaling factor in score_to_uci().
742 if (wdl == 1 && dtz <= 100)
743 score = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200);
744 else if (wdl == -1 && dtz >= -100)
745 score = -(Value)(((200 + dtz - cnt50) * int(PawnValueEg)) / 200);
747 // Now be a bit smart about filtering out moves.
749 if (dtz > 0) { // winning (or 50-move rule draw)
751 for (size_t i = 0; i < rootMoves.size(); i++) {
752 int v = rootMoves[i].score;
753 if (v > 0 && v < best)
757 // If the current phase has not seen repetitions, then try all moves
758 // that stay safely within the 50-move budget, if there are any.
759 if (!has_repeated(st.previous) && best + cnt50 <= 99)
761 for (size_t i = 0; i < rootMoves.size(); i++) {
762 int v = rootMoves[i].score;
763 if (v > 0 && v <= max)
764 rootMoves[j++] = rootMoves[i];
766 } else if (dtz < 0) { // losing (or 50-move rule draw)
768 for (size_t i = 0; i < rootMoves.size(); i++) {
769 int v = rootMoves[i].score;
773 // Try all moves, unless we approach or have a 50-move rule draw.
774 if (-best * 2 + cnt50 < 100)
776 for (size_t i = 0; i < rootMoves.size(); i++) {
777 if (rootMoves[i].score == best)
778 rootMoves[j++] = rootMoves[i];
781 // Try all moves that preserve the draw.
782 for (size_t i = 0; i < rootMoves.size(); i++) {
783 if (rootMoves[i].score == 0)
784 rootMoves[j++] = rootMoves[i];
787 rootMoves.resize(j, Search::RootMove(MOVE_NONE));
792 // Use the WDL tables to filter out moves that don't preserve the win or draw.
793 // This is a fallback for the case that some or all DTZ tables are missing.
795 // A return value false indicates that not all probes were successful and that
796 // no moves were filtered out.
797 bool Tablebases::root_probe_wdl(Position& pos, Search::RootMoveVector& rootMoves, Value& score)
801 int wdl = Tablebases::probe_wdl(pos, &success);
802 if (!success) return false;
803 score = wdl_to_Value[wdl + 2];
811 for (size_t i = 0; i < rootMoves.size(); i++) {
812 Move move = rootMoves[i].pv[0];
813 pos.do_move(move, st, pos.gives_check(move, ci));
814 int v = -Tablebases::probe_wdl(pos, &success);
816 if (!success) return false;
817 rootMoves[i].score = (Value)v;
823 for (size_t i = 0; i < rootMoves.size(); i++) {
824 if (rootMoves[i].score == best)
825 rootMoves[j++] = rootMoves[i];
827 rootMoves.resize(j, Search::RootMove(MOVE_NONE));