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