2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2009 Marco Costalba
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 Stockfish is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
29 #include "direction.h"
34 const uint64_t BMult[64] = {
35 0x440049104032280ULL, 0x1021023c82008040ULL, 0x404040082000048ULL,
36 0x48c4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL,
37 0x181011002e06040ULL, 0x9101004104200e00ULL, 0x1240848848310401ULL,
38 0x2000142828050024ULL, 0x1004024d5000ULL, 0x102044400800200ULL,
39 0x8108108820112000ULL, 0xa880818210c00046ULL, 0x4008008801082000ULL,
40 0x60882404049400ULL, 0x104402004240810ULL, 0xa002084250200ULL,
41 0x100b0880801100ULL, 0x4080201220101ULL, 0x44008080a00000ULL,
42 0x202200842000ULL, 0x5006004882d00808ULL, 0x200045080802ULL,
43 0x86100020200601ULL, 0xa802080a20112c02ULL, 0x80411218080900ULL,
44 0x200a0880080a0ULL, 0x9a01010000104000ULL, 0x28008003100080ULL,
45 0x211021004480417ULL, 0x401004188220806ULL, 0x825051400c2006ULL,
46 0x140c0210943000ULL, 0x242800300080ULL, 0xc2208120080200ULL,
47 0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL,
48 0x822081014405ULL, 0x800c049e40400804ULL, 0x4a0404028a000820ULL,
49 0x22060201041200ULL, 0x360904200840801ULL, 0x881a08208800400ULL,
50 0x60202c00400420ULL, 0x1204440086061400ULL, 0x8184042804040ULL,
51 0x64040315300400ULL, 0xc01008801090a00ULL, 0x808010401140c00ULL,
52 0x4004830c2020040ULL, 0x80005002020054ULL, 0x40000c14481a0490ULL,
53 0x10500101042048ULL, 0x1010100200424000ULL, 0x640901901040ULL,
54 0xa0201014840ULL, 0x840082aa011002ULL, 0x10010840084240aULL,
55 0x420400810420608ULL, 0x8d40230408102100ULL, 0x4a00200612222409ULL,
59 const uint64_t RMult[64] = {
60 0xa8002c000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL,
61 0x380180080141000ULL, 0x1a00060008211044ULL, 0x410001000a0c0008ULL,
62 0x9500060004008100ULL, 0x100024284a20700ULL, 0x802140008000ULL,
63 0x80c01002a00840ULL, 0x402004282011020ULL, 0x9862000820420050ULL,
64 0x1001448011100ULL, 0x6432800200800400ULL, 0x40100010002000cULL,
65 0x2800d0010c080ULL, 0x90c0008000803042ULL, 0x4010004000200041ULL,
66 0x3010010200040ULL, 0xa40828028001000ULL, 0x123010008000430ULL,
67 0x24008004020080ULL, 0x60040001104802ULL, 0x582200028400d1ULL,
68 0x4000802080044000ULL, 0x408208200420308ULL, 0x610038080102000ULL,
69 0x3601000900100020ULL, 0x80080040180ULL, 0xc2020080040080ULL,
70 0x80084400100102ULL, 0x4022408200014401ULL, 0x40052040800082ULL,
71 0xb08200280804000ULL, 0x8a80a008801000ULL, 0x4000480080801000ULL,
72 0x911808800801401ULL, 0x822a003002001894ULL, 0x401068091400108aULL,
73 0x4a10a00004cULL, 0x2000800640008024ULL, 0x1486408102020020ULL,
74 0x100a000d50041ULL, 0x810050020b0020ULL, 0x204000800808004ULL,
75 0x20048100a000cULL, 0x112000831020004ULL, 0x9000040810002ULL,
76 0x440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL,
77 0x4b824a2010010100ULL, 0x4080801810c0080ULL, 0x400802a0080ULL,
78 0x8224080110026400ULL, 0x40002c4104088200ULL, 0x1002100104a0282ULL,
79 0x1208400811048021ULL, 0x3201014a40d02001ULL, 0x5100019200501ULL,
80 0x101000208001005ULL, 0x2008450080702ULL, 0x1002080301d00cULL,
84 const int BShift[64] = {
85 58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59,
86 59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59,
87 59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59,
88 59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58
91 const int RShift[64] = {
92 52, 53, 53, 53, 53, 53, 53, 52, 53, 54, 54, 54, 54, 54, 54, 53,
93 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53,
94 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53,
95 53, 54, 54, 54, 54, 54, 54, 53, 52, 53, 53, 53, 53, 53, 53, 52
98 #else // if !defined(IS_64BIT)
100 const uint64_t BMult[64] = {
101 0x54142844c6a22981ULL, 0x710358a6ea25c19eULL, 0x704f746d63a4a8dcULL,
102 0xbfed1a0b80f838c5ULL, 0x90561d5631e62110ULL, 0x2804260376e60944ULL,
103 0x84a656409aa76871ULL, 0xf0267f64c28b6197ULL, 0x70764ebb762f0585ULL,
104 0x92aa09e0cfe161deULL, 0x41ee1f6bb266f60eULL, 0xddcbf04f6039c444ULL,
105 0x5a3fab7bac0d988aULL, 0xd3727877fa4eaa03ULL, 0xd988402d868ddaaeULL,
106 0x812b291afa075c7cULL, 0x94faf987b685a932ULL, 0x3ed867d8470d08dbULL,
107 0x92517660b8901de8ULL, 0x2d97e43e058814b4ULL, 0x880a10c220b25582ULL,
108 0xc7c6520d1f1a0477ULL, 0xdbfc7fbcd7656aa6ULL, 0x78b1b9bfb1a2b84fULL,
109 0x2f20037f112a0bc1ULL, 0x657171ea2269a916ULL, 0xc08302b07142210eULL,
110 0x880a4403064080bULL, 0x3602420842208c00ULL, 0x852800dc7e0b6602ULL,
111 0x595a3fbbaa0f03b2ULL, 0x9f01411558159d5eULL, 0x2b4a4a5f88b394f2ULL,
112 0x4afcbffc292dd03aULL, 0x4a4094a3b3f10522ULL, 0xb06f00b491f30048ULL,
113 0xd5b3820280d77004ULL, 0x8b2e01e7c8e57a75ULL, 0x2d342794e886c2e6ULL,
114 0xc302c410cde21461ULL, 0x111f426f1379c274ULL, 0xe0569220abb31588ULL,
115 0x5026d3064d453324ULL, 0xe2076040c343cd8aULL, 0x93efd1e1738021eeULL,
116 0xb680804bed143132ULL, 0x44e361b21986944cULL, 0x44c60170ef5c598cULL,
117 0xf4da475c195c9c94ULL, 0xa3afbb5f72060b1dULL, 0xbc75f410e41c4ffcULL,
118 0xb51c099390520922ULL, 0x902c011f8f8ec368ULL, 0x950b56b3d6f5490aULL,
119 0x3909e0635bf202d0ULL, 0x5744f90206ec10ccULL, 0xdc59fd76317abbc1ULL,
120 0x881c7c67fcbfc4f6ULL, 0x47ca41e7e440d423ULL, 0xeb0c88112048d004ULL,
121 0x51c60e04359aef1aULL, 0x1aa1fe0e957a5554ULL, 0xdd9448db4f5e3104ULL,
122 0xdc01f6dca4bebbdcULL,
125 const uint64_t RMult[64] = {
126 0xd7445cdec88002c0ULL, 0xd0a505c1f2001722ULL, 0xe065d1c896002182ULL,
127 0x9a8c41e75a000892ULL, 0x8900b10c89002aa8ULL, 0x9b28d1c1d60005a2ULL,
128 0x15d6c88de002d9aULL, 0xb1dbfc802e8016a9ULL, 0x149a1042d9d60029ULL,
129 0xb9c08050599e002fULL, 0x132208c3af300403ULL, 0xc1000ce2e9c50070ULL,
130 0x9d9aa13c99020012ULL, 0xb6b078daf71e0046ULL, 0x9d880182fb6e002eULL,
131 0x52889f467e850037ULL, 0xda6dc008d19a8480ULL, 0x468286034f902420ULL,
132 0x7140ac09dc54c020ULL, 0xd76ffffa39548808ULL, 0xea901c4141500808ULL,
133 0xc91004093f953a02ULL, 0x2882afa8f6bb402ULL, 0xaebe335692442c01ULL,
134 0xe904a22079fb91eULL, 0x13a514851055f606ULL, 0x76c782018c8fe632ULL,
135 0x1dc012a9d116da06ULL, 0x3c9e0037264fffa6ULL, 0x2036002853c6e4a2ULL,
136 0xe3fe08500afb47d4ULL, 0xf38af25c86b025c2ULL, 0xc0800e2182cf9a40ULL,
137 0x72002480d1f60673ULL, 0x2500200bae6e9b53ULL, 0xc60018c1eefca252ULL,
138 0x600590473e3608aULL, 0x46002c4ab3fe51b2ULL, 0xa200011486bcc8d2ULL,
139 0xb680078095784c63ULL, 0x2742002639bf11aeULL, 0xc7d60021a5bdb142ULL,
140 0xc8c04016bb83d820ULL, 0xbd520028123b4842ULL, 0x9d1600344ac2a832ULL,
141 0x6a808005631c8a05ULL, 0x604600a148d5389aULL, 0xe2e40103d40dea65ULL,
142 0x945b5a0087c62a81ULL, 0x12dc200cd82d28eULL, 0x2431c600b5f9ef76ULL,
143 0xfb142a006a9b314aULL, 0x6870e00a1c97d62ULL, 0x2a9db2004a2689a2ULL,
144 0xd3594600caf5d1a2ULL, 0xee0e4900439344a7ULL, 0x89c4d266ca25007aULL,
145 0x3e0013a2743f97e3ULL, 0x180e31a0431378aULL, 0x3a9e465a4d42a512ULL,
146 0x98d0a11a0c0d9cc2ULL, 0x8e711c1aba19b01eULL, 0x8dcdc836dd201142ULL,
147 0x5ac08a4735370479ULL,
150 const int BShift[64] = {
151 26, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 27, 27,
152 27, 27, 25, 25, 25, 25, 27, 27, 27, 27, 25, 23, 23, 25, 27, 27,
153 27, 27, 25, 23, 23, 25, 27, 27, 27, 27, 25, 25, 25, 25, 27, 27,
154 27, 27, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 26
157 const int RShift[64] = {
158 20, 21, 21, 21, 21, 21, 21, 20, 21, 22, 22, 22, 22, 22, 22, 21,
159 21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21,
160 21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21,
161 21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20
164 #endif // defined(IS_64BIT)
168 int RAttackIndex[64];
169 Bitboard RAttacks[0x19000];
172 int BAttackIndex[64];
173 Bitboard BAttacks[0x1480];
175 Bitboard SetMaskBB[65];
176 Bitboard ClearMaskBB[65];
178 Bitboard StepAttackBB[16][64];
179 Bitboard RayBB[64][8];
180 Bitboard BetweenBB[64][64];
182 Bitboard PassedPawnMask[2][64];
183 Bitboard OutpostMask[2][64];
185 Bitboard BishopPseudoAttacks[64];
186 Bitboard RookPseudoAttacks[64];
187 Bitboard QueenPseudoAttacks[64];
191 //// Local definitions
197 void init_ray_bitboards();
199 void init_between_bitboards();
200 Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
201 int fmin, int fmax, int rmin, int rmax);
202 Bitboard index_to_bitboard(int index, Bitboard mask);
203 void init_sliding_attacks(Bitboard attacks[],
204 int attackIndex[], Bitboard mask[],
205 const int shift[2], const Bitboard mult[],
207 void init_pseudo_attacks();
215 /// print_bitboard() prints a bitboard in an easily readable format to the
216 /// standard output. This is sometimes useful for debugging.
218 void print_bitboard(Bitboard b) {
219 for(Rank r = RANK_8; r >= RANK_1; r--) {
220 std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
221 for(File f = FILE_A; f <= FILE_H; f++)
222 std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' ';
223 std::cout << "|" << std::endl;
225 std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
229 /// init_bitboards() initializes various bitboard arrays. It is called during
230 /// program initialization.
232 void init_bitboards() {
233 int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
234 int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
236 init_ray_bitboards();
238 init_between_bitboards();
239 init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas);
240 init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas);
241 init_pseudo_attacks();
245 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
246 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
247 /// nonzero bitboard.
249 #if defined(IS_64BIT) && !defined(USE_BSFQ)
251 static const int BitTable[64] = {
252 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15,
253 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39,
254 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43,
258 Square first_1(Bitboard b) {
259 return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
262 Square pop_1st_bit(Bitboard* b) {
265 return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
268 #elif !defined(USE_BSFQ)
270 static const int BitTable[64] = {
271 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
272 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
273 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
274 58, 20, 37, 17, 36, 8
277 Square first_1(Bitboard b) {
279 uint32_t fold = int(b) ^ int(b >> 32);
280 return Square(BitTable[(fold * 0x783a9b23) >> 26]);
293 // WARNING: Needs -fno-strict-aliasing compiler option
294 Square pop_1st_bit(Bitboard* bb) {
304 *((uint32_t*)bb) = b & (b - 1);
310 *((uint32_t*)bb+1) = b & (b - 1); // Little endian only?
313 return Square(BitTable[(b * 0x783a9b23) >> 26]);
320 // All functions below are used to precompute various bitboards during
321 // program initialization. Some of the functions may be difficult to
322 // understand, but they all seem to work correctly, and it should never
323 // be necessary to touch any of them.
326 SetMaskBB[SQ_NONE] = 0ULL;
327 ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE];
328 for(Square s = SQ_A1; s <= SQ_H8; s++) {
329 SetMaskBB[s] = (1ULL << s);
330 ClearMaskBB[s] = ~SetMaskBB[s];
332 for(Color c = WHITE; c <= BLACK; c++)
333 for(Square s = SQ_A1; s <= SQ_H8; s++) {
334 PassedPawnMask[c][s] =
335 in_front_bb(c, s) & this_and_neighboring_files_bb(s);
336 OutpostMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
341 void init_ray_bitboards() {
342 int d[8] = {1, -1, 16, -16, 17, -17, 15, -15};
343 for(int i = 0; i < 128; i = (i + 9) & ~8) {
344 for(int j = 0; j < 8; j++) {
345 RayBB[(i&7)|((i>>4)<<3)][j] = EmptyBoardBB;
346 for(int k = i + d[j]; (k & 0x88) == 0; k += d[j])
347 set_bit(&(RayBB[(i&7)|((i>>4)<<3)][j]), Square((k&7)|((k>>4)<<3)));
353 void init_attacks() {
357 {7,9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
358 {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}, {0}, {0},
359 {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
360 {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}
363 for(i = 0; i < 64; i++) {
364 for(j = 0; j <= int(BK); j++) {
365 StepAttackBB[j][i] = EmptyBoardBB;
366 for(k = 0; k < 8 && step[j][k] != 0; k++) {
368 if(l >= 0 && l < 64 && abs((i&7) - (l&7)) < 3)
369 StepAttackBB[j][i] |= (1ULL << l);
376 Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
377 int fmin=0, int fmax=7, int rmin=0, int rmax=7) {
378 Bitboard result = 0ULL;
379 int rk = sq / 8, fl = sq % 8, r, f, i;
380 for(i = 0; i < dirs; i++) {
381 int dx = deltas[i][0], dy = deltas[i][1];
382 for(f = fl+dx, r = rk+dy;
383 (dx==0 || (f>=fmin && f<=fmax)) && (dy==0 || (r>=rmin && r<=rmax));
385 result |= (1ULL << (f + r*8));
386 if(block & (1ULL << (f + r*8))) break;
393 void init_between_bitboards() {
394 SquareDelta step[8] = {
395 DELTA_E, DELTA_W, DELTA_N, DELTA_S, DELTA_NE, DELTA_SW, DELTA_NW, DELTA_SE
398 for(Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
399 for(Square s2 = SQ_A1; s2 <= SQ_H8; s2++) {
400 BetweenBB[s1][s2] = EmptyBoardBB;
401 d = signed_direction_between_squares(s1, s2);
402 if(d != SIGNED_DIR_NONE)
403 for(Square s3 = s1 + step[d]; s3 != s2; s3 += step[d])
404 set_bit(&(BetweenBB[s1][s2]), s3);
409 Bitboard index_to_bitboard(int index, Bitboard mask) {
410 int i, j, bits = count_1s(mask);
411 Bitboard result = 0ULL;
412 for(i = 0; i < bits; i++) {
413 j = pop_1st_bit(&mask);
414 if(index & (1 << i)) result |= (1ULL << j);
420 void init_sliding_attacks(Bitboard attacks[],
421 int attackIndex[], Bitboard mask[],
422 const int shift[2], const Bitboard mult[],
424 int i, j, k, index = 0;
426 for(i = 0; i < 64; i++) {
427 attackIndex[i] = index;
428 mask[i] = sliding_attacks(i, 0ULL, 4, deltas, 1, 6, 1, 6);
430 #if defined(IS_64BIT)
431 j = (1 << (64 - shift[i]));
433 j = (1 << (32 - shift[i]));
436 for(k = 0; k < j; k++) {
438 #if defined(IS_64BIT)
439 b = index_to_bitboard(k, mask[i]);
440 attacks[index + ((b * mult[i]) >> shift[i])] =
441 sliding_attacks(i, b, 4, deltas);
443 b = index_to_bitboard(k, mask[i]);
445 (unsigned(int(b) * int(mult[i]) ^
446 int(b >> 32) * int(mult[i] >> 32))
448 sliding_attacks(i, b, 4, deltas);
456 void init_pseudo_attacks() {
458 for(s = SQ_A1; s <= SQ_H8; s++) {
459 BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
460 RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB);
461 QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB);