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