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-2010 Marco Costalba, Joona Kiiski, Tord Romstad
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/>.
33 const uint64_t BMult[64] = {
34 0x440049104032280ULL, 0x1021023c82008040ULL, 0x404040082000048ULL,
35 0x48c4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL,
36 0x181011002e06040ULL, 0x9101004104200e00ULL, 0x1240848848310401ULL,
37 0x2000142828050024ULL, 0x1004024d5000ULL, 0x102044400800200ULL,
38 0x8108108820112000ULL, 0xa880818210c00046ULL, 0x4008008801082000ULL,
39 0x60882404049400ULL, 0x104402004240810ULL, 0xa002084250200ULL,
40 0x100b0880801100ULL, 0x4080201220101ULL, 0x44008080a00000ULL,
41 0x202200842000ULL, 0x5006004882d00808ULL, 0x200045080802ULL,
42 0x86100020200601ULL, 0xa802080a20112c02ULL, 0x80411218080900ULL,
43 0x200a0880080a0ULL, 0x9a01010000104000ULL, 0x28008003100080ULL,
44 0x211021004480417ULL, 0x401004188220806ULL, 0x825051400c2006ULL,
45 0x140c0210943000ULL, 0x242800300080ULL, 0xc2208120080200ULL,
46 0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL,
47 0x822081014405ULL, 0x800c049e40400804ULL, 0x4a0404028a000820ULL,
48 0x22060201041200ULL, 0x360904200840801ULL, 0x881a08208800400ULL,
49 0x60202c00400420ULL, 0x1204440086061400ULL, 0x8184042804040ULL,
50 0x64040315300400ULL, 0xc01008801090a00ULL, 0x808010401140c00ULL,
51 0x4004830c2020040ULL, 0x80005002020054ULL, 0x40000c14481a0490ULL,
52 0x10500101042048ULL, 0x1010100200424000ULL, 0x640901901040ULL,
53 0xa0201014840ULL, 0x840082aa011002ULL, 0x10010840084240aULL,
54 0x420400810420608ULL, 0x8d40230408102100ULL, 0x4a00200612222409ULL,
58 const uint64_t RMult[64] = {
59 0xa8002c000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL,
60 0x380180080141000ULL, 0x1a00060008211044ULL, 0x410001000a0c0008ULL,
61 0x9500060004008100ULL, 0x100024284a20700ULL, 0x802140008000ULL,
62 0x80c01002a00840ULL, 0x402004282011020ULL, 0x9862000820420050ULL,
63 0x1001448011100ULL, 0x6432800200800400ULL, 0x40100010002000cULL,
64 0x2800d0010c080ULL, 0x90c0008000803042ULL, 0x4010004000200041ULL,
65 0x3010010200040ULL, 0xa40828028001000ULL, 0x123010008000430ULL,
66 0x24008004020080ULL, 0x60040001104802ULL, 0x582200028400d1ULL,
67 0x4000802080044000ULL, 0x408208200420308ULL, 0x610038080102000ULL,
68 0x3601000900100020ULL, 0x80080040180ULL, 0xc2020080040080ULL,
69 0x80084400100102ULL, 0x4022408200014401ULL, 0x40052040800082ULL,
70 0xb08200280804000ULL, 0x8a80a008801000ULL, 0x4000480080801000ULL,
71 0x911808800801401ULL, 0x822a003002001894ULL, 0x401068091400108aULL,
72 0x4a10a00004cULL, 0x2000800640008024ULL, 0x1486408102020020ULL,
73 0x100a000d50041ULL, 0x810050020b0020ULL, 0x204000800808004ULL,
74 0x20048100a000cULL, 0x112000831020004ULL, 0x9000040810002ULL,
75 0x440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL,
76 0x4b824a2010010100ULL, 0x4080801810c0080ULL, 0x400802a0080ULL,
77 0x8224080110026400ULL, 0x40002c4104088200ULL, 0x1002100104a0282ULL,
78 0x1208400811048021ULL, 0x3201014a40d02001ULL, 0x5100019200501ULL,
79 0x101000208001005ULL, 0x2008450080702ULL, 0x1002080301d00cULL,
83 const int BShift[64] = {
84 58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59,
85 59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59,
86 59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59,
87 59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58
90 const int RShift[64] = {
91 52, 53, 53, 53, 53, 53, 53, 52, 53, 54, 54, 54, 54, 54, 54, 53,
92 53, 54, 54, 54, 54, 54, 54, 53, 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, 52, 53, 53, 53, 53, 53, 53, 52
97 #else // if !defined(IS_64BIT)
99 const uint64_t BMult[64] = {
100 0x54142844c6a22981ULL, 0x710358a6ea25c19eULL, 0x704f746d63a4a8dcULL,
101 0xbfed1a0b80f838c5ULL, 0x90561d5631e62110ULL, 0x2804260376e60944ULL,
102 0x84a656409aa76871ULL, 0xf0267f64c28b6197ULL, 0x70764ebb762f0585ULL,
103 0x92aa09e0cfe161deULL, 0x41ee1f6bb266f60eULL, 0xddcbf04f6039c444ULL,
104 0x5a3fab7bac0d988aULL, 0xd3727877fa4eaa03ULL, 0xd988402d868ddaaeULL,
105 0x812b291afa075c7cULL, 0x94faf987b685a932ULL, 0x3ed867d8470d08dbULL,
106 0x92517660b8901de8ULL, 0x2d97e43e058814b4ULL, 0x880a10c220b25582ULL,
107 0xc7c6520d1f1a0477ULL, 0xdbfc7fbcd7656aa6ULL, 0x78b1b9bfb1a2b84fULL,
108 0x2f20037f112a0bc1ULL, 0x657171ea2269a916ULL, 0xc08302b07142210eULL,
109 0x880a4403064080bULL, 0x3602420842208c00ULL, 0x852800dc7e0b6602ULL,
110 0x595a3fbbaa0f03b2ULL, 0x9f01411558159d5eULL, 0x2b4a4a5f88b394f2ULL,
111 0x4afcbffc292dd03aULL, 0x4a4094a3b3f10522ULL, 0xb06f00b491f30048ULL,
112 0xd5b3820280d77004ULL, 0x8b2e01e7c8e57a75ULL, 0x2d342794e886c2e6ULL,
113 0xc302c410cde21461ULL, 0x111f426f1379c274ULL, 0xe0569220abb31588ULL,
114 0x5026d3064d453324ULL, 0xe2076040c343cd8aULL, 0x93efd1e1738021eeULL,
115 0xb680804bed143132ULL, 0x44e361b21986944cULL, 0x44c60170ef5c598cULL,
116 0xf4da475c195c9c94ULL, 0xa3afbb5f72060b1dULL, 0xbc75f410e41c4ffcULL,
117 0xb51c099390520922ULL, 0x902c011f8f8ec368ULL, 0x950b56b3d6f5490aULL,
118 0x3909e0635bf202d0ULL, 0x5744f90206ec10ccULL, 0xdc59fd76317abbc1ULL,
119 0x881c7c67fcbfc4f6ULL, 0x47ca41e7e440d423ULL, 0xeb0c88112048d004ULL,
120 0x51c60e04359aef1aULL, 0x1aa1fe0e957a5554ULL, 0xdd9448db4f5e3104ULL,
121 0xdc01f6dca4bebbdcULL,
124 const uint64_t RMult[64] = {
125 0xd7445cdec88002c0ULL, 0xd0a505c1f2001722ULL, 0xe065d1c896002182ULL,
126 0x9a8c41e75a000892ULL, 0x8900b10c89002aa8ULL, 0x9b28d1c1d60005a2ULL,
127 0x15d6c88de002d9aULL, 0xb1dbfc802e8016a9ULL, 0x149a1042d9d60029ULL,
128 0xb9c08050599e002fULL, 0x132208c3af300403ULL, 0xc1000ce2e9c50070ULL,
129 0x9d9aa13c99020012ULL, 0xb6b078daf71e0046ULL, 0x9d880182fb6e002eULL,
130 0x52889f467e850037ULL, 0xda6dc008d19a8480ULL, 0x468286034f902420ULL,
131 0x7140ac09dc54c020ULL, 0xd76ffffa39548808ULL, 0xea901c4141500808ULL,
132 0xc91004093f953a02ULL, 0x2882afa8f6bb402ULL, 0xaebe335692442c01ULL,
133 0xe904a22079fb91eULL, 0x13a514851055f606ULL, 0x76c782018c8fe632ULL,
134 0x1dc012a9d116da06ULL, 0x3c9e0037264fffa6ULL, 0x2036002853c6e4a2ULL,
135 0xe3fe08500afb47d4ULL, 0xf38af25c86b025c2ULL, 0xc0800e2182cf9a40ULL,
136 0x72002480d1f60673ULL, 0x2500200bae6e9b53ULL, 0xc60018c1eefca252ULL,
137 0x600590473e3608aULL, 0x46002c4ab3fe51b2ULL, 0xa200011486bcc8d2ULL,
138 0xb680078095784c63ULL, 0x2742002639bf11aeULL, 0xc7d60021a5bdb142ULL,
139 0xc8c04016bb83d820ULL, 0xbd520028123b4842ULL, 0x9d1600344ac2a832ULL,
140 0x6a808005631c8a05ULL, 0x604600a148d5389aULL, 0xe2e40103d40dea65ULL,
141 0x945b5a0087c62a81ULL, 0x12dc200cd82d28eULL, 0x2431c600b5f9ef76ULL,
142 0xfb142a006a9b314aULL, 0x6870e00a1c97d62ULL, 0x2a9db2004a2689a2ULL,
143 0xd3594600caf5d1a2ULL, 0xee0e4900439344a7ULL, 0x89c4d266ca25007aULL,
144 0x3e0013a2743f97e3ULL, 0x180e31a0431378aULL, 0x3a9e465a4d42a512ULL,
145 0x98d0a11a0c0d9cc2ULL, 0x8e711c1aba19b01eULL, 0x8dcdc836dd201142ULL,
146 0x5ac08a4735370479ULL,
149 const int BShift[64] = {
150 26, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 27, 27,
151 27, 27, 25, 25, 25, 25, 27, 27, 27, 27, 25, 23, 23, 25, 27, 27,
152 27, 27, 25, 23, 23, 25, 27, 27, 27, 27, 25, 25, 25, 25, 27, 27,
153 27, 27, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 26
156 const int RShift[64] = {
157 20, 21, 21, 21, 21, 21, 21, 20, 21, 22, 22, 22, 22, 22, 22, 21,
158 21, 22, 22, 22, 22, 22, 22, 21, 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, 20, 21, 21, 21, 21, 21, 21, 20
163 #endif // defined(IS_64BIT)
165 static const Bitboard DarkSquaresBB = 0xAA55AA55AA55AA55ULL;
167 const Bitboard SquaresByColorBB[2] = { DarkSquaresBB, ~DarkSquaresBB };
169 const Bitboard FileBB[8] = {
170 FileABB, FileBBB, FileCBB, FileDBB, FileEBB, FileFBB, FileGBB, FileHBB
173 const Bitboard NeighboringFilesBB[8] = {
174 FileBBB, FileABB|FileCBB, FileBBB|FileDBB, FileCBB|FileEBB,
175 FileDBB|FileFBB, FileEBB|FileGBB, FileFBB|FileHBB, FileGBB
178 const Bitboard ThisAndNeighboringFilesBB[8] = {
179 FileABB|FileBBB, FileABB|FileBBB|FileCBB,
180 FileBBB|FileCBB|FileDBB, FileCBB|FileDBB|FileEBB,
181 FileDBB|FileEBB|FileFBB, FileEBB|FileFBB|FileGBB,
182 FileFBB|FileGBB|FileHBB, FileGBB|FileHBB
185 const Bitboard RankBB[8] = {
186 Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB
189 const Bitboard InFrontBB[2][8] = {
190 { Rank2BB | Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
191 Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
192 Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
193 Rank5BB | Rank6BB | Rank7BB | Rank8BB,
194 Rank6BB | Rank7BB | Rank8BB,
202 Rank3BB | Rank2BB | Rank1BB,
203 Rank4BB | Rank3BB | Rank2BB | Rank1BB,
204 Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB,
205 Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB,
206 Rank7BB | Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB
210 // Global bitboards definitions with static storage duration are
211 // automatically set to zero before enter main().
213 int RAttackIndex[64];
214 Bitboard RAttacks[0x19000];
217 int BAttackIndex[64];
218 Bitboard BAttacks[0x1480];
220 Bitboard SetMaskBB[65];
221 Bitboard ClearMaskBB[65];
223 Bitboard NonSlidingAttacksBB[16][64];
224 Bitboard BetweenBB[64][64];
226 Bitboard SquaresInFrontMask[2][64];
227 Bitboard PassedPawnMask[2][64];
228 Bitboard AttackSpanMask[2][64];
230 Bitboard BishopPseudoAttacks[64];
231 Bitboard RookPseudoAttacks[64];
232 Bitboard QueenPseudoAttacks[64];
234 uint8_t BitCount8Bit[256];
240 void init_non_sliding_attacks();
241 void init_pseudo_attacks();
242 void init_between_bitboards();
243 Bitboard index_to_bitboard(int index, Bitboard mask);
244 Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
245 int fmin, int fmax, int rmin, int rmax);
246 void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
247 const int shift[], const Bitboard mult[], int deltas[][2]);
251 /// print_bitboard() prints a bitboard in an easily readable format to the
252 /// standard output. This is sometimes useful for debugging.
254 void print_bitboard(Bitboard b) {
256 for (Rank r = RANK_8; r >= RANK_1; r--)
258 std::cout << "+---+---+---+---+---+---+---+---+" << '\n';
259 for (File f = FILE_A; f <= FILE_H; f++)
260 std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' ';
264 std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
268 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
269 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
270 /// nonzero bitboard.
272 #if defined(IS_64BIT) && !defined(USE_BSFQ)
274 static CACHE_LINE_ALIGNMENT
275 const int BitTable[64] = {
276 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15,
277 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39,
278 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43,
282 Square first_1(Bitboard b) {
283 return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
286 Square pop_1st_bit(Bitboard* b) {
289 return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
292 #elif !defined(USE_BSFQ)
294 static CACHE_LINE_ALIGNMENT
295 const int BitTable[64] = {
296 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
297 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
298 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
299 58, 20, 37, 17, 36, 8
302 Square first_1(Bitboard b) {
305 uint32_t fold = int(b) ^ int(b >> 32);
306 return Square(BitTable[(fold * 0x783a9b23) >> 26]);
314 #if defined (BIGENDIAN)
324 Square pop_1st_bit(Bitboard* bb) {
333 ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 26]);
334 u.dw.l &= (u.dw.l - 1);
338 ret = Square(BitTable[((~(u.dw.h ^ (u.dw.h - 1))) * 0x783a9b23) >> 26]);
339 u.dw.h &= (u.dw.h - 1);
347 /// init_bitboards() initializes various bitboard arrays. It is called during
348 /// program initialization.
350 void init_bitboards() {
352 int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
353 int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
356 init_non_sliding_attacks();
357 init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas);
358 init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas);
359 init_pseudo_attacks();
360 init_between_bitboards();
365 // All functions below are used to precompute various bitboards during
366 // program initialization. Some of the functions may be difficult to
367 // understand, but they all seem to work correctly, and it should never
368 // be necessary to touch any of them.
372 SetMaskBB[SQ_NONE] = EmptyBoardBB;
373 ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE];
375 for (Square s = SQ_A1; s <= SQ_H8; s++)
377 SetMaskBB[s] = (1ULL << s);
378 ClearMaskBB[s] = ~SetMaskBB[s];
381 for (Color c = WHITE; c <= BLACK; c++)
382 for (Square s = SQ_A1; s <= SQ_H8; s++)
384 SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
385 PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
386 AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
389 for (Bitboard b = 0; b < 256; b++)
390 BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
393 void init_non_sliding_attacks() {
395 const int step[][9] = {
397 {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0},
398 {9,7,-7,-9,8,1,-1,-8,0}, {0}, {0},
399 {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0},
400 {9,7,-7,-9,8,1,-1,-8,0}
403 for (Square s = SQ_A1; s <= SQ_H8; s++)
404 for (Piece pc = WP; pc <= BK; pc++)
405 for (int k = 0; step[pc][k] != 0; k++)
407 Square to = s + Square(step[pc][k]);
409 if (square_is_ok(to) && square_distance(s, to) < 3)
410 set_bit(&NonSlidingAttacksBB[pc][s], to);
414 Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
415 int fmin=0, int fmax=7, int rmin=0, int rmax=7) {
420 for (int i = 0; i < dirs; i++)
422 int dx = deltas[i][0];
423 int dy = deltas[i][1];
427 while ( (dx == 0 || (f >= fmin && f <= fmax))
428 && (dy == 0 || (r >= rmin && r <= rmax)))
430 result |= (1ULL << (f + r*8));
431 if (block & (1ULL << (f + r*8)))
441 Bitboard index_to_bitboard(int index, Bitboard mask) {
443 Bitboard result = EmptyBoardBB;
448 sq = pop_1st_bit(&mask);
450 if (index & (1 << cnt++))
451 result |= (1ULL << sq);
456 void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
457 const int shift[], const Bitboard mult[], int deltas[][2]) {
459 for (int i = 0, index = 0; i < 64; i++)
461 attackIndex[i] = index;
462 mask[i] = sliding_attacks(i, 0, 4, deltas, 1, 6, 1, 6);
464 #if defined(IS_64BIT)
465 int j = (1 << (64 - shift[i]));
467 int j = (1 << (32 - shift[i]));
470 for (int k = 0; k < j; k++)
472 #if defined(IS_64BIT)
473 Bitboard b = index_to_bitboard(k, mask[i]);
474 attacks[index + ((b * mult[i]) >> shift[i])] = sliding_attacks(i, b, 4, deltas);
476 Bitboard b = index_to_bitboard(k, mask[i]);
477 unsigned v = int(b) * int(mult[i]) ^ int(b >> 32) * int(mult[i] >> 32);
478 attacks[index + (v >> shift[i])] = sliding_attacks(i, b, 4, deltas);
485 void init_pseudo_attacks() {
487 for (Square s = SQ_A1; s <= SQ_H8; s++)
489 BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
490 RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB);
491 QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB);
495 void init_between_bitboards() {
501 for (s1 = SQ_A1; s1 <= SQ_H8; s1++)
502 for (s2 = SQ_A1; s2 <= SQ_H8; s2++)
503 if (bit_is_set(QueenPseudoAttacks[s1], s2))
505 f = file_distance(s1, s2);
506 r = rank_distance(s1, s2);
508 d = SquareDelta(s2 - s1) / Max(f, r);
510 for (s3 = s1 + d; s3 != s2; s3 += d)
511 set_bit(&(BetweenBB[s1][s2]), s3);