git.sesse.net Git - stockfish/blob - src/bitboard.cpp

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