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