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.
10 #include "../position.h"
11 #include "../movegen.h"
12 #include "../bitboard.h"
13 #include "../search.h"
14 #include "../bitcount.h"
22 extern Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
25 int Tablebases::MaxCardinality = 0;
27 // Given a position with 6 or fewer pieces, produce a text string
28 // of the form KQPvKRP, where "KQP" represents the white pieces if
29 // mirror == 0 and the black pieces if mirror == 1.
30 static void prt_str(Position& pos, char *str, int mirror)
36 color = !mirror ? WHITE : BLACK;
37 for (pt = KING; pt >= PAWN; --pt)
38 for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
39 *str++ = pchr[6 - pt];
42 for (pt = KING; pt >= PAWN; --pt)
43 for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
44 *str++ = pchr[6 - pt];
48 // Given a position, produce a 64-bit material signature key.
49 // If the engine supports such a key, it should equal the engine's key.
50 static uint64 calc_key(Position& pos, int mirror)
57 color = !mirror ? WHITE : BLACK;
58 for (pt = PAWN; pt <= KING; ++pt)
59 for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
60 key ^= Zobrist::psq[WHITE][pt][i - 1];
62 for (pt = PAWN; pt <= KING; ++pt)
63 for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
64 key ^= Zobrist::psq[BLACK][pt][i - 1];
69 // Produce a 64-bit material key corresponding to the material combination
70 // defined by pcs[16], where pcs[1], ..., pcs[6] is the number of white
71 // pawns, ..., kings and pcs[9], ..., pcs[14] is the number of black
73 static uint64 calc_key_from_pcs(int *pcs, int mirror)
80 color = !mirror ? 0 : 8;
81 for (pt = PAWN; pt <= KING; ++pt)
82 for (i = 0; i < pcs[color + pt]; i++)
83 key ^= Zobrist::psq[WHITE][pt][i];
85 for (pt = PAWN; pt <= KING; ++pt)
86 for (i = 0; i < pcs[color + pt]; i++)
87 key ^= Zobrist::psq[BLACK][pt][i];
92 bool is_little_endian() {
101 static ubyte decompress_pairs(struct PairsData *d, uint64 idx)
103 static const bool isLittleEndian = is_little_endian();
104 return isLittleEndian ? decompress_pairs<true >(d, idx)
105 : decompress_pairs<false>(d, idx);
108 // probe_wdl_table and probe_dtz_table require similar adaptations.
109 static int probe_wdl_table(Position& pos, int *success)
112 struct TBHashEntry *ptr2;
119 // Obtain the position's material signature key.
120 key = pos.material_key();
123 if (key == (Zobrist::psq[WHITE][KING][0] ^ Zobrist::psq[BLACK][KING][0]))
126 ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
127 for (i = 0; i < HSHMAX; i++)
128 if (ptr2[i].key == key) break;
139 prt_str(pos, str, ptr->key != key);
140 if (!init_table_wdl(ptr, str)) {
146 // Memory barrier to ensure ptr->ready = 1 is not reordered.
147 __asm__ __volatile__ ("" ::: "memory");
153 int bside, mirror, cmirror;
154 if (!ptr->symmetric) {
155 if (key != ptr->key) {
158 bside = (pos.side_to_move() == WHITE);
160 cmirror = mirror = 0;
161 bside = !(pos.side_to_move() == WHITE);
164 cmirror = pos.side_to_move() == WHITE ? 0 : 8;
165 mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
169 // p[i] is to contain the square 0-63 (A1-H8) for a piece of type
170 // pc[i] ^ cmirror, where 1 = white pawn, ..., 14 = black king.
171 // Pieces of the same type are guaranteed to be consecutive.
172 if (!ptr->has_pawns) {
173 struct TBEntry_piece *entry = (struct TBEntry_piece *)ptr;
174 ubyte *pc = entry->pieces[bside];
175 for (i = 0; i < entry->num;) {
176 Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
177 (PieceType)(pc[i] & 0x07));
179 p[i++] = pop_lsb(&bb);
182 idx = encode_piece(entry, entry->norm[bside], p, entry->factor[bside]);
183 res = decompress_pairs(entry->precomp[bside], idx);
185 struct TBEntry_pawn *entry = (struct TBEntry_pawn *)ptr;
186 int k = entry->file[0].pieces[0][0] ^ cmirror;
187 Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));
190 p[i++] = pop_lsb(&bb) ^ mirror;
192 int f = pawn_file(entry, p);
193 ubyte *pc = entry->file[f].pieces[bside];
194 for (; i < entry->num;) {
195 bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
196 (PieceType)(pc[i] & 0x07));
198 p[i++] = pop_lsb(&bb) ^ mirror;
201 idx = encode_pawn(entry, entry->file[f].norm[bside], p, entry->file[f].factor[bside]);
202 res = decompress_pairs(entry->file[f].precomp[bside], idx);
205 return ((int)res) - 2;
208 static int probe_dtz_table(Position& pos, int wdl, int *success)
215 // Obtain the position's material signature key.
216 uint64 key = pos.material_key();
218 if (DTZ_table[0].key1 != key && DTZ_table[0].key2 != key) {
219 for (i = 1; i < DTZ_ENTRIES; i++)
220 if (DTZ_table[i].key1 == key) break;
221 if (i < DTZ_ENTRIES) {
222 struct DTZTableEntry table_entry = DTZ_table[i];
224 DTZ_table[i] = DTZ_table[i - 1];
225 DTZ_table[0] = table_entry;
227 struct TBHashEntry *ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
228 for (i = 0; i < HSHMAX; i++)
229 if (ptr2[i].key == key) break;
236 int mirror = (ptr->key != key);
237 prt_str(pos, str, mirror);
238 if (DTZ_table[DTZ_ENTRIES - 1].entry)
239 free_dtz_entry(DTZ_table[DTZ_ENTRIES-1].entry);
240 for (i = DTZ_ENTRIES - 1; i > 0; i--)
241 DTZ_table[i] = DTZ_table[i - 1];
242 load_dtz_table(str, calc_key(pos, mirror), calc_key(pos, !mirror));
246 ptr = DTZ_table[0].entry;
252 int bside, mirror, cmirror;
253 if (!ptr->symmetric) {
254 if (key != ptr->key) {
257 bside = (pos.side_to_move() == WHITE);
259 cmirror = mirror = 0;
260 bside = !(pos.side_to_move() == WHITE);
263 cmirror = pos.side_to_move() == WHITE ? 0 : 8;
264 mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
268 if (!ptr->has_pawns) {
269 struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr;
270 if ((entry->flags & 1) != bside && !entry->symmetric) {
274 ubyte *pc = entry->pieces;
275 for (i = 0; i < entry->num;) {
276 Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
277 (PieceType)(pc[i] & 0x07));
279 p[i++] = pop_lsb(&bb);
282 idx = encode_piece((struct TBEntry_piece *)entry, entry->norm, p, entry->factor);
283 res = decompress_pairs(entry->precomp, idx);
285 if (entry->flags & 2)
286 res = entry->map[entry->map_idx[wdl_to_map[wdl + 2]] + res];
288 if (!(entry->flags & pa_flags[wdl + 2]) || (wdl & 1))
291 struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *)ptr;
292 int k = entry->file[0].pieces[0] ^ cmirror;
293 Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));
296 p[i++] = pop_lsb(&bb) ^ mirror;
298 int f = pawn_file((struct TBEntry_pawn *)entry, p);
299 if ((entry->flags[f] & 1) != bside) {
303 ubyte *pc = entry->file[f].pieces;
304 for (; i < entry->num;) {
305 bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
306 (PieceType)(pc[i] & 0x07));
308 p[i++] = pop_lsb(&bb) ^ mirror;
311 idx = encode_pawn((struct TBEntry_pawn *)entry, entry->file[f].norm, p, entry->file[f].factor);
312 res = decompress_pairs(entry->file[f].precomp, idx);
314 if (entry->flags[f] & 2)
315 res = entry->map[entry->map_idx[f][wdl_to_map[wdl + 2]] + res];
317 if (!(entry->flags[f] & pa_flags[wdl + 2]) || (wdl & 1))
324 // Add underpromotion captures to list of captures.
325 static ExtMove *add_underprom_caps(Position& pos, ExtMove *stack, ExtMove *end)
327 ExtMove *moves, *extra = end;
329 for (moves = stack; moves < end; moves++) {
330 Move move = moves->move;
331 if (type_of(move) == PROMOTION && !pos.empty(to_sq(move))) {
332 (*extra++).move = (Move)(move - (1 << 12));
333 (*extra++).move = (Move)(move - (2 << 12));
334 (*extra++).move = (Move)(move - (3 << 12));
341 static int probe_ab(Position& pos, int alpha, int beta, int *success)
345 ExtMove *moves, *end;
348 // Generate (at least) all legal non-ep captures including (under)promotions.
349 // It is OK to generate more, as long as they are filtered out below.
350 if (!pos.checkers()) {
351 end = generate<CAPTURES>(pos, stack);
352 // Since underpromotion captures are not included, we need to add them.
353 end = add_underprom_caps(pos, stack, end);
355 end = generate<EVASIONS>(pos, stack);
359 for (moves = stack; moves < end; moves++) {
360 Move capture = moves->move;
361 if (!pos.capture(capture) || type_of(capture) == ENPASSANT
362 || !pos.legal(capture, ci.pinned))
364 pos.do_move(capture, st, ci, pos.gives_check(capture, ci));
365 v = -probe_ab(pos, -beta, -alpha, success);
366 pos.undo_move(capture);
367 if (*success == 0) return 0;
377 v = probe_wdl_table(pos, success);
378 if (*success == 0) return 0;
380 *success = 1 + (alpha > 0);
388 // Probe the WDL table for a particular position.
389 // If *success != 0, the probe was successful.
390 // The return value is from the point of view of the side to move:
392 // -1 : loss, but draw under 50-move rule
394 // 1 : win, but draw under 50-move rule
396 int Tablebases::probe_wdl(Position& pos, int *success)
401 v = probe_ab(pos, -2, 2, success);
403 // If en passant is not possible, we are done.
404 if (pos.ep_square() == SQ_NONE)
406 if (!(*success)) return 0;
408 // Now handle en passant.
410 // Generate (at least) all legal en passant captures.
412 ExtMove *moves, *end;
416 end = generate<CAPTURES>(pos, stack);
418 end = generate<EVASIONS>(pos, stack);
422 for (moves = stack; moves < end; moves++) {
423 Move capture = moves->move;
424 if (type_of(capture) != ENPASSANT
425 || !pos.legal(capture, ci.pinned))
427 pos.do_move(capture, st, ci, pos.gives_check(capture, ci));
428 int v0 = -probe_ab(pos, -2, 2, success);
429 pos.undo_move(capture);
430 if (*success == 0) return 0;
431 if (v0 > v1) v1 = v0;
436 // Check whether there is at least one legal non-ep move.
437 for (moves = stack; moves < end; moves++) {
438 Move capture = moves->move;
439 if (type_of(capture) == ENPASSANT) continue;
440 if (pos.legal(capture, ci.pinned)) break;
442 if (moves == end && !pos.checkers()) {
443 end = generate<QUIETS>(pos, end);
444 for (; moves < end; moves++) {
445 Move move = moves->move;
446 if (pos.legal(move, ci.pinned))
450 // If not, then we are forced to play the losing ep capture.
459 // This routine treats a position with en passant captures as one without.
460 static int probe_dtz_no_ep(Position& pos, int *success)
464 wdl = probe_ab(pos, -2, 2, success);
465 if (*success == 0) return 0;
467 if (wdl == 0) return 0;
470 return wdl == 2 ? 1 : 101;
473 ExtMove *moves, *end = NULL;
478 // Generate at least all legal non-capturing pawn moves
479 // including non-capturing promotions.
481 end = generate<NON_EVASIONS>(pos, stack);
483 end = generate<EVASIONS>(pos, stack);
485 for (moves = stack; moves < end; moves++) {
486 Move move = moves->move;
487 if (type_of(pos.moved_piece(move)) != PAWN || pos.capture(move)
488 || !pos.legal(move, ci.pinned))
490 pos.do_move(move, st, ci, pos.gives_check(move, ci));
491 int v = -probe_ab(pos, -2, -wdl + 1, success);
493 if (*success == 0) return 0;
495 return v == 2 ? 1 : 101;
499 dtz = 1 + probe_dtz_table(pos, wdl, success);
501 if (wdl & 1) dtz += 100;
502 return wdl >= 0 ? dtz : -dtz;
507 for (moves = stack; moves < end; moves++) {
508 Move move = moves->move;
509 if (pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN
510 || !pos.legal(move, ci.pinned))
512 pos.do_move(move, st, ci, pos.gives_check(move, ci));
513 int v = -Tablebases::probe_dtz(pos, success);
515 if (*success == 0) return 0;
516 if (v > 0 && v + 1 < best)
523 end = generate<NON_EVASIONS>(pos, stack);
525 end = generate<EVASIONS>(pos, stack);
526 for (moves = stack; moves < end; moves++) {
528 Move move = moves->move;
529 if (!pos.legal(move, ci.pinned))
531 pos.do_move(move, st, ci, pos.gives_check(move, ci));
532 if (st.rule50 == 0) {
533 if (wdl == -2) v = -1;
535 v = probe_ab(pos, 1, 2, success);
536 v = (v == 2) ? 0 : -101;
539 v = -Tablebases::probe_dtz(pos, success) - 1;
542 if (*success == 0) return 0;
550 static int wdl_to_dtz[] = {
554 // Probe the DTZ table for a particular position.
555 // If *success != 0, the probe was successful.
556 // The return value is from the point of view of the side to move:
557 // n < -100 : loss, but draw under 50-move rule
558 // -100 <= n < -1 : loss in n ply (assuming 50-move counter == 0)
560 // 1 < n <= 100 : win in n ply (assuming 50-move counter == 0)
561 // 100 < n : win, but draw under 50-move rule
563 // The return value n can be off by 1: a return value -n can mean a loss
564 // in n+1 ply and a return value +n can mean a win in n+1 ply. This
565 // cannot happen for tables with positions exactly on the "edge" of
568 // This implies that if dtz > 0 is returned, the position is certainly
569 // a win if dtz + 50-move-counter <= 99. Care must be taken that the engine
570 // picks moves that preserve dtz + 50-move-counter <= 99.
572 // If n = 100 immediately after a capture or pawn move, then the position
573 // is also certainly a win, and during the whole phase until the next
574 // capture or pawn move, the inequality to be preserved is
575 // dtz + 50-movecounter <= 100.
577 // In short, if a move is available resulting in dtz + 50-move-counter <= 99,
578 // then do not accept moves leading to dtz + 50-move-counter == 100.
580 int Tablebases::probe_dtz(Position& pos, int *success)
583 int v = probe_dtz_no_ep(pos, success);
585 if (pos.ep_square() == SQ_NONE)
587 if (*success == 0) return 0;
589 // Now handle en passant.
593 ExtMove *moves, *end;
597 end = generate<CAPTURES>(pos, stack);
599 end = generate<EVASIONS>(pos, stack);
602 for (moves = stack; moves < end; moves++) {
603 Move capture = moves->move;
604 if (type_of(capture) != ENPASSANT
605 || !pos.legal(capture, ci.pinned))
607 pos.do_move(capture, st, ci, pos.gives_check(capture, ci));
608 int v0 = -probe_ab(pos, -2, 2, success);
609 pos.undo_move(capture);
610 if (*success == 0) return 0;
611 if (v0 > v1) v1 = v0;
614 v1 = wdl_to_dtz[v1 + 2];
619 if (v1 >= 0 || v1 < 100)
621 } else if (v > 100) {
627 } else if (v1 >= 0) {
630 for (moves = stack; moves < end; moves++) {
631 Move move = moves->move;
632 if (type_of(move) == ENPASSANT) continue;
633 if (pos.legal(move, ci.pinned)) break;
635 if (moves == end && !pos.checkers()) {
636 end = generate<QUIETS>(pos, end);
637 for (; moves < end; moves++) {
638 Move move = moves->move;
639 if (pos.legal(move, ci.pinned))
651 // Check whether there has been at least one repetition of positions
652 // since the last capture or pawn move.
653 static int has_repeated(StateInfo *st)
656 int i = 4, e = std::min(st->rule50, st->pliesFromNull);
659 StateInfo *stp = st->previous->previous;
661 stp = stp->previous->previous;
662 if (stp->key == st->key)
670 static Value wdl_to_Value[5] = {
671 -VALUE_MATE + MAX_PLY + 1,
675 VALUE_MATE - MAX_PLY - 1
678 // Use the DTZ tables to filter out moves that don't preserve the win or draw.
679 // If the position is lost, but DTZ is fairly high, only keep moves that
682 // A return value false indicates that not all probes were successful and that
683 // no moves were filtered out.
684 bool Tablebases::root_probe(Position& pos, Search::RootMoveVector& rootMoves, Value& score)
688 int dtz = probe_dtz(pos, &success);
689 if (!success) return false;
695 for (size_t i = 0; i < rootMoves.size(); i++) {
696 Move move = rootMoves[i].pv[0];
697 pos.do_move(move, st, ci, pos.gives_check(move, ci));
699 if (pos.checkers() && dtz > 0) {
701 if (generate<LEGAL>(pos, s) == s)
705 if (st.rule50 != 0) {
706 v = -Tablebases::probe_dtz(pos, &success);
710 v = -Tablebases::probe_wdl(pos, &success);
711 v = wdl_to_dtz[v + 2];
715 if (!success) return false;
716 rootMoves[i].score = (Value)v;
719 // Obtain 50-move counter for the root position.
720 // In Stockfish there seems to be no clean way, so we do it like this:
721 int cnt50 = st.previous->rule50;
723 // Use 50-move counter to determine whether the root position is
724 // won, lost or drawn.
727 wdl = (dtz + cnt50 <= 100) ? 2 : 1;
729 wdl = (-dtz + cnt50 <= 100) ? -2 : -1;
731 // Determine the score to report to the user.
732 score = wdl_to_Value[wdl + 2];
733 // If the position is winning or losing, but too few moves left, adjust the
734 // score to show how close it is to winning or losing.
735 // NOTE: int(PawnValueEg) is used as scaling factor in score_to_uci().
736 if (wdl == 1 && dtz <= 100)
737 score = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200);
738 else if (wdl == -1 && dtz >= -100)
739 score = -(Value)(((200 + dtz - cnt50) * int(PawnValueEg)) / 200);
741 // Now be a bit smart about filtering out moves.
743 if (dtz > 0) { // winning (or 50-move rule draw)
745 for (size_t i = 0; i < rootMoves.size(); i++) {
746 int v = rootMoves[i].score;
747 if (v > 0 && v < best)
751 // If the current phase has not seen repetitions, then try all moves
752 // that stay safely within the 50-move budget, if there are any.
753 if (!has_repeated(st.previous) && best + cnt50 <= 99)
755 for (size_t i = 0; i < rootMoves.size(); i++) {
756 int v = rootMoves[i].score;
757 if (v > 0 && v <= max)
758 rootMoves[j++] = rootMoves[i];
760 } else if (dtz < 0) { // losing (or 50-move rule draw)
762 for (size_t i = 0; i < rootMoves.size(); i++) {
763 int v = rootMoves[i].score;
767 // Try all moves, unless we approach or have a 50-move rule draw.
768 if (-best * 2 + cnt50 < 100)
770 for (size_t i = 0; i < rootMoves.size(); i++) {
771 if (rootMoves[i].score == best)
772 rootMoves[j++] = rootMoves[i];
775 // Try all moves that preserve the draw.
776 for (size_t i = 0; i < rootMoves.size(); i++) {
777 if (rootMoves[i].score == 0)
778 rootMoves[j++] = rootMoves[i];
781 rootMoves.resize(j, Search::RootMove(MOVE_NONE));
786 // Use the WDL tables to filter out moves that don't preserve the win or draw.
787 // This is a fallback for the case that some or all DTZ tables are missing.
789 // A return value false indicates that not all probes were successful and that
790 // no moves were filtered out.
791 bool Tablebases::root_probe_wdl(Position& pos, Search::RootMoveVector& rootMoves, Value& score)
795 int wdl = Tablebases::probe_wdl(pos, &success);
796 if (!success) return false;
797 score = wdl_to_Value[wdl + 2];
805 for (size_t i = 0; i < rootMoves.size(); i++) {
806 Move move = rootMoves[i].pv[0];
807 pos.do_move(move, st, ci, pos.gives_check(move, ci));
808 int v = -Tablebases::probe_wdl(pos, &success);
810 if (!success) return false;
811 rootMoves[i].score = (Value)v;
817 for (size_t i = 0; i < rootMoves.size(); i++) {
818 if (rootMoves[i].score == best)
819 rootMoves[j++] = rootMoves[i];
821 rootMoves.resize(j, Search::RootMove(MOVE_NONE));