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