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