Update comments in LMR step
[stockfish] / 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, 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, 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, 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, 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, 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, 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, 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, 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