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/>.
25 // Global bitboards definitions with static storage duration are
26 // automatically set to zero before enter main().
27 Bitboard RAttacks[0x19000];
28 Bitboard BAttacks[0x1480];
33 Bitboard SetMaskBB[65];
34 Bitboard ClearMaskBB[65];
36 Bitboard SquaresByColorBB[2];
39 Bitboard NeighboringFilesBB[8];
40 Bitboard ThisAndNeighboringFilesBB[8];
41 Bitboard InFrontBB[2][8];
42 Bitboard StepAttacksBB[16][64];
43 Bitboard BetweenBB[64][64];
44 Bitboard SquaresInFrontMask[2][64];
45 Bitboard PassedPawnMask[2][64];
46 Bitboard AttackSpanMask[2][64];
48 Bitboard BishopPseudoAttacks[64];
49 Bitboard RookPseudoAttacks[64];
50 Bitboard QueenPseudoAttacks[64];
52 uint8_t BitCount8Bit[256];
58 const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL;
60 const uint64_t BMult[64] = {
61 0x0440049104032280ULL, 0x1021023C82008040ULL, 0x0404040082000048ULL,
62 0x48C4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL,
63 0x0181011002E06040ULL, 0x9101004104200E00ULL, 0x1240848848310401ULL,
64 0x2000142828050024ULL, 0x00001004024D5000ULL, 0x0102044400800200ULL,
65 0x8108108820112000ULL, 0xA880818210C00046ULL, 0x4008008801082000ULL,
66 0x0060882404049400ULL, 0x0104402004240810ULL, 0x000A002084250200ULL,
67 0x00100B0880801100ULL, 0x0004080201220101ULL, 0x0044008080A00000ULL,
68 0x0000202200842000ULL, 0x5006004882D00808ULL, 0x0000200045080802ULL,
69 0x0086100020200601ULL, 0xA802080A20112C02ULL, 0x0080411218080900ULL,
70 0x000200A0880080A0ULL, 0x9A01010000104000ULL, 0x0028008003100080ULL,
71 0x0211021004480417ULL, 0x0401004188220806ULL, 0x00825051400C2006ULL,
72 0x00140C0210943000ULL, 0x0000242800300080ULL, 0x00C2208120080200ULL,
73 0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL,
74 0x0000822081014405ULL, 0x800C049E40400804ULL, 0x4A0404028A000820ULL,
75 0x0022060201041200ULL, 0x0360904200840801ULL, 0x0881A08208800400ULL,
76 0x0060202C00400420ULL, 0x1204440086061400ULL, 0x0008184042804040ULL,
77 0x0064040315300400ULL, 0x0C01008801090A00ULL, 0x0808010401140C00ULL,
78 0x04004830C2020040ULL, 0x0080005002020054ULL, 0x40000C14481A0490ULL,
79 0x0010500101042048ULL, 0x1010100200424000ULL, 0x0000640901901040ULL,
80 0x00000A0201014840ULL, 0x00840082AA011002ULL, 0x010010840084240AULL,
81 0x0420400810420608ULL, 0x8D40230408102100ULL, 0x4A00200612222409ULL,
85 const uint64_t RMult[64] = {
86 0x0A8002C000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL,
87 0x0380180080141000ULL, 0x1A00060008211044ULL, 0x410001000A0C0008ULL,
88 0x9500060004008100ULL, 0x0100024284A20700ULL, 0x0000802140008000ULL,
89 0x0080C01002A00840ULL, 0x0402004282011020ULL, 0x9862000820420050ULL,
90 0x0001001448011100ULL, 0x6432800200800400ULL, 0x040100010002000CULL,
91 0x0002800D0010C080ULL, 0x90C0008000803042ULL, 0x4010004000200041ULL,
92 0x0003010010200040ULL, 0x0A40828028001000ULL, 0x0123010008000430ULL,
93 0x0024008004020080ULL, 0x0060040001104802ULL, 0x00582200028400D1ULL,
94 0x4000802080044000ULL, 0x0408208200420308ULL, 0x0610038080102000ULL,
95 0x3601000900100020ULL, 0x0000080080040180ULL, 0x00C2020080040080ULL,
96 0x0080084400100102ULL, 0x4022408200014401ULL, 0x0040052040800082ULL,
97 0x0B08200280804000ULL, 0x008A80A008801000ULL, 0x4000480080801000ULL,
98 0x0911808800801401ULL, 0x822A003002001894ULL, 0x401068091400108AULL,
99 0x000004A10A00004CULL, 0x2000800640008024ULL, 0x1486408102020020ULL,
100 0x000100A000D50041ULL, 0x00810050020B0020ULL, 0x0204000800808004ULL,
101 0x00020048100A000CULL, 0x0112000831020004ULL, 0x0009000040810002ULL,
102 0x0440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL,
103 0x4B824A2010010100ULL, 0x04080801810C0080ULL, 0x00000400802A0080ULL,
104 0x8224080110026400ULL, 0x40002C4104088200ULL, 0x01002100104A0282ULL,
105 0x1208400811048021ULL, 0x3201014A40D02001ULL, 0x0005100019200501ULL,
106 0x0101000208001005ULL, 0x0002008450080702ULL, 0x001002080301D00CULL,
107 0x410201CE5C030092ULL
110 #else // if !defined(IS_64BIT)
112 const uint32_t DeBruijnMagic = 0x783A9B23;
114 const uint64_t BMult[64] = {
115 0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL,
116 0xBFED1A0B80F838C5ULL, 0x90561D5631E62110ULL, 0x2804260376E60944ULL,
117 0x84A656409AA76871ULL, 0xF0267F64C28B6197ULL, 0x70764EBB762F0585ULL,
118 0x92AA09E0CFE161DEULL, 0x41EE1F6BB266F60EULL, 0xDDCBF04F6039C444ULL,
119 0x5A3FAB7BAC0D988AULL, 0xD3727877FA4EAA03ULL, 0xD988402D868DDAAEULL,
120 0x812B291AFA075C7CULL, 0x94FAF987B685A932ULL, 0x3ED867D8470D08DBULL,
121 0x92517660B8901DE8ULL, 0x2D97E43E058814B4ULL, 0x880A10C220B25582ULL,
122 0xC7C6520D1F1A0477ULL, 0xDBFC7FBCD7656AA6ULL, 0x78B1B9BFB1A2B84FULL,
123 0x2F20037F112A0BC1ULL, 0x657171EA2269A916ULL, 0xC08302B07142210EULL,
124 0x0880A4403064080BULL, 0x3602420842208C00ULL, 0x852800DC7E0B6602ULL,
125 0x595A3FBBAA0F03B2ULL, 0x9F01411558159D5EULL, 0x2B4A4A5F88B394F2ULL,
126 0x4AFCBFFC292DD03AULL, 0x4A4094A3B3F10522ULL, 0xB06F00B491F30048ULL,
127 0xD5B3820280D77004ULL, 0x8B2E01E7C8E57A75ULL, 0x2D342794E886C2E6ULL,
128 0xC302C410CDE21461ULL, 0x111F426F1379C274ULL, 0xE0569220ABB31588ULL,
129 0x5026D3064D453324ULL, 0xE2076040C343CD8AULL, 0x93EFD1E1738021EEULL,
130 0xB680804BED143132ULL, 0x44E361B21986944CULL, 0x44C60170EF5C598CULL,
131 0xF4DA475C195C9C94ULL, 0xA3AFBB5F72060B1DULL, 0xBC75F410E41C4FFCULL,
132 0xB51C099390520922ULL, 0x902C011F8F8EC368ULL, 0x950B56B3D6F5490AULL,
133 0x3909E0635BF202D0ULL, 0x5744F90206EC10CCULL, 0xDC59FD76317ABBC1ULL,
134 0x881C7C67FCBFC4F6ULL, 0x47CA41E7E440D423ULL, 0xEB0C88112048D004ULL,
135 0x51C60E04359AEF1AULL, 0x1AA1FE0E957A5554ULL, 0xDD9448DB4F5E3104ULL,
136 0xDC01F6DCA4BEBBDCULL,
139 const uint64_t RMult[64] = {
140 0xD7445CDEC88002C0ULL, 0xD0A505C1F2001722ULL, 0xE065D1C896002182ULL,
141 0x9A8C41E75A000892ULL, 0x8900B10C89002AA8ULL, 0x9B28D1C1D60005A2ULL,
142 0x015D6C88DE002D9AULL, 0xB1DBFC802E8016A9ULL, 0x149A1042D9D60029ULL,
143 0xB9C08050599E002FULL, 0x132208C3AF300403ULL, 0xC1000CE2E9C50070ULL,
144 0x9D9AA13C99020012ULL, 0xB6B078DAF71E0046ULL, 0x9D880182FB6E002EULL,
145 0x52889F467E850037ULL, 0xDA6DC008D19A8480ULL, 0x468286034F902420ULL,
146 0x7140AC09DC54C020ULL, 0xD76FFFFA39548808ULL, 0xEA901C4141500808ULL,
147 0xC91004093F953A02ULL, 0x02882AFA8F6BB402ULL, 0xAEBE335692442C01ULL,
148 0x0E904A22079FB91EULL, 0x13A514851055F606ULL, 0x76C782018C8FE632ULL,
149 0x1DC012A9D116DA06ULL, 0x3C9E0037264FFFA6ULL, 0x2036002853C6E4A2ULL,
150 0xE3FE08500AFB47D4ULL, 0xF38AF25C86B025C2ULL, 0xC0800E2182CF9A40ULL,
151 0x72002480D1F60673ULL, 0x2500200BAE6E9B53ULL, 0xC60018C1EEFCA252ULL,
152 0x0600590473E3608AULL, 0x46002C4AB3FE51B2ULL, 0xA200011486BCC8D2ULL,
153 0xB680078095784C63ULL, 0x2742002639BF11AEULL, 0xC7D60021A5BDB142ULL,
154 0xC8C04016BB83D820ULL, 0xBD520028123B4842ULL, 0x9D1600344AC2A832ULL,
155 0x6A808005631C8A05ULL, 0x604600A148D5389AULL, 0xE2E40103D40DEA65ULL,
156 0x945B5A0087C62A81ULL, 0x012DC200CD82D28EULL, 0x2431C600B5F9EF76ULL,
157 0xFB142A006A9B314AULL, 0x06870E00A1C97D62ULL, 0x2A9DB2004A2689A2ULL,
158 0xD3594600CAF5D1A2ULL, 0xEE0E4900439344A7ULL, 0x89C4D266CA25007AULL,
159 0x3E0013A2743F97E3ULL, 0x0180E31A0431378AULL, 0x3A9E465A4D42A512ULL,
160 0x98D0A11A0C0D9CC2ULL, 0x8E711C1ABA19B01EULL, 0x8DCDC836DD201142ULL,
161 0x5AC08A4735370479ULL,
164 #endif // defined(IS_64BIT)
166 CACHE_LINE_ALIGNMENT int BSFTable[64];
168 void init_sliding_attacks(Bitboard attacks[], Magics m[], const Bitboard mult[], Square deltas[]);
172 /// print_bitboard() prints a bitboard in an easily readable format to the
173 /// standard output. This is sometimes useful for debugging.
175 void print_bitboard(Bitboard b) {
177 for (Rank r = RANK_8; r >= RANK_1; r--)
179 std::cout << "+---+---+---+---+---+---+---+---+" << '\n';
180 for (File f = FILE_A; f <= FILE_H; f++)
181 std::cout << "| " << (bit_is_set(b, make_square(f, r)) ? 'X' : ' ') << ' ';
185 std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
189 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
190 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
191 /// nonzero bitboard.
193 #if defined(IS_64BIT) && !defined(USE_BSFQ)
195 Square first_1(Bitboard b) {
196 return Square(BSFTable[((b & -b) * DeBruijnMagic) >> 58]);
199 Square pop_1st_bit(Bitboard* b) {
202 return Square(BSFTable[((bb & -bb) * DeBruijnMagic) >> 58]);
205 #elif !defined(USE_BSFQ)
207 Square first_1(Bitboard b) {
209 uint32_t fold = unsigned(b) ^ unsigned(b >> 32);
210 return Square(BSFTable[(fold * DeBruijnMagic) >> 26]);
218 #if defined (BIGENDIAN)
228 Square pop_1st_bit(Bitboard* bb) {
237 ret = Square(BSFTable[((u.dw.l ^ (u.dw.l - 1)) * DeBruijnMagic) >> 26]);
238 u.dw.l &= (u.dw.l - 1);
242 ret = Square(BSFTable[((~(u.dw.h ^ (u.dw.h - 1))) * DeBruijnMagic) >> 26]);
243 u.dw.h &= (u.dw.h - 1);
248 #endif // !defined(USE_BSFQ)
251 /// init_bitboards() initializes various bitboard arrays. It is called during
252 /// program initialization.
254 void init_bitboards() {
256 SquaresByColorBB[DARK] = 0xAA55AA55AA55AA55ULL;
257 SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK];
259 for (Square s = SQ_A1; s <= SQ_H8; s++)
261 SetMaskBB[s] = (1ULL << s);
262 ClearMaskBB[s] = ~SetMaskBB[s];
265 ClearMaskBB[SQ_NONE] = ~EmptyBoardBB;
267 FileBB[FILE_A] = FileABB;
268 RankBB[RANK_1] = Rank1BB;
270 for (int f = FILE_B; f <= FILE_H; f++)
272 FileBB[f] = FileBB[f - 1] << 1;
273 RankBB[f] = RankBB[f - 1] << 8;
276 for (int f = FILE_A; f <= FILE_H; f++)
278 NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
279 ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f];
282 for (int rw = RANK_7, rb = RANK_2; rw >= RANK_1; rw--, rb++)
284 InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1];
285 InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1];
288 for (Color c = WHITE; c <= BLACK; c++)
289 for (Square s = SQ_A1; s <= SQ_H8; s++)
291 SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
292 PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
293 AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
296 for (Bitboard b = 0; b < 256; b++)
297 BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
299 for (int i = 1; i < 64; i++)
300 if (!CpuIs64Bit) // Matt Taylor's folding trick for 32 bit systems
302 Bitboard b = 1ULL << i;
305 BSFTable[uint32_t(b * DeBruijnMagic) >> 26] = i;
308 BSFTable[((1ULL << i) * DeBruijnMagic) >> 58] = i;
311 {0}, {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0}, {9,7,-7,-9,8,1,-1,-8,0}
314 for (Color c = WHITE; c <= BLACK; c++)
315 for (Square s = SQ_A1; s <= SQ_H8; s++)
316 for (PieceType pt = PAWN; pt <= KING; pt++)
317 for (int k = 0; steps[pt][k]; k++)
319 Square to = s + Square(c == WHITE ? steps[pt][k] : -steps[pt][k]);
321 if (square_is_ok(to) && square_distance(s, to) < 3)
322 set_bit(&StepAttacksBB[make_piece(c, pt)][s], to);
325 Square RDeltas[] = { DELTA_N, DELTA_E, DELTA_S, DELTA_W };
326 Square BDeltas[] = { DELTA_NE, DELTA_SE, DELTA_SW, DELTA_NW };
328 init_sliding_attacks(RAttacks, RMagics, RMult, RDeltas);
329 init_sliding_attacks(BAttacks, BMagics, BMult, BDeltas);
331 for (Square s = SQ_A1; s <= SQ_H8; s++)
333 BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
334 RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB);
335 QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB);
338 for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
339 for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
340 if (bit_is_set(QueenPseudoAttacks[s1], s2))
342 int f = file_distance(s1, s2);
343 int r = rank_distance(s1, s2);
345 Square d = (s2 - s1) / Max(f, r);
347 for (Square s3 = s1 + d; s3 != s2; s3 += d)
348 set_bit(&BetweenBB[s1][s2], s3);
355 Bitboard submask(Bitboard mask, int key) {
357 Bitboard subMask = 0;
360 // Extract an unique submask out of a mask according to the given key
361 for (Square s = SQ_A1; s <= SQ_H8; s++)
362 if (bit_is_set(mask, s) && bit_is_set(key, Square(++bitNum)))
363 set_bit(&subMask, s);
368 Bitboard sliding_attacks(Square sq, Bitboard occupied, Square deltas[], Bitboard excluded) {
370 Bitboard attacks = 0;
372 for (int i = 0; i < 4; i++)
374 Square s = sq + deltas[i];
376 while ( square_is_ok(s)
377 && square_distance(s, s - deltas[i]) == 1
378 && !bit_is_set(excluded, s))
380 set_bit(&attacks, s);
382 if (bit_is_set(occupied, s))
391 void init_sliding_attacks(Bitboard attacks[], Magics m[], const Bitboard mult[], Square deltas[]) {
393 Bitboard occupancy, index, excluded;
394 int maxKey, offset = 0;
396 for (Square s = SQ_A1; s <= SQ_H8; s++)
398 excluded = ((Rank1BB | Rank8BB) & ~rank_bb(s)) | ((FileABB | FileHBB) & ~file_bb(s));
400 m[s].offset = offset;
402 m[s].mask = sliding_attacks(s, EmptyBoardBB, deltas, excluded);
403 m[s].shift = (CpuIs64Bit ? 64 : 32) - count_1s<CNT64>(m[s].mask);
405 maxKey = 1 << count_1s<CNT64>(m[s].mask);
407 for (int key = 0; key < maxKey; key++)
409 occupancy = submask(m[s].mask, key);
411 index = CpuIs64Bit ? occupancy * mult[s]
412 : unsigned(occupancy * mult[s] ^ (occupancy >> 32) * (mult[s] >> 32));
414 attacks[offset + (index >> m[s].shift)] = sliding_attacks(s, occupancy, deltas, EmptyBoardBB);