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