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