1 /*
2  * tbprobe.c
3  * Copyright (c) 2013-2015 Ronald de Man
4  * This file may be redistributed and/or modified without restrictions.
5  *
6  * (C) 2015 basil, all rights reserved,
7  * Permission is hereby granted, free of charge, to any person obtaining a
8  * copy of this software and associated documentation files (the "Software"),
9  * to deal in the Software without restriction, including without limitation
10  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11  * and/or sell copies of the Software, and to permit persons to whom the
12  * Software is furnished to do so, subject to the following conditions:
13  *
14  * The above copyright notice and this permission notice shall be included in
15  * all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
22  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
23  * DEALINGS IN THE SOFTWARE.
24  */
25 
26 #include <assert.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 
30 #include "tbprobe.h"
31 
32 //#include <x86intrin.h>
33 
34 #define WHITE_KING              (TB_WPAWN + 5)
35 #define WHITE_QUEEN             (TB_WPAWN + 4)
36 #define WHITE_ROOK              (TB_WPAWN + 3)
37 #define WHITE_BISHOP            (TB_WPAWN + 2)
38 #define WHITE_KNIGHT            (TB_WPAWN + 1)
39 #define WHITE_PAWN              TB_WPAWN
40 #define BLACK_KING              (TB_BPAWN + 5)
41 #define BLACK_QUEEN             (TB_BPAWN + 4)
42 #define BLACK_ROOK              (TB_BPAWN + 3)
43 #define BLACK_BISHOP            (TB_BPAWN + 2)
44 #define BLACK_KNIGHT            (TB_BPAWN + 1)
45 #define BLACK_PAWN              TB_BPAWN
46 
47 #define PRIME_WHITE_QUEEN       11811845319353239651ull
48 #define PRIME_WHITE_ROOK        10979190538029446137ull
49 #define PRIME_WHITE_BISHOP      12311744257139811149ull
50 #define PRIME_WHITE_KNIGHT      15202887380319082783ull
51 #define PRIME_WHITE_PAWN        17008651141875982339ull
52 #define PRIME_BLACK_QUEEN       15484752644942473553ull
53 #define PRIME_BLACK_ROOK        18264461213049635989ull
54 #define PRIME_BLACK_BISHOP      15394650811035483107ull
55 #define PRIME_BLACK_KNIGHT      13469005675588064321ull
56 #define PRIME_BLACK_PAWN        11695583624105689831ull
57 
58 #define BOARD_RANK_EDGE         0x8181818181818181ull
59 #define BOARD_FILE_EDGE         0xFF000000000000FFull
60 #define BOARD_EDGE              (BOARD_RANK_EDGE | BOARD_FILE_EDGE)
61 #define BOARD_RANK_1            0x00000000000000FFull
62 #define BOARD_FILE_A            0x8080808080808080ull
63 
64 #define KEY_KvK                 0
65 
66 #define BEST_NONE               0xFFFF
67 #define SCORE_ILLEGAL           0x7FFF
68 
69 #define popcount(v) PopCnt(v)
70 
71 #define poplsb(x)               ((x) & ((x) - 1))
72 
73 #define make_move(promote, from, to)                                    \
74     ((((promote) & 0x7) << 12) | (((from) & 0x3F) << 6) | ((to) & 0x3F))
75 #define move_from(move)                                                 \
76     (((move) >> 6) & 0x3F)
77 #define move_to(move)                                                   \
78     ((move) & 0x3F)
79 #define move_promotes(move)                                             \
80     (((move) >> 12) & 0x7)
81 
82 #define MAX_MOVES               TB_MAX_MOVES
83 #define MOVE_STALEMATE          0xFFFF
84 #define MOVE_CHECKMATE          0xFFFE
85 
86 struct pos {
87   uint64_t white;
88   uint64_t black;
89   uint64_t kings;
90   uint64_t queens;
91   uint64_t rooks;
92   uint64_t bishops;
93   uint64_t knights;
94   uint64_t pawns;
95   uint8_t rule50;
96   uint8_t ep;
97   bool turn;
98 };
99 
100 static bool do_move(struct pos *pos, const struct pos *pos0, uint16_t move);
101 static int probe_dtz(const struct pos *pos, int *success);
102 
103 unsigned TB_LARGEST = 0;
104 #include "tbcore.c"
105 
106 #define rank(s)                 ((s) >> 3)
107 #define file(s)                 ((s) & 0x07)
108 #define board(s)                ((uint64_t)1 << (s))
_lsb(uint64_t b)109 static inline unsigned _lsb(uint64_t b) {
110   size_t idx;
111 __asm__("bsfq %1, %0": "=r"(idx):"rm"(b));
112   return idx;
113 }
114 
115 #define square(r, f)            (8 * (r) + (f))
116 
117 #ifdef TB_KING_ATTACKS
118 #  define king_attacks(s)         TB_KING_ATTACKS(s)
119 #  define king_attacks_init()
120                             /* NOP */
121 #else                           /* TB_KING_ATTACKS */
122 
123 static uint64_t king_attacks_table[64];
124 
125 #  define king_attacks(s)         king_attacks_table[(s)]
126 
king_attacks_init(void)127 static void king_attacks_init(void) {
128   for (unsigned s = 0; s < 64; s++) {
129     unsigned r = rank(s);
130     unsigned f = file(s);
131     uint64_t b = 0;
132     if (r != 0 && f != 0)
133       b |= board(square(r - 1, f - 1));
134     if (r != 0)
135       b |= board(square(r - 1, f));
136     if (r != 0 && f != 7)
137       b |= board(square(r - 1, f + 1));
138     if (f != 7)
139       b |= board(square(r, f + 1));
140     if (r != 7 && f != 7)
141       b |= board(square(r + 1, f + 1));
142     if (r != 7)
143       b |= board(square(r + 1, f));
144     if (r != 7 && f != 0)
145       b |= board(square(r + 1, f - 1));
146     if (f != 0)
147       b |= board(square(r, f - 1));
148     king_attacks_table[s] = b;
149   }
150 }
151 
152 #endif                          /* TB_KING_ATTACKS */
153 
154 #ifdef TB_KNIGHT_ATTACKS
155 #  define knight_attacks(s)       TB_KNIGHT_ATTACKS(s)
156 #  define knight_attacks_init()
157                               /* NOP */
158 #else                           /* TB_KNIGHT_ATTACKS */
159 
160 static uint64_t knight_attacks_table[64];
161 
162 #  define knight_attacks(s)       knight_attacks_table[(s)]
163 
knight_attacks_init(void)164 static void knight_attacks_init(void) {
165   for (unsigned s = 0; s < 64; s++) {
166     int r1, r = rank(s);
167     int f1, f = file(s);
168     uint64_t b = 0;
169     r1 = r - 1;
170     f1 = f - 2;
171     if (r1 >= 0 && f1 >= 0)
172       b |= board(square(r1, f1));
173     r1 = r - 1;
174     f1 = f + 2;
175     if (r1 >= 0 && f1 <= 7)
176       b |= board(square(r1, f1));
177     r1 = r - 2;
178     f1 = f - 1;
179     if (r1 >= 0 && f1 >= 0)
180       b |= board(square(r1, f1));
181     r1 = r - 2;
182     f1 = f + 1;
183     if (r1 >= 0 && f1 <= 7)
184       b |= board(square(r1, f1));
185     r1 = r + 1;
186     f1 = f - 2;
187     if (r1 <= 7 && f1 >= 0)
188       b |= board(square(r1, f1));
189     r1 = r + 1;
190     f1 = f + 2;
191     if (r1 <= 7 && f1 <= 7)
192       b |= board(square(r1, f1));
193     r1 = r + 2;
194     f1 = f - 1;
195     if (r1 <= 7 && f1 >= 0)
196       b |= board(square(r1, f1));
197     r1 = r + 2;
198     f1 = f + 1;
199     if (r1 <= 7 && f1 <= 7)
200       b |= board(square(r1, f1));
201     knight_attacks_table[s] = b;
202   }
203 }
204 
205 #endif                          /* TB_KNIGHT_ATTACKS */
206 
207 #ifdef TB_BISHOP_ATTACKS
208 #  define bishop_attacks(s, occ)  TB_BISHOP_ATTACKS(s, occ)
209 #  define bishop_attacks_init()
210                               /* NOP */
211 #else                           /* TB_BISHOP_ATTACKS */
212 
213 static uint64_t diag_attacks_table[64][64];
214 static uint64_t anti_attacks_table[64][64];
215 
216 static const unsigned square2diag_table[64] = {
217   0, 1, 2, 3, 4, 5, 6, 7,
218   14, 0, 1, 2, 3, 4, 5, 6,
219   13, 14, 0, 1, 2, 3, 4, 5,
220   12, 13, 14, 0, 1, 2, 3, 4,
221   11, 12, 13, 14, 0, 1, 2, 3,
222   10, 11, 12, 13, 14, 0, 1, 2,
223   9, 10, 11, 12, 13, 14, 0, 1,
224   8, 9, 10, 11, 12, 13, 14, 0
225 };
226 
227 static const unsigned square2anti_table[64] = {
228   8, 9, 10, 11, 12, 13, 14, 0,
229   9, 10, 11, 12, 13, 14, 0, 1,
230   10, 11, 12, 13, 14, 0, 1, 2,
231   11, 12, 13, 14, 0, 1, 2, 3,
232   12, 13, 14, 0, 1, 2, 3, 4,
233   13, 14, 0, 1, 2, 3, 4, 5,
234   14, 0, 1, 2, 3, 4, 5, 6,
235   0, 1, 2, 3, 4, 5, 6, 7
236 };
237 
238 static const uint64_t diag2board_table[15] = {
239   0x8040201008040201ull,
240   0x0080402010080402ull,
241   0x0000804020100804ull,
242   0x0000008040201008ull,
243   0x0000000080402010ull,
244   0x0000000000804020ull,
245   0x0000000000008040ull,
246   0x0000000000000080ull,
247   0x0100000000000000ull,
248   0x0201000000000000ull,
249   0x0402010000000000ull,
250   0x0804020100000000ull,
251   0x1008040201000000ull,
252   0x2010080402010000ull,
253   0x4020100804020100ull,
254 };
255 
256 static const uint64_t anti2board_table[15] = {
257   0x0102040810204080ull,
258   0x0204081020408000ull,
259   0x0408102040800000ull,
260   0x0810204080000000ull,
261   0x1020408000000000ull,
262   0x2040800000000000ull,
263   0x4080000000000000ull,
264   0x8000000000000000ull,
265   0x0000000000000001ull,
266   0x0000000000000102ull,
267   0x0000000000010204ull,
268   0x0000000001020408ull,
269   0x0000000102040810ull,
270   0x0000010204081020ull,
271   0x0001020408102040ull,
272 };
273 
diag2index(uint64_t b,unsigned d)274 static inline size_t diag2index(uint64_t b, unsigned d) {
275   b *= 0x0101010101010101ull;
276   b >>= 56;
277   b >>= 1;
278   return (size_t) b;
279 }
280 
anti2index(uint64_t b,unsigned a)281 static inline size_t anti2index(uint64_t b, unsigned a) {
282   return diag2index(b, a);
283 }
284 
285 #  define diag(s)                 square2diag_table[(s)]
286 #  define anti(s)                 square2anti_table[(s)]
287 #  define diag2board(d)           diag2board_table[(d)]
288 #  define anti2board(a)           anti2board_table[(a)]
289 
bishop_attacks(unsigned sq,uint64_t occ)290 static uint64_t bishop_attacks(unsigned sq, uint64_t occ) {
291   occ &= ~board(sq);
292   unsigned d = diag(sq), a = anti(sq);
293   uint64_t d_occ = occ & (diag2board(d) & ~BOARD_EDGE);
294   uint64_t a_occ = occ & (anti2board(a) & ~BOARD_EDGE);
295   size_t d_idx = diag2index(d_occ, d);
296   size_t a_idx = anti2index(a_occ, a);
297   uint64_t d_attacks = diag_attacks_table[sq][d_idx];
298   uint64_t a_attacks = anti_attacks_table[sq][a_idx];
299   return d_attacks | a_attacks;
300 }
301 
bishop_attacks_init(void)302 static void bishop_attacks_init(void) {
303   for (unsigned idx = 0; idx < 64; idx++) {
304     unsigned idx1 = idx << 1;
305     for (unsigned s = 0; s < 64; s++) {
306       int r = rank(s);
307       int f = file(s);
308       uint64_t b = 0;
309       for (int i = -1; f + i >= 0 && r + i >= 0; i--) {
310         unsigned occ = (1 << (f + i));
311         b |= board(square(r + i, f + i));
312         if (idx1 & occ)
313           break;
314       }
315       for (int i = 1; f + i <= 7 && r + i <= 7; i++) {
316         unsigned occ = (1 << (f + i));
317         b |= board(square(r + i, f + i));
318         if (idx1 & occ)
319           break;
320       }
321       diag_attacks_table[s][idx] = b;
322     }
323   }
324 
325   for (unsigned idx = 0; idx < 64; idx++) {
326     unsigned idx1 = idx << 1;
327     for (unsigned s = 0; s < 64; s++) {
328       int r = rank(s);
329       int f = file(s);
330       uint64_t b = 0;
331       for (int i = -1; f + i >= 0 && r - i <= 7; i--) {
332         unsigned occ = (1 << (f + i));
333         b |= board(square(r - i, f + i));
334         if (idx1 & occ)
335           break;
336       }
337       for (int i = 1; f + i <= 7 && r - i >= 0; i++) {
338         unsigned occ = (1 << (f + i));
339         b |= board(square(r - i, f + i));
340         if (idx1 & occ)
341           break;
342       }
343       anti_attacks_table[s][idx] = b;
344     }
345   }
346 }
347 
348 #endif                          /* TB_BISHOP_ATTACKS */
349 
350 #ifdef TB_ROOK_ATTACKS
351 #  define rook_attacks(s, occ)    TB_ROOK_ATTACKS(s, occ)
352 #  define rook_attacks_init()
353                             /* NOP */
354 #else                           /* TB_ROOK_ATTACKS */
355 
356 static uint64_t rank_attacks_table[64][64];
357 static uint64_t file_attacks_table[64][64];
358 
rank2index(uint64_t b,unsigned r)359 static inline size_t rank2index(uint64_t b, unsigned r) {
360   b >>= (8 * r);
361   b >>= 1;
362   return (size_t) b;
363 }
364 
file2index(uint64_t b,unsigned f)365 static inline size_t file2index(uint64_t b, unsigned f) {
366   b >>= f;
367   b *= 0x0102040810204080ull;
368   b >>= 56;
369   b >>= 1;
370   return (size_t) b;
371 }
372 
373 #  define rank2board(r)           (0xFFull << (8 * (r)))
374 #  define file2board(f)           (0x0101010101010101ull << (f))
375 
rook_attacks(unsigned sq,uint64_t occ)376 static uint64_t rook_attacks(unsigned sq, uint64_t occ) {
377   occ &= ~board(sq);
378   unsigned r = rank(sq), f = file(sq);
379   uint64_t r_occ = occ & (rank2board(r) & ~BOARD_RANK_EDGE);
380   uint64_t f_occ = occ & (file2board(f) & ~BOARD_FILE_EDGE);
381   size_t r_idx = rank2index(r_occ, r);
382   size_t f_idx = file2index(f_occ, f);
383   uint64_t r_attacks = rank_attacks_table[sq][r_idx];
384   uint64_t f_attacks = file_attacks_table[sq][f_idx];
385   return r_attacks | f_attacks;
386 }
387 
rook_attacks_init(void)388 static void rook_attacks_init(void) {
389   for (unsigned idx = 0; idx < 64; idx++) {
390     unsigned idx1 = idx << 1, occ;
391     for (int f = 0; f <= 7; f++) {
392       uint64_t b = 0;
393       if (f > 0) {
394         int i = f - 1;
395         do {
396           occ = (1 << i);
397           b |= board(square(0, i));
398           i--;
399         }
400         while (!(idx1 & occ) && i >= 0);
401       }
402       if (f < 7) {
403         int i = f + 1;
404         do {
405           occ = (1 << i);
406           b |= board(square(0, i));
407           i++;
408         }
409         while (!(idx1 & occ) && i <= 7);
410       }
411       for (int r = 0; r <= 7; r++) {
412         rank_attacks_table[square(r, f)][idx] = b;
413         b <<= 8;
414       }
415     }
416   }
417   for (unsigned idx = 0; idx < 64; idx++) {
418     unsigned idx1 = idx << 1, occ;
419     for (int r = 0; r <= 7; r++) {
420       uint64_t b = 0;
421       if (r > 0) {
422         int i = r - 1;
423         do {
424           occ = (1 << i);
425           b |= board(square(i, 0));
426           i--;
427         }
428         while (!(idx1 & occ) && i >= 0);
429       }
430       if (r < 7) {
431         int i = r + 1;
432         do {
433           occ = (1 << i);
434           b |= board(square(i, 0));
435           i++;
436         }
437         while (!(idx1 & occ) && i <= 7);
438       }
439       for (int f = 0; f <= 7; f++) {
440         file_attacks_table[square(r, f)][idx] = b;
441         b <<= 1;
442       }
443     }
444   }
445 }
446 
447 #endif                          /* TB_ROOK_ATTACKS */
448 
449 #ifdef TB_QUEEN_ATTACKS
450 #  define queen_attacks(s, occ)   TB_QUEEN_ATTACKS(s, occ)
451 #else                           /* TB_QUEEN_ATTACKS */
452 #  define queen_attacks(s, occ)   \
453     (rook_attacks((s), (occ)) | bishop_attacks((s), (occ)))
454 #endif                          /* TB_QUEEN_ATTACKS */
455 
456 #ifdef TB_PAWN_ATTACKS
457 #  define pawn_attacks(s, c)      TB_PAWN_ATTACKS(s, c)
458 #  define pawn_attacks_init()
459                             /* NOP */
460 #else                           /* TB_PAWN_ATTACKS */
461 
462 static uint64_t pawn_attacks_table[2][64];
463 
464 #  define pawn_attacks(s, c)      pawn_attacks_table[(c)][(s)]
465 
pawn_attacks_init(void)466 static void pawn_attacks_init(void) {
467   for (unsigned s = 0; s < 64; s++) {
468     int r = rank(s);
469     int f = file(s);
470 
471     uint64_t b = 0;
472     if (r != 7) {
473       if (f != 0)
474         b |= board(square(r + 1, f - 1));
475       if (f != 7)
476         b |= board(square(r + 1, f + 1));
477     }
478     pawn_attacks_table[1][s] = b;
479 
480     b = 0;
481     if (r != 0) {
482       if (f != 0)
483         b |= board(square(r - 1, f - 1));
484       if (f != 7)
485         b |= board(square(r - 1, f + 1));
486     }
487     pawn_attacks_table[0][s] = b;
488   }
489 }
490 
491 #endif                          /* TB_PAWN_ATTACKS */
492 
prt_str(const struct pos * pos,char * str,bool mirror)493 static void prt_str(const struct pos *pos, char *str, bool mirror) {
494   uint64_t white = pos->white, black = pos->black;
495   int i;
496   if (mirror) {
497     uint64_t tmp = white;
498     white = black;
499     black = tmp;
500   }
501   *str++ = 'K';
502   for (i = popcount(white & pos->queens); i > 0; i--)
503     *str++ = 'Q';
504   for (i = popcount(white & pos->rooks); i > 0; i--)
505     *str++ = 'R';
506   for (i = popcount(white & pos->bishops); i > 0; i--)
507     *str++ = 'B';
508   for (i = popcount(white & pos->knights); i > 0; i--)
509     *str++ = 'N';
510   for (i = popcount(white & pos->pawns); i > 0; i--)
511     *str++ = 'P';
512   *str++ = 'v';
513   *str++ = 'K';
514   for (i = popcount(black & pos->queens); i > 0; i--)
515     *str++ = 'Q';
516   for (i = popcount(black & pos->rooks); i > 0; i--)
517     *str++ = 'R';
518   for (i = popcount(black & pos->bishops); i > 0; i--)
519     *str++ = 'B';
520   for (i = popcount(black & pos->knights); i > 0; i--)
521     *str++ = 'N';
522   for (i = popcount(black & pos->pawns); i > 0; i--)
523     *str++ = 'P';
524   *str++ = '\0';
525 }
526 
527 /*
528  * Given a position, produce a 64-bit material signature key.
529  */
calc_key(const struct pos * pos,bool mirror)530 static uint64_t calc_key(const struct pos *pos, bool mirror) {
531   uint64_t white = pos->white, black = pos->black;
532   if (mirror) {
533     uint64_t tmp = white;
534     white = black;
535     black = tmp;
536   }
537   return popcount(white & pos->queens) * PRIME_WHITE_QUEEN +
538       popcount(white & pos->rooks) * PRIME_WHITE_ROOK +
539       popcount(white & pos->bishops) * PRIME_WHITE_BISHOP +
540       popcount(white & pos->knights) * PRIME_WHITE_KNIGHT +
541       popcount(white & pos->pawns) * PRIME_WHITE_PAWN +
542       popcount(black & pos->queens) * PRIME_BLACK_QUEEN +
543       popcount(black & pos->rooks) * PRIME_BLACK_ROOK +
544       popcount(black & pos->bishops) * PRIME_BLACK_BISHOP +
545       popcount(black & pos->knights) * PRIME_BLACK_KNIGHT +
546       popcount(black & pos->pawns) * PRIME_BLACK_PAWN;
547 }
548 
calc_key_from_pcs(int * pcs,int mirror)549 static uint64_t calc_key_from_pcs(int *pcs, int mirror) {
550   mirror = (mirror ? 8 : 0);
551   return pcs[WHITE_QUEEN ^ mirror] * PRIME_WHITE_QUEEN +
552       pcs[WHITE_ROOK ^ mirror] * PRIME_WHITE_ROOK +
553       pcs[WHITE_BISHOP ^ mirror] * PRIME_WHITE_BISHOP +
554       pcs[WHITE_KNIGHT ^ mirror] * PRIME_WHITE_KNIGHT +
555       pcs[WHITE_PAWN ^ mirror] * PRIME_WHITE_PAWN +
556       pcs[BLACK_QUEEN ^ mirror] * PRIME_BLACK_QUEEN +
557       pcs[BLACK_ROOK ^ mirror] * PRIME_BLACK_ROOK +
558       pcs[BLACK_BISHOP ^ mirror] * PRIME_BLACK_BISHOP +
559       pcs[BLACK_KNIGHT ^ mirror] * PRIME_BLACK_KNIGHT +
560       pcs[BLACK_PAWN ^ mirror] * PRIME_BLACK_PAWN;
561 }
562 
get_pieces(const struct pos * pos,uint8_t code)563 static uint64_t get_pieces(const struct pos *pos, uint8_t code) {
564   switch (code) {
565     case WHITE_KING:
566       return pos->kings & pos->white;
567     case WHITE_QUEEN:
568       return pos->queens & pos->white;
569     case WHITE_ROOK:
570       return pos->rooks & pos->white;
571     case WHITE_BISHOP:
572       return pos->bishops & pos->white;
573     case WHITE_KNIGHT:
574       return pos->knights & pos->white;
575     case WHITE_PAWN:
576       return pos->pawns & pos->white;
577     case BLACK_KING:
578       return pos->kings & pos->black;
579     case BLACK_QUEEN:
580       return pos->queens & pos->black;
581     case BLACK_ROOK:
582       return pos->rooks & pos->black;
583     case BLACK_BISHOP:
584       return pos->bishops & pos->black;
585     case BLACK_KNIGHT:
586       return pos->knights & pos->black;
587     case BLACK_PAWN:
588       return pos->pawns & pos->black;
589     default:
590       return 0; // Dummy.
591   }
592 }
593 
probe_wdl_table(const struct pos * pos,int * success)594 static int probe_wdl_table(const struct pos *pos, int *success) {
595   struct TBEntry *ptr;
596   struct TBHashEntry *ptr2;
597   uint64_t idx;
598   uint64_t key;
599   int i;
600   uint8_t res;
601   int p[TBPIECES];
602 
603  // Obtain the position's material signature key.
604   key = calc_key(pos, false);
605 
606  // Test for KvK.
607   if (key == KEY_KvK)
608     return 0;
609 
610   ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
611   for (i = 0; i < HSHMAX; i++) {
612     if (ptr2[i].key == key)
613       break;
614   }
615   if (i == HSHMAX) {
616     *success = 0;
617     return 0;
618   }
619 
620   ptr = ptr2[i].ptr;
621   if (!ptr->ready) {
622     LOCK(TB_MUTEX);
623     if (!ptr->ready) {
624       char str[16];
625       prt_str(pos, str, ptr->key != key);
626       if (!init_table_wdl(ptr, str)) {
627         ptr2[i].key = 0ULL;
628         *success = 0;
629         UNLOCK(TB_MUTEX);
630         return 0;
631       }
632      // Memory barrier to ensure ptr->ready = 1 is not reordered.
633       __asm__ __volatile__("":::"memory");
634       ptr->ready = 1;
635     }
636     UNLOCK(TB_MUTEX);
637   }
638 
639   int bside, mirror, cmirror;
640   if (!ptr->symmetric) {
641     if (key != ptr->key) {
642       cmirror = 8;
643       mirror = 0x38;
644       bside = pos->turn;
645     } else {
646       cmirror = mirror = 0;
647       bside = !pos->turn;
648     }
649   } else {
650     cmirror = (pos->turn ? 0 : 8);
651     mirror = (pos->turn ? 0 : 0x38);
652     bside = 0;
653   }
654 
655  // p[i] is to contain the square 0-63 (A1-H8) for a piece of type
656  // pc[i] ^ cmirror, where 1 = white pawn, ..., 14 = black king.
657  // Pieces of the same type are guaranteed to be consecutive.
658   if (!ptr->has_pawns) {
659     struct TBEntry_piece *entry = (struct TBEntry_piece *) ptr;
660     uint8_t *pc = entry->pieces[bside];
661     for (i = 0; i < entry->num;) {
662       uint64_t bb = get_pieces(pos, pc[i] ^ cmirror);
663       do {
664         p[i++] = _lsb(bb);
665         bb = poplsb(bb);
666       } while (bb);
667     }
668     idx = encode_piece(entry, entry->norm[bside], p, entry->factor[bside]);
669     res = decompress_pairs(entry->precomp[bside], idx);
670   } else {
671     struct TBEntry_pawn *entry = (struct TBEntry_pawn *) ptr;
672     int k = entry->file[0].pieces[0][0] ^ cmirror;
673     uint64_t bb = get_pieces(pos, k);
674     i = 0;
675     do {
676       p[i++] = _lsb(bb) ^ mirror;
677       bb = poplsb(bb);
678     } while (bb);
679     int f = pawn_file(entry, p);
680     uint8_t *pc = entry->file[f].pieces[bside];
681     for (; i < entry->num;) {
682       bb = get_pieces(pos, pc[i] ^ cmirror);
683       do {
684         p[i++] = _lsb(bb) ^ mirror;
685         bb = poplsb(bb);
686       } while (bb);
687     }
688     idx =
689         encode_pawn(entry, entry->file[f].norm[bside], p,
690         entry->file[f].factor[bside]);
691     res = decompress_pairs(entry->file[f].precomp[bside], idx);
692   }
693 
694   return ((int) res) - 2;
695 }
696 
probe_dtz_table(const struct pos * pos,int wdl,int * success)697 static int probe_dtz_table(const struct pos *pos, int wdl, int *success) {
698   struct TBEntry *ptr;
699   uint64_t idx;
700   int i, res;
701   int p[TBPIECES];
702 
703  // Obtain the position's material signature key.
704   uint64_t key = calc_key(pos, false);
705 
706   if (DTZ_table[0].key1 != key && DTZ_table[0].key2 != key) {
707     for (i = 1; i < DTZ_ENTRIES; i++) {
708       if (DTZ_table[i].key1 == key || DTZ_table[i].key2 == key)
709         break; //new
710      /*if (DTZ_table[i].key1 == key)
711         break; *///mfb old
712     }
713     if (i < DTZ_ENTRIES) {
714       struct DTZTableEntry table_entry = DTZ_table[i];
715       for (; i > 0; i--)
716         DTZ_table[i] = DTZ_table[i - 1];
717       DTZ_table[0] = table_entry;
718     } else {
719       struct TBHashEntry *ptr2 = TB_hash[key >> (64 - TBHASHBITS)];
720       for (i = 0; i < HSHMAX; i++) {
721         if (ptr2[i].key == key)
722           break;
723       }
724       if (i == HSHMAX) {
725         *success = 0;
726         return 0;
727       }
728       ptr = ptr2[i].ptr;
729       char str[16];
730       int mirror = (ptr->key != key);
731       prt_str(pos, str, mirror);
732       if (DTZ_table[DTZ_ENTRIES - 1].entry)
733         free_dtz_entry(DTZ_table[DTZ_ENTRIES - 1].entry);
734       for (i = DTZ_ENTRIES - 1; i > 0; i--)
735         DTZ_table[i] = DTZ_table[i - 1];
736       uint64_t key1 = calc_key(pos, mirror);
737       uint64_t key2 = calc_key(pos, !mirror);
738       load_dtz_table(str, key1, key2);
739     }
740   }
741 
742   ptr = DTZ_table[0].entry;
743   if (!ptr) {
744     *success = 0;
745     return 0;
746   }
747 
748   int bside, mirror, cmirror;
749   if (!ptr->symmetric) {
750     if (key != ptr->key) {
751       cmirror = 8;
752       mirror = 0x38;
753       bside = pos->turn;
754     } else {
755       cmirror = mirror = 0;
756       bside = !pos->turn;
757     }
758   } else {
759     cmirror = (pos->turn ? 0 : 8);
760     mirror = (pos->turn ? 0 : 0x38);
761     bside = 0;
762   }
763 
764   if (!ptr->has_pawns) {
765     struct DTZEntry_piece *entry = (struct DTZEntry_piece *) ptr;
766     if ((entry->flags & 1) != bside && !entry->symmetric) {
767       *success = -1;
768       return 0;
769     }
770     uint8_t *pc = entry->pieces;
771     for (i = 0; i < entry->num;) {
772       uint64_t bb = get_pieces(pos, pc[i] ^ cmirror);
773       do {
774         p[i++] = _lsb(bb);
775         bb = poplsb(bb);
776       }
777       while (bb);
778     }
779     idx =
780         encode_piece((struct TBEntry_piece *) entry, entry->norm, p,
781         entry->factor);
782     res = decompress_pairs(entry->precomp, idx);
783 
784     if (entry->flags & 2)
785       res = entry->map[entry->map_idx[wdl_to_map[wdl + 2]] + res];
786     if (!(entry->flags & pa_flags[wdl + 2]) || (wdl & 1))
787       res *= 2;
788   } else {
789     struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *) ptr;
790     int k = entry->file[0].pieces[0] ^ cmirror;
791     uint64_t bb = get_pieces(pos, k);
792     i = 0;
793     do {
794       p[i++] = _lsb(bb) ^ mirror;
795       bb = poplsb(bb);
796     }
797     while (bb);
798     int f = pawn_file((struct TBEntry_pawn *) entry, p);
799     if ((entry->flags[f] & 1) != bside) {
800       *success = -1;
801       return 0;
802     }
803     uint8_t *pc = entry->file[f].pieces;
804     for (; i < entry->num;) {
805       bb = get_pieces(pos, pc[i] ^ cmirror);
806       do {
807         p[i++] = _lsb(bb) ^ mirror;
808         bb = poplsb(bb);
809       }
810       while (bb);
811     }
812     idx =
813         encode_pawn((struct TBEntry_pawn *) entry, entry->file[f].norm, p,
814         entry->file[f].factor);
815     res = decompress_pairs(entry->file[f].precomp, idx);
816 
817     if (entry->flags[f] & 2)
818       res = entry->map[entry->map_idx[f][wdl_to_map[wdl + 2]] + res];
819     if (!(entry->flags[f] & pa_flags[wdl + 2]) || (wdl & 1))
820       res *= 2;
821   }
822 
823   return res;
824 }
825 
add_move(uint16_t * moves,bool promotes,unsigned from,unsigned to)826 static uint16_t *add_move(uint16_t * moves, bool promotes, unsigned from,
827     unsigned to) {
828   if (!promotes)
829     *moves++ = make_move(TB_PROMOTES_NONE, from, to);
830   else {
831     *moves++ = make_move(TB_PROMOTES_QUEEN, from, to);
832     *moves++ = make_move(TB_PROMOTES_KNIGHT, from, to);
833     *moves++ = make_move(TB_PROMOTES_ROOK, from, to);
834     *moves++ = make_move(TB_PROMOTES_BISHOP, from, to);
835   }
836   return moves;
837 }
838 
839 /*
840  * Generate all captures or promotions.
841  */
gen_captures_or_promotions(const struct pos * pos,uint16_t * moves)842 static uint16_t *gen_captures_or_promotions(const struct pos *pos,
843     uint16_t * moves) {
844   uint64_t occ = pos->white | pos->black;
845   uint64_t us = (pos->turn ? pos->white : pos->black), them =
846       (pos->turn ? pos->black : pos->white);
847   uint64_t b, att;
848   {
849     unsigned from = _lsb(pos->kings & us);
850     for (att = king_attacks(from) & them; att; att = poplsb(att)) {
851       unsigned to = _lsb(att);
852       moves = add_move(moves, false, from, to);
853     }
854   }
855   for (b = us & pos->queens; b; b = poplsb(b)) {
856     unsigned from = _lsb(b);
857     for (att = queen_attacks(from, occ) & them; att; att = poplsb(att)) {
858       unsigned to = _lsb(att);
859       moves = add_move(moves, false, from, to);
860     }
861   }
862   for (b = us & pos->rooks; b; b = poplsb(b)) {
863     unsigned from = _lsb(b);
864     for (att = rook_attacks(from, occ) & them; att; att = poplsb(att)) {
865       unsigned to = _lsb(att);
866       moves = add_move(moves, false, from, to);
867     }
868   }
869   for (b = us & pos->bishops; b; b = poplsb(b)) {
870     unsigned from = _lsb(b);
871     for (att = bishop_attacks(from, occ) & them; att; att = poplsb(att)) {
872       unsigned to = _lsb(att);
873       moves = add_move(moves, false, from, to);
874     }
875   }
876   for (b = us & pos->knights; b; b = poplsb(b)) {
877     unsigned from = _lsb(b);
878     for (att = knight_attacks(from) & them; att; att = poplsb(att)) {
879       unsigned to = _lsb(att);
880       moves = add_move(moves, false, from, to);
881     }
882   }
883   for (b = us & pos->pawns; b; b = poplsb(b)) {
884     unsigned from = _lsb(b);
885     att = pawn_attacks(from, pos->turn);
886     if (pos->ep != 0 && ((att & board(pos->ep)) != 0)) {
887       unsigned to = pos->ep;
888       moves = add_move(moves, false, from, to);
889     }
890     for (att = att & them; att; att = poplsb(att)) {
891       unsigned to = _lsb(att);
892       moves = add_move(moves, (rank(to) == 7 || rank(to) == 0), from, to);
893     }
894     if (pos->turn && rank(from) == 6) {
895       unsigned to = from + 8;
896       if ((board(to) & occ) == 0)
897         moves = add_move(moves, true, from, to);
898     } else if (!pos->turn && rank(from) == 1) {
899       unsigned to = from - 8;
900       if ((board(to) & occ) == 0)
901         moves = add_move(moves, true, from, to);
902     }
903   }
904   return moves;
905 }
906 
907 /*
908  * Generate all non-capture pawn moves and promotions.
909  */
gen_pawn_quiets_or_promotions(const struct pos * pos,uint16_t * moves)910 static uint16_t *gen_pawn_quiets_or_promotions(const struct pos *pos,
911     uint16_t * moves) {
912   uint64_t occ = pos->white | pos->black;
913   uint64_t us = (pos->turn ? pos->white : pos->black);
914   uint64_t b, att;
915 
916   for (b = us & pos->pawns; b; b = poplsb(b)) {
917     unsigned from = _lsb(b);
918     unsigned next = from + (pos->turn ? 8 : -8);
919     att = 0;
920     if ((board(next) & occ) == 0) {
921       att |= board(next);
922       unsigned next2 = from + (pos->turn ? 16 : -16);
923       if ((pos->turn ? rank(from) == 1 : rank(from) == 6) &&
924           ((board(next2) & occ) == 0))
925         att |= board(next2);
926     }
927     for (; att; att = poplsb(att)) {
928       unsigned to = _lsb(att);
929       moves = add_move(moves, (rank(to) == 7 || rank(to) == 0), from, to);
930     }
931   }
932   return moves;
933 }
934 
935 /*
936  * Generate all en passant captures.
937  */
gen_pawn_ep_captures(const struct pos * pos,uint16_t * moves)938 static uint16_t *gen_pawn_ep_captures(const struct pos *pos, uint16_t * moves) {
939   if (pos->ep == 0)
940     return moves;
941   uint64_t ep = board(pos->ep);
942   unsigned to = pos->ep;
943   uint64_t us = (pos->turn ? pos->white : pos->black);
944   uint64_t b;
945   for (b = us & pos->pawns; b; b = poplsb(b)) {
946     unsigned from = _lsb(b);
947     if ((pawn_attacks(from, pos->turn) & ep) != 0)
948       moves = add_move(moves, false, from, to);
949   }
950   return moves;
951 }
952 
953 /*
954  * Generate all moves.
955  */
gen_moves(const struct pos * pos,uint16_t * moves)956 static uint16_t *gen_moves(const struct pos *pos, uint16_t * moves) {
957   uint64_t occ = pos->white | pos->black;
958   uint64_t us = (pos->turn ? pos->white : pos->black), them =
959       (pos->turn ? pos->black : pos->white);
960   uint64_t b, att;
961 
962   {
963     unsigned from = _lsb(pos->kings & us);
964     for (att = king_attacks(from) & ~us; att; att = poplsb(att)) {
965       unsigned to = _lsb(att);
966       moves = add_move(moves, false, from, to);
967     }
968   }
969   for (b = us & pos->queens; b; b = poplsb(b)) {
970     unsigned from = _lsb(b);
971     for (att = queen_attacks(from, occ) & ~us; att; att = poplsb(att)) {
972       unsigned to = _lsb(att);
973       moves = add_move(moves, false, from, to);
974     }
975   }
976   for (b = us & pos->rooks; b; b = poplsb(b)) {
977     unsigned from = _lsb(b);
978     for (att = rook_attacks(from, occ) & ~us; att; att = poplsb(att)) {
979       unsigned to = _lsb(att);
980       moves = add_move(moves, false, from, to);
981     }
982   }
983   for (b = us & pos->bishops; b; b = poplsb(b)) {
984     unsigned from = _lsb(b);
985     for (att = bishop_attacks(from, occ) & ~us; att; att = poplsb(att)) {
986       unsigned to = _lsb(att);
987       moves = add_move(moves, false, from, to);
988     }
989   }
990   for (b = us & pos->knights; b; b = poplsb(b)) {
991     unsigned from = _lsb(b);
992     for (att = knight_attacks(from) & ~us; att; att = poplsb(att)) {
993       unsigned to = _lsb(att);
994       moves = add_move(moves, false, from, to);
995     }
996   }
997   for (b = us & pos->pawns; b; b = poplsb(b)) {
998     unsigned from = _lsb(b);
999     unsigned next = from + (pos->turn ? 8 : -8);
1000     att = pawn_attacks(from, pos->turn);
1001     if (pos->ep != 0 && ((att & board(pos->ep)) != 0)) {
1002       unsigned to = pos->ep;
1003       moves = add_move(moves, false, from, to);
1004     }
1005     att &= them;
1006     if ((board(next) & occ) == 0) {
1007       att |= board(next);
1008       unsigned next2 = from + (pos->turn ? 16 : -16);
1009       if ((pos->turn ? rank(from) == 1 : rank(from) == 6) &&
1010           ((board(next2) & occ) == 0))
1011         att |= board(next2);
1012     }
1013     for (; att; att = poplsb(att)) {
1014       unsigned to = _lsb(att);
1015       moves = add_move(moves, (rank(to) == 7 || rank(to) == 0), from, to);
1016     }
1017   }
1018   return moves;
1019 }
1020 
1021 /*
1022  * Test if the given move is an en passant capture.
1023  */
is_en_passant(const struct pos * pos,uint16_t move)1024 static bool is_en_passant(const struct pos *pos, uint16_t move) {
1025   uint16_t from = move_from(move);
1026   uint16_t to = move_to(move);
1027   uint64_t us = (pos->turn ? pos->white : pos->black);
1028   if (pos->ep == 0)
1029     return false;
1030   if (to != pos->ep)
1031     return false;
1032   if ((board(from) & us & pos->pawns) != 0)
1033     return false;
1034   return true;
1035 }
1036 
1037 /*
1038  * Test if the given position is legal (can the king be captured?)
1039  */
is_legal(const struct pos * pos)1040 static bool is_legal(const struct pos *pos) {
1041   uint64_t occ = pos->white | pos->black;
1042   uint64_t us = (pos->turn ? pos->black : pos->white), them =
1043       (pos->turn ? pos->white : pos->black);
1044   uint64_t king = pos->kings & us;
1045   unsigned sq = _lsb(king);
1046   if (king_attacks(sq) & (pos->kings & them))
1047     return false;
1048   uint64_t ratt = rook_attacks(sq, occ);
1049   uint64_t batt = bishop_attacks(sq, occ);
1050   if (ratt & (pos->rooks & them))
1051     return false;
1052   if (batt & (pos->bishops & them))
1053     return false;
1054   if ((ratt | batt) & (pos->queens & them))
1055     return false;
1056   if (knight_attacks(sq) & (pos->knights & them))
1057     return false;
1058   if (pawn_attacks(sq, !pos->turn) & (pos->pawns & them))
1059     return false;
1060   return true;
1061 }
1062 
1063 /*
1064  * Test if the king is in check.
1065  */
is_check(const struct pos * pos)1066 static bool is_check(const struct pos *pos) {
1067   uint64_t occ = pos->white | pos->black;
1068   uint64_t us = (pos->turn ? pos->white : pos->black), them =
1069       (pos->turn ? pos->black : pos->white);
1070   uint64_t king = pos->kings & us;
1071   unsigned sq = _lsb(king);
1072   uint64_t ratt = rook_attacks(sq, occ);
1073   uint64_t batt = bishop_attacks(sq, occ);
1074   if (ratt & (pos->rooks & them))
1075     return true;
1076   if (batt & (pos->bishops & them))
1077     return true;
1078   if ((ratt | batt) & (pos->queens & them))
1079     return true;
1080   if (knight_attacks(sq) & (pos->knights & them))
1081     return true;
1082   if (pawn_attacks(sq, pos->turn) & (pos->pawns & them))
1083     return true;
1084   return false;
1085 }
1086 
1087 /*
1088  * Test if the king is in checkmate.
1089  */
is_mate(const struct pos * pos)1090 static bool is_mate(const struct pos *pos) {
1091   if (!is_check(pos))
1092     return false;
1093   uint16_t moves0[MAX_MOVES];
1094   uint16_t *moves = moves0;
1095   uint16_t *end = gen_moves(pos, moves);
1096   for (; moves < end; moves++) {
1097     struct pos pos1;
1098     if (do_move(&pos1, pos, *moves))
1099       return false;
1100   }
1101   return true;
1102 }
1103 
1104 /*
1105  * Test if the position is valid.
1106  */
is_valid(const struct pos * pos)1107 static bool is_valid(const struct pos *pos) {
1108   if (popcount(pos->kings) != 2)
1109     return false;
1110   if (popcount(pos->kings & pos->white) != 1)
1111     return false;
1112   if (popcount(pos->kings & pos->black) != 1)
1113     return false;
1114   if ((pos->white & pos->black) != 0)
1115     return false;
1116   if ((pos->kings & pos->queens) != 0)
1117     return false;
1118   if ((pos->kings & pos->rooks) != 0)
1119     return false;
1120   if ((pos->kings & pos->bishops) != 0)
1121     return false;
1122   if ((pos->kings & pos->knights) != 0)
1123     return false;
1124   if ((pos->kings & pos->pawns) != 0)
1125     return false;
1126   if ((pos->queens & pos->rooks) != 0)
1127     return false;
1128   if ((pos->queens & pos->bishops) != 0)
1129     return false;
1130   if ((pos->queens & pos->knights) != 0)
1131     return false;
1132   if ((pos->queens & pos->pawns) != 0)
1133     return false;
1134   if ((pos->rooks & pos->bishops) != 0)
1135     return false;
1136   if ((pos->rooks & pos->knights) != 0)
1137     return false;
1138   if ((pos->rooks & pos->pawns) != 0)
1139     return false;
1140   if ((pos->bishops & pos->knights) != 0)
1141     return false;
1142   if ((pos->bishops & pos->pawns) != 0)
1143     return false;
1144   if ((pos->knights & pos->pawns) != 0)
1145     return false;
1146   if ((pos->white | pos->black) !=
1147       (pos->kings | pos->queens | pos->rooks | pos->
1148           bishops | pos->knights | pos->pawns))
1149     return false;
1150   return is_legal(pos);
1151 }
1152 
1153 #define do_bb_move(b, from, to)                                         \
1154     (((b) & (~board(to)) & (~board(from))) |                            \
1155         ((((b) >> (from)) & 0x1) << (to)))
1156 
do_move(struct pos * pos,const struct pos * pos0,uint16_t move)1157 static bool do_move(struct pos *pos, const struct pos *pos0, uint16_t move) {
1158   unsigned from = move_from(move);
1159   unsigned to = move_to(move);
1160   unsigned promotes = move_promotes(move);
1161   pos->turn = !pos0->turn;
1162   pos->white = do_bb_move(pos0->white, from, to);
1163   pos->black = do_bb_move(pos0->black, from, to);
1164   pos->kings = do_bb_move(pos0->kings, from, to);
1165   pos->queens = do_bb_move(pos0->queens, from, to);
1166   pos->rooks = do_bb_move(pos0->rooks, from, to);
1167   pos->bishops = do_bb_move(pos0->bishops, from, to);
1168   pos->knights = do_bb_move(pos0->knights, from, to);
1169   pos->pawns = do_bb_move(pos0->pawns, from, to);
1170   pos->ep = 0;
1171   if (promotes != TB_PROMOTES_NONE) {
1172     pos->pawns &= ~board(to); // Promotion
1173     switch (promotes) {
1174       case TB_PROMOTES_QUEEN:
1175         pos->queens |= board(to);
1176         break;
1177       case TB_PROMOTES_ROOK:
1178         pos->rooks |= board(to);
1179         break;
1180       case TB_PROMOTES_BISHOP:
1181         pos->bishops |= board(to);
1182         break;
1183       case TB_PROMOTES_KNIGHT:
1184         pos->knights |= board(to);
1185         break;
1186     }
1187     pos->rule50 = 0;
1188   } else if ((board(from) & pos0->pawns) != 0) {
1189     pos->rule50 = 0; // Pawn move
1190     if (rank(from) == 1 && rank(to) == 3 &&
1191         (pawn_attacks(from + 8, true) & pos0->pawns & pos0->black) != 0)
1192       pos->ep = from + 8;
1193     else if (rank(from) == 6 && rank(to) == 4 &&
1194         (pawn_attacks(from - 8, false) & pos0->pawns & pos0->white) != 0)
1195       pos->ep = from - 8;
1196     else if (to == pos0->ep) {
1197       unsigned ep_to = (pos0->turn ? to + 8 : to - 8);
1198       uint64_t ep_mask = ~board(ep_to);
1199       pos->white &= ep_mask;
1200       pos->black &= ep_mask;
1201       pos->pawns &= ep_mask;
1202     }
1203   } else if ((board(to) & (pos0->white | pos0->black)) != 0)
1204     pos->rule50 = 0; // Capture
1205   else
1206     pos->rule50 = pos0->rule50 + 1; // Normal move
1207   if (!is_legal(pos))
1208     return false;
1209   return true;
1210 }
1211 
probe_ab(const struct pos * pos,int alpha,int beta,int * success)1212 static int probe_ab(const struct pos *pos, int alpha, int beta, int *success) {
1213   int v;
1214   uint16_t moves0[64];
1215   uint16_t *moves = moves0;
1216   uint16_t *end = gen_captures_or_promotions(pos, moves);
1217   for (; moves < end; moves++) {
1218     if (is_en_passant(pos, *moves))
1219       continue;
1220     struct pos pos1;
1221     if (!do_move(&pos1, pos, *moves))
1222       continue;
1223     v = -probe_ab(&pos1, -beta, -alpha, success);
1224     if (*success == 0)
1225       return 0;
1226     if (v > alpha) {
1227       if (v >= beta) {
1228         *success = 2;
1229         return v;
1230       }
1231       alpha = v;
1232     }
1233   }
1234 
1235   v = probe_wdl_table(pos, success);
1236   if (*success == 0)
1237     return 0;
1238   if (alpha >= v) {
1239     *success = 1 + (alpha > 0);
1240     return alpha;
1241   } else {
1242     *success = 1;
1243     return v;
1244   }
1245 }
1246 
probe_wdl(const struct pos * pos,int * success)1247 static int probe_wdl(const struct pos *pos, int *success) {
1248   *success = 1;
1249   int v = probe_ab(pos, -2, 2, success);
1250   if (*success == 0)
1251     return 0;
1252 
1253  // If en passant is not possible, we are done.
1254   if (pos->ep == 0)
1255     return v;
1256 
1257  // Now handle en passant.
1258   int v1 = -3;
1259   uint16_t moves0[2];           // Max=2 possible en-passant captures.
1260   uint16_t *moves = moves0;
1261   uint16_t *end = gen_pawn_ep_captures(pos, moves);
1262   for (; moves < end; moves++) {
1263     struct pos pos1;
1264     if (!do_move(&pos1, pos, *moves))
1265       continue;
1266     int v0 = -probe_ab(pos, -2, 2, success);
1267     if (*success == 0)
1268       return 0;
1269     if (v0 > v1)
1270       v1 = v0;
1271   }
1272   if (v1 > -3) {
1273     if (v1 >= v)
1274       v = v1;
1275     else if (v == 0) {
1276      // Check whether there is at least one legal non-ep move.
1277       uint16_t moves0[MAX_MOVES];
1278       uint16_t *moves = moves0;
1279       uint16_t *end = gen_moves(pos, moves);
1280       bool found = false;
1281       for (; moves < end; moves++) {
1282         if (is_en_passant(pos, *moves))
1283           continue;
1284         struct pos pos1;
1285         if (do_move(&pos1, pos, *moves)) {
1286           found = true;
1287           break;
1288         }
1289       }
1290       if (!found)
1291         v = v1; // Forced to play the losing ep capture.
1292     }
1293   }
1294 
1295   return v;
1296 }
1297 
probe_dtz_no_ep(const struct pos * pos,int * success)1298 static int probe_dtz_no_ep(const struct pos *pos, int *success) {
1299   int wdl, dtz;
1300   wdl = probe_ab(pos, -2, 2, success);
1301   if (wdl == 0)
1302     return 0;
1303   if (*success == 2)
1304     return wdl == 2 ? 1 : 101;
1305 
1306   uint16_t moves0[MAX_MOVES];
1307   uint16_t *moves = moves0, *end = NULL;
1308 
1309   if (wdl > 0) {
1310    // Generate at least all legal non-capturing pawn moves
1311    // including non-capturing promotions.
1312     end = gen_pawn_quiets_or_promotions(pos, moves);
1313     for (; moves < end; moves++) {
1314       struct pos pos1;
1315       if (!do_move(&pos1, pos, *moves))
1316         continue;
1317      //int v = pos.ep_square() == SQ_NONE ? -probe_ab(pos, -2, -wdl + 1, success)
1318      //                                   : -probe_wdl(pos, success);
1319      //int v = -probe_ab(&pos1, -2, -wdl + 1, success);removed mfb
1320       int v = (pos1.ep == 0 ? -probe_ab(&pos1, -2, -wdl + 1, success) : -probe_wdl(&pos1, success)); //added mfb
1321       if (*success == 0)
1322         return 0;
1323       if (v == wdl)
1324         return (v == 2 ? 1 : 101);
1325     }
1326   }
1327 
1328   dtz = 1 + probe_dtz_table(pos, wdl, success);
1329   if (*success >= 0) {
1330     if (wdl & 1)
1331       dtz += 100;
1332     return (wdl >= 0 ? dtz : -dtz);
1333   }
1334 
1335   if (wdl > 0) {
1336     int best = BEST_NONE;
1337     moves = moves0;
1338     end = gen_moves(pos, moves);
1339     for (; moves < end; moves++) {
1340       struct pos pos1;
1341       if (!do_move(&pos1, pos, *moves))
1342         continue;
1343       if (pos1.rule50 == 0)
1344         continue;
1345       int v = -probe_dtz(&pos1, success);
1346       if (*success == 0)
1347         return 0;
1348       if (v > 0 && v + 1 < best)
1349         best = v + 1;
1350     }
1351     assert(best != BEST_NONE);
1352     return best;
1353   } else {
1354     int best = -1;
1355     end = gen_moves(pos, moves);
1356     for (; moves < end; moves++) {
1357       int v;
1358       struct pos pos1;
1359       if (!do_move(&pos1, pos, *moves))
1360         continue;
1361       if (pos1.rule50 == 0) {
1362         if (wdl == -2)
1363           v = -1;
1364         else {
1365           v = probe_ab(&pos1, 1, 2, success);
1366           v = (v == 2) ? 0 : -101;
1367         }
1368       } else
1369         v = -probe_dtz(&pos1, success) - 1;
1370       if (*success == 0)
1371         return 0;
1372       if (v < best)
1373         best = v;
1374     }
1375     return best;
1376   }
1377 }
1378 
1379 static const int wdl_to_dtz[] = {
1380   -1, -101, 0, 101, 1
1381 };
1382 
1383 /*
1384  * Probe the DTZ table for a particular position.
1385  * If *success != 0, the probe was successful.
1386  * The return value is from the point of view of the side to move:
1387  *         n < -100 : loss, but draw under 50-move rule
1388  * -100 <= n < -1   : loss in n ply (assuming 50-move counter == 0)
1389  *         0            : draw
1390  *     1 < n <= 100 : win in n ply (assuming 50-move counter == 0)
1391  *   100 < n        : win, but draw under 50-move rule
1392  *
1393  * The return value n can be off by 1: a return value -n can mean a loss
1394  * in n+1 ply and a return value +n can mean a win in n+1 ply. This
1395  * cannot happen for tables with positions exactly on the "edge" of
1396  * the 50-move rule.
1397  *
1398  * This implies that if dtz > 0 is returned, the position is certainly
1399  * a win if dtz + 50-move-counter <= 99. Care must be taken that the engine
1400  * picks moves that preserve dtz + 50-move-counter <= 99.
1401  *
1402  * If n = 100 immediately after a capture or pawn move, then the position
1403  * is also certainly a win, and during the whole phase until the next
1404  * capture or pawn move, the inequality to be preserved is
1405  * dtz + 50-movecounter <= 100.
1406  *
1407  * In short, if a move is available resulting in dtz + 50-move-counter <= 99,
1408  * then do not accept moves leading to dtz + 50-move-counter == 100.
1409  */
probe_dtz(const struct pos * pos,int * success)1410 static int probe_dtz(const struct pos *pos, int *success) {
1411   *success = 1;
1412   int v = probe_dtz_no_ep(pos, success);
1413   if (*success == 0)
1414     return 0;
1415 
1416   if (pos->ep == 0)
1417     return v;
1418 
1419   int v1 = -3;
1420   uint16_t moves0[2];           // Max=2 possible en-passant captures.
1421   uint16_t *moves = moves0;
1422   uint16_t *end = gen_pawn_ep_captures(pos, moves);
1423   for (; moves < end; moves++) {
1424     struct pos pos1;
1425     if (!do_move(&pos1, pos, *moves))
1426       continue;
1427     int v0 = -probe_ab(pos, -2, 2, success);
1428     if (*success == 0)
1429       return 0;
1430     if (v0 > v1)
1431       v1 = v0;
1432   }
1433 
1434   if (v1 > -3) {
1435     v1 = wdl_to_dtz[v1 + 2];
1436     if (v < -100) {
1437       if (v1 >= 0)
1438         v = v1;
1439     } else if (v < 0) {
1440       if (v1 >= 0 || v1 < -100)
1441         v = v1;
1442     } else if (v > 100) {
1443       if (v1 > 0)
1444         v = v1;
1445     } else if (v > 0) {
1446       if (v1 == 1)
1447         v = v1;
1448     } else if (v1 >= 0)
1449       v = v1;
1450     else {
1451       uint16_t moves0[MAX_MOVES];
1452       uint16_t *moves = moves0;
1453       uint16_t *end = gen_moves(pos, moves);
1454       bool found = false;
1455       for (; moves < end; moves++) {
1456         if (is_en_passant(pos, *moves))
1457           continue;
1458         struct pos pos1;
1459         if (do_move(&pos1, pos, *moves)) {
1460           found = true;
1461           break;
1462         }
1463       }
1464       if (!found)
1465         v = v1; // Forced to play the losing ep capture.
1466     }
1467   }
1468 
1469   return v;
1470 }
1471 
dtz_to_wdl(int cnt50,int dtz)1472 unsigned dtz_to_wdl(int cnt50, int dtz) {
1473   int wdl = 0;
1474   if (dtz > 0)
1475     wdl = (dtz + cnt50 <= 100 ? 2 : 1);
1476   else if (dtz < 0)
1477     wdl = (-dtz + cnt50 <= 100 ? -2 : -1);
1478   return wdl + 2;
1479 }
1480 
probe_root(const struct pos * pos,int * score,unsigned * results)1481 static uint16_t probe_root(const struct pos *pos, int *score,
1482     unsigned *results) {
1483   int success;
1484   int dtz = probe_dtz(pos, &success);
1485   if (!success)
1486     return 0;
1487 
1488   int16_t scores[MAX_MOVES];
1489   uint16_t moves0[MAX_MOVES];
1490   uint16_t *moves = moves0;
1491   uint16_t *end = gen_moves(pos, moves);
1492   size_t len = end - moves;
1493   size_t num_draw = 0;
1494   unsigned j = 0;
1495   unsigned i = 0;               //mfb
1496   for (i = 0; i < len; i++) {
1497     struct pos pos1;
1498     if (!do_move(&pos1, pos, moves[i])) {
1499       scores[i] = SCORE_ILLEGAL;
1500       continue;
1501     }
1502     int v = 0;
1503     if (dtz > 0 && is_mate(&pos1))
1504       v = 1;
1505     else {
1506       if (pos1.rule50 != 0) {
1507         v = -probe_dtz(&pos1, &success);
1508         if (v > 0)
1509           v++;
1510         else if (v < 0)
1511           v--;
1512       } else {
1513         v = -probe_wdl(&pos1, &success);
1514         v = wdl_to_dtz[v + 2];
1515       }
1516     }
1517     num_draw += (v == 0);
1518     if (!success)
1519       return 0;
1520     scores[i] = v;
1521     if (results != NULL) {
1522       unsigned res = 0;
1523       res = TB_SET_WDL(res, dtz_to_wdl(pos->rule50, v));
1524       res = TB_SET_FROM(res, move_from(moves[i]));
1525       res = TB_SET_TO(res, move_to(moves[i]));
1526       res = TB_SET_PROMOTES(res, move_promotes(moves[i]));
1527       res = TB_SET_EP(res, is_en_passant(pos, moves[i]));
1528       res = TB_SET_DTZ(res, (dtz < 0 ? -dtz : dtz));
1529       results[j++] = res;
1530     }
1531   }
1532   if (results != NULL)
1533     results[j++] = TB_RESULT_FAILED;
1534   if (score != NULL)
1535     *score = dtz;
1536 
1537  // Now be a bit smart about filtering out moves.
1538   if (dtz > 0) // winning (or 50-move rule draw)
1539   {
1540     int best = BEST_NONE;
1541     uint16_t best_move = 0;
1542     for (i = 0; i < len; i++) {
1543       int v = scores[i];
1544       if (v == SCORE_ILLEGAL)
1545         continue;
1546       if (v > 0 && v < best) {
1547         best = v;
1548         best_move = moves[i];
1549       }
1550     }
1551     return (best == BEST_NONE ? 0 : best_move);
1552   } else if (dtz < 0) // losing (or 50-move rule draw)
1553   {
1554     int best = 0;
1555     uint16_t best_move = 0;
1556     for (i = 0; i < len; i++) {
1557       int v = scores[i];
1558       if (v == SCORE_ILLEGAL)
1559         continue;
1560       if (v < best) {
1561         best = v;
1562         best_move = moves[i];
1563       }
1564     }
1565     return (best == 0 ? MOVE_CHECKMATE : best_move);
1566   } else // drawing
1567   {
1568    // Check for stalemate:
1569     if (num_draw == 0)
1570       return MOVE_STALEMATE;
1571 
1572    // Select a "random" move that preserves the draw.
1573    // Uses calc_key as the PRNG.
1574     size_t count = calc_key(pos, !pos->turn) % num_draw;
1575     for (i = 0; i < len; i++) {
1576       int v = scores[i];
1577       if (v == SCORE_ILLEGAL)
1578         continue;
1579       if (v == 0) {
1580         if (count == 0)
1581           return moves[i];
1582         count--;
1583       }
1584     }
1585     return 0;
1586   }
1587 }
1588 
tb_init_impl(const char * path)1589 extern bool tb_init_impl(const char *path) {
1590   if (sizeof(uint64_t) != 8 && // Paranoid check
1591       sizeof(uint32_t) != 4 && sizeof(uint16_t) != 2 && sizeof(uint8_t) != 1)
1592     return false;
1593   king_attacks_init();
1594   knight_attacks_init();
1595   bishop_attacks_init();
1596   rook_attacks_init();
1597   pawn_attacks_init();
1598   if (path == NULL)
1599     path = "";
1600   init_tablebases(path);
1601   return true;
1602 }
1603 
tb_probe_wdl_impl(uint64_t white,uint64_t black,uint64_t kings,uint64_t queens,uint64_t rooks,uint64_t bishops,uint64_t knights,uint64_t pawns,unsigned ep,bool turn,uint64_t hash)1604 extern unsigned tb_probe_wdl_impl(uint64_t white, uint64_t black,
1605     uint64_t kings, uint64_t queens, uint64_t rooks, uint64_t bishops,
1606     uint64_t knights, uint64_t pawns, unsigned ep, bool turn, uint64_t hash) {
1607   struct pos pos = {
1608     white,
1609     black,
1610     kings,
1611     queens,
1612     rooks,
1613     bishops,
1614     knights,
1615     pawns,
1616     0,
1617     ep,
1618     turn
1619   };
1620   static uint64_t cache[4096] = { 0 };
1621   uint64_t idx = hash % 1024;
1622   if ((cache[idx] & ~0x7) == (hash & ~0x7)) {
1623    // Hit
1624 //        FILE *F = fopen("debug.txt", "a");
1625 //        fprintf(F, "CACHE_HIT = %.16lX (result=%u)\n", cache[idx],
1626 //            (unsigned)(cache[idx] & 0x7));
1627 //        fclose(F);
1628     return (cache[idx] & 0x7);
1629   }
1630  // Miss
1631   int success;
1632   int v = probe_wdl(&pos, &success);
1633   if (success == 0)
1634     return TB_RESULT_FAILED;
1635   unsigned result = (unsigned) (v + 2);
1636   hash &= ~0x7;
1637   hash |= (uint64_t) result;
1638   cache[idx] = hash;
1639   return result;
1640 }
1641 
tb_probe_root_impl(uint64_t white,uint64_t black,uint64_t kings,uint64_t queens,uint64_t rooks,uint64_t bishops,uint64_t knights,uint64_t pawns,unsigned rule50,unsigned ep,bool turn,unsigned * results)1642 extern unsigned tb_probe_root_impl(uint64_t white, uint64_t black,
1643     uint64_t kings, uint64_t queens, uint64_t rooks, uint64_t bishops,
1644     uint64_t knights, uint64_t pawns, unsigned rule50, unsigned ep, bool turn,
1645     unsigned *results) {
1646   struct pos pos = {
1647     white,
1648     black,
1649     kings,
1650     queens,
1651     rooks,
1652     bishops,
1653     knights,
1654     pawns,
1655     rule50,
1656     ep,
1657     turn
1658   };
1659   int dtz;
1660   if (!is_valid(&pos))
1661     return TB_RESULT_FAILED;
1662   uint16_t move = probe_root(&pos, &dtz, results);
1663   if (move == 0)
1664     return TB_RESULT_FAILED;
1665   if (move == MOVE_CHECKMATE)
1666     return TB_RESULT_CHECKMATE;
1667   if (move == MOVE_STALEMATE)
1668     return TB_RESULT_STALEMATE;
1669   unsigned res = 0;
1670   res = TB_SET_WDL(res, dtz_to_wdl(rule50, dtz));
1671   res = TB_SET_FROM(res, move_from(move));
1672   res = TB_SET_TO(res, move_to(move));
1673   res = TB_SET_PROMOTES(res, move_promotes(move));
1674   res = TB_SET_EP(res, is_en_passant(&pos, move));
1675   return res;
1676 }
1677 
1678 #ifndef TB_NO_HELPER_API
1679 
tb_pop_count(uint64_t bb)1680 unsigned tb_pop_count(uint64_t bb) {
1681   return popcount(bb);
1682 }
1683 
tb_lsb(uint64_t bb)1684 unsigned tb_lsb(uint64_t bb) {
1685   return _lsb(bb);
1686 }
1687 
tb_pop_lsb(uint64_t bb)1688 uint64_t tb_pop_lsb(uint64_t bb) {
1689   return poplsb(bb);
1690 }
1691 
tb_king_attacks(unsigned sq)1692 uint64_t tb_king_attacks(unsigned sq) {
1693   return king_attacks(sq);
1694 }
1695 
tb_queen_attacks(unsigned sq,uint64_t occ)1696 uint64_t tb_queen_attacks(unsigned sq, uint64_t occ) {
1697   return queen_attacks(sq, occ);
1698 }
1699 
tb_rook_attacks(unsigned sq,uint64_t occ)1700 uint64_t tb_rook_attacks(unsigned sq, uint64_t occ) {
1701   return rook_attacks(sq, occ);
1702 }
1703 
tb_bishop_attacks(unsigned sq,uint64_t occ)1704 uint64_t tb_bishop_attacks(unsigned sq, uint64_t occ) {
1705   return bishop_attacks(sq, occ);
1706 }
1707 
tb_knight_attacks(unsigned sq)1708 uint64_t tb_knight_attacks(unsigned sq) {
1709   return knight_attacks(sq);
1710 }
1711 
tb_pawn_attacks(unsigned sq,bool color)1712 uint64_t tb_pawn_attacks(unsigned sq, bool color) {
1713   return pawn_attacks(sq, color);
1714 }
1715 
1716 #endif                          /* TB_NO_HELPER_API */
1717