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