Better name and document magic botboard stuff
[stockfish] / src / bitboard.cpp
1 /*
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
5
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.
10
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.
15
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/>.
18 */
19
20 #include <iostream>
21
22 #include "bitboard.h"
23 #include "bitcount.h"
24
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];
29
30 Magics RMagics[64];
31 Magics BMagics[64];
32
33 Bitboard SetMaskBB[65];
34 Bitboard ClearMaskBB[65];
35
36 Bitboard SquaresByColorBB[2];
37 Bitboard FileBB[8];
38 Bitboard RankBB[8];
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];
47
48 Bitboard BishopPseudoAttacks[64];
49 Bitboard RookPseudoAttacks[64];
50 Bitboard QueenPseudoAttacks[64];
51
52 uint8_t BitCount8Bit[256];
53
54 namespace {
55
56 #if defined(IS_64BIT)
57
58 const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL;
59
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,
82   0x0A08520292120600ULL
83 };
84
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
108 };
109
110 const int BShift[64] = {
111   58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59,
112   59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59,
113   59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59,
114   59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58
115 };
116
117 const int RShift[64] = {
118   52, 53, 53, 53, 53, 53, 53, 52, 53, 54, 54, 54, 54, 54, 54, 53,
119   53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53,
120   53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53,
121   53, 54, 54, 54, 54, 54, 54, 53, 52, 53, 53, 53, 53, 53, 53, 52
122 };
123
124 #else // if !defined(IS_64BIT)
125
126 const uint32_t DeBruijnMagic = 0x783A9B23;
127
128 const uint64_t BMult[64] = {
129   0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL,
130   0xBFED1A0B80F838C5ULL, 0x90561D5631E62110ULL, 0x2804260376E60944ULL,
131   0x84A656409AA76871ULL, 0xF0267F64C28B6197ULL, 0x70764EBB762F0585ULL,
132   0x92AA09E0CFE161DEULL, 0x41EE1F6BB266F60EULL, 0xDDCBF04F6039C444ULL,
133   0x5A3FAB7BAC0D988AULL, 0xD3727877FA4EAA03ULL, 0xD988402D868DDAAEULL,
134   0x812B291AFA075C7CULL, 0x94FAF987B685A932ULL, 0x3ED867D8470D08DBULL,
135   0x92517660B8901DE8ULL, 0x2D97E43E058814B4ULL, 0x880A10C220B25582ULL,
136   0xC7C6520D1F1A0477ULL, 0xDBFC7FBCD7656AA6ULL, 0x78B1B9BFB1A2B84FULL,
137   0x2F20037F112A0BC1ULL, 0x657171EA2269A916ULL, 0xC08302B07142210EULL,
138   0x0880A4403064080BULL, 0x3602420842208C00ULL, 0x852800DC7E0B6602ULL,
139   0x595A3FBBAA0F03B2ULL, 0x9F01411558159D5EULL, 0x2B4A4A5F88B394F2ULL,
140   0x4AFCBFFC292DD03AULL, 0x4A4094A3B3F10522ULL, 0xB06F00B491F30048ULL,
141   0xD5B3820280D77004ULL, 0x8B2E01E7C8E57A75ULL, 0x2D342794E886C2E6ULL,
142   0xC302C410CDE21461ULL, 0x111F426F1379C274ULL, 0xE0569220ABB31588ULL,
143   0x5026D3064D453324ULL, 0xE2076040C343CD8AULL, 0x93EFD1E1738021EEULL,
144   0xB680804BED143132ULL, 0x44E361B21986944CULL, 0x44C60170EF5C598CULL,
145   0xF4DA475C195C9C94ULL, 0xA3AFBB5F72060B1DULL, 0xBC75F410E41C4FFCULL,
146   0xB51C099390520922ULL, 0x902C011F8F8EC368ULL, 0x950B56B3D6F5490AULL,
147   0x3909E0635BF202D0ULL, 0x5744F90206EC10CCULL, 0xDC59FD76317ABBC1ULL,
148   0x881C7C67FCBFC4F6ULL, 0x47CA41E7E440D423ULL, 0xEB0C88112048D004ULL,
149   0x51C60E04359AEF1AULL, 0x1AA1FE0E957A5554ULL, 0xDD9448DB4F5E3104ULL,
150   0xDC01F6DCA4BEBBDCULL,
151 };
152
153 const uint64_t RMult[64] = {
154   0xD7445CDEC88002C0ULL, 0xD0A505C1F2001722ULL, 0xE065D1C896002182ULL,
155   0x9A8C41E75A000892ULL, 0x8900B10C89002AA8ULL, 0x9B28D1C1D60005A2ULL,
156   0x015D6C88DE002D9AULL, 0xB1DBFC802E8016A9ULL, 0x149A1042D9D60029ULL,
157   0xB9C08050599E002FULL, 0x132208C3AF300403ULL, 0xC1000CE2E9C50070ULL,
158   0x9D9AA13C99020012ULL, 0xB6B078DAF71E0046ULL, 0x9D880182FB6E002EULL,
159   0x52889F467E850037ULL, 0xDA6DC008D19A8480ULL, 0x468286034F902420ULL,
160   0x7140AC09DC54C020ULL, 0xD76FFFFA39548808ULL, 0xEA901C4141500808ULL,
161   0xC91004093F953A02ULL, 0x02882AFA8F6BB402ULL, 0xAEBE335692442C01ULL,
162   0x0E904A22079FB91EULL, 0x13A514851055F606ULL, 0x76C782018C8FE632ULL,
163   0x1DC012A9D116DA06ULL, 0x3C9E0037264FFFA6ULL, 0x2036002853C6E4A2ULL,
164   0xE3FE08500AFB47D4ULL, 0xF38AF25C86B025C2ULL, 0xC0800E2182CF9A40ULL,
165   0x72002480D1F60673ULL, 0x2500200BAE6E9B53ULL, 0xC60018C1EEFCA252ULL,
166   0x0600590473E3608AULL, 0x46002C4AB3FE51B2ULL, 0xA200011486BCC8D2ULL,
167   0xB680078095784C63ULL, 0x2742002639BF11AEULL, 0xC7D60021A5BDB142ULL,
168   0xC8C04016BB83D820ULL, 0xBD520028123B4842ULL, 0x9D1600344AC2A832ULL,
169   0x6A808005631C8A05ULL, 0x604600A148D5389AULL, 0xE2E40103D40DEA65ULL,
170   0x945B5A0087C62A81ULL, 0x012DC200CD82D28EULL, 0x2431C600B5F9EF76ULL,
171   0xFB142A006A9B314AULL, 0x06870E00A1C97D62ULL, 0x2A9DB2004A2689A2ULL,
172   0xD3594600CAF5D1A2ULL, 0xEE0E4900439344A7ULL, 0x89C4D266CA25007AULL,
173   0x3E0013A2743F97E3ULL, 0x0180E31A0431378AULL, 0x3A9E465A4D42A512ULL,
174   0x98D0A11A0C0D9CC2ULL, 0x8E711C1ABA19B01EULL, 0x8DCDC836DD201142ULL,
175   0x5AC08A4735370479ULL,
176 };
177
178 const int BShift[64] = {
179   26, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 27, 27,
180   27, 27, 25, 25, 25, 25, 27, 27, 27, 27, 25, 23, 23, 25, 27, 27,
181   27, 27, 25, 23, 23, 25, 27, 27, 27, 27, 25, 25, 25, 25, 27, 27,
182   27, 27, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 26
183 };
184
185 const int RShift[64] = {
186   20, 21, 21, 21, 21, 21, 21, 20, 21, 22, 22, 22, 22, 22, 22, 21,
187   21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21,
188   21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21,
189   21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20
190 };
191
192 #endif // defined(IS_64BIT)
193
194   CACHE_LINE_ALIGNMENT int BSFTable[64];
195
196   void init_sliding_attacks(Bitboard attacks[], Magics m[], const int shift[],
197                             const Bitboard mult[], Square deltas[]);
198 }
199
200
201 /// print_bitboard() prints a bitboard in an easily readable format to the
202 /// standard output. This is sometimes useful for debugging.
203
204 void print_bitboard(Bitboard b) {
205
206   for (Rank r = RANK_8; r >= RANK_1; r--)
207   {
208       std::cout << "+---+---+---+---+---+---+---+---+" << '\n';
209       for (File f = FILE_A; f <= FILE_H; f++)
210           std::cout << "| " << (bit_is_set(b, make_square(f, r)) ? 'X' : ' ') << ' ';
211
212       std::cout << "|\n";
213   }
214   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
215 }
216
217
218 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
219 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
220 /// nonzero bitboard.
221
222 #if defined(IS_64BIT) && !defined(USE_BSFQ)
223
224 Square first_1(Bitboard b) {
225   return Square(BSFTable[((b & -b) * DeBruijnMagic) >> 58]);
226 }
227
228 Square pop_1st_bit(Bitboard* b) {
229   Bitboard bb = *b;
230   *b &= (*b - 1);
231   return Square(BSFTable[((bb & -bb) * DeBruijnMagic) >> 58]);
232 }
233
234 #elif !defined(USE_BSFQ)
235
236 Square first_1(Bitboard b) {
237   b ^= (b - 1);
238   uint32_t fold = unsigned(b) ^ unsigned(b >> 32);
239   return Square(BSFTable[(fold * DeBruijnMagic) >> 26]);
240 }
241
242 // Use type-punning
243 union b_union {
244
245     Bitboard b;
246     struct {
247 #if defined (BIGENDIAN)
248         uint32_t h;
249         uint32_t l;
250 #else
251         uint32_t l;
252         uint32_t h;
253 #endif
254     } dw;
255 };
256
257 Square pop_1st_bit(Bitboard* bb) {
258
259    b_union u;
260    Square ret;
261
262    u.b = *bb;
263
264    if (u.dw.l)
265    {
266        ret = Square(BSFTable[((u.dw.l ^ (u.dw.l - 1)) * DeBruijnMagic) >> 26]);
267        u.dw.l &= (u.dw.l - 1);
268        *bb = u.b;
269        return ret;
270    }
271    ret = Square(BSFTable[((~(u.dw.h ^ (u.dw.h - 1))) * DeBruijnMagic) >> 26]);
272    u.dw.h &= (u.dw.h - 1);
273    *bb = u.b;
274    return ret;
275 }
276
277 #endif // !defined(USE_BSFQ)
278
279
280 /// init_bitboards() initializes various bitboard arrays. It is called during
281 /// program initialization.
282
283 void init_bitboards() {
284
285   SquaresByColorBB[DARK]  =  0xAA55AA55AA55AA55ULL;
286   SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK];
287
288   for (Square s = SQ_A1; s <= SQ_H8; s++)
289   {
290       SetMaskBB[s] = (1ULL << s);
291       ClearMaskBB[s] = ~SetMaskBB[s];
292   }
293
294   ClearMaskBB[SQ_NONE] = ~EmptyBoardBB;
295
296   FileBB[FILE_A] = FileABB;
297   RankBB[RANK_1] = Rank1BB;
298
299   for (int f = FILE_B; f <= FILE_H; f++)
300   {
301       FileBB[f] = FileBB[f - 1] << 1;
302       RankBB[f] = RankBB[f - 1] << 8;
303   }
304
305   for (int f = FILE_A; f <= FILE_H; f++)
306   {
307       NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
308       ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f];
309   }
310
311   for (int rw = RANK_7, rb = RANK_2; rw >= RANK_1; rw--, rb++)
312   {
313       InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1];
314       InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1];
315   }
316
317   for (Color c = WHITE; c <= BLACK; c++)
318       for (Square s = SQ_A1; s <= SQ_H8; s++)
319       {
320           SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
321           PassedPawnMask[c][s]     = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
322           AttackSpanMask[c][s]     = in_front_bb(c, s) & neighboring_files_bb(s);
323       }
324
325   for (Bitboard b = 0; b < 256; b++)
326       BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
327
328   for (int i = 1; i < 64; i++)
329       if (!CpuIs64Bit) // Matt Taylor's folding trick for 32 bit systems
330       {
331           Bitboard b = 1ULL << i;
332           b ^= b - 1;
333           b ^= b >> 32;
334           BSFTable[uint32_t(b * DeBruijnMagic) >> 26] = i;
335       }
336       else
337           BSFTable[((1ULL << i) * DeBruijnMagic) >> 58] = i;
338
339   int steps[][9] = {
340     {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}
341   };
342
343   for (Color c = WHITE; c <= BLACK; c++)
344       for (Square s = SQ_A1; s <= SQ_H8; s++)
345           for (PieceType pt = PAWN; pt <= KING; pt++)
346               for (int k = 0; steps[pt][k]; k++)
347               {
348                   Square to = s + Square(c == WHITE ? steps[pt][k] : -steps[pt][k]);
349
350                   if (square_is_ok(to) && square_distance(s, to) < 3)
351                       set_bit(&StepAttacksBB[make_piece(c, pt)][s], to);
352               }
353
354   Square RDeltas[] = { DELTA_N,  DELTA_E,  DELTA_S,  DELTA_W  };
355   Square BDeltas[] = { DELTA_NE, DELTA_SE, DELTA_SW, DELTA_NW };
356
357   init_sliding_attacks(RAttacks, RMagics, RShift, RMult, RDeltas);
358   init_sliding_attacks(BAttacks, BMagics, BShift, BMult, BDeltas);
359
360   for (Square s = SQ_A1; s <= SQ_H8; s++)
361   {
362       BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
363       RookPseudoAttacks[s]   = rook_attacks_bb(s, EmptyBoardBB);
364       QueenPseudoAttacks[s]  = queen_attacks_bb(s, EmptyBoardBB);
365   }
366
367   for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
368       for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
369           if (bit_is_set(QueenPseudoAttacks[s1], s2))
370           {
371               int f = file_distance(s1, s2);
372               int r = rank_distance(s1, s2);
373
374               Square d = (s2 - s1) / Max(f, r);
375
376               for (Square s3 = s1 + d; s3 != s2; s3 += d)
377                   set_bit(&BetweenBB[s1][s2], s3);
378           }
379 }
380
381
382 namespace {
383
384   Bitboard submask(Bitboard mask, int key) {
385
386     Bitboard subMask = 0;
387     int bitNum = -1;
388
389     // Extract an unique submask out of a mask according to the given key
390     for (Square s = SQ_A1; s <= SQ_H8; s++)
391         if (bit_is_set(mask, s) && bit_is_set(key, Square(++bitNum)))
392             set_bit(&subMask, s);
393
394     return subMask;
395   }
396
397   Bitboard sliding_attacks(Square sq, Bitboard occupied, Square deltas[], bool skipLast) {
398
399     Bitboard attacks = 0;
400
401     for (int i = 0; i < 4; i++)
402     {
403         Square s = sq + deltas[i];
404
405         while (    square_is_ok(s)
406                &&  square_distance(s, s - deltas[i]) == 1
407                && (!skipLast || !file_distance(s, sq) || (square_file(s) != FILE_A && square_file(s) != FILE_H))
408                && (!skipLast || !rank_distance(s, sq) || (square_rank(s) != RANK_1 && square_rank(s) != RANK_8)))
409         {
410             attacks |= 1ULL << s;
411
412             if (occupied & (1ULL << s))
413                 break;
414
415             s += deltas[i];
416         }
417     }
418     return attacks;
419   }
420
421   void init_sliding_attacks(Bitboard attacks[], Magics m[], const int shift[],
422                             const Bitboard mult[], Square deltas[]) {
423     Bitboard occupancy, index;
424     int maxKey, offset = 0;
425
426     for (Square s = SQ_A1; s <= SQ_H8; s++)
427     {
428         m[s].offset = offset;
429         m[s].mult   = mult[s];
430         m[s].shift  = shift[s];
431         m[s].mask   = sliding_attacks(s, EmptyBoardBB, deltas, true);
432
433         maxKey = 1 << (CpuIs64Bit ? 64 - shift[s] : 32 - shift[s]);
434
435         for (int key = 0; key < maxKey; key++)
436         {
437             occupancy = submask(m[s].mask, key);
438
439             index = CpuIs64Bit ? occupancy * mult[s]
440                                : unsigned(occupancy * mult[s] ^ (occupancy >> 32) * (mult[s] >> 32));
441
442             attacks[offset + (index >> shift[s])] = sliding_attacks(s, occupancy, deltas, false);
443         }
444         offset += maxKey;
445     }
446   }
447 }