git.sesse.net Git - stockfish/blob - src/syzygy/tbprobe.cpp

   1 /*
   2   Copyright (c) 2013 Ronald de Man
   3   This file may be redistributed and/or modified without restrictions.
   4
   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.
   8 */
   9
  10 #define NOMINMAX
  11
  12 #include <algorithm>
  13
  14 #include "../position.h"
  15 #include "../movegen.h"
  16 #include "../bitboard.h"
  17 #include "../search.h"
  18
  19 #include "tbprobe.h"
  20 #include "tbcore.h"
  21
  22 #include "tbcore.cpp"
  23
  24 namespace Zobrist {
  25   extern Key psq[PIECE_NB][SQUARE_NB];
  26 }
  27
  28 int Tablebases::MaxCardinality = 0;
  29
  30 // Given a position with 6 or fewer pieces, produce a text string
  31 // of the form KQPvKRP, where "KQP" represents the white pieces if
  32 // mirror == 0 and the black pieces if mirror == 1.
  33 static void prt_str(Position& pos, char *str, int mirror)
  34 {
  35   Color color;
  36   PieceType pt;
  37   int i;
  38
  39   color = !mirror ? WHITE : BLACK;
  40   for (pt = KING; pt >= PAWN; --pt)
  41     for (i = popcount(pos.pieces(color, pt)); i > 0; i--)
  42       *str++ = pchr[6 - pt];
  43   *str++ = 'v';
  44   color = ~color;
  45   for (pt = KING; pt >= PAWN; --pt)
  46     for (i = popcount(pos.pieces(color, pt)); i > 0; i--)
  47       *str++ = pchr[6 - pt];
  48   *str++ = 0;
  49 }
  50
  51 // Given a position, produce a 64-bit material signature key.
  52 // If the engine supports such a key, it should equal the engine's key.
  53 static uint64 calc_key(Position& pos, int mirror)
  54 {
  55   Color color;
  56   PieceType pt;
  57   int i;
  58   uint64 key = 0;
  59
  60   color = !mirror ? WHITE : BLACK;
  61   for (pt = PAWN; pt <= KING; ++pt)
  62     for (i = popcount(pos.pieces(color, pt)); i > 0; i--)
  63       key ^= Zobrist::psq[make_piece(WHITE, pt)][i - 1];
  64   color = ~color;
  65   for (pt = PAWN; pt <= KING; ++pt)
  66     for (i = popcount(pos.pieces(color, pt)); i > 0; i--)
  67       key ^= Zobrist::psq[make_piece(BLACK, pt)][i - 1];
  68
  69   return key;
  70 }
  71
  72 // Produce a 64-bit material key corresponding to the material combination
  73 // defined by pcs[16], where pcs[1], ..., pcs[6] is the number of white
  74 // pawns, ..., kings and pcs[9], ..., pcs[14] is the number of black
  75 // pawns, ..., kings.
  76 static uint64 calc_key_from_pcs(int *pcs, int mirror)
  77 {
  78   int color;
  79   PieceType pt;
  80   int i;
  81   uint64 key = 0;
  82
  83   color = !mirror ? 0 : 8;
  84   for (pt = PAWN; pt <= KING; ++pt)
  85     for (i = 0; i < pcs[color + pt]; i++)
  86       key ^= Zobrist::psq[make_piece(WHITE, pt)][i];
  87   color ^= 8;
  88   for (pt = PAWN; pt <= KING; ++pt)
  89     for (i = 0; i < pcs[color + pt]; i++)
  90       key ^= Zobrist::psq[make_piece(BLACK, pt)][i];
  91
  92   return key;
  93 }
  94
  95 bool is_little_endian() {
  96   union {
  97     int i;
  98     char c[sizeof(int)];
  99   } x;
 100   x.i = 1;
 101   return x.c[0] == 1;
 102 }
 103
 104 static ubyte decompress_pairs(struct PairsData *d, uint64 idx)
 105 {
 106   static const bool isLittleEndian = is_little_endian();
 107   return isLittleEndian ? decompress_pairs<true >(d, idx)
 108                         : decompress_pairs<false>(d, idx);
 109 }
 110
 111 // probe_wdl_table and probe_dtz_table require similar adaptations.
 112 static int probe_wdl_table(Position& pos, int *success)
 113 {
 114   struct TBEntry *ptr;
 115   struct TBHashEntry *ptr2;
 116   uint64 idx;
 117   uint64 key;
 118   int i;
 119   ubyte res;
 120   int p[TBPIECES];
 121
 122   // Obtain the position's material signature key.
 123   key = pos.material_key();
 124
 125   // Test for KvK.
 126   if (key == (Zobrist::psq[W_KING][0] ^ Zobrist::psq[B_KING][0]))
 127     return 0;
 128
 129   ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
 130   for (i = 0; i < HSHMAX; i++)
 131     if (ptr2[i].key == key) break;
 132   if (i == HSHMAX) {
 133     *success = 0;
 134     return 0;
 135   }
 136
 137   ptr = ptr2[i].ptr;
 138   if (!ptr->ready) {
 139     LOCK(TB_mutex);
 140     if (!ptr->ready) {
 141       char str[16];
 142       prt_str(pos, str, ptr->key != key);
 143       if (!init_table_wdl(ptr, str)) {
 144         ptr2[i].key = 0ULL;
 145         *success = 0;
 146         UNLOCK(TB_mutex);
 147         return 0;
 148       }
 149       // Memory barrier to ensure ptr->ready = 1 is not reordered.
 150 #ifdef _MSC_VER
 151       _ReadWriteBarrier();
 152 #else
 153       __asm__ __volatile__ ("" ::: "memory");
 154 #endif
 155       ptr->ready = 1;
 156     }
 157     UNLOCK(TB_mutex);
 158   }
 159
 160   int bside, mirror, cmirror;
 161   if (!ptr->symmetric) {
 162     if (key != ptr->key) {
 163       cmirror = 8;
 164       mirror = 0x38;
 165       bside = (pos.side_to_move() == WHITE);
 166     } else {
 167       cmirror = mirror = 0;
 168       bside = !(pos.side_to_move() == WHITE);
 169     }
 170   } else {
 171     cmirror = pos.side_to_move() == WHITE ? 0 : 8;
 172     mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
 173     bside = 0;
 174   }
 175
 176   // p[i] is to contain the square 0-63 (A1-H8) for a piece of type
 177   // pc[i] ^ cmirror, where 1 = white pawn, ..., 14 = black king.
 178   // Pieces of the same type are guaranteed to be consecutive.
 179   if (!ptr->has_pawns) {
 180     struct TBEntry_piece *entry = (struct TBEntry_piece *)ptr;
 181     ubyte *pc = entry->pieces[bside];
 182     for (i = 0; i < entry->num;) {
 183       Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
 184                                       (PieceType)(pc[i] & 0x07));
 185       do {
 186         p[i++] = pop_lsb(&bb);
 187       } while (bb);
 188     }
 189     idx = encode_piece(entry, entry->norm[bside], p, entry->factor[bside]);
 190     res = decompress_pairs(entry->precomp[bside], idx);
 191   } else {
 192     struct TBEntry_pawn *entry = (struct TBEntry_pawn *)ptr;
 193     int k = entry->file[0].pieces[0][0] ^ cmirror;
 194     Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));
 195     i = 0;
 196     do {
 197       p[i++] = pop_lsb(&bb) ^ mirror;
 198     } while (bb);
 199     int f = pawn_file(entry, p);
 200     ubyte *pc = entry->file[f].pieces[bside];
 201     for (; i < entry->num;) {
 202       bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
 203                                     (PieceType)(pc[i] & 0x07));
 204       do {
 205         p[i++] = pop_lsb(&bb) ^ mirror;
 206       } while (bb);
 207     }
 208     idx = encode_pawn(entry, entry->file[f].norm[bside], p, entry->file[f].factor[bside]);
 209     res = decompress_pairs(entry->file[f].precomp[bside], idx);
 210   }
 211
 212   return ((int)res) - 2;
 213 }
 214
 215 static int probe_dtz_table(Position& pos, int wdl, int *success)
 216 {
 217   struct TBEntry *ptr;
 218   uint64 idx;
 219   int i, res;
 220   int p[TBPIECES];
 221
 222   // Obtain the position's material signature key.
 223   uint64 key = pos.material_key();
 224
 225   if (DTZ_table[0].key1 != key && DTZ_table[0].key2 != key) {
 226     for (i = 1; i < DTZ_ENTRIES; i++)
 227       if (DTZ_table[i].key1 == key) break;
 228     if (i < DTZ_ENTRIES) {
 229       struct DTZTableEntry table_entry = DTZ_table[i];
 230       for (; i > 0; i--)
 231         DTZ_table[i] = DTZ_table[i - 1];
 232       DTZ_table[0] = table_entry;
 233     } else {
 234       struct TBHashEntry *ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
 235       for (i = 0; i < HSHMAX; i++)
 236         if (ptr2[i].key == key) break;
 237       if (i == HSHMAX) {
 238         *success = 0;
 239         return 0;
 240       }
 241       ptr = ptr2[i].ptr;
 242       char str[16];
 243       int mirror = (ptr->key != key);
 244       prt_str(pos, str, mirror);
 245       if (DTZ_table[DTZ_ENTRIES - 1].entry)
 246         free_dtz_entry(DTZ_table[DTZ_ENTRIES-1].entry);
 247       for (i = DTZ_ENTRIES - 1; i > 0; i--)
 248         DTZ_table[i] = DTZ_table[i - 1];
 249       load_dtz_table(str, calc_key(pos, mirror), calc_key(pos, !mirror));
 250     }
 251   }
 252
 253   ptr = DTZ_table[0].entry;
 254   if (!ptr) {
 255     *success = 0;
 256     return 0;
 257   }
 258
 259   int bside, mirror, cmirror;
 260   if (!ptr->symmetric) {
 261     if (key != ptr->key) {
 262       cmirror = 8;
 263       mirror = 0x38;
 264       bside = (pos.side_to_move() == WHITE);
 265     } else {
 266       cmirror = mirror = 0;
 267       bside = !(pos.side_to_move() == WHITE);
 268     }
 269   } else {
 270     cmirror = pos.side_to_move() == WHITE ? 0 : 8;
 271     mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
 272     bside = 0;
 273   }
 274
 275   if (!ptr->has_pawns) {
 276     struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr;
 277     if ((entry->flags & 1) != bside && !entry->symmetric) {
 278       *success = -1;
 279       return 0;
 280     }
 281     ubyte *pc = entry->pieces;
 282     for (i = 0; i < entry->num;) {
 283       Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
 284                                     (PieceType)(pc[i] & 0x07));
 285       do {
 286         p[i++] = pop_lsb(&bb);
 287       } while (bb);
 288     }
 289     idx = encode_piece((struct TBEntry_piece *)entry, entry->norm, p, entry->factor);
 290     res = decompress_pairs(entry->precomp, idx);
 291
 292     if (entry->flags & 2)
 293       res = entry->map[entry->map_idx[wdl_to_map[wdl + 2]] + res];
 294
 295     if (!(entry->flags & pa_flags[wdl + 2]) || (wdl & 1))
 296       res *= 2;
 297   } else {
 298     struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *)ptr;
 299     int k = entry->file[0].pieces[0] ^ cmirror;
 300     Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));
 301     i = 0;
 302     do {
 303       p[i++] = pop_lsb(&bb) ^ mirror;
 304     } while (bb);
 305     int f = pawn_file((struct TBEntry_pawn *)entry, p);
 306     if ((entry->flags[f] & 1) != bside) {
 307       *success = -1;
 308       return 0;
 309     }
 310     ubyte *pc = entry->file[f].pieces;
 311     for (; i < entry->num;) {
 312       bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),
 313                             (PieceType)(pc[i] & 0x07));
 314       do {
 315         p[i++] = pop_lsb(&bb) ^ mirror;
 316       } while (bb);
 317     }
 318     idx = encode_pawn((struct TBEntry_pawn *)entry, entry->file[f].norm, p, entry->file[f].factor);
 319     res = decompress_pairs(entry->file[f].precomp, idx);
 320
 321     if (entry->flags[f] & 2)
 322       res = entry->map[entry->map_idx[f][wdl_to_map[wdl + 2]] + res];
 323
 324     if (!(entry->flags[f] & pa_flags[wdl + 2]) || (wdl & 1))
 325       res *= 2;
 326   }
 327
 328   return res;
 329 }
 330
 331 // Add underpromotion captures to list of captures.
 332 static ExtMove *add_underprom_caps(Position& pos, ExtMove *stack, ExtMove *end)
 333 {
 334   ExtMove *moves, *extra = end;
 335
 336   for (moves = stack; moves < end; moves++) {
 337     Move move = moves->move;
 338     if (type_of(move) == PROMOTION && !pos.empty(to_sq(move))) {
 339       (*extra++).move = (Move)(move - (1 << 12));
 340       (*extra++).move = (Move)(move - (2 << 12));
 341       (*extra++).move = (Move)(move - (3 << 12));
 342     }
 343   }
 344
 345   return extra;
 346 }
 347
 348 static int probe_ab(Position& pos, int alpha, int beta, int *success)
 349 {
 350   int v;
 351   ExtMove stack[64];
 352   ExtMove *moves, *end;
 353   StateInfo st;
 354
 355   // Generate (at least) all legal non-ep captures including (under)promotions.
 356   // It is OK to generate more, as long as they are filtered out below.
 357   if (!pos.checkers()) {
 358     end = generate<CAPTURES>(pos, stack);
 359     // Since underpromotion captures are not included, we need to add them.
 360     end = add_underprom_caps(pos, stack, end);
 361   } else
 362     end = generate<EVASIONS>(pos, stack);
 363
 364   for (moves = stack; moves < end; moves++) {
 365     Move capture = moves->move;
 366     if (!pos.capture(capture) || type_of(capture) == ENPASSANT
 367                         || !pos.legal(capture))
 368       continue;
 369     pos.do_move(capture, st, pos.gives_check(capture));
 370     v = -probe_ab(pos, -beta, -alpha, success);
 371     pos.undo_move(capture);
 372     if (*success == 0) return 0;
 373     if (v > alpha) {
 374       if (v >= beta) {
 375         *success = 2;
 376         return v;
 377       }
 378       alpha = v;
 379     }
 380   }
 381
 382   v = probe_wdl_table(pos, success);
 383   if (*success == 0) return 0;
 384   if (alpha >= v) {
 385     *success = 1 + (alpha > 0);
 386     return alpha;
 387   } else {
 388     *success = 1;
 389     return v;
 390   }
 391 }
 392
 393 // Probe the WDL table for a particular position.
 394 // If *success != 0, the probe was successful.
 395 // The return value is from the point of view of the side to move:
 396 // -2 : loss
 397 // -1 : loss, but draw under 50-move rule
 398 //  0 : draw
 399 //  1 : win, but draw under 50-move rule
 400 //  2 : win
 401 int Tablebases::probe_wdl(Position& pos, int *success)
 402 {
 403   int v;
 404
 405   *success = 1;
 406   v = probe_ab(pos, -2, 2, success);
 407
 408   // If en passant is not possible, we are done.
 409   if (pos.ep_square() == SQ_NONE)
 410     return v;
 411   if (!(*success)) return 0;
 412
 413   // Now handle en passant.
 414   int v1 = -3;
 415   // Generate (at least) all legal en passant captures.
 416   ExtMove stack[192];
 417   ExtMove *moves, *end;
 418   StateInfo st;
 419
 420   if (!pos.checkers())
 421     end = generate<CAPTURES>(pos, stack);
 422   else
 423     end = generate<EVASIONS>(pos, stack);
 424
 425   for (moves = stack; moves < end; moves++) {
 426     Move capture = moves->move;
 427     if (type_of(capture) != ENPASSANT
 428           || !pos.legal(capture))
 429       continue;
 430     pos.do_move(capture, st, pos.gives_check(capture));
 431     int v0 = -probe_ab(pos, -2, 2, success);
 432     pos.undo_move(capture);
 433     if (*success == 0) return 0;
 434     if (v0 > v1) v1 = v0;
 435   }
 436   if (v1 > -3) {
 437     if (v1 >= v) v = v1;
 438     else if (v == 0) {
 439       // Check whether there is at least one legal non-ep move.
 440       for (moves = stack; moves < end; moves++) {
 441         Move capture = moves->move;
 442         if (type_of(capture) == ENPASSANT) continue;
 443         if (pos.legal(capture)) break;
 444       }
 445       if (moves == end && !pos.checkers()) {
 446         end = generate<QUIETS>(pos, end);
 447         for (; moves < end; moves++) {
 448           Move move = moves->move;
 449           if (pos.legal(move))
 450             break;
 451         }
 452       }
 453       // If not, then we are forced to play the losing ep capture.
 454       if (moves == end)
 455         v = v1;
 456     }
 457   }
 458
 459   return v;
 460 }
 461
 462 // This routine treats a position with en passant captures as one without.
 463 static int probe_dtz_no_ep(Position& pos, int *success)
 464 {
 465   int wdl, dtz;
 466
 467   wdl = probe_ab(pos, -2, 2, success);
 468   if (*success == 0) return 0;
 469
 470   if (wdl == 0) return 0;
 471
 472   if (*success == 2)
 473     return wdl == 2 ? 1 : 101;
 474
 475   ExtMove stack[192];
 476   ExtMove *moves, *end = NULL;
 477   StateInfo st;
 478
 479   if (wdl > 0) {
 480     // Generate at least all legal non-capturing pawn moves
 481     // including non-capturing promotions.
 482     if (!pos.checkers())
 483       end = generate<NON_EVASIONS>(pos, stack);
 484     else
 485       end = generate<EVASIONS>(pos, stack);
 486
 487     for (moves = stack; moves < end; moves++) {
 488       Move move = moves->move;
 489       if (type_of(pos.moved_piece(move)) != PAWN || pos.capture(move)
 490                 || !pos.legal(move))
 491         continue;
 492       pos.do_move(move, st, pos.gives_check(move));
 493       int v = -Tablebases::probe_wdl(pos, success);
 494       pos.undo_move(move);
 495       if (*success == 0) return 0;
 496       if (v == wdl)
 497         return v == 2 ? 1 : 101;
 498     }
 499   }
 500
 501   dtz = 1 + probe_dtz_table(pos, wdl, success);
 502   if (*success >= 0) {
 503     if (wdl & 1) dtz += 100;
 504     return wdl >= 0 ? dtz : -dtz;
 505   }
 506
 507   if (wdl > 0) {
 508     int best = 0xffff;
 509     for (moves = stack; moves < end; moves++) {
 510       Move move = moves->move;
 511       if (pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN
 512                 || !pos.legal(move))
 513         continue;
 514       pos.do_move(move, st, pos.gives_check(move));
 515       int v = -Tablebases::probe_dtz(pos, success);
 516       pos.undo_move(move);
 517       if (*success == 0) return 0;
 518       if (v > 0 && v + 1 < best)
 519         best = v + 1;
 520     }
 521     return best;
 522   } else {
 523     int best = -1;
 524     if (!pos.checkers())
 525       end = generate<NON_EVASIONS>(pos, stack);
 526     else
 527       end = generate<EVASIONS>(pos, stack);
 528     for (moves = stack; moves < end; moves++) {
 529       int v;
 530       Move move = moves->move;
 531       if (!pos.legal(move))
 532         continue;
 533       pos.do_move(move, st, pos.gives_check(move));
 534       if (st.rule50 == 0) {
 535         if (wdl == -2) v = -1;
 536         else {
 537           v = probe_ab(pos, 1, 2, success);
 538           v = (v == 2) ? 0 : -101;
 539         }
 540       } else {
 541         v = -Tablebases::probe_dtz(pos, success) - 1;
 542       }
 543       pos.undo_move(move);
 544       if (*success == 0) return 0;
 545       if (v < best)
 546         best = v;
 547     }
 548     return best;
 549   }
 550 }
 551
 552 static int wdl_to_dtz[] = {
 553   -1, -101, 0, 101, 1
 554 };
 555
 556 // Probe the DTZ table for a particular position.
 557 // If *success != 0, the probe was successful.
 558 // The return value is from the point of view of the side to move:
 559 //         n < -100 : loss, but draw under 50-move rule
 560 // -100 <= n < -1   : loss in n ply (assuming 50-move counter == 0)
 561 //         0        : draw
 562 //     1 < n <= 100 : win in n ply (assuming 50-move counter == 0)
 563 //   100 < n        : win, but draw under 50-move rule
 564 //
 565 // The return value n can be off by 1: a return value -n can mean a loss
 566 // in n+1 ply and a return value +n can mean a win in n+1 ply. This
 567 // cannot happen for tables with positions exactly on the "edge" of
 568 // the 50-move rule.
 569 //
 570 // This implies that if dtz > 0 is returned, the position is certainly
 571 // a win if dtz + 50-move-counter <= 99. Care must be taken that the engine
 572 // picks moves that preserve dtz + 50-move-counter <= 99.
 573 //
 574 // If n = 100 immediately after a capture or pawn move, then the position
 575 // is also certainly a win, and during the whole phase until the next
 576 // capture or pawn move, the inequality to be preserved is
 577 // dtz + 50-movecounter <= 100.
 578 //
 579 // In short, if a move is available resulting in dtz + 50-move-counter <= 99,
 580 // then do not accept moves leading to dtz + 50-move-counter == 100.
 581 //
 582 int Tablebases::probe_dtz(Position& pos, int *success)
 583 {
 584   *success = 1;
 585   int v = probe_dtz_no_ep(pos, success);
 586
 587   if (pos.ep_square() == SQ_NONE)
 588     return v;
 589   if (*success == 0) return 0;
 590
 591   // Now handle en passant.
 592   int v1 = -3;
 593
 594   ExtMove stack[192];
 595   ExtMove *moves, *end;
 596   StateInfo st;
 597
 598   if (!pos.checkers())
 599     end = generate<CAPTURES>(pos, stack);
 600   else
 601     end = generate<EVASIONS>(pos, stack);
 602
 603   for (moves = stack; moves < end; moves++) {
 604     Move capture = moves->move;
 605     if (type_of(capture) != ENPASSANT
 606                 || !pos.legal(capture))
 607       continue;
 608     pos.do_move(capture, st, pos.gives_check(capture));
 609     int v0 = -probe_ab(pos, -2, 2, success);
 610     pos.undo_move(capture);
 611     if (*success == 0) return 0;
 612     if (v0 > v1) v1 = v0;
 613   }
 614   if (v1 > -3) {
 615     v1 = wdl_to_dtz[v1 + 2];
 616     if (v < -100) {
 617       if (v1 >= 0)
 618         v = v1;
 619     } else if (v < 0) {
 620       if (v1 >= 0 || v1 < -100)
 621         v = v1;
 622     } else if (v > 100) {
 623       if (v1 > 0)
 624         v = v1;
 625     } else if (v > 0) {
 626       if (v1 == 1)
 627         v = v1;
 628     } else if (v1 >= 0) {
 629       v = v1;
 630     } else {
 631       for (moves = stack; moves < end; moves++) {
 632         Move move = moves->move;
 633         if (type_of(move) == ENPASSANT) continue;
 634         if (pos.legal(move)) break;
 635       }
 636       if (moves == end && !pos.checkers()) {
 637         end = generate<QUIETS>(pos, end);
 638         for (; moves < end; moves++) {
 639           Move move = moves->move;
 640           if (pos.legal(move))
 641             break;
 642         }
 643       }
 644       if (moves == end)
 645         v = v1;
 646     }
 647   }
 648
 649   return v;
 650 }
 651
 652 // Check whether there has been at least one repetition of positions
 653 // since the last capture or pawn move.
 654 static int has_repeated(StateInfo *st)
 655 {
 656   while (1) {
 657     int i = 4, e = std::min(st->rule50, st->pliesFromNull);
 658     if (e < i)
 659       return 0;
 660     StateInfo *stp = st->previous->previous;
 661     do {
 662       stp = stp->previous->previous;
 663       if (stp->key == st->key)
 664         return 1;
 665       i += 2;
 666     } while (i <= e);
 667     st = st->previous;
 668   }
 669 }
 670
 671 static Value wdl_to_Value[5] = {
 672   -VALUE_MATE + MAX_PLY + 1,
 673   VALUE_DRAW - 2,
 674   VALUE_DRAW,
 675   VALUE_DRAW + 2,
 676   VALUE_MATE - MAX_PLY - 1
 677 };
 678
 679 // Use the DTZ tables to filter out moves that don't preserve the win or draw.
 680 // If the position is lost, but DTZ is fairly high, only keep moves that
 681 // maximise DTZ.
 682 //
 683 // A return value false indicates that not all probes were successful and that
 684 // no moves were filtered out.
 685 bool Tablebases::root_probe(Position& pos, Search::RootMoves& rootMoves, Value& score)
 686 {
 687   int success;
 688
 689   int dtz = probe_dtz(pos, &success);
 690   if (!success) return false;
 691
 692   StateInfo st;
 693
 694   // Probe each move.
 695   for (size_t i = 0; i < rootMoves.size(); i++) {
 696     Move move = rootMoves[i].pv[0];
 697     pos.do_move(move, st, pos.gives_check(move));
 698     int v = 0;
 699     if (pos.checkers() && dtz > 0) {
 700       ExtMove s[192];
 701       if (generate<LEGAL>(pos, s) == s)
 702         v = 1;
 703     }
 704     if (!v) {
 705       if (st.rule50 != 0) {
 706         v = -Tablebases::probe_dtz(pos, &success);
 707         if (v > 0) v++;
 708         else if (v < 0) v--;
 709       } else {
 710         v = -Tablebases::probe_wdl(pos, &success);
 711         v = wdl_to_dtz[v + 2];
 712       }
 713     }
 714     pos.undo_move(move);
 715     if (!success) return false;
 716     rootMoves[i].score = (Value)v;
 717   }
 718
 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;
 722
 723   // Use 50-move counter to determine whether the root position is
 724   // won, lost or drawn.
 725   int wdl = 0;
 726   if (dtz > 0)
 727     wdl = (dtz + cnt50 <= 100) ? 2 : 1;
 728   else if (dtz < 0)
 729     wdl = (-dtz + cnt50 <= 100) ? -2 : -1;
 730
 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);
 740
 741   // Now be a bit smart about filtering out moves.
 742   size_t j = 0;
 743   if (dtz > 0) { // winning (or 50-move rule draw)
 744     int best = 0xffff;
 745     for (size_t i = 0; i < rootMoves.size(); i++) {
 746       int v = rootMoves[i].score;
 747       if (v > 0 && v < best)
 748         best = v;
 749     }
 750     int max = 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)
 754       max = 99 - cnt50;
 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];
 759     }
 760   } else if (dtz < 0) { // losing (or 50-move rule draw)
 761     int best = 0;
 762     for (size_t i = 0; i < rootMoves.size(); i++) {
 763       int v = rootMoves[i].score;
 764       if (v < best)
 765         best = v;
 766     }
 767     // Try all moves, unless we approach or have a 50-move rule draw.
 768     if (-best * 2 + cnt50 < 100)
 769       return true;
 770     for (size_t i = 0; i < rootMoves.size(); i++) {
 771       if (rootMoves[i].score == best)
 772         rootMoves[j++] = rootMoves[i];
 773     }
 774   } else { // drawing
 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];
 779     }
 780   }
 781   rootMoves.resize(j, Search::RootMove(MOVE_NONE));
 782
 783   return true;
 784 }
 785
 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.
 788 //
 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::RootMoves& rootMoves, Value& score)
 792 {
 793   int success;
 794
 795   int wdl = Tablebases::probe_wdl(pos, &success);
 796   if (!success) return false;
 797   score = wdl_to_Value[wdl + 2];
 798
 799   StateInfo st;
 800
 801   int best = -2;
 802
 803   // Probe each move.
 804   for (size_t i = 0; i < rootMoves.size(); i++) {
 805     Move move = rootMoves[i].pv[0];
 806     pos.do_move(move, st, pos.gives_check(move));
 807     int v = -Tablebases::probe_wdl(pos, &success);
 808     pos.undo_move(move);
 809     if (!success) return false;
 810     rootMoves[i].score = (Value)v;
 811     if (v > best)
 812       best = v;
 813   }
 814
 815   size_t j = 0;
 816   for (size_t i = 0; i < rootMoves.size(); i++) {
 817     if (rootMoves[i].score == best)
 818       rootMoves[j++] = rootMoves[i];
 819   }
 820   rootMoves.resize(j, Search::RootMove(MOVE_NONE));
 821
 822   return true;
 823 }
 824