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 static const Bitboard DarkSquaresBB  = 0xAA55AA55AA55AA55ULL;
 166
 167 const Bitboard SquaresByColorBB[2] = { DarkSquaresBB, ~DarkSquaresBB };
 168
 169 const Bitboard FileBB[8] = {
 170   FileABB, FileBBB, FileCBB, FileDBB, FileEBB, FileFBB, FileGBB, FileHBB
 171 };
 172
 173 const Bitboard NeighboringFilesBB[8] = {
 174   FileBBB, FileABB|FileCBB, FileBBB|FileDBB, FileCBB|FileEBB,
 175   FileDBB|FileFBB, FileEBB|FileGBB, FileFBB|FileHBB, FileGBB
 176 };
 177
 178 const Bitboard ThisAndNeighboringFilesBB[8] = {
 179   FileABB|FileBBB, FileABB|FileBBB|FileCBB,
 180   FileBBB|FileCBB|FileDBB, FileCBB|FileDBB|FileEBB,
 181   FileDBB|FileEBB|FileFBB, FileEBB|FileFBB|FileGBB,
 182   FileFBB|FileGBB|FileHBB, FileGBB|FileHBB
 183 };
 184
 185 const Bitboard RankBB[8] = {
 186   Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB
 187 };
 188
 189 const Bitboard InFrontBB[2][8] = {
 190   { Rank2BB | Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 191     Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 192     Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 193     Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 194     Rank6BB | Rank7BB | Rank8BB,
 195     Rank7BB | Rank8BB,
 196     Rank8BB,
 197     EmptyBoardBB
 198   },
 199   { EmptyBoardBB,
 200     Rank1BB,
 201     Rank2BB | Rank1BB,
 202     Rank3BB | Rank2BB | Rank1BB,
 203     Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 204     Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 205     Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 206     Rank7BB | Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB
 207   }
 208 };
 209
 210 // Global bitboards definitions with static storage duration are
 211 // automatically set to zero before enter main().
 212 Bitboard RMask[64];
 213 int RAttackIndex[64];
 214 Bitboard RAttacks[0x19000];
 215
 216 Bitboard BMask[64];
 217 int BAttackIndex[64];
 218 Bitboard BAttacks[0x1480];
 219
 220 Bitboard SetMaskBB[65];
 221 Bitboard ClearMaskBB[65];
 222
 223 Bitboard NonSlidingAttacksBB[16][64];
 224 Bitboard BetweenBB[64][64];
 225
 226 Bitboard SquaresInFrontMask[2][64];
 227 Bitboard PassedPawnMask[2][64];
 228 Bitboard AttackSpanMask[2][64];
 229
 230 Bitboard BishopPseudoAttacks[64];
 231 Bitboard RookPseudoAttacks[64];
 232 Bitboard QueenPseudoAttacks[64];
 233
 234 uint8_t BitCount8Bit[256];
 235
 236
 237 namespace {
 238
 239   void init_masks();
 240   void init_non_sliding_attacks();
 241   void init_pseudo_attacks();
 242   void init_between_bitboards();
 243   Bitboard index_to_bitboard(int index, Bitboard mask);
 244   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
 245                            int fmin, int fmax, int rmin, int rmax);
 246   void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
 247                             const int shift[], const Bitboard mult[], int deltas[][2]);
 248 }
 249
 250
 251 /// print_bitboard() prints a bitboard in an easily readable format to the
 252 /// standard output. This is sometimes useful for debugging.
 253
 254 void print_bitboard(Bitboard b) {
 255
 256   for (Rank r = RANK_8; r >= RANK_1; r--)
 257   {
 258       std::cout << "+---+---+---+---+---+---+---+---+" << '\n';
 259       for (File f = FILE_A; f <= FILE_H; f++)
 260           std::cout << "| " << (bit_is_set(b, make_square(f, r))? 'X' : ' ') << ' ';
 261
 262       std::cout << "|\n";
 263   }
 264   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
 265 }
 266
 267
 268 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
 269 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
 270 /// nonzero bitboard.
 271
 272 #if defined(IS_64BIT) && !defined(USE_BSFQ)
 273
 274 static CACHE_LINE_ALIGNMENT
 275 const int BitTable[64] = {
 276   0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15,
 277   46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39,
 278   16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43,
 279   51, 60, 42, 59, 58
 280 };
 281
 282 Square first_1(Bitboard b) {
 283   return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
 284 }
 285
 286 Square pop_1st_bit(Bitboard* b) {
 287   Bitboard bb = *b;
 288   *b &= (*b - 1);
 289   return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
 290 }
 291
 292 #elif !defined(USE_BSFQ)
 293
 294 static CACHE_LINE_ALIGNMENT
 295 const int BitTable[64] = {
 296   63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
 297   51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
 298   26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
 299   58, 20, 37, 17, 36, 8
 300 };
 301
 302 Square first_1(Bitboard b) {
 303
 304   b ^= (b - 1);
 305   uint32_t fold = int(b) ^ int(b >> 32);
 306   return Square(BitTable[(fold * 0x783a9b23) >> 26]);
 307 }
 308
 309 // Use type-punning
 310 union b_union {
 311
 312     Bitboard b;
 313     struct {
 314 #if defined (BIGENDIAN)
 315         uint32_t h;
 316         uint32_t l;
 317 #else
 318         uint32_t l;
 319         uint32_t h;
 320 #endif
 321     } dw;
 322 };
 323
 324 Square pop_1st_bit(Bitboard* bb) {
 325
 326    b_union u;
 327    Square ret;
 328
 329    u.b = *bb;
 330
 331    if (u.dw.l)
 332    {
 333        ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 26]);
 334        u.dw.l &= (u.dw.l - 1);
 335        *bb = u.b;
 336        return ret;
 337    }
 338    ret = Square(BitTable[((~(u.dw.h ^ (u.dw.h - 1))) * 0x783a9b23) >> 26]);
 339    u.dw.h &= (u.dw.h - 1);
 340    *bb = u.b;
 341    return ret;
 342 }
 343
 344 #endif
 345
 346
 347 /// init_bitboards() initializes various bitboard arrays. It is called during
 348 /// program initialization.
 349
 350 void init_bitboards() {
 351
 352   int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
 353   int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
 354
 355   init_masks();
 356   init_non_sliding_attacks();
 357   init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas);
 358   init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas);
 359   init_pseudo_attacks();
 360   init_between_bitboards();
 361 }
 362
 363 namespace {
 364
 365   // All functions below are used to precompute various bitboards during
 366   // program initialization.  Some of the functions may be difficult to
 367   // understand, but they all seem to work correctly, and it should never
 368   // be necessary to touch any of them.
 369
 370   void init_masks() {
 371
 372     SetMaskBB[SQ_NONE] = EmptyBoardBB;
 373     ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE];
 374
 375     for (Square s = SQ_A1; s <= SQ_H8; s++)
 376     {
 377         SetMaskBB[s] = (1ULL << s);
 378         ClearMaskBB[s] = ~SetMaskBB[s];
 379     }
 380
 381     for (Color c = WHITE; c <= BLACK; c++)
 382         for (Square s = SQ_A1; s <= SQ_H8; s++)
 383         {
 384             SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
 385             PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
 386             AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
 387         }
 388
 389     for (Bitboard b = 0; b < 256; b++)
 390         BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
 391   }
 392
 393   void init_non_sliding_attacks() {
 394
 395     const int step[][9] =  {
 396       {0},
 397       {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0},
 398       {9,7,-7,-9,8,1,-1,-8,0}, {0}, {0},
 399       {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0},
 400       {9,7,-7,-9,8,1,-1,-8,0}
 401     };
 402
 403     for (Square s = SQ_A1; s <= SQ_H8; s++)
 404         for (Piece pc = WP; pc <= BK; pc++)
 405             for (int k = 0; step[pc][k] != 0; k++)
 406             {
 407                 Square to = s + Square(step[pc][k]);
 408
 409                 if (square_is_ok(to) && square_distance(s, to) < 3)
 410                     set_bit(&NonSlidingAttacksBB[pc][s], to);
 411            }
 412   }
 413
 414   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
 415                            int fmin=0, int fmax=7, int rmin=0, int rmax=7) {
 416     Bitboard result = 0;
 417     int rk = sq / 8;
 418     int fl = sq % 8;
 419
 420     for (int i = 0; i < dirs; i++)
 421     {
 422         int dx = deltas[i][0];
 423         int dy = deltas[i][1];
 424         int f = fl + dx;
 425         int r = rk + dy;
 426
 427         while (   (dx == 0 || (f >= fmin && f <= fmax))
 428                && (dy == 0 || (r >= rmin && r <= rmax)))
 429         {
 430             result |= (1ULL << (f + r*8));
 431             if (block & (1ULL << (f + r*8)))
 432                 break;
 433
 434             f += dx;
 435             r += dy;
 436         }
 437     }
 438     return result;
 439   }
 440
 441   Bitboard index_to_bitboard(int index, Bitboard mask) {
 442
 443     Bitboard result = EmptyBoardBB;
 444     int sq, cnt = 0;
 445
 446     while (mask)
 447     {
 448         sq = pop_1st_bit(&mask);
 449
 450         if (index & (1 << cnt++))
 451             result |= (1ULL << sq);
 452     }
 453     return result;
 454   }
 455
 456   void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
 457                             const int shift[], const Bitboard mult[], int deltas[][2]) {
 458
 459     for (int i = 0, index = 0; i < 64; i++)
 460     {
 461         attackIndex[i] = index;
 462         mask[i] = sliding_attacks(i, 0, 4, deltas, 1, 6, 1, 6);
 463
 464 #if defined(IS_64BIT)
 465         int j = (1 << (64 - shift[i]));
 466 #else
 467         int j = (1 << (32 - shift[i]));
 468 #endif
 469
 470         for (int k = 0; k < j; k++)
 471         {
 472 #if defined(IS_64BIT)
 473             Bitboard b = index_to_bitboard(k, mask[i]);
 474             attacks[index + ((b * mult[i]) >> shift[i])] = sliding_attacks(i, b, 4, deltas);
 475 #else
 476             Bitboard b = index_to_bitboard(k, mask[i]);
 477             unsigned v = int(b) * int(mult[i]) ^ int(b >> 32) * int(mult[i] >> 32);
 478             attacks[index + (v >> shift[i])] = sliding_attacks(i, b, 4, deltas);
 479 #endif
 480         }
 481         index += j;
 482     }
 483   }
 484
 485   void init_pseudo_attacks() {
 486
 487     for (Square s = SQ_A1; s <= SQ_H8; s++)
 488     {
 489         BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
 490         RookPseudoAttacks[s]   = rook_attacks_bb(s, EmptyBoardBB);
 491         QueenPseudoAttacks[s]  = queen_attacks_bb(s, EmptyBoardBB);
 492     }
 493   }
 494
 495   void init_between_bitboards() {
 496
 497     Square s1, s2, s3;
 498     SquareDelta d;
 499     int f, r;
 500
 501     for (s1 = SQ_A1; s1 <= SQ_H8; s1++)
 502         for (s2 = SQ_A1; s2 <= SQ_H8; s2++)
 503             if (bit_is_set(QueenPseudoAttacks[s1], s2))
 504             {
 505                 f = file_distance(s1, s2);
 506                 r = rank_distance(s1, s2);
 507
 508                 d = SquareDelta(s2 - s1) / Max(f, r);
 509
 510                 for (s3 = s1 + d; s3 != s2; s3 += d)
 511                     set_bit(&(BetweenBB[s1][s2]), s3);
 512             }
 513   }
 514
 515 }