Introduce bitcount.h
[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 #ifdef _MSC_VER
26     #include <intrin.h>
27     #ifdef _WIN64
28         #pragma intrinsic(_BitScanForward64)
29     #else
30         #pragma intrinsic(_BitScanForward)
31     #endif
32     #define USING_INTRINSICS
33 #endif
34
35 #include <iostream>
36
37 #include "bitboard.h"
38 #include "bitcount.h"
39 #include "direction.h"
40
41
42 #if defined(USE_COMPACT_ROOK_ATTACKS)
43
44 Bitboard RankAttacks[8][64], FileAttacks[8][64];
45
46 #elif defined(USE_32BIT_ATTACKS)
47
48 const uint64_t RMult[64] = {
49   0xd7445cdec88002c0ULL, 0xd0a505c1f2001722ULL, 0xe065d1c896002182ULL,
50   0x9a8c41e75a000892ULL, 0x8900b10c89002aa8ULL, 0x9b28d1c1d60005a2ULL,
51   0x15d6c88de002d9aULL, 0xb1dbfc802e8016a9ULL, 0x149a1042d9d60029ULL,
52   0xb9c08050599e002fULL, 0x132208c3af300403ULL, 0xc1000ce2e9c50070ULL,
53   0x9d9aa13c99020012ULL, 0xb6b078daf71e0046ULL, 0x9d880182fb6e002eULL,
54   0x52889f467e850037ULL, 0xda6dc008d19a8480ULL, 0x468286034f902420ULL,
55   0x7140ac09dc54c020ULL, 0xd76ffffa39548808ULL, 0xea901c4141500808ULL,
56   0xc91004093f953a02ULL, 0x2882afa8f6bb402ULL, 0xaebe335692442c01ULL,
57   0xe904a22079fb91eULL, 0x13a514851055f606ULL, 0x76c782018c8fe632ULL,
58   0x1dc012a9d116da06ULL, 0x3c9e0037264fffa6ULL, 0x2036002853c6e4a2ULL,
59   0xe3fe08500afb47d4ULL, 0xf38af25c86b025c2ULL, 0xc0800e2182cf9a40ULL,
60   0x72002480d1f60673ULL, 0x2500200bae6e9b53ULL, 0xc60018c1eefca252ULL,
61   0x600590473e3608aULL, 0x46002c4ab3fe51b2ULL, 0xa200011486bcc8d2ULL,
62   0xb680078095784c63ULL, 0x2742002639bf11aeULL, 0xc7d60021a5bdb142ULL,
63   0xc8c04016bb83d820ULL, 0xbd520028123b4842ULL, 0x9d1600344ac2a832ULL,
64   0x6a808005631c8a05ULL, 0x604600a148d5389aULL, 0xe2e40103d40dea65ULL,
65   0x945b5a0087c62a81ULL, 0x12dc200cd82d28eULL, 0x2431c600b5f9ef76ULL,
66   0xfb142a006a9b314aULL, 0x6870e00a1c97d62ULL, 0x2a9db2004a2689a2ULL,
67   0xd3594600caf5d1a2ULL, 0xee0e4900439344a7ULL, 0x89c4d266ca25007aULL,
68   0x3e0013a2743f97e3ULL, 0x180e31a0431378aULL, 0x3a9e465a4d42a512ULL,
69   0x98d0a11a0c0d9cc2ULL, 0x8e711c1aba19b01eULL, 0x8dcdc836dd201142ULL,
70   0x5ac08a4735370479ULL,
71 };
72
73 const int RShift[64] = {
74   20, 21, 21, 21, 21, 21, 21, 20, 21, 22, 22, 22, 22, 22, 22, 21,
75   21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21,
76   21, 22, 22, 22, 22, 22, 22, 21, 21, 22, 22, 22, 22, 22, 22, 21,
77   21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20
78 };
79
80 #else // if defined(USE_32BIT_ATTACKS)
81
82 const uint64_t RMult[64] = {
83   0xa8002c000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL,
84   0x380180080141000ULL, 0x1a00060008211044ULL, 0x410001000a0c0008ULL,
85   0x9500060004008100ULL, 0x100024284a20700ULL, 0x802140008000ULL,
86   0x80c01002a00840ULL, 0x402004282011020ULL, 0x9862000820420050ULL,
87   0x1001448011100ULL, 0x6432800200800400ULL, 0x40100010002000cULL,
88   0x2800d0010c080ULL, 0x90c0008000803042ULL, 0x4010004000200041ULL,
89   0x3010010200040ULL, 0xa40828028001000ULL, 0x123010008000430ULL,
90   0x24008004020080ULL, 0x60040001104802ULL, 0x582200028400d1ULL,
91   0x4000802080044000ULL, 0x408208200420308ULL, 0x610038080102000ULL,
92   0x3601000900100020ULL, 0x80080040180ULL, 0xc2020080040080ULL,
93   0x80084400100102ULL, 0x4022408200014401ULL, 0x40052040800082ULL,
94   0xb08200280804000ULL, 0x8a80a008801000ULL, 0x4000480080801000ULL,
95   0x911808800801401ULL, 0x822a003002001894ULL, 0x401068091400108aULL,
96   0x4a10a00004cULL, 0x2000800640008024ULL, 0x1486408102020020ULL,
97   0x100a000d50041ULL, 0x810050020b0020ULL, 0x204000800808004ULL,
98   0x20048100a000cULL, 0x112000831020004ULL, 0x9000040810002ULL,
99   0x440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL,
100   0x4b824a2010010100ULL, 0x4080801810c0080ULL, 0x400802a0080ULL,
101   0x8224080110026400ULL, 0x40002c4104088200ULL, 0x1002100104a0282ULL,
102   0x1208400811048021ULL, 0x3201014a40d02001ULL, 0x5100019200501ULL,
103   0x101000208001005ULL, 0x2008450080702ULL, 0x1002080301d00cULL,
104   0x410201ce5c030092ULL
105 };
106
107 const int RShift[64] = {
108   52, 53, 53, 53, 53, 53, 53, 52, 53, 54, 54, 54, 54, 54, 54, 53,
109   53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53,
110   53, 54, 54, 54, 54, 54, 54, 53, 53, 54, 54, 54, 54, 54, 54, 53,
111   53, 54, 54, 54, 54, 54, 54, 53, 52, 53, 53, 53, 53, 53, 53, 52
112 };
113
114 #endif // defined(USE_32BIT_ATTACKS)
115
116 #if !defined(USE_COMPACT_ROOK_ATTACKS)
117 Bitboard RMask[64];
118 int RAttackIndex[64];
119 Bitboard RAttacks[0x19000];
120 #endif
121
122 #if defined(USE_32BIT_ATTACKS)
123
124 const uint64_t BMult[64] = {
125   0x54142844c6a22981ULL, 0x710358a6ea25c19eULL, 0x704f746d63a4a8dcULL,
126   0xbfed1a0b80f838c5ULL, 0x90561d5631e62110ULL, 0x2804260376e60944ULL,
127   0x84a656409aa76871ULL, 0xf0267f64c28b6197ULL, 0x70764ebb762f0585ULL,
128   0x92aa09e0cfe161deULL, 0x41ee1f6bb266f60eULL, 0xddcbf04f6039c444ULL,
129   0x5a3fab7bac0d988aULL, 0xd3727877fa4eaa03ULL, 0xd988402d868ddaaeULL,
130   0x812b291afa075c7cULL, 0x94faf987b685a932ULL, 0x3ed867d8470d08dbULL,
131   0x92517660b8901de8ULL, 0x2d97e43e058814b4ULL, 0x880a10c220b25582ULL,
132   0xc7c6520d1f1a0477ULL, 0xdbfc7fbcd7656aa6ULL, 0x78b1b9bfb1a2b84fULL,
133   0x2f20037f112a0bc1ULL, 0x657171ea2269a916ULL, 0xc08302b07142210eULL,
134   0x880a4403064080bULL, 0x3602420842208c00ULL, 0x852800dc7e0b6602ULL,
135   0x595a3fbbaa0f03b2ULL, 0x9f01411558159d5eULL, 0x2b4a4a5f88b394f2ULL,
136   0x4afcbffc292dd03aULL, 0x4a4094a3b3f10522ULL, 0xb06f00b491f30048ULL,
137   0xd5b3820280d77004ULL, 0x8b2e01e7c8e57a75ULL, 0x2d342794e886c2e6ULL,
138   0xc302c410cde21461ULL, 0x111f426f1379c274ULL, 0xe0569220abb31588ULL,
139   0x5026d3064d453324ULL, 0xe2076040c343cd8aULL, 0x93efd1e1738021eeULL,
140   0xb680804bed143132ULL, 0x44e361b21986944cULL, 0x44c60170ef5c598cULL,
141   0xf4da475c195c9c94ULL, 0xa3afbb5f72060b1dULL, 0xbc75f410e41c4ffcULL,
142   0xb51c099390520922ULL, 0x902c011f8f8ec368ULL, 0x950b56b3d6f5490aULL,
143   0x3909e0635bf202d0ULL, 0x5744f90206ec10ccULL, 0xdc59fd76317abbc1ULL,
144   0x881c7c67fcbfc4f6ULL, 0x47ca41e7e440d423ULL, 0xeb0c88112048d004ULL,
145   0x51c60e04359aef1aULL, 0x1aa1fe0e957a5554ULL, 0xdd9448db4f5e3104ULL,
146   0xdc01f6dca4bebbdcULL,
147 };
148
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
154 };
155
156 #else // if defined(USE_32BIT_ATTACKS)
157
158 const uint64_t BMult[64] = {
159   0x440049104032280ULL, 0x1021023c82008040ULL, 0x404040082000048ULL,
160   0x48c4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL,
161   0x181011002e06040ULL, 0x9101004104200e00ULL, 0x1240848848310401ULL,
162   0x2000142828050024ULL, 0x1004024d5000ULL, 0x102044400800200ULL,
163   0x8108108820112000ULL, 0xa880818210c00046ULL, 0x4008008801082000ULL,
164   0x60882404049400ULL, 0x104402004240810ULL, 0xa002084250200ULL,
165   0x100b0880801100ULL, 0x4080201220101ULL, 0x44008080a00000ULL,
166   0x202200842000ULL, 0x5006004882d00808ULL, 0x200045080802ULL,
167   0x86100020200601ULL, 0xa802080a20112c02ULL, 0x80411218080900ULL,
168   0x200a0880080a0ULL, 0x9a01010000104000ULL, 0x28008003100080ULL,
169   0x211021004480417ULL, 0x401004188220806ULL, 0x825051400c2006ULL,
170   0x140c0210943000ULL, 0x242800300080ULL, 0xc2208120080200ULL,
171   0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL,
172   0x822081014405ULL, 0x800c049e40400804ULL, 0x4a0404028a000820ULL,
173   0x22060201041200ULL, 0x360904200840801ULL, 0x881a08208800400ULL,
174   0x60202c00400420ULL, 0x1204440086061400ULL, 0x8184042804040ULL,
175   0x64040315300400ULL, 0xc01008801090a00ULL, 0x808010401140c00ULL,
176   0x4004830c2020040ULL, 0x80005002020054ULL, 0x40000c14481a0490ULL,
177   0x10500101042048ULL, 0x1010100200424000ULL, 0x640901901040ULL,
178   0xa0201014840ULL, 0x840082aa011002ULL, 0x10010840084240aULL,
179   0x420400810420608ULL, 0x8d40230408102100ULL, 0x4a00200612222409ULL,
180   0xa08520292120600ULL
181 };
182
183 const int BShift[64] = {
184   58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59,
185   59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59,
186   59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59,
187   59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58
188 };
189
190 #endif // defined(USE_32BIT_ATTACKS)
191
192 Bitboard BMask[64];
193 int BAttackIndex[64];
194 Bitboard BAttacks[0x1480];
195
196 Bitboard SetMaskBB[65];
197 Bitboard ClearMaskBB[65];
198
199 Bitboard StepAttackBB[16][64];
200 Bitboard RayBB[64][8];
201 Bitboard BetweenBB[64][64];
202
203 Bitboard PassedPawnMask[2][64];
204 Bitboard OutpostMask[2][64];
205
206 Bitboard BishopPseudoAttacks[64];
207 Bitboard RookPseudoAttacks[64];
208 Bitboard QueenPseudoAttacks[64];
209
210
211 ////
212 //// Local definitions
213 ////
214
215 namespace {
216
217   void init_masks();
218   void init_ray_bitboards();
219   void init_attacks();
220   void init_between_bitboards();
221   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
222                            int fmin, int fmax, int rmin, int rmax);
223   Bitboard index_to_bitboard(int index, Bitboard mask);
224   void init_sliding_attacks(Bitboard attacks[],
225                             int attackIndex[], Bitboard mask[],
226                             const int shift[2], const Bitboard mult[],
227                             int deltas[][2]);
228   void init_pseudo_attacks();
229 #if defined(USE_COMPACT_ROOK_ATTACKS)
230   void init_file_and_rank_attacks();
231 #endif
232 }
233
234
235 ////
236 //// Functions
237 ////
238
239 /// print_bitboard() prints a bitboard in an easily readable format to the
240 /// standard output.  This is sometimes useful for debugging.
241
242 void print_bitboard(Bitboard b) {
243   for(Rank r = RANK_8; r >= RANK_1; r--) {
244     std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
245     for(File f = FILE_A; f <= FILE_H; f++)
246       std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' ';
247     std::cout << "|" << std::endl;
248   }
249   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
250 }
251
252
253 /// init_bitboards() initializes various bitboard arrays.  It is called during
254 /// program initialization.
255
256 void init_bitboards() {
257   int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
258   int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
259   init_masks();
260   init_ray_bitboards();
261   init_attacks();
262   init_between_bitboards();
263 #if defined(USE_COMPACT_ROOK_ATTACKS)
264   init_file_and_rank_attacks();
265 #else
266   init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift,
267                        RMult, rookDeltas);
268 #endif
269   init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift,
270                        BMult, bishopDeltas);
271   init_pseudo_attacks();
272 }
273
274
275 #if defined(USE_FOLDED_BITSCAN)
276
277 static const int BitTable[64] = {
278   63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
279   51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
280   26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
281   58, 20, 37, 17, 36, 8
282 };
283
284
285 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
286
287 Square first_1(Bitboard b) {
288   b ^= (b - 1);
289   uint32_t fold = int(b) ^ int(b >> 32);
290   return Square(BitTable[(fold * 0x783a9b23) >> 26]);
291 }
292
293
294 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
295 /// nonzero bitboard.
296
297 #if defined(USE_32BIT_ATTACKS)
298
299 // Use type-punning
300 union b_union {
301
302     Bitboard b;
303     struct {
304         uint32_t l;
305         uint32_t h;
306     } dw;
307 };
308
309 // WARNING: Needs -fno-strict-aliasing compiler option
310 Square pop_1st_bit(Bitboard *bb) {
311
312   b_union u;
313   uint32_t b;
314
315   u.b = *bb;
316
317   if (u.dw.l)
318   {
319       b = u.dw.l;
320       *((uint32_t*)bb) = b & (b - 1);
321       b ^= (b - 1);
322   }
323   else
324   {
325       b = u.dw.h;
326       *((uint32_t*)bb+1) = b & (b - 1); // Little endian only?
327       b = ~(b ^ (b - 1));
328   }
329   return Square(BitTable[(b * 0x783a9b23) >> 26]);
330 }
331
332 #else
333
334 Square pop_1st_bit(Bitboard *b) {
335   Bitboard bb = *b ^ (*b - 1);
336   uint32_t fold = int(bb) ^ int(bb >> 32);
337   *b &= (*b - 1);
338   return Square(BitTable[(fold * 0x783a9b23) >> 26]);
339 }
340
341 #endif
342
343 #else
344
345 static const int BitTable[64] = {
346   0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15,
347   46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39,
348   16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43,
349   51, 60, 42, 59, 58
350 };
351
352
353 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
354
355 Square first_1(Bitboard b) {
356   return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
357 }
358
359
360 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
361 /// nonzero bitboard.
362
363 Square pop_1st_bit(Bitboard *b) {
364   Bitboard bb = *b;
365   *b &= (*b - 1);
366   return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
367 }
368
369 #endif // defined(USE_FOLDED_BITSCAN)
370
371
372 namespace {
373
374   // All functions below are used to precompute various bitboards during
375   // program initialization.  Some of the functions may be difficult to
376   // understand, but they all seem to work correctly, and it should never
377   // be necessary to touch any of them.
378
379   void init_masks() {
380     SetMaskBB[SQ_NONE] = 0ULL;
381     ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE];
382     for(Square s = SQ_A1; s <= SQ_H8; s++) {
383       SetMaskBB[s] = (1ULL << s);
384       ClearMaskBB[s] = ~SetMaskBB[s];
385     }
386     for(Color c = WHITE; c <= BLACK; c++)
387       for(Square s = SQ_A1; s <= SQ_H8; s++) {
388         PassedPawnMask[c][s] =
389           in_front_bb(c, s) & this_and_neighboring_files_bb(s);
390         OutpostMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
391       }
392   }
393
394
395   void init_ray_bitboards() {
396     int d[8] = {1, -1, 16, -16, 17, -17, 15, -15};
397     for(int i = 0; i < 128; i = (i + 9) & ~8) {
398       for(int j = 0; j < 8; j++) {
399         RayBB[(i&7)|((i>>4)<<3)][j] = EmptyBoardBB;
400         for(int k = i + d[j]; (k & 0x88) == 0; k += d[j])
401           set_bit(&(RayBB[(i&7)|((i>>4)<<3)][j]), Square((k&7)|((k>>4)<<3)));
402       }
403     }
404   }
405
406
407   void init_attacks() {
408     int i, j, k, l;
409     int step[16][8] =  {
410       {0},
411       {7,9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
412       {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}, {0}, {0},
413       {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
414       {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}
415     };
416
417     for(i = 0; i < 64; i++) {
418       for(j = 0; j <= int(BK); j++) {
419         StepAttackBB[j][i] = EmptyBoardBB;
420         for(k = 0; k < 8 && step[j][k] != 0; k++) {
421           l = i + step[j][k];
422           if(l >= 0 && l < 64 && abs((i&7) - (l&7)) < 3)
423             StepAttackBB[j][i] |= (1ULL << l);
424         }
425       }
426     }
427   }
428
429
430   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
431                            int fmin=0, int fmax=7, int rmin=0, int rmax=7) {
432     Bitboard result = 0ULL;
433     int rk = sq / 8, fl = sq % 8, r, f, i;
434     for(i = 0; i < dirs; i++) {
435       int dx = deltas[i][0], dy = deltas[i][1];
436       for(f = fl+dx, r = rk+dy;
437           (dx==0 || (f>=fmin && f<=fmax)) && (dy==0 || (r>=rmin && r<=rmax));
438           f += dx, r += dy) {
439         result |= (1ULL << (f + r*8));
440         if(block & (1ULL << (f + r*8))) break;
441       }
442     }
443     return result;
444   }
445
446
447   void init_between_bitboards() {
448     SquareDelta step[8] = {
449       DELTA_E, DELTA_W, DELTA_N, DELTA_S, DELTA_NE, DELTA_SW, DELTA_NW, DELTA_SE
450     };
451     SignedDirection d;
452     for(Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
453       for(Square s2 = SQ_A1; s2 <= SQ_H8; s2++) {
454         BetweenBB[s1][s2] = EmptyBoardBB;
455         d = signed_direction_between_squares(s1, s2);
456         if(d != SIGNED_DIR_NONE)
457           for(Square s3 = s1 + step[d]; s3 != s2; s3 += step[d])
458             set_bit(&(BetweenBB[s1][s2]), s3);
459       }
460   }
461
462
463   Bitboard index_to_bitboard(int index, Bitboard mask) {
464     int i, j, bits = count_1s<false>(mask);
465     Bitboard result = 0ULL;
466     for(i = 0; i < bits; i++) {
467       j = pop_1st_bit(&mask);
468       if(index & (1 << i)) result |= (1ULL << j);
469     }
470     return result;
471   }
472
473
474   void init_sliding_attacks(Bitboard attacks[],
475                             int attackIndex[], Bitboard mask[],
476                             const int shift[2], const Bitboard mult[],
477                             int deltas[][2]) {
478     int i, j, k, index = 0;
479     Bitboard b;
480     for(i = 0; i < 64; i++) {
481       attackIndex[i] = index;
482       mask[i] = sliding_attacks(i, 0ULL, 4, deltas, 1, 6, 1, 6);
483
484 #if defined(USE_32BIT_ATTACKS)
485       j = (1 << (32 - shift[i]));
486 #else
487       j = (1 << (64 - shift[i]));
488 #endif
489
490       for(k = 0; k < j; k++) {
491
492 #if defined(USE_32BIT_ATTACKS)
493         b = index_to_bitboard(k, mask[i]);
494         attacks[index +
495                  (unsigned(int(b) * int(mult[i]) ^
496                            int(b >> 32) * int(mult[i] >> 32))
497                   >> shift[i])] =
498           sliding_attacks(i, b, 4, deltas);
499 #else
500         b = index_to_bitboard(k, mask[i]);
501         attacks[index + ((b * mult[i]) >> shift[i])] =
502           sliding_attacks(i, b, 4, deltas);
503 #endif
504       }
505       index += j;
506     }
507   }
508
509
510   void init_pseudo_attacks() {
511     Square s;
512     for(s = SQ_A1; s <= SQ_H8; s++) {
513       BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
514       RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB);
515       QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB);
516     }
517   }
518
519 #if defined(USE_COMPACT_ROOK_ATTACKS)
520   void init_file_and_rank_attacks() {
521     int i, j, k, l, m, s;
522     Bitboard b1, b2;
523     for(i = 0; i < 64; i++) {
524
525       for(m = 0; m <= 1; m++) {
526         b1 = 0ULL;
527         for(j = 0; j < 6; j++) if(i & (1<<j)) b1 |= (1ULL << ((j+1)*(1+m*7)));
528         for(j = 0; j < 8; j++) {
529           b2 = 0ULL;
530           for(k = 0, s = 1; k < 2; k++, s *= -1) {
531             for(l = j+s; l >= 0 && l <= 7; l += s) {
532               b2 |= (m? RankBB[l] : FileBB[l]);
533               if(b1 & (1ULL << (l*(1+m*7)))) break;
534             }
535           }
536           if(m) FileAttacks[j][(b1*0xd6e8802041d0c441ULL) >> 58] = b2;
537           else RankAttacks[j][i] = b2;
538         }
539       }
540     }
541   }
542 #endif // defined(USE_COMPACT_ROOK_ATTACKS)
543
544 }