LMR Simplification
[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
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