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