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