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