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