]> git.sesse.net Git - stockfish/blob - src/bitboard.cpp
0bdb9d3ae627bf1793d5cf450fb814f50360b5bd
[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-2009 Marco Costalba
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
21 ////
22 //// Includes
23 ////
24
25 #include <iostream>
26
27 #include "bitboard.h"
28 #include "bitcount.h"
29 #include "direction.h"
30
31
32 #if defined(IS_64BIT)
33
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,
56   0xa08520292120600ULL
57 };
58
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,
81   0x410201ce5c030092ULL
82 };
83
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
89 };
90
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
96 };
97
98 #else // if !defined(IS_64BIT)
99
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,
123 };
124
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,
148 };
149
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
155 };
156
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
162 };
163
164 #endif // defined(IS_64BIT)
165
166
167 Bitboard RMask[64];
168 int RAttackIndex[64];
169 Bitboard RAttacks[0x19000];
170
171 Bitboard BMask[64];
172 int BAttackIndex[64];
173 Bitboard BAttacks[0x1480];
174
175 Bitboard SetMaskBB[65];
176 Bitboard ClearMaskBB[65];
177
178 Bitboard StepAttackBB[16][64];
179 Bitboard RayBB[64][8];
180 Bitboard BetweenBB[64][64];
181
182 Bitboard PassedPawnMask[2][64];
183 Bitboard OutpostMask[2][64];
184
185 Bitboard BishopPseudoAttacks[64];
186 Bitboard RookPseudoAttacks[64];
187 Bitboard QueenPseudoAttacks[64];
188
189
190 ////
191 //// Local definitions
192 ////
193
194 namespace {
195
196   void init_masks();
197   void init_ray_bitboards();
198   void init_attacks();
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[],
206                             int deltas[][2]);
207   void init_pseudo_attacks();
208 }
209
210
211 ////
212 //// Functions
213 ////
214
215 /// print_bitboard() prints a bitboard in an easily readable format to the
216 /// standard output.  This is sometimes useful for debugging.
217
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;
224   }
225   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
226 }
227
228
229 /// init_bitboards() initializes various bitboard arrays.  It is called during
230 /// program initialization.
231
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}};
235   init_masks();
236   init_ray_bitboards();
237   init_attacks();
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();
242 }
243
244
245 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
246 /// nonzero bitboard.
247
248 #if defined(IS_64BIT) && !defined(USE_BSFQ)
249
250 Square pop_1st_bit(Bitboard* b) {
251   Bitboard bb = *b ^ (*b - 1);
252   uint32_t fold = int(bb) ^ int(bb >> 32);
253   *b &= (*b - 1);
254   return Square(BitTable[(fold * 0x783a9b23) >> 26]);
255 }
256
257 #elif !defined(USE_BSFQ)
258
259 // Use type-punning
260 union b_union {
261
262     Bitboard b;
263     struct {
264         uint32_t l;
265         uint32_t h;
266     } dw;
267 };
268
269 // WARNING: Needs -fno-strict-aliasing compiler option
270 Square pop_1st_bit(Bitboard* bb) {
271
272   b_union u;
273   uint32_t b;
274
275   u.b = *bb;
276
277   if (u.dw.l)
278   {
279       b = u.dw.l;
280       *((uint32_t*)bb) = b & (b - 1);
281       b ^= (b - 1);
282   }
283   else
284   {
285       b = u.dw.h;
286       *((uint32_t*)bb+1) = b & (b - 1); // Little endian only?
287       b = ~(b ^ (b - 1));
288   }
289   return Square(BitTable[(b * 0x783a9b23) >> 26]);
290 }
291
292 #endif
293
294 namespace {
295
296   // All functions below are used to precompute various bitboards during
297   // program initialization.  Some of the functions may be difficult to
298   // understand, but they all seem to work correctly, and it should never
299   // be necessary to touch any of them.
300
301   void init_masks() {
302     SetMaskBB[SQ_NONE] = 0ULL;
303     ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE];
304     for(Square s = SQ_A1; s <= SQ_H8; s++) {
305       SetMaskBB[s] = (1ULL << s);
306       ClearMaskBB[s] = ~SetMaskBB[s];
307     }
308     for(Color c = WHITE; c <= BLACK; c++)
309       for(Square s = SQ_A1; s <= SQ_H8; s++) {
310         PassedPawnMask[c][s] =
311           in_front_bb(c, s) & this_and_neighboring_files_bb(s);
312         OutpostMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
313       }
314   }
315
316
317   void init_ray_bitboards() {
318     int d[8] = {1, -1, 16, -16, 17, -17, 15, -15};
319     for(int i = 0; i < 128; i = (i + 9) & ~8) {
320       for(int j = 0; j < 8; j++) {
321         RayBB[(i&7)|((i>>4)<<3)][j] = EmptyBoardBB;
322         for(int k = i + d[j]; (k & 0x88) == 0; k += d[j])
323           set_bit(&(RayBB[(i&7)|((i>>4)<<3)][j]), Square((k&7)|((k>>4)<<3)));
324       }
325     }
326   }
327
328
329   void init_attacks() {
330     int i, j, k, l;
331     int step[16][8] =  {
332       {0},
333       {7,9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
334       {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}, {0}, {0},
335       {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
336       {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}
337     };
338
339     for(i = 0; i < 64; i++) {
340       for(j = 0; j <= int(BK); j++) {
341         StepAttackBB[j][i] = EmptyBoardBB;
342         for(k = 0; k < 8 && step[j][k] != 0; k++) {
343           l = i + step[j][k];
344           if(l >= 0 && l < 64 && abs((i&7) - (l&7)) < 3)
345             StepAttackBB[j][i] |= (1ULL << l);
346         }
347       }
348     }
349   }
350
351
352   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
353                            int fmin=0, int fmax=7, int rmin=0, int rmax=7) {
354     Bitboard result = 0ULL;
355     int rk = sq / 8, fl = sq % 8, r, f, i;
356     for(i = 0; i < dirs; i++) {
357       int dx = deltas[i][0], dy = deltas[i][1];
358       for(f = fl+dx, r = rk+dy;
359           (dx==0 || (f>=fmin && f<=fmax)) && (dy==0 || (r>=rmin && r<=rmax));
360           f += dx, r += dy) {
361         result |= (1ULL << (f + r*8));
362         if(block & (1ULL << (f + r*8))) break;
363       }
364     }
365     return result;
366   }
367
368
369   void init_between_bitboards() {
370     SquareDelta step[8] = {
371       DELTA_E, DELTA_W, DELTA_N, DELTA_S, DELTA_NE, DELTA_SW, DELTA_NW, DELTA_SE
372     };
373     SignedDirection d;
374     for(Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
375       for(Square s2 = SQ_A1; s2 <= SQ_H8; s2++) {
376         BetweenBB[s1][s2] = EmptyBoardBB;
377         d = signed_direction_between_squares(s1, s2);
378         if(d != SIGNED_DIR_NONE)
379           for(Square s3 = s1 + step[d]; s3 != s2; s3 += step[d])
380             set_bit(&(BetweenBB[s1][s2]), s3);
381       }
382   }
383
384
385   Bitboard index_to_bitboard(int index, Bitboard mask) {
386     int i, j, bits = count_1s(mask);
387     Bitboard result = 0ULL;
388     for(i = 0; i < bits; i++) {
389       j = pop_1st_bit(&mask);
390       if(index & (1 << i)) result |= (1ULL << j);
391     }
392     return result;
393   }
394
395
396   void init_sliding_attacks(Bitboard attacks[],
397                             int attackIndex[], Bitboard mask[],
398                             const int shift[2], const Bitboard mult[],
399                             int deltas[][2]) {
400     int i, j, k, index = 0;
401     Bitboard b;
402     for(i = 0; i < 64; i++) {
403       attackIndex[i] = index;
404       mask[i] = sliding_attacks(i, 0ULL, 4, deltas, 1, 6, 1, 6);
405
406 #if defined(IS_64BIT)
407       j = (1 << (64 - shift[i]));
408 #else
409       j = (1 << (32 - shift[i]));
410 #endif
411
412       for(k = 0; k < j; k++) {
413
414 #if defined(IS_64BIT)
415         b = index_to_bitboard(k, mask[i]);
416         attacks[index + ((b * mult[i]) >> shift[i])] =
417           sliding_attacks(i, b, 4, deltas);
418 #else
419         b = index_to_bitboard(k, mask[i]);
420         attacks[index +
421                  (unsigned(int(b) * int(mult[i]) ^
422                            int(b >> 32) * int(mult[i] >> 32))
423                   >> shift[i])] =
424           sliding_attacks(i, b, 4, deltas);
425 #endif
426       }
427       index += j;
428     }
429   }
430
431
432   void init_pseudo_attacks() {
433     Square s;
434     for(s = SQ_A1; s <= SQ_H8; s++) {
435       BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
436       RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB);
437       QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB);
438     }
439   }
440
441 }