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[COLOR_NB][PIECE_TYPE_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[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[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[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[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[WHITE][KING][0] ^ Zobrist::psq[BLACK][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   CheckInfo ci(pos);
 365
 366   for (moves = stack; moves < end; moves++) {
 367     Move capture = moves->move;
 368     if (!pos.capture(capture) || type_of(capture) == ENPASSANT
 369                         || !pos.legal(capture, ci.pinned))
 370       continue;
 371     pos.do_move(capture, st, pos.gives_check(capture, ci));
 372     v = -probe_ab(pos, -beta, -alpha, success);
 373     pos.undo_move(capture);
 374     if (*success == 0) return 0;
 375     if (v > alpha) {
 376       if (v >= beta) {
 377         *success = 2;
 378         return v;
 379       }
 380       alpha = v;
 381     }
 382   }
 383
 384   v = probe_wdl_table(pos, success);
 385   if (*success == 0) return 0;
 386   if (alpha >= v) {
 387     *success = 1 + (alpha > 0);
 388     return alpha;
 389   } else {
 390     *success = 1;
 391     return v;
 392   }
 393 }
 394
 395 // Probe the WDL table for a particular position.
 396 // If *success != 0, the probe was successful.
 397 // The return value is from the point of view of the side to move:
 398 // -2 : loss
 399 // -1 : loss, but draw under 50-move rule
 400 //  0 : draw
 401 //  1 : win, but draw under 50-move rule
 402 //  2 : win
 403 int Tablebases::probe_wdl(Position& pos, int *success)
 404 {
 405   int v;
 406
 407   *success = 1;
 408   v = probe_ab(pos, -2, 2, success);
 409
 410   // If en passant is not possible, we are done.
 411   if (pos.ep_square() == SQ_NONE)
 412     return v;
 413   if (!(*success)) return 0;
 414
 415   // Now handle en passant.
 416   int v1 = -3;
 417   // Generate (at least) all legal en passant captures.
 418   ExtMove stack[192];
 419   ExtMove *moves, *end;
 420   StateInfo st;
 421
 422   if (!pos.checkers())
 423     end = generate<CAPTURES>(pos, stack);
 424   else
 425     end = generate<EVASIONS>(pos, stack);
 426
 427   CheckInfo ci(pos);
 428
 429   for (moves = stack; moves < end; moves++) {
 430     Move capture = moves->move;
 431     if (type_of(capture) != ENPASSANT
 432           || !pos.legal(capture, ci.pinned))
 433       continue;
 434     pos.do_move(capture, st, pos.gives_check(capture, ci));
 435     int v0 = -probe_ab(pos, -2, 2, success);
 436     pos.undo_move(capture);
 437     if (*success == 0) return 0;
 438     if (v0 > v1) v1 = v0;
 439   }
 440   if (v1 > -3) {
 441     if (v1 >= v) v = v1;
 442     else if (v == 0) {
 443       // Check whether there is at least one legal non-ep move.
 444       for (moves = stack; moves < end; moves++) {
 445         Move capture = moves->move;
 446         if (type_of(capture) == ENPASSANT) continue;
 447         if (pos.legal(capture, ci.pinned)) break;
 448       }
 449       if (moves == end && !pos.checkers()) {
 450         end = generate<QUIETS>(pos, end);
 451         for (; moves < end; moves++) {
 452           Move move = moves->move;
 453           if (pos.legal(move, ci.pinned))
 454             break;
 455         }
 456       }
 457       // If not, then we are forced to play the losing ep capture.
 458       if (moves == end)
 459         v = v1;
 460     }
 461   }
 462
 463   return v;
 464 }
 465
 466 // This routine treats a position with en passant captures as one without.
 467 static int probe_dtz_no_ep(Position& pos, int *success)
 468 {
 469   int wdl, dtz;
 470
 471   wdl = probe_ab(pos, -2, 2, success);
 472   if (*success == 0) return 0;
 473
 474   if (wdl == 0) return 0;
 475
 476   if (*success == 2)
 477     return wdl == 2 ? 1 : 101;
 478
 479   ExtMove stack[192];
 480   ExtMove *moves, *end = NULL;
 481   StateInfo st;
 482   CheckInfo ci(pos);
 483
 484   if (wdl > 0) {
 485     // Generate at least all legal non-capturing pawn moves
 486     // including non-capturing promotions.
 487     if (!pos.checkers())
 488       end = generate<NON_EVASIONS>(pos, stack);
 489     else
 490       end = generate<EVASIONS>(pos, stack);
 491
 492     for (moves = stack; moves < end; moves++) {
 493       Move move = moves->move;
 494       if (type_of(pos.moved_piece(move)) != PAWN || pos.capture(move)
 495                 || !pos.legal(move, ci.pinned))
 496         continue;
 497       pos.do_move(move, st, pos.gives_check(move, ci));
 498       int v = -probe_ab(pos, -2, -wdl + 1, success);
 499       pos.undo_move(move);
 500       if (*success == 0) return 0;
 501       if (v == wdl)
 502         return v == 2 ? 1 : 101;
 503     }
 504   }
 505
 506   dtz = 1 + probe_dtz_table(pos, wdl, success);
 507   if (*success >= 0) {
 508     if (wdl & 1) dtz += 100;
 509     return wdl >= 0 ? dtz : -dtz;
 510   }
 511
 512   if (wdl > 0) {
 513     int best = 0xffff;
 514     for (moves = stack; moves < end; moves++) {
 515       Move move = moves->move;
 516       if (pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN
 517                 || !pos.legal(move, ci.pinned))
 518         continue;
 519       pos.do_move(move, st, pos.gives_check(move, ci));
 520       int v = -Tablebases::probe_dtz(pos, success);
 521       pos.undo_move(move);
 522       if (*success == 0) return 0;
 523       if (v > 0 && v + 1 < best)
 524         best = v + 1;
 525     }
 526     return best;
 527   } else {
 528     int best = -1;
 529     if (!pos.checkers())
 530       end = generate<NON_EVASIONS>(pos, stack);
 531     else
 532       end = generate<EVASIONS>(pos, stack);
 533     for (moves = stack; moves < end; moves++) {
 534       int v;
 535       Move move = moves->move;
 536       if (!pos.legal(move, ci.pinned))
 537         continue;
 538       pos.do_move(move, st, pos.gives_check(move, ci));
 539       if (st.rule50 == 0) {
 540         if (wdl == -2) v = -1;
 541         else {
 542           v = probe_ab(pos, 1, 2, success);
 543           v = (v == 2) ? 0 : -101;
 544         }
 545       } else {
 546         v = -Tablebases::probe_dtz(pos, success) - 1;
 547       }
 548       pos.undo_move(move);
 549       if (*success == 0) return 0;
 550       if (v < best)
 551         best = v;
 552     }
 553     return best;
 554   }
 555 }
 556
 557 static int wdl_to_dtz[] = {
 558   -1, -101, 0, 101, 1
 559 };
 560
 561 // Probe the DTZ table for a particular position.
 562 // If *success != 0, the probe was successful.
 563 // The return value is from the point of view of the side to move:
 564 //         n < -100 : loss, but draw under 50-move rule
 565 // -100 <= n < -1   : loss in n ply (assuming 50-move counter == 0)
 566 //         0        : draw
 567 //     1 < n <= 100 : win in n ply (assuming 50-move counter == 0)
 568 //   100 < n        : win, but draw under 50-move rule
 569 //
 570 // The return value n can be off by 1: a return value -n can mean a loss
 571 // in n+1 ply and a return value +n can mean a win in n+1 ply. This
 572 // cannot happen for tables with positions exactly on the "edge" of
 573 // the 50-move rule.
 574 //
 575 // This implies that if dtz > 0 is returned, the position is certainly
 576 // a win if dtz + 50-move-counter <= 99. Care must be taken that the engine
 577 // picks moves that preserve dtz + 50-move-counter <= 99.
 578 //
 579 // If n = 100 immediately after a capture or pawn move, then the position
 580 // is also certainly a win, and during the whole phase until the next
 581 // capture or pawn move, the inequality to be preserved is
 582 // dtz + 50-movecounter <= 100.
 583 //
 584 // In short, if a move is available resulting in dtz + 50-move-counter <= 99,
 585 // then do not accept moves leading to dtz + 50-move-counter == 100.
 586 //
 587 int Tablebases::probe_dtz(Position& pos, int *success)
 588 {
 589   *success = 1;
 590   int v = probe_dtz_no_ep(pos, success);
 591
 592   if (pos.ep_square() == SQ_NONE)
 593     return v;
 594   if (*success == 0) return 0;
 595
 596   // Now handle en passant.
 597   int v1 = -3;
 598
 599   ExtMove stack[192];
 600   ExtMove *moves, *end;
 601   StateInfo st;
 602
 603   if (!pos.checkers())
 604     end = generate<CAPTURES>(pos, stack);
 605   else
 606     end = generate<EVASIONS>(pos, stack);
 607   CheckInfo ci(pos);
 608
 609   for (moves = stack; moves < end; moves++) {
 610     Move capture = moves->move;
 611     if (type_of(capture) != ENPASSANT
 612                 || !pos.legal(capture, ci.pinned))
 613       continue;
 614     pos.do_move(capture, st, pos.gives_check(capture, ci));
 615     int v0 = -probe_ab(pos, -2, 2, success);
 616     pos.undo_move(capture);
 617     if (*success == 0) return 0;
 618     if (v0 > v1) v1 = v0;
 619   }
 620   if (v1 > -3) {
 621     v1 = wdl_to_dtz[v1 + 2];
 622     if (v < -100) {
 623       if (v1 >= 0)
 624         v = v1;
 625     } else if (v < 0) {
 626       if (v1 >= 0 || v1 < -100)
 627         v = v1;
 628     } else if (v > 100) {
 629       if (v1 > 0)
 630         v = v1;
 631     } else if (v > 0) {
 632       if (v1 == 1)
 633         v = v1;
 634     } else if (v1 >= 0) {
 635       v = v1;
 636     } else {
 637       for (moves = stack; moves < end; moves++) {
 638         Move move = moves->move;
 639         if (type_of(move) == ENPASSANT) continue;
 640         if (pos.legal(move, ci.pinned)) break;
 641       }
 642       if (moves == end && !pos.checkers()) {
 643         end = generate<QUIETS>(pos, end);
 644         for (; moves < end; moves++) {
 645           Move move = moves->move;
 646           if (pos.legal(move, ci.pinned))
 647             break;
 648         }
 649       }
 650       if (moves == end)
 651         v = v1;
 652     }
 653   }
 654
 655   return v;
 656 }
 657
 658 // Check whether there has been at least one repetition of positions
 659 // since the last capture or pawn move.
 660 static int has_repeated(StateInfo *st)
 661 {
 662   while (1) {
 663     int i = 4, e = std::min(st->rule50, st->pliesFromNull);
 664     if (e < i)
 665       return 0;
 666     StateInfo *stp = st->previous->previous;
 667     do {
 668       stp = stp->previous->previous;
 669       if (stp->key == st->key)
 670         return 1;
 671       i += 2;
 672     } while (i <= e);
 673     st = st->previous;
 674   }
 675 }
 676
 677 static Value wdl_to_Value[5] = {
 678   -VALUE_MATE + MAX_PLY + 1,
 679   VALUE_DRAW - 2,
 680   VALUE_DRAW,
 681   VALUE_DRAW + 2,
 682   VALUE_MATE - MAX_PLY - 1
 683 };
 684
 685 // Use the DTZ tables to filter out moves that don't preserve the win or draw.
 686 // If the position is lost, but DTZ is fairly high, only keep moves that
 687 // maximise DTZ.
 688 //
 689 // A return value false indicates that not all probes were successful and that
 690 // no moves were filtered out.
 691 bool Tablebases::root_probe(Position& pos, Search::RootMoves& rootMoves, Value& score)
 692 {
 693   int success;
 694
 695   int dtz = probe_dtz(pos, &success);
 696   if (!success) return false;
 697
 698   StateInfo st;
 699   CheckInfo ci(pos);
 700
 701   // Probe each move.
 702   for (size_t i = 0; i < rootMoves.size(); i++) {
 703     Move move = rootMoves[i].pv[0];
 704     pos.do_move(move, st, pos.gives_check(move, ci));
 705     int v = 0;
 706     if (pos.checkers() && dtz > 0) {
 707       ExtMove s[192];
 708       if (generate<LEGAL>(pos, s) == s)
 709         v = 1;
 710     }
 711     if (!v) {
 712       if (st.rule50 != 0) {
 713         v = -Tablebases::probe_dtz(pos, &success);
 714         if (v > 0) v++;
 715         else if (v < 0) v--;
 716       } else {
 717         v = -Tablebases::probe_wdl(pos, &success);
 718         v = wdl_to_dtz[v + 2];
 719       }
 720     }
 721     pos.undo_move(move);
 722     if (!success) return false;
 723     rootMoves[i].score = (Value)v;
 724   }
 725
 726   // Obtain 50-move counter for the root position.
 727   // In Stockfish there seems to be no clean way, so we do it like this:
 728   int cnt50 = st.previous->rule50;
 729
 730   // Use 50-move counter to determine whether the root position is
 731   // won, lost or drawn.
 732   int wdl = 0;
 733   if (dtz > 0)
 734     wdl = (dtz + cnt50 <= 100) ? 2 : 1;
 735   else if (dtz < 0)
 736     wdl = (-dtz + cnt50 <= 100) ? -2 : -1;
 737
 738   // Determine the score to report to the user.
 739   score = wdl_to_Value[wdl + 2];
 740   // If the position is winning or losing, but too few moves left, adjust the
 741   // score to show how close it is to winning or losing.
 742   // NOTE: int(PawnValueEg) is used as scaling factor in score_to_uci().
 743   if (wdl == 1 && dtz <= 100)
 744     score = (Value)(((200 - dtz - cnt50) * int(PawnValueEg)) / 200);
 745   else if (wdl == -1 && dtz >= -100)
 746     score = -(Value)(((200 + dtz - cnt50) * int(PawnValueEg)) / 200);
 747
 748   // Now be a bit smart about filtering out moves.
 749   size_t j = 0;
 750   if (dtz > 0) { // winning (or 50-move rule draw)
 751     int best = 0xffff;
 752     for (size_t i = 0; i < rootMoves.size(); i++) {
 753       int v = rootMoves[i].score;
 754       if (v > 0 && v < best)
 755         best = v;
 756     }
 757     int max = best;
 758     // If the current phase has not seen repetitions, then try all moves
 759     // that stay safely within the 50-move budget, if there are any.
 760     if (!has_repeated(st.previous) && best + cnt50 <= 99)
 761       max = 99 - cnt50;
 762     for (size_t i = 0; i < rootMoves.size(); i++) {
 763       int v = rootMoves[i].score;
 764       if (v > 0 && v <= max)
 765         rootMoves[j++] = rootMoves[i];
 766     }
 767   } else if (dtz < 0) { // losing (or 50-move rule draw)
 768     int best = 0;
 769     for (size_t i = 0; i < rootMoves.size(); i++) {
 770       int v = rootMoves[i].score;
 771       if (v < best)
 772         best = v;
 773     }
 774     // Try all moves, unless we approach or have a 50-move rule draw.
 775     if (-best * 2 + cnt50 < 100)
 776       return true;
 777     for (size_t i = 0; i < rootMoves.size(); i++) {
 778       if (rootMoves[i].score == best)
 779         rootMoves[j++] = rootMoves[i];
 780     }
 781   } else { // drawing
 782     // Try all moves that preserve the draw.
 783     for (size_t i = 0; i < rootMoves.size(); i++) {
 784       if (rootMoves[i].score == 0)
 785         rootMoves[j++] = rootMoves[i];
 786     }
 787   }
 788   rootMoves.resize(j, Search::RootMove(MOVE_NONE));
 789
 790   return true;
 791 }
 792
 793 // Use the WDL tables to filter out moves that don't preserve the win or draw.
 794 // This is a fallback for the case that some or all DTZ tables are missing.
 795 //
 796 // A return value false indicates that not all probes were successful and that
 797 // no moves were filtered out.
 798 bool Tablebases::root_probe_wdl(Position& pos, Search::RootMoves& rootMoves, Value& score)
 799 {
 800   int success;
 801
 802   int wdl = Tablebases::probe_wdl(pos, &success);
 803   if (!success) return false;
 804   score = wdl_to_Value[wdl + 2];
 805
 806   StateInfo st;
 807   CheckInfo ci(pos);
 808
 809   int best = -2;
 810
 811   // Probe each move.
 812   for (size_t i = 0; i < rootMoves.size(); i++) {
 813     Move move = rootMoves[i].pv[0];
 814     pos.do_move(move, st, pos.gives_check(move, ci));
 815     int v = -Tablebases::probe_wdl(pos, &success);
 816     pos.undo_move(move);
 817     if (!success) return false;
 818     rootMoves[i].score = (Value)v;
 819     if (v > best)
 820       best = v;
 821   }
 822
 823   size_t j = 0;
 824   for (size_t i = 0; i < rootMoves.size(); i++) {
 825     if (rootMoves[i].score == best)
 826       rootMoves[j++] = rootMoves[i];
 827   }
 828   rootMoves.resize(j, Search::RootMove(MOVE_NONE));
 829
 830   return true;
 831 }
 832