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 #include "direction.h"
  30
  31
  32 #if defined(IS_64BIT)
  33
  34 const uint64_t BMult[64] = {
  35   0x440049104032280ULL, 0x1021023c82008040ULL, 0x404040082000048ULL,
  36   0x48c4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL,
  37   0x181011002e06040ULL, 0x9101004104200e00ULL, 0x1240848848310401ULL,
  38   0x2000142828050024ULL, 0x1004024d5000ULL, 0x102044400800200ULL,
  39   0x8108108820112000ULL, 0xa880818210c00046ULL, 0x4008008801082000ULL,
  40   0x60882404049400ULL, 0x104402004240810ULL, 0xa002084250200ULL,
  41   0x100b0880801100ULL, 0x4080201220101ULL, 0x44008080a00000ULL,
  42   0x202200842000ULL, 0x5006004882d00808ULL, 0x200045080802ULL,
  43   0x86100020200601ULL, 0xa802080a20112c02ULL, 0x80411218080900ULL,
  44   0x200a0880080a0ULL, 0x9a01010000104000ULL, 0x28008003100080ULL,
  45   0x211021004480417ULL, 0x401004188220806ULL, 0x825051400c2006ULL,
  46   0x140c0210943000ULL, 0x242800300080ULL, 0xc2208120080200ULL,
  47   0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL,
  48   0x822081014405ULL, 0x800c049e40400804ULL, 0x4a0404028a000820ULL,
  49   0x22060201041200ULL, 0x360904200840801ULL, 0x881a08208800400ULL,
  50   0x60202c00400420ULL, 0x1204440086061400ULL, 0x8184042804040ULL,
  51   0x64040315300400ULL, 0xc01008801090a00ULL, 0x808010401140c00ULL,
  52   0x4004830c2020040ULL, 0x80005002020054ULL, 0x40000c14481a0490ULL,
  53   0x10500101042048ULL, 0x1010100200424000ULL, 0x640901901040ULL,
  54   0xa0201014840ULL, 0x840082aa011002ULL, 0x10010840084240aULL,
  55   0x420400810420608ULL, 0x8d40230408102100ULL, 0x4a00200612222409ULL,
  56   0xa08520292120600ULL
  57 };
  58
  59 const uint64_t RMult[64] = {
  60   0xa8002c000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL,
  61   0x380180080141000ULL, 0x1a00060008211044ULL, 0x410001000a0c0008ULL,
  62   0x9500060004008100ULL, 0x100024284a20700ULL, 0x802140008000ULL,
  63   0x80c01002a00840ULL, 0x402004282011020ULL, 0x9862000820420050ULL,
  64   0x1001448011100ULL, 0x6432800200800400ULL, 0x40100010002000cULL,
  65   0x2800d0010c080ULL, 0x90c0008000803042ULL, 0x4010004000200041ULL,
  66   0x3010010200040ULL, 0xa40828028001000ULL, 0x123010008000430ULL,
  67   0x24008004020080ULL, 0x60040001104802ULL, 0x582200028400d1ULL,
  68   0x4000802080044000ULL, 0x408208200420308ULL, 0x610038080102000ULL,
  69   0x3601000900100020ULL, 0x80080040180ULL, 0xc2020080040080ULL,
  70   0x80084400100102ULL, 0x4022408200014401ULL, 0x40052040800082ULL,
  71   0xb08200280804000ULL, 0x8a80a008801000ULL, 0x4000480080801000ULL,
  72   0x911808800801401ULL, 0x822a003002001894ULL, 0x401068091400108aULL,
  73   0x4a10a00004cULL, 0x2000800640008024ULL, 0x1486408102020020ULL,
  74   0x100a000d50041ULL, 0x810050020b0020ULL, 0x204000800808004ULL,
  75   0x20048100a000cULL, 0x112000831020004ULL, 0x9000040810002ULL,
  76   0x440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL,
  77   0x4b824a2010010100ULL, 0x4080801810c0080ULL, 0x400802a0080ULL,
  78   0x8224080110026400ULL, 0x40002c4104088200ULL, 0x1002100104a0282ULL,
  79   0x1208400811048021ULL, 0x3201014a40d02001ULL, 0x5100019200501ULL,
  80   0x101000208001005ULL, 0x2008450080702ULL, 0x1002080301d00cULL,
  81   0x410201ce5c030092ULL
  82 };
  83
  84 const int BShift[64] = {
  85   58, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 59, 59,
  86   59, 59, 57, 57, 57, 57, 59, 59, 59, 59, 57, 55, 55, 57, 59, 59,
  87   59, 59, 57, 55, 55, 57, 59, 59, 59, 59, 57, 57, 57, 57, 59, 59,
  88   59, 59, 59, 59, 59, 59, 59, 59, 58, 59, 59, 59, 59, 59, 59, 58
  89 };
  90
  91 const int RShift[64] = {
  92   52, 53, 53, 53, 53, 53, 53, 52, 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, 53, 54, 54, 54, 54, 54, 54, 53,
  95   53, 54, 54, 54, 54, 54, 54, 53, 52, 53, 53, 53, 53, 53, 53, 52
  96 };
  97
  98 #else // if !defined(IS_64BIT)
  99
 100 const uint64_t BMult[64] = {
 101   0x54142844c6a22981ULL, 0x710358a6ea25c19eULL, 0x704f746d63a4a8dcULL,
 102   0xbfed1a0b80f838c5ULL, 0x90561d5631e62110ULL, 0x2804260376e60944ULL,
 103   0x84a656409aa76871ULL, 0xf0267f64c28b6197ULL, 0x70764ebb762f0585ULL,
 104   0x92aa09e0cfe161deULL, 0x41ee1f6bb266f60eULL, 0xddcbf04f6039c444ULL,
 105   0x5a3fab7bac0d988aULL, 0xd3727877fa4eaa03ULL, 0xd988402d868ddaaeULL,
 106   0x812b291afa075c7cULL, 0x94faf987b685a932ULL, 0x3ed867d8470d08dbULL,
 107   0x92517660b8901de8ULL, 0x2d97e43e058814b4ULL, 0x880a10c220b25582ULL,
 108   0xc7c6520d1f1a0477ULL, 0xdbfc7fbcd7656aa6ULL, 0x78b1b9bfb1a2b84fULL,
 109   0x2f20037f112a0bc1ULL, 0x657171ea2269a916ULL, 0xc08302b07142210eULL,
 110   0x880a4403064080bULL, 0x3602420842208c00ULL, 0x852800dc7e0b6602ULL,
 111   0x595a3fbbaa0f03b2ULL, 0x9f01411558159d5eULL, 0x2b4a4a5f88b394f2ULL,
 112   0x4afcbffc292dd03aULL, 0x4a4094a3b3f10522ULL, 0xb06f00b491f30048ULL,
 113   0xd5b3820280d77004ULL, 0x8b2e01e7c8e57a75ULL, 0x2d342794e886c2e6ULL,
 114   0xc302c410cde21461ULL, 0x111f426f1379c274ULL, 0xe0569220abb31588ULL,
 115   0x5026d3064d453324ULL, 0xe2076040c343cd8aULL, 0x93efd1e1738021eeULL,
 116   0xb680804bed143132ULL, 0x44e361b21986944cULL, 0x44c60170ef5c598cULL,
 117   0xf4da475c195c9c94ULL, 0xa3afbb5f72060b1dULL, 0xbc75f410e41c4ffcULL,
 118   0xb51c099390520922ULL, 0x902c011f8f8ec368ULL, 0x950b56b3d6f5490aULL,
 119   0x3909e0635bf202d0ULL, 0x5744f90206ec10ccULL, 0xdc59fd76317abbc1ULL,
 120   0x881c7c67fcbfc4f6ULL, 0x47ca41e7e440d423ULL, 0xeb0c88112048d004ULL,
 121   0x51c60e04359aef1aULL, 0x1aa1fe0e957a5554ULL, 0xdd9448db4f5e3104ULL,
 122   0xdc01f6dca4bebbdcULL,
 123 };
 124
 125 const uint64_t RMult[64] = {
 126   0xd7445cdec88002c0ULL, 0xd0a505c1f2001722ULL, 0xe065d1c896002182ULL,
 127   0x9a8c41e75a000892ULL, 0x8900b10c89002aa8ULL, 0x9b28d1c1d60005a2ULL,
 128   0x15d6c88de002d9aULL, 0xb1dbfc802e8016a9ULL, 0x149a1042d9d60029ULL,
 129   0xb9c08050599e002fULL, 0x132208c3af300403ULL, 0xc1000ce2e9c50070ULL,
 130   0x9d9aa13c99020012ULL, 0xb6b078daf71e0046ULL, 0x9d880182fb6e002eULL,
 131   0x52889f467e850037ULL, 0xda6dc008d19a8480ULL, 0x468286034f902420ULL,
 132   0x7140ac09dc54c020ULL, 0xd76ffffa39548808ULL, 0xea901c4141500808ULL,
 133   0xc91004093f953a02ULL, 0x2882afa8f6bb402ULL, 0xaebe335692442c01ULL,
 134   0xe904a22079fb91eULL, 0x13a514851055f606ULL, 0x76c782018c8fe632ULL,
 135   0x1dc012a9d116da06ULL, 0x3c9e0037264fffa6ULL, 0x2036002853c6e4a2ULL,
 136   0xe3fe08500afb47d4ULL, 0xf38af25c86b025c2ULL, 0xc0800e2182cf9a40ULL,
 137   0x72002480d1f60673ULL, 0x2500200bae6e9b53ULL, 0xc60018c1eefca252ULL,
 138   0x600590473e3608aULL, 0x46002c4ab3fe51b2ULL, 0xa200011486bcc8d2ULL,
 139   0xb680078095784c63ULL, 0x2742002639bf11aeULL, 0xc7d60021a5bdb142ULL,
 140   0xc8c04016bb83d820ULL, 0xbd520028123b4842ULL, 0x9d1600344ac2a832ULL,
 141   0x6a808005631c8a05ULL, 0x604600a148d5389aULL, 0xe2e40103d40dea65ULL,
 142   0x945b5a0087c62a81ULL, 0x12dc200cd82d28eULL, 0x2431c600b5f9ef76ULL,
 143   0xfb142a006a9b314aULL, 0x6870e00a1c97d62ULL, 0x2a9db2004a2689a2ULL,
 144   0xd3594600caf5d1a2ULL, 0xee0e4900439344a7ULL, 0x89c4d266ca25007aULL,
 145   0x3e0013a2743f97e3ULL, 0x180e31a0431378aULL, 0x3a9e465a4d42a512ULL,
 146   0x98d0a11a0c0d9cc2ULL, 0x8e711c1aba19b01eULL, 0x8dcdc836dd201142ULL,
 147   0x5ac08a4735370479ULL,
 148 };
 149
 150 const int BShift[64] = {
 151   26, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 27, 27,
 152   27, 27, 25, 25, 25, 25, 27, 27, 27, 27, 25, 23, 23, 25, 27, 27,
 153   27, 27, 25, 23, 23, 25, 27, 27, 27, 27, 25, 25, 25, 25, 27, 27,
 154   27, 27, 27, 27, 27, 27, 27, 27, 26, 27, 27, 27, 27, 27, 27, 26
 155 };
 156
 157 const int RShift[64] = {
 158   20, 21, 21, 21, 21, 21, 21, 20, 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, 21, 22, 22, 22, 22, 22, 22, 21,
 161   21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20
 162 };
 163
 164 #endif // defined(IS_64BIT)
 165
 166 const Bitboard SquaresByColorBB[2] = { BlackSquaresBB, WhiteSquaresBB };
 167
 168 const Bitboard FileBB[8] = {
 169   FileABB, FileBBB, FileCBB, FileDBB, FileEBB, FileFBB, FileGBB, FileHBB
 170 };
 171
 172 const Bitboard NeighboringFilesBB[8] = {
 173   FileBBB, FileABB|FileCBB, FileBBB|FileDBB, FileCBB|FileEBB,
 174   FileDBB|FileFBB, FileEBB|FileGBB, FileFBB|FileHBB, FileGBB
 175 };
 176
 177 const Bitboard ThisAndNeighboringFilesBB[8] = {
 178   FileABB|FileBBB, FileABB|FileBBB|FileCBB,
 179   FileBBB|FileCBB|FileDBB, FileCBB|FileDBB|FileEBB,
 180   FileDBB|FileEBB|FileFBB, FileEBB|FileFBB|FileGBB,
 181   FileFBB|FileGBB|FileHBB, FileGBB|FileHBB
 182 };
 183
 184 const Bitboard RankBB[8] = {
 185   Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB
 186 };
 187
 188 const Bitboard RelativeRankBB[2][8] = {
 189   { Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB },
 190   { Rank8BB, Rank7BB, Rank6BB, Rank5BB, Rank4BB, Rank3BB, Rank2BB, Rank1BB }
 191 };
 192
 193 const Bitboard InFrontBB[2][8] = {
 194   { Rank2BB | Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 195     Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 196     Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 197     Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 198     Rank6BB | Rank7BB | Rank8BB,
 199     Rank7BB | Rank8BB,
 200     Rank8BB,
 201     EmptyBoardBB
 202   },
 203   { EmptyBoardBB,
 204     Rank1BB,
 205     Rank2BB | Rank1BB,
 206     Rank3BB | Rank2BB | Rank1BB,
 207     Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 208     Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 209     Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 210     Rank7BB | Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB
 211   }
 212 };
 213
 214 Bitboard RMask[64];
 215 int RAttackIndex[64];
 216 Bitboard RAttacks[0x19000];
 217
 218 Bitboard BMask[64];
 219 int BAttackIndex[64];
 220 Bitboard BAttacks[0x1480];
 221
 222 Bitboard SetMaskBB[65];
 223 Bitboard ClearMaskBB[65];
 224
 225 Bitboard StepAttackBB[16][64];
 226 Bitboard RayBB[64][8];
 227 Bitboard BetweenBB[64][64];
 228
 229 Bitboard SquaresInFrontMask[2][64];
 230 Bitboard PassedPawnMask[2][64];
 231 Bitboard AttackSpanMask[2][64];
 232
 233 Bitboard BishopPseudoAttacks[64];
 234 Bitboard RookPseudoAttacks[64];
 235 Bitboard QueenPseudoAttacks[64];
 236
 237 uint8_t BitCount8Bit[256];
 238
 239
 240 ////
 241 //// Local definitions
 242 ////
 243
 244 namespace {
 245
 246   void init_masks();
 247   void init_ray_bitboards();
 248   void init_attacks();
 249   void init_between_bitboards();
 250   void init_pseudo_attacks();
 251   Bitboard index_to_bitboard(int index, Bitboard mask);
 252   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
 253                            int fmin, int fmax, int rmin, int rmax);
 254   void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
 255                             const int shift[], const Bitboard mult[], int deltas[][2]);
 256 }
 257
 258
 259 ////
 260 //// Functions
 261 ////
 262
 263 /// print_bitboard() prints a bitboard in an easily readable format to the
 264 /// standard output.  This is sometimes useful for debugging.
 265
 266 void print_bitboard(Bitboard b) {
 267
 268   for (Rank r = RANK_8; r >= RANK_1; r--)
 269   {
 270       std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
 271       for (File f = FILE_A; f <= FILE_H; f++)
 272           std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' ';
 273
 274       std::cout << "|" << std::endl;
 275   }
 276   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
 277 }
 278
 279
 280 /// init_bitboards() initializes various bitboard arrays.  It is called during
 281 /// program initialization.
 282
 283 void init_bitboards() {
 284
 285   int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
 286   int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
 287
 288   init_masks();
 289   init_ray_bitboards();
 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 = 0ULL; b < 256ULL; b++)
 404         BitCount8Bit[b] = (uint8_t)count_1s(b);
 405   }
 406
 407   int remove_bit_8(int i) { return ((i & ~15) >> 1) | (i & 7); }
 408
 409   void init_ray_bitboards() {
 410
 411     int d[8] = {1, -1, 16, -16, 17, -17, 15, -15};
 412
 413     for (int i = 0; i < 128; i = (i + 9) & ~8)
 414         for (int j = 0; j < 8; j++)
 415         {
 416             RayBB[remove_bit_8(i)][j] = EmptyBoardBB;
 417             for (int k = i + d[j]; (k & 0x88) == 0; k += d[j])
 418                 set_bit(&(RayBB[remove_bit_8(i)][j]), Square(remove_bit_8(k)));
 419         }
 420   }
 421
 422   void init_attacks() {
 423
 424     const int step[16][8] =  {
 425       {0},
 426       {7,9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
 427       {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}, {0}, {0},
 428       {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
 429       {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}
 430     };
 431
 432     for (int i = 0; i < 64; i++)
 433         for (int j = 0; j <= int(BK); j++)
 434         {
 435             StepAttackBB[j][i] = EmptyBoardBB;
 436             for (int k = 0; k < 8 && step[j][k] != 0; k++)
 437             {
 438                 int l = i + step[j][k];
 439                 if (l >= 0 && l < 64 && abs((i & 7) - (l & 7)) < 3)
 440                     StepAttackBB[j][i] |= (1ULL << l);
 441            }
 442         }
 443   }
 444
 445   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
 446                            int fmin=0, int fmax=7, int rmin=0, int rmax=7) {
 447     Bitboard result = 0ULL;
 448     int rk = sq / 8;
 449     int fl = sq % 8;
 450
 451     for (int i = 0; i < dirs; i++)
 452     {
 453         int dx = deltas[i][0];
 454         int dy = deltas[i][1];
 455         int f = fl + dx;
 456         int r = rk + dy;
 457
 458         while (   (dx == 0 || (f >= fmin && f <= fmax))
 459                && (dy == 0 || (r >= rmin && r <= rmax)))
 460         {
 461             result |= (1ULL << (f + r*8));
 462             if (block & (1ULL << (f + r*8)))
 463                 break;
 464
 465             f += dx;
 466             r += dy;
 467         }
 468     }
 469     return result;
 470   }
 471
 472   void init_between_bitboards() {
 473
 474     const SquareDelta step[8] = { DELTA_E, DELTA_W, DELTA_N, DELTA_S,
 475                                   DELTA_NE, DELTA_SW, DELTA_NW, DELTA_SE };
 476
 477     for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
 478         for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
 479         {
 480             BetweenBB[s1][s2] = EmptyBoardBB;
 481             SignedDirection d = signed_direction_between_squares(s1, s2);
 482
 483             if (d != SIGNED_DIR_NONE)
 484             {
 485                 for (Square s3 = s1 + step[d]; s3 != s2; s3 += step[d])
 486                     set_bit(&(BetweenBB[s1][s2]), s3);
 487             }
 488       }
 489   }
 490
 491   Bitboard index_to_bitboard(int index, Bitboard mask) {
 492
 493     Bitboard result = 0ULL;
 494     int bits = count_1s(mask);
 495
 496     for (int i = 0; i < bits; i++)
 497     {
 498         int j = pop_1st_bit(&mask);
 499         if (index & (1 << i))
 500             result |= (1ULL << j);
 501     }
 502     return result;
 503   }
 504
 505   void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
 506                             const int shift[], const Bitboard mult[], int deltas[][2]) {
 507
 508     for (int i = 0, index = 0; i < 64; i++)
 509     {
 510         attackIndex[i] = index;
 511         mask[i] = sliding_attacks(i, 0ULL, 4, deltas, 1, 6, 1, 6);
 512
 513 #if defined(IS_64BIT)
 514         int j = (1 << (64 - shift[i]));
 515 #else
 516         int j = (1 << (32 - shift[i]));
 517 #endif
 518
 519         for (int k = 0; k < j; k++)
 520         {
 521 #if defined(IS_64BIT)
 522             Bitboard b = index_to_bitboard(k, mask[i]);
 523             attacks[index + ((b * mult[i]) >> shift[i])] = sliding_attacks(i, b, 4, deltas);
 524 #else
 525             Bitboard b = index_to_bitboard(k, mask[i]);
 526             unsigned v = int(b) * int(mult[i]) ^ int(b >> 32) * int(mult[i] >> 32);
 527             attacks[index + (v >> shift[i])] = sliding_attacks(i, b, 4, deltas);
 528 #endif
 529         }
 530         index += j;
 531     }
 532   }
 533
 534   void init_pseudo_attacks() {
 535
 536     for (Square s = SQ_A1; s <= SQ_H8; s++)
 537     {
 538         BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
 539         RookPseudoAttacks[s]   = rook_attacks_bb(s, EmptyBoardBB);
 540         QueenPseudoAttacks[s]  = queen_attacks_bb(s, EmptyBoardBB);
 541     }
 542   }
 543
 544 }