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/>.
27 const uint64_t BMult[64] = {
28 0x0440049104032280ULL, 0x1021023C82008040ULL, 0x0404040082000048ULL,
29 0x48C4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL,
30 0x0181011002E06040ULL, 0x9101004104200E00ULL, 0x1240848848310401ULL,
31 0x2000142828050024ULL, 0x00001004024D5000ULL, 0x0102044400800200ULL,
32 0x8108108820112000ULL, 0xA880818210C00046ULL, 0x4008008801082000ULL,
33 0x0060882404049400ULL, 0x0104402004240810ULL, 0x000A002084250200ULL,
34 0x00100B0880801100ULL, 0x0004080201220101ULL, 0x0044008080A00000ULL,
35 0x0000202200842000ULL, 0x5006004882D00808ULL, 0x0000200045080802ULL,
36 0x0086100020200601ULL, 0xA802080A20112C02ULL, 0x0080411218080900ULL,
37 0x000200A0880080A0ULL, 0x9A01010000104000ULL, 0x0028008003100080ULL,
38 0x0211021004480417ULL, 0x0401004188220806ULL, 0x00825051400C2006ULL,
39 0x00140C0210943000ULL, 0x0000242800300080ULL, 0x00C2208120080200ULL,
40 0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL,
41 0x0000822081014405ULL, 0x800C049E40400804ULL, 0x4A0404028A000820ULL,
42 0x0022060201041200ULL, 0x0360904200840801ULL, 0x0881A08208800400ULL,
43 0x0060202C00400420ULL, 0x1204440086061400ULL, 0x0008184042804040ULL,
44 0x0064040315300400ULL, 0x0C01008801090A00ULL, 0x0808010401140C00ULL,
45 0x04004830C2020040ULL, 0x0080005002020054ULL, 0x40000C14481A0490ULL,
46 0x0010500101042048ULL, 0x1010100200424000ULL, 0x0000640901901040ULL,
47 0x00000A0201014840ULL, 0x00840082AA011002ULL, 0x010010840084240AULL,
48 0x0420400810420608ULL, 0x8D40230408102100ULL, 0x4A00200612222409ULL,
52 const uint64_t RMult[64] = {
53 0x0A8002C000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL,
54 0x0380180080141000ULL, 0x1A00060008211044ULL, 0x410001000A0C0008ULL,
55 0x9500060004008100ULL, 0x0100024284A20700ULL, 0x0000802140008000ULL,
56 0x0080C01002A00840ULL, 0x0402004282011020ULL, 0x9862000820420050ULL,
57 0x0001001448011100ULL, 0x6432800200800400ULL, 0x040100010002000CULL,
58 0x0002800D0010C080ULL, 0x90C0008000803042ULL, 0x4010004000200041ULL,
59 0x0003010010200040ULL, 0x0A40828028001000ULL, 0x0123010008000430ULL,
60 0x0024008004020080ULL, 0x0060040001104802ULL, 0x00582200028400D1ULL,
61 0x4000802080044000ULL, 0x0408208200420308ULL, 0x0610038080102000ULL,
62 0x3601000900100020ULL, 0x0000080080040180ULL, 0x00C2020080040080ULL,
63 0x0080084400100102ULL, 0x4022408200014401ULL, 0x0040052040800082ULL,
64 0x0B08200280804000ULL, 0x008A80A008801000ULL, 0x4000480080801000ULL,
65 0x0911808800801401ULL, 0x822A003002001894ULL, 0x401068091400108AULL,
66 0x000004A10A00004CULL, 0x2000800640008024ULL, 0x1486408102020020ULL,
67 0x000100A000D50041ULL, 0x00810050020B0020ULL, 0x0204000800808004ULL,
68 0x00020048100A000CULL, 0x0112000831020004ULL, 0x0009000040810002ULL,
69 0x0440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL,
70 0x4B824A2010010100ULL, 0x04080801810C0080ULL, 0x00000400802A0080ULL,
71 0x8224080110026400ULL, 0x40002C4104088200ULL, 0x01002100104A0282ULL,
72 0x1208400811048021ULL, 0x3201014A40D02001ULL, 0x0005100019200501ULL,
73 0x0101000208001005ULL, 0x0002008450080702ULL, 0x001002080301D00CULL,
77 const int BShift[64] = {
78 58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59,
79 59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59,
80 59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59,
81 59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58
84 const int RShift[64] = {
85 52, 53, 53, 53, 53, 53, 53, 52, 53, 54, 54, 54, 54, 54, 54, 53,
86 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53,
87 53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53,
88 53, 54, 54, 54, 54, 54, 54, 53, 52, 53, 53, 53, 53, 53, 53, 52
91 #else // if !defined(IS_64BIT)
93 const uint64_t BMult[64] = {
94 0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL,
95 0xBFED1A0B80F838C5ULL, 0x90561D5631E62110ULL, 0x2804260376E60944ULL,
96 0x84A656409AA76871ULL, 0xF0267F64C28B6197ULL, 0x70764EBB762F0585ULL,
97 0x92AA09E0CFE161DEULL, 0x41EE1F6BB266F60EULL, 0xDDCBF04F6039C444ULL,
98 0x5A3FAB7BAC0D988AULL, 0xD3727877FA4EAA03ULL, 0xD988402D868DDAAEULL,
99 0x812B291AFA075C7CULL, 0x94FAF987B685A932ULL, 0x3ED867D8470D08DBULL,
100 0x92517660B8901DE8ULL, 0x2D97E43E058814B4ULL, 0x880A10C220B25582ULL,
101 0xC7C6520D1F1A0477ULL, 0xDBFC7FBCD7656AA6ULL, 0x78B1B9BFB1A2B84FULL,
102 0x2F20037F112A0BC1ULL, 0x657171EA2269A916ULL, 0xC08302B07142210EULL,
103 0x0880A4403064080BULL, 0x3602420842208C00ULL, 0x852800DC7E0B6602ULL,
104 0x595A3FBBAA0F03B2ULL, 0x9F01411558159D5EULL, 0x2B4A4A5F88B394F2ULL,
105 0x4AFCBFFC292DD03AULL, 0x4A4094A3B3F10522ULL, 0xB06F00B491F30048ULL,
106 0xD5B3820280D77004ULL, 0x8B2E01E7C8E57A75ULL, 0x2D342794E886C2E6ULL,
107 0xC302C410CDE21461ULL, 0x111F426F1379C274ULL, 0xE0569220ABB31588ULL,
108 0x5026D3064D453324ULL, 0xE2076040C343CD8AULL, 0x93EFD1E1738021EEULL,
109 0xB680804BED143132ULL, 0x44E361B21986944CULL, 0x44C60170EF5C598CULL,
110 0xF4DA475C195C9C94ULL, 0xA3AFBB5F72060B1DULL, 0xBC75F410E41C4FFCULL,
111 0xB51C099390520922ULL, 0x902C011F8F8EC368ULL, 0x950B56B3D6F5490AULL,
112 0x3909E0635BF202D0ULL, 0x5744F90206EC10CCULL, 0xDC59FD76317ABBC1ULL,
113 0x881C7C67FCBFC4F6ULL, 0x47CA41E7E440D423ULL, 0xEB0C88112048D004ULL,
114 0x51C60E04359AEF1AULL, 0x1AA1FE0E957A5554ULL, 0xDD9448DB4F5E3104ULL,
115 0xDC01F6DCA4BEBBDCULL,
118 const uint64_t RMult[64] = {
119 0xD7445CDEC88002C0ULL, 0xD0A505C1F2001722ULL, 0xE065D1C896002182ULL,
120 0x9A8C41E75A000892ULL, 0x8900B10C89002AA8ULL, 0x9B28D1C1D60005A2ULL,
121 0x015D6C88DE002D9AULL, 0xB1DBFC802E8016A9ULL, 0x149A1042D9D60029ULL,
122 0xB9C08050599E002FULL, 0x132208C3AF300403ULL, 0xC1000CE2E9C50070ULL,
123 0x9D9AA13C99020012ULL, 0xB6B078DAF71E0046ULL, 0x9D880182FB6E002EULL,
124 0x52889F467E850037ULL, 0xDA6DC008D19A8480ULL, 0x468286034F902420ULL,
125 0x7140AC09DC54C020ULL, 0xD76FFFFA39548808ULL, 0xEA901C4141500808ULL,
126 0xC91004093F953A02ULL, 0x02882AFA8F6BB402ULL, 0xAEBE335692442C01ULL,
127 0x0E904A22079FB91EULL, 0x13A514851055F606ULL, 0x76C782018C8FE632ULL,
128 0x1DC012A9D116DA06ULL, 0x3C9E0037264FFFA6ULL, 0x2036002853C6E4A2ULL,
129 0xE3FE08500AFB47D4ULL, 0xF38AF25C86B025C2ULL, 0xC0800E2182CF9A40ULL,
130 0x72002480D1F60673ULL, 0x2500200BAE6E9B53ULL, 0xC60018C1EEFCA252ULL,
131 0x0600590473E3608AULL, 0x46002C4AB3FE51B2ULL, 0xA200011486BCC8D2ULL,
132 0xB680078095784C63ULL, 0x2742002639BF11AEULL, 0xC7D60021A5BDB142ULL,
133 0xC8C04016BB83D820ULL, 0xBD520028123B4842ULL, 0x9D1600344AC2A832ULL,
134 0x6A808005631C8A05ULL, 0x604600A148D5389AULL, 0xE2E40103D40DEA65ULL,
135 0x945B5A0087C62A81ULL, 0x012DC200CD82D28EULL, 0x2431C600B5F9EF76ULL,
136 0xFB142A006A9B314AULL, 0x06870E00A1C97D62ULL, 0x2A9DB2004A2689A2ULL,
137 0xD3594600CAF5D1A2ULL, 0xEE0E4900439344A7ULL, 0x89C4D266CA25007AULL,
138 0x3E0013A2743F97E3ULL, 0x0180E31A0431378AULL, 0x3A9E465A4D42A512ULL,
139 0x98D0A11A0C0D9CC2ULL, 0x8E711C1ABA19B01EULL, 0x8DCDC836DD201142ULL,
140 0x5AC08A4735370479ULL,
143 const int BShift[64] = {
144 26, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 27, 27,
145 27, 27, 25, 25, 25, 25, 27, 27, 27, 27, 25, 23, 23, 25, 27, 27,
146 27, 27, 25, 23, 23, 25, 27, 27, 27, 27, 25, 25, 25, 25, 27, 27,
147 27, 27, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 26
150 const int RShift[64] = {
151 20, 21, 21, 21, 21, 21, 21, 20, 21, 22, 22, 22, 22, 22, 22, 21,
152 21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21,
153 21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21,
154 21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20
157 #endif // defined(IS_64BIT)
159 // Global bitboards definitions with static storage duration are
160 // automatically set to zero before enter main().
162 int RAttackIndex[64];
163 Bitboard RAttacks[0x19000];
166 int BAttackIndex[64];
167 Bitboard BAttacks[0x1480];
169 Bitboard SetMaskBB[65];
170 Bitboard ClearMaskBB[65];
172 Bitboard SquaresByColorBB[2];
175 Bitboard NeighboringFilesBB[8];
176 Bitboard ThisAndNeighboringFilesBB[8];
177 Bitboard InFrontBB[2][8];
178 Bitboard StepAttacksBB[16][64];
179 Bitboard BetweenBB[64][64];
180 Bitboard SquaresInFrontMask[2][64];
181 Bitboard PassedPawnMask[2][64];
182 Bitboard AttackSpanMask[2][64];
184 Bitboard BishopPseudoAttacks[64];
185 Bitboard RookPseudoAttacks[64];
186 Bitboard QueenPseudoAttacks[64];
188 uint8_t BitCount8Bit[256];
194 void init_step_attacks();
195 void init_pseudo_attacks();
196 void init_between_bitboards();
197 Bitboard index_to_bitboard(int index, Bitboard mask);
198 Bitboard sliding_attacks(int sq, Bitboard occupied, int deltas[][2],
199 int fmin, int fmax, int rmin, int rmax);
200 void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
201 const int shift[], const Bitboard mult[], int deltas[][2]);
205 /// print_bitboard() prints a bitboard in an easily readable format to the
206 /// standard output. This is sometimes useful for debugging.
208 void print_bitboard(Bitboard b) {
210 for (Rank r = RANK_8; r >= RANK_1; r--)
212 std::cout << "+---+---+---+---+---+---+---+---+" << '\n';
213 for (File f = FILE_A; f <= FILE_H; f++)
214 std::cout << "| " << (bit_is_set(b, make_square(f, r)) ? 'X' : ' ') << ' ';
218 std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
222 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
223 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
224 /// nonzero bitboard.
226 #if defined(IS_64BIT) && !defined(USE_BSFQ)
228 static CACHE_LINE_ALIGNMENT
229 const int BitTable[64] = {
230 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26,
231 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27,
232 33, 39, 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61,
233 22, 43, 51, 60, 42, 59, 58
236 Square first_1(Bitboard b) {
237 return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
240 Square pop_1st_bit(Bitboard* b) {
243 return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
246 #elif !defined(USE_BSFQ)
248 static CACHE_LINE_ALIGNMENT
249 const int BitTable[64] = {
250 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
251 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5,
252 52, 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38,
253 28, 58, 20, 37, 17, 36, 8
256 Square first_1(Bitboard b) {
259 uint32_t fold = int(b) ^ int(b >> 32);
260 return Square(BitTable[(fold * 0x783a9b23) >> 26]);
268 #if defined (BIGENDIAN)
278 Square pop_1st_bit(Bitboard* bb) {
287 ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 26]);
288 u.dw.l &= (u.dw.l - 1);
292 ret = Square(BitTable[((~(u.dw.h ^ (u.dw.h - 1))) * 0x783a9b23) >> 26]);
293 u.dw.h &= (u.dw.h - 1);
298 #endif // !defined(USE_BSFQ)
301 /// init_bitboards() initializes various bitboard arrays. It is called during
302 /// program initialization.
304 void init_bitboards() {
306 int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
307 int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
311 init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas);
312 init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas);
313 init_pseudo_attacks();
314 init_between_bitboards();
319 // All functions below are used to precompute various bitboards during
320 // program initialization. Some of the functions may be difficult to
321 // understand, but they all seem to work correctly, and it should never
322 // be necessary to touch any of them.
326 SquaresByColorBB[DARK] = 0xAA55AA55AA55AA55ULL;
327 SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK];
329 FileBB[FILE_A] = FileABB;
330 RankBB[RANK_1] = Rank1BB;
332 for (int f = FILE_B; f <= FILE_H; f++)
334 FileBB[f] = FileBB[f - 1] << 1;
335 RankBB[f] = RankBB[f - 1] << 8;
338 for (int f = FILE_A; f <= FILE_H; f++)
340 NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
341 ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f];
344 for (int rw = RANK_7, rb = RANK_2; rw >= RANK_1; rw--, rb++)
346 InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1];
347 InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1];
350 SetMaskBB[SQ_NONE] = EmptyBoardBB;
351 ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE];
353 for (Square s = SQ_A1; s <= SQ_H8; s++)
355 SetMaskBB[s] = (1ULL << s);
356 ClearMaskBB[s] = ~SetMaskBB[s];
359 for (Color c = WHITE; c <= BLACK; c++)
360 for (Square s = SQ_A1; s <= SQ_H8; s++)
362 SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
363 PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
364 AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
367 for (Bitboard b = 0; b < 256; b++)
368 BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
371 void init_step_attacks() {
373 const int step[][9] = {
375 {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0},
376 {9,7,-7,-9,8,1,-1,-8,0}, {0}, {0},
377 {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0},
378 {9,7,-7,-9,8,1,-1,-8,0}
381 for (Square s = SQ_A1; s <= SQ_H8; s++)
382 for (Piece pc = WP; pc <= BK; pc++)
383 for (int k = 0; step[pc][k] != 0; k++)
385 Square to = s + Square(step[pc][k]);
387 if (square_is_ok(to) && square_distance(s, to) < 3)
388 set_bit(&StepAttacksBB[pc][s], to);
392 Bitboard sliding_attacks(int sq, Bitboard occupied, int deltas[][2],
393 int fmin, int fmax, int rmin, int rmax) {
397 Bitboard attacks = EmptyBoardBB;
399 for (int i = 0; i < 4; i++)
406 while ( (dx == 0 || (f >= fmin && f <= fmax))
407 && (dy == 0 || (r >= rmin && r <= rmax)))
409 attacks |= (1ULL << (f + r * 8));
411 if (occupied & (1ULL << (f + r * 8)))
421 Bitboard index_to_bitboard(int index, Bitboard mask) {
423 Bitboard result = EmptyBoardBB;
428 sq = pop_1st_bit(&mask);
430 if (index & (1 << cnt++))
431 result |= (1ULL << sq);
436 void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
437 const int shift[], const Bitboard mult[], int deltas[][2]) {
441 for (i = index = 0; i < 64; i++)
443 attackIndex[i] = index;
444 mask[i] = sliding_attacks(i, 0, deltas, 1, 6, 1, 6);
445 j = 1 << ((CpuIs64Bit ? 64 : 32) - shift[i]);
447 for (int k = 0; k < j; k++)
449 b = index_to_bitboard(k, mask[i]);
450 v = CpuIs64Bit ? b * mult[i] : unsigned(b * mult[i] ^ (b >> 32) * (mult[i] >> 32));
451 attacks[index + (v >> shift[i])] = sliding_attacks(i, b, deltas, 0, 7, 0, 7);
457 void init_pseudo_attacks() {
459 for (Square s = SQ_A1; s <= SQ_H8; s++)
461 BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
462 RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB);
463 QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB);
467 void init_between_bitboards() {
469 Square s1, s2, s3, d;
472 for (s1 = SQ_A1; s1 <= SQ_H8; s1++)
473 for (s2 = SQ_A1; s2 <= SQ_H8; s2++)
474 if (bit_is_set(QueenPseudoAttacks[s1], s2))
476 f = file_distance(s1, s2);
477 r = rank_distance(s1, s2);
479 d = (s2 - s1) / Max(f, r);
481 for (s3 = s1 + d; s3 != s2; s3 += d)
482 set_bit(&(BetweenBB[s1][s2]), s3);