git.sesse.net Git - stockfish/blob - 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
 240
 241 ////
 242 //// Local definitions
 243 ////
 244
 245 namespace {
 246
 247   void init_masks();
 248   void init_attacks();
 249   void init_between_bitboards();
 250   void init_pseudo_attacks();
 251   SquareDelta ray_direction(Square orig, Square dest);
 252   Bitboard index_to_bitboard(int index, Bitboard mask);
 253   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
 254                            int fmin, int fmax, int rmin, int rmax);
 255   void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
 256                             const int shift[], const Bitboard mult[], int deltas[][2]);
 257 }
 258
 259
 260 ////
 261 //// Functions
 262 ////
 263
 264 /// print_bitboard() prints a bitboard in an easily readable format to the
 265 /// standard output.  This is sometimes useful for debugging.
 266
 267 void print_bitboard(Bitboard b) {
 268
 269   for (Rank r = RANK_8; r >= RANK_1; r--)
 270   {
 271       std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
 272       for (File f = FILE_A; f <= FILE_H; f++)
 273           std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' ';
 274
 275       std::cout << "|" << std::endl;
 276   }
 277   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
 278 }
 279
 280
 281 /// init_bitboards() initializes various bitboard arrays.  It is called during
 282 /// program initialization.
 283
 284 void init_bitboards() {
 285
 286   int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
 287   int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
 288
 289   init_masks();
 290   init_attacks();
 291   init_between_bitboards();
 292   init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas);
 293   init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas);
 294   init_pseudo_attacks();
 295 }
 296
 297
 298 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
 299 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
 300 /// nonzero bitboard.
 301
 302 #if defined(IS_64BIT) && !defined(USE_BSFQ)
 303
 304 static CACHE_LINE_ALIGNMENT
 305 const int BitTable[64] = {
 306   0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15,
 307   46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39,
 308   16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43,
 309   51, 60, 42, 59, 58
 310 };
 311
 312 Square first_1(Bitboard b) {
 313   return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
 314 }
 315
 316 Square pop_1st_bit(Bitboard* b) {
 317   Bitboard bb = *b;
 318   *b &= (*b - 1);
 319   return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
 320 }
 321
 322 #elif !defined(USE_BSFQ)
 323
 324 static CACHE_LINE_ALIGNMENT
 325 const int BitTable[64] = {
 326   63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
 327   51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
 328   26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
 329   58, 20, 37, 17, 36, 8
 330 };
 331
 332 Square first_1(Bitboard b) {
 333
 334   b ^= (b - 1);
 335   uint32_t fold = int(b) ^ int(b >> 32);
 336   return Square(BitTable[(fold * 0x783a9b23) >> 26]);
 337 }
 338
 339 // Use type-punning
 340 union b_union {
 341
 342     Bitboard b;
 343     struct {
 344 #if defined (BIGENDIAN)
 345         uint32_t h;
 346         uint32_t l;
 347 #else
 348         uint32_t l;
 349         uint32_t h;
 350 #endif
 351     } dw;
 352 };
 353
 354 Square pop_1st_bit(Bitboard* bb) {
 355
 356    b_union u;
 357    Square ret;
 358
 359    u.b = *bb;
 360
 361    if (u.dw.l)
 362    {
 363        ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 26]);
 364        u.dw.l &= (u.dw.l - 1);
 365        *bb = u.b;
 366        return ret;
 367    }
 368    ret = Square(BitTable[((~(u.dw.h ^ (u.dw.h - 1))) * 0x783a9b23) >> 26]);
 369    u.dw.h &= (u.dw.h - 1);
 370    *bb = u.b;
 371    return ret;
 372 }
 373
 374 #endif
 375
 376
 377 namespace {
 378
 379   // All functions below are used to precompute various bitboards during
 380   // program initialization.  Some of the functions may be difficult to
 381   // understand, but they all seem to work correctly, and it should never
 382   // be necessary to touch any of them.
 383
 384   void init_masks() {
 385
 386     SetMaskBB[SQ_NONE] = 0ULL;
 387     ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE];
 388
 389     for (Square s = SQ_A1; s <= SQ_H8; s++)
 390     {
 391         SetMaskBB[s] = (1ULL << s);
 392         ClearMaskBB[s] = ~SetMaskBB[s];
 393     }
 394
 395     for (Color c = WHITE; c <= BLACK; c++)
 396         for (Square s = SQ_A1; s <= SQ_H8; s++)
 397         {
 398             SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
 399             PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
 400             AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
 401         }
 402
 403     for (Bitboard b = 0; b < 256; b++)
 404         BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
 405   }
 406
 407   void init_attacks() {
 408
 409     const 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 (int i = 0; i < 64; i++)
 418         for (int j = 0; j <= int(BK); j++)
 419         {
 420             StepAttackBB[j][i] = EmptyBoardBB;
 421             for (int k = 0; k < 8 && step[j][k] != 0; k++)
 422             {
 423                 int l = i + step[j][k];
 424                 if (l >= 0 && l < 64 && abs((i & 7) - (l & 7)) < 3)
 425                     StepAttackBB[j][i] |= (1ULL << l);
 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;
 434     int fl = sq % 8;
 435
 436     for (int i = 0; i < dirs; i++)
 437     {
 438         int dx = deltas[i][0];
 439         int dy = deltas[i][1];
 440         int f = fl + dx;
 441         int r = rk + dy;
 442
 443         while (   (dx == 0 || (f >= fmin && f <= fmax))
 444                && (dy == 0 || (r >= rmin && r <= rmax)))
 445         {
 446             result |= (1ULL << (f + r*8));
 447             if (block & (1ULL << (f + r*8)))
 448                 break;
 449
 450             f += dx;
 451             r += dy;
 452         }
 453     }
 454     return result;
 455   }
 456
 457   SquareDelta ray_direction(Square orig, Square dest) {
 458
 459     int df = file_distance(orig, dest);
 460     int dr = rank_distance(orig, dest);
 461
 462     if (orig != dest && (!df || !dr || df == dr))
 463         return SquareDelta(dest - orig) / Max(df, dr);
 464
 465     return DELTA_NONE;
 466   }
 467
 468   void init_between_bitboards() {
 469
 470     Square s1, s2, s3;
 471     SquareDelta d;
 472
 473     for (s1 = SQ_A1; s1 <= SQ_H8; s1++)
 474         for (s2 = SQ_A1; s2 <= SQ_H8; s2++)
 475         {
 476             BetweenBB[s1][s2] = EmptyBoardBB;
 477             d = ray_direction(s1, s2);
 478
 479             if (d != DELTA_NONE)
 480                 for (s3 = s1 + d; s3 != s2; s3 += d)
 481                     set_bit(&(BetweenBB[s1][s2]), s3);
 482       }
 483   }
 484
 485   Bitboard index_to_bitboard(int index, Bitboard mask) {
 486
 487     Bitboard result = 0ULL;
 488     int bits = count_1s<CNT32>(mask);
 489
 490     for (int i = 0; i < bits; i++)
 491     {
 492         int j = pop_1st_bit(&mask);
 493         if (index & (1 << i))
 494             result |= (1ULL << j);
 495     }
 496     return result;
 497   }
 498
 499   void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
 500                             const int shift[], const Bitboard mult[], int deltas[][2]) {
 501
 502     for (int i = 0, index = 0; i < 64; i++)
 503     {
 504         attackIndex[i] = index;
 505         mask[i] = sliding_attacks(i, 0, 4, deltas, 1, 6, 1, 6);
 506
 507 #if defined(IS_64BIT)
 508         int j = (1 << (64 - shift[i]));
 509 #else
 510         int j = (1 << (32 - shift[i]));
 511 #endif
 512
 513         for (int k = 0; k < j; k++)
 514         {
 515 #if defined(IS_64BIT)
 516             Bitboard b = index_to_bitboard(k, mask[i]);
 517             attacks[index + ((b * mult[i]) >> shift[i])] = sliding_attacks(i, b, 4, deltas);
 518 #else
 519             Bitboard b = index_to_bitboard(k, mask[i]);
 520             unsigned v = int(b) * int(mult[i]) ^ int(b >> 32) * int(mult[i] >> 32);
 521             attacks[index + (v >> shift[i])] = sliding_attacks(i, b, 4, deltas);
 522 #endif
 523         }
 524         index += j;
 525     }
 526   }
 527
 528   void init_pseudo_attacks() {
 529
 530     for (Square s = SQ_A1; s <= SQ_H8; s++)
 531     {
 532         BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
 533         RookPseudoAttacks[s]   = rook_attacks_bb(s, EmptyBoardBB);
 534         QueenPseudoAttacks[s]  = queen_attacks_bb(s, EmptyBoardBB);
 535     }
 536   }
 537
 538 }