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