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 #include "../position.h"
  11 #include "../movegen.h"
  12 #include "../bitboard.h"
  13 #include "../search.h"
  14 #include "../bitcount.h"
  15
  16 #include "tbprobe.h"
  17 #include "tbcore.h"
  18
  19 #include "tbcore.cpp"
  20
  21 namespace Zobrist {
  22   extern Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];
  23 }
  24
  25 int Tablebases::TBLargest = 0;
  26
  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)
  31 {
  32   Color color;
  33   PieceType pt;
  34   int i;
  35
  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];
  40   *str++ = 'v';
  41   color = ~color;
  42   for (pt = KING; pt >= PAWN; --pt)
  43     for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
  44       *str++ = pchr[6 - pt];
  45   *str++ = 0;
  46 }
  47
  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)
  51 {
  52   Color color;
  53   PieceType pt;
  54   int i;
  55   uint64 key = 0;
  56
  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];
  61   color = ~color;
  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];
  65
  66   return key;
  67 }
  68
  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
  72 // pawns, ..., kings.
  73 static uint64 calc_key_from_pcs(int *pcs, int mirror)
  74 {
  75   int color;
  76   PieceType pt;
  77   int i;
  78   uint64 key = 0;
  79
  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];
  84   color ^= 8;
  85   for (pt = PAWN; pt <= KING; ++pt)
  86     for (i = 0; i < pcs[color + pt]; i++)
  87       key ^= Zobrist::psq[BLACK][pt][i];
  88
  89   return key;
  90 }
  91
  92 bool is_little_endian() {
  93   union {
  94     int i;
  95     char c[sizeof(int)];
  96   } x;
  97   x.i = 1;
  98   return x.c[0] == 1;
  99 }
 100
 101 static ubyte decompress_pairs(struct PairsData *d, uint64 idx)
 102 {
 103   static const bool isLittleEndian = is_little_endian();
 104   return isLittleEndian ? decompress_pairs<true >(d, idx)
 105                         : decompress_pairs<false>(d, idx);
 106 }
 107
 108 // probe_wdl_table and probe_dtz_table require similar adaptations.
 109 static int probe_wdl_table(Position& pos, int *success)
 110 {
 111   struct TBEntry *ptr;
 112   struct TBHashEntry *ptr2;
 113   uint64 idx;
 114   uint64 key;
 115   int i;
 116   ubyte res;
 117   int p[TBPIECES];
 118
 119   // Obtain the position's material signature key.
 120   key = pos.material_key();
 121
 122   // Test for KvK.
 123   if (key == (Zobrist::psq[WHITE][KING][0] ^ Zobrist::psq[BLACK][KING][0]))
 124     return 0;
 125
 126   ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
 127   for (i = 0; i < HSHMAX; i++)
 128     if (ptr2[i].key == key) break;
 129   if (i == HSHMAX) {
 130     *success = 0;
 131     return 0;
 132   }
 133
 134   ptr = ptr2[i].ptr;
 135   if (!ptr->ready) {
 136     LOCK(TB_mutex);
 137     if (!ptr->ready) {
 138       char str[16];
 139       prt_str(pos, str, ptr->key != key);
 140       if (!init_table_wdl(ptr, str)) {
 141         ptr2[i].key = 0ULL;
 142         *success = 0;
 143         UNLOCK(TB_mutex);
 144         return 0;
 145       }
 146       // Memory barrier to ensure ptr->ready = 1 is not reordered.
 147       __asm__ __volatile__ ("" ::: "memory");
 148       ptr->ready = 1;
 149     }
 150     UNLOCK(TB_mutex);
 151   }
 152
 153   int bside, mirror, cmirror;
 154   if (!ptr->symmetric) {
 155     if (key != ptr->key) {
 156       cmirror = 8;
 157       mirror = 0x38;
 158       bside = (pos.side_to_move() == WHITE);
 159     } else {
 160       cmirror = mirror = 0;
 161       bside = !(pos.side_to_move() == WHITE);
 162     }
 163   } else {
 164     cmirror = pos.side_to_move() == WHITE ? 0 : 8;
 165     mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
 166     bside = 0;
 167   }
 168
 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));
 178       do {
 179         p[i++] = pop_lsb(&bb);
 180       } while (bb);
 181     }
 182     idx = encode_piece(entry, entry->norm[bside], p, entry->factor[bside]);
 183     res = decompress_pairs(entry->precomp[bside], idx);
 184   } else {
 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));
 188     i = 0;
 189     do {
 190       p[i++] = pop_lsb(&bb) ^ mirror;
 191     } while (bb);
 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));
 197       do {
 198         p[i++] = pop_lsb(&bb) ^ mirror;
 199       } while (bb);
 200     }
 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);
 203   }
 204
 205   return ((int)res) - 2;
 206 }
 207
 208 static int probe_dtz_table(Position& pos, int wdl, int *success)
 209 {
 210   struct TBEntry *ptr;
 211   uint64 idx;
 212   int i, res;
 213   int p[TBPIECES];
 214
 215   // Obtain the position's material signature key.
 216   uint64 key = pos.material_key();
 217
 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];
 223       for (; i > 0; i--)
 224         DTZ_table[i] = DTZ_table[i - 1];
 225       DTZ_table[0] = table_entry;
 226     } else {
 227       struct TBHashEntry *ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
 228       for (i = 0; i < HSHMAX; i++)
 229         if (ptr2[i].key == key) break;
 230       if (i == HSHMAX) {
 231         *success = 0;
 232         return 0;
 233       }
 234       ptr = ptr2[i].ptr;
 235       char str[16];
 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));
 243     }
 244   }
 245
 246   ptr = DTZ_table[0].entry;
 247   if (!ptr) {
 248     *success = 0;
 249     return 0;
 250   }
 251
 252   int bside, mirror, cmirror;
 253   if (!ptr->symmetric) {
 254     if (key != ptr->key) {
 255       cmirror = 8;
 256       mirror = 0x38;
 257       bside = (pos.side_to_move() == WHITE);
 258     } else {
 259       cmirror = mirror = 0;
 260       bside = !(pos.side_to_move() == WHITE);
 261     }
 262   } else {
 263     cmirror = pos.side_to_move() == WHITE ? 0 : 8;
 264     mirror = pos.side_to_move() == WHITE ? 0 : 0x38;
 265     bside = 0;
 266   }
 267
 268   if (!ptr->has_pawns) {
 269     struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr;
 270     if ((entry->flags & 1) != bside && !entry->symmetric) {
 271       *success = -1;
 272       return 0;
 273     }
 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));
 278       do {
 279         p[i++] = pop_lsb(&bb);
 280       } while (bb);
 281     }
 282     idx = encode_piece((struct TBEntry_piece *)entry, entry->norm, p, entry->factor);
 283     res = decompress_pairs(entry->precomp, idx);
 284
 285     if (entry->flags & 2)
 286       res = entry->map[entry->map_idx[wdl_to_map[wdl + 2]] + res];
 287
 288     if (!(entry->flags & pa_flags[wdl + 2]) || (wdl & 1))
 289       res *= 2;
 290   } else {
 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));
 294     i = 0;
 295     do {
 296       p[i++] = pop_lsb(&bb) ^ mirror;
 297     } while (bb);
 298     int f = pawn_file((struct TBEntry_pawn *)entry, p);
 299     if ((entry->flags[f] & 1) != bside) {
 300       *success = -1;
 301       return 0;
 302     }
 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));
 307       do {
 308         p[i++] = pop_lsb(&bb) ^ mirror;
 309       } while (bb);
 310     }
 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);
 313
 314     if (entry->flags[f] & 2)
 315       res = entry->map[entry->map_idx[f][wdl_to_map[wdl + 2]] + res];
 316
 317     if (!(entry->flags[f] & pa_flags[wdl + 2]) || (wdl & 1))
 318       res *= 2;
 319   }
 320
 321   return res;
 322 }
 323
 324 // Add underpromotion captures to list of captures.
 325 static ExtMove *add_underprom_caps(Position& pos, ExtMove *stack, ExtMove *end)
 326 {
 327   ExtMove *moves, *extra = end;
 328
 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));
 335     }
 336   }
 337
 338   return extra;
 339 }
 340
 341 static int probe_ab(Position& pos, int alpha, int beta, int *success)
 342 {
 343   int v;
 344   ExtMove stack[64];
 345   ExtMove *moves, *end;
 346   StateInfo st;
 347
 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);
 354   } else
 355     end = generate<EVASIONS>(pos, stack);
 356
 357   CheckInfo ci(pos);
 358
 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))
 363       continue;
 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;
 368     if (v > alpha) {
 369       if (v >= beta) {
 370         *success = 2;
 371         return v;
 372       }
 373       alpha = v;
 374     }
 375   }
 376
 377   v = probe_wdl_table(pos, success);
 378   if (*success == 0) return 0;
 379   if (alpha >= v) {
 380     *success = 1 + (alpha > 0);
 381     return alpha;
 382   } else {
 383     *success = 1;
 384     return v;
 385   }
 386 }
 387
 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:
 391 // -2 : loss
 392 // -1 : loss, but draw under 50-move rule
 393 //  0 : draw
 394 //  1 : win, but draw under 50-move rule
 395 //  2 : win
 396 int Tablebases::probe_wdl(Position& pos, int *success)
 397 {
 398   int v;
 399
 400   *success = 1;
 401   v = probe_ab(pos, -2, 2, success);
 402
 403   // If en passant is not possible, we are done.
 404   if (pos.ep_square() == SQ_NONE)
 405     return v;
 406   if (!(*success)) return 0;
 407
 408   // Now handle en passant.
 409   int v1 = -3;
 410   // Generate (at least) all legal en passant captures.
 411   ExtMove stack[192];
 412   ExtMove *moves, *end;
 413   StateInfo st;
 414
 415   if (!pos.checkers())
 416     end = generate<CAPTURES>(pos, stack);
 417   else
 418     end = generate<EVASIONS>(pos, stack);
 419
 420   CheckInfo ci(pos);
 421
 422   for (moves = stack; moves < end; moves++) {
 423     Move capture = moves->move;
 424     if (type_of(capture) != ENPASSANT
 425           || !pos.legal(capture, ci.pinned))
 426       continue;
 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;
 432   }
 433   if (v1 > -3) {
 434     if (v1 >= v) v = v1;
 435     else if (v == 0) {
 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;
 441       }
 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))
 447             break;
 448         }
 449       }
 450       // If not, then we are forced to play the losing ep capture.
 451       if (moves == end)
 452         v = v1;
 453     }
 454   }
 455
 456   return v;
 457 }
 458
 459 // This routine treats a position with en passant captures as one without.
 460 static int probe_dtz_no_ep(Position& pos, int *success)
 461 {
 462   int wdl, dtz;
 463
 464   wdl = probe_ab(pos, -2, 2, success);
 465   if (*success == 0) return 0;
 466
 467   if (wdl == 0) return 0;
 468
 469   if (*success == 2)
 470     return wdl == 2 ? 1 : 101;
 471
 472   ExtMove stack[192];
 473   ExtMove *moves, *end = NULL;
 474   StateInfo st;
 475   CheckInfo ci(pos);
 476
 477   if (wdl > 0) {
 478     // Generate at least all legal non-capturing pawn moves
 479     // including non-capturing promotions.
 480     if (!pos.checkers())
 481       end = generate<NON_EVASIONS>(pos, stack);
 482     else
 483       end = generate<EVASIONS>(pos, stack);
 484
 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))
 489         continue;
 490       pos.do_move(move, st, ci, pos.gives_check(move, ci));
 491       int v = -probe_ab(pos, -2, -wdl + 1, success);
 492       pos.undo_move(move);
 493       if (*success == 0) return 0;
 494       if (v == wdl)
 495         return v == 2 ? 1 : 101;
 496     }
 497   }
 498
 499   dtz = 1 + probe_dtz_table(pos, wdl, success);
 500   if (*success >= 0) {
 501     if (wdl & 1) dtz += 100;
 502     return wdl >= 0 ? dtz : -dtz;
 503   }
 504
 505   if (wdl > 0) {
 506     int best = 0xffff;
 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))
 511         continue;
 512       pos.do_move(move, st, ci, pos.gives_check(move, ci));
 513       int v = -Tablebases::probe_dtz(pos, success);
 514       pos.undo_move(move);
 515       if (*success == 0) return 0;
 516       if (v > 0 && v + 1 < best)
 517         best = v + 1;
 518     }
 519     return best;
 520   } else {
 521     int best = -1;
 522     if (!pos.checkers())
 523       end = generate<NON_EVASIONS>(pos, stack);
 524     else
 525       end = generate<EVASIONS>(pos, stack);
 526     for (moves = stack; moves < end; moves++) {
 527       int v;
 528       Move move = moves->move;
 529       if (!pos.legal(move, ci.pinned))
 530         continue;
 531       pos.do_move(move, st, ci, pos.gives_check(move, ci));
 532       if (st.rule50 == 0) {
 533         if (wdl == -2) v = -1;
 534         else {
 535           v = probe_ab(pos, 1, 2, success);
 536           v = (v == 2) ? 0 : -101;
 537         }
 538       } else {
 539         v = -Tablebases::probe_dtz(pos, success) - 1;
 540       }
 541       pos.undo_move(move);
 542       if (*success == 0) return 0;
 543       if (v < best)
 544         best = v;
 545     }
 546     return best;
 547   }
 548 }
 549
 550 static int wdl_to_dtz[] = {
 551   -1, -101, 0, 101, 1
 552 };
 553
 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)
 559 //         0        : draw
 560 //     1 < n <= 100 : win in n ply (assuming 50-move counter == 0)
 561 //   100 < n        : win, but draw under 50-move rule
 562 //
 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
 566 // the 50-move rule.
 567 //
 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.
 571 //
 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.
 576 //
 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.
 579 //
 580 int Tablebases::probe_dtz(Position& pos, int *success)
 581 {
 582   *success = 1;
 583   int v = probe_dtz_no_ep(pos, success);
 584
 585   if (pos.ep_square() == SQ_NONE)
 586     return v;
 587   if (*success == 0) return 0;
 588
 589   // Now handle en passant.
 590   int v1 = -3;
 591
 592   ExtMove stack[192];
 593   ExtMove *moves, *end;
 594   StateInfo st;
 595
 596   if (!pos.checkers())
 597     end = generate<CAPTURES>(pos, stack);
 598   else
 599     end = generate<EVASIONS>(pos, stack);
 600   CheckInfo ci(pos);
 601
 602   for (moves = stack; moves < end; moves++) {
 603     Move capture = moves->move;
 604     if (type_of(capture) != ENPASSANT
 605                 || !pos.legal(capture, ci.pinned))
 606       continue;
 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;
 612   }
 613   if (v1 > -3) {
 614     v1 = wdl_to_dtz[v1 + 2];
 615     if (v < -100) {
 616       if (v1 >= 0)
 617         v = v1;
 618     } else if (v < 0) {
 619       if (v1 >= 0 || v1 < 100)
 620         v = v1;
 621     } else if (v > 100) {
 622       if (v1 > 0)
 623         v = v1;
 624     } else if (v > 0) {
 625       if (v1 == 1)
 626         v = v1;
 627     } else if (v1 >= 0) {
 628       v = v1;
 629     } else {
 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;
 634       }
 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))
 640             break;
 641         }
 642       }
 643       if (moves == end)
 644         v = v1;
 645     }
 646   }
 647
 648   return v;
 649 }
 650
 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)
 654 {
 655   while (1) {
 656     int i = 4, e = std::min(st->rule50, st->pliesFromNull);
 657     if (e < i)
 658       return 0;
 659     StateInfo *stp = st->previous->previous;
 660     do {
 661       stp = stp->previous->previous;
 662       if (stp->key == st->key)
 663         return 1;
 664       i += 2;
 665     } while (i <= e);
 666     st = st->previous;
 667   }
 668 }
 669
 670 static Value wdl_to_Value[5] = {
 671   -VALUE_MATE + MAX_PLY + 1,
 672   VALUE_DRAW - 2,
 673   VALUE_DRAW,
 674   VALUE_DRAW + 2,
 675   VALUE_MATE - MAX_PLY - 1
 676 };
 677
 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
 680 // maximise DTZ.
 681 //
 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, Value& TBScore)
 685 {
 686   int success;
 687
 688   int dtz = probe_dtz(pos, &success);
 689   if (!success) return false;
 690
 691   StateInfo st;
 692   CheckInfo ci(pos);
 693
 694   // Probe each move.
 695   for (size_t i = 0; i < Search::RootMoves.size(); i++) {
 696     Move move = Search::RootMoves[i].pv[0];
 697     pos.do_move(move, st, ci, pos.gives_check(move, ci));
 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     Search::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   TBScore = 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     TBScore = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200);
 738   else if (wdl == -1 && dtz >= -100)
 739     TBScore = -(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 < Search::RootMoves.size(); i++) {
 746       int v = Search::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 < Search::RootMoves.size(); i++) {
 756       int v = Search::RootMoves[i].score;
 757       if (v > 0 && v <= max)
 758         Search::RootMoves[j++] = Search::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 < Search::RootMoves.size(); i++) {
 763       int v = Search::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 < Search::RootMoves.size(); i++) {
 771       if (Search::RootMoves[i].score == best)
 772         Search::RootMoves[j++] = Search::RootMoves[i];
 773     }
 774   } else { // drawing
 775     // Try all moves that preserve the draw.
 776     for (size_t i = 0; i < Search::RootMoves.size(); i++) {
 777       if (Search::RootMoves[i].score == 0)
 778         Search::RootMoves[j++] = Search::RootMoves[i];
 779     }
 780   }
 781   Search::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, Value& TBScore)
 792 {
 793   int success;
 794
 795   int wdl = Tablebases::probe_wdl(pos, &success);
 796   if (!success) return false;
 797   TBScore = wdl_to_Value[wdl + 2];
 798
 799   StateInfo st;
 800   CheckInfo ci(pos);
 801
 802   int best = -2;
 803
 804   // Probe each move.
 805   for (size_t i = 0; i < Search::RootMoves.size(); i++) {
 806     Move move = Search::RootMoves[i].pv[0];
 807     pos.do_move(move, st, ci, pos.gives_check(move, ci));
 808     int v = -Tablebases::probe_wdl(pos, &success);
 809     pos.undo_move(move);
 810     if (!success) return false;
 811     Search::RootMoves[i].score = (Value)v;
 812     if (v > best)
 813       best = v;
 814   }
 815
 816   size_t j = 0;
 817   for (size_t i = 0; i < Search::RootMoves.size(); i++) {
 818     if (Search::RootMoves[i].score == best)
 819       Search::RootMoves[j++] = Search::RootMoves[i];
 820   }
 821   Search::RootMoves.resize(j, Search::RootMove(MOVE_NONE));
 822
 823   return true;
 824 }
 825