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 #if defined(USE_32BIT_ATTACKS)
 343
 344 Square pop_1st_bit(Bitboard *bb) {
 345
 346   uint32_t  t = uint32_t(*bb);
 347   uint32_t* p = t ? (uint32_t*)bb : (uint32_t*)bb + 1; // Little endian only?
 348   uint32_t  b = t ? t : *p;
 349
 350   *p = b & (b -1);
 351
 352   if (t)
 353      b ^= (b - 1);
 354   else
 355      b = ~(b ^ (b - 1));
 356
 357   return Square(BitTable[(b * 0x783a9b23) >> 26]);
 358 }
 359
 360 #else
 361
 362 Square pop_1st_bit(Bitboard *b) {
 363   Bitboard bb = *b ^ (*b - 1);
 364   uint32_t fold = int(bb) ^ int(bb >> 32);
 365   *b &= (*b - 1);
 366   return Square(BitTable[(fold * 0x783a9b23) >> 26]);
 367 }
 368
 369 #endif
 370
 371 #else
 372
 373 static const int BitTable[64] = {
 374   0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15,
 375   46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39,
 376   16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43,
 377   51, 60, 42, 59, 58
 378 };
 379
 380
 381 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
 382
 383 Square first_1(Bitboard b) {
 384   return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
 385 }
 386
 387
 388 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
 389 /// nonzero bitboard.
 390
 391 Square pop_1st_bit(Bitboard *b) {
 392   Bitboard bb = *b;
 393   *b &= (*b - 1);
 394   return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
 395 }
 396
 397 #endif // defined(USE_FOLDED_BITSCAN)
 398
 399
 400 namespace {
 401
 402   // All functions below are used to precompute various bitboards during
 403   // program initialization.  Some of the functions may be difficult to
 404   // understand, but they all seem to work correctly, and it should never
 405   // be necessary to touch any of them.
 406
 407   void init_masks() {
 408     for(Square s = SQ_A1; s <= SQ_H8; s++) {
 409       SetMaskBB[s] = (1ULL << s);
 410       ClearMaskBB[s] = ~SetMaskBB[s];
 411     }
 412     for(Color c = WHITE; c <= BLACK; c++)
 413       for(Square s = SQ_A1; s <= SQ_H8; s++) {
 414         PassedPawnMask[c][s] =
 415           in_front_bb(c, s) & this_and_neighboring_files_bb(s);
 416         OutpostMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
 417       }
 418   }
 419
 420
 421   void init_ray_bitboards() {
 422     int d[8] = {1, -1, 16, -16, 17, -17, 15, -15};
 423     for(int i = 0; i < 128; i = i + 9 & ~8) {
 424       for(int j = 0; j < 8; j++) {
 425         RayBB[(i&7)|((i>>4)<<3)][j] = EmptyBoardBB;
 426         for(int k = i + d[j]; (k & 0x88) == 0; k += d[j])
 427           set_bit(&(RayBB[(i&7)|((i>>4)<<3)][j]), Square((k&7)|((k>>4)<<3)));
 428       }
 429     }
 430   }
 431
 432
 433   void init_attacks() {
 434     int i, j, k, l;
 435     int step[16][8] =  {
 436       {0},
 437       {7,9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
 438       {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}, {0}, {0},
 439       {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17}, {9,7,-7,-9,0}, {8,1,-1,-8,0},
 440       {9,7,-7,-9,8,1,-1,-8}, {9,7,-7,-9,8,1,-1,-8}
 441     };
 442
 443     for(i = 0; i < 64; i++) {
 444       for(j = 0; j <= int(BK); j++) {
 445         StepAttackBB[j][i] = EmptyBoardBB;
 446         for(k = 0; k < 8 && step[j][k] != 0; k++) {
 447           l = i + step[j][k];
 448           if(l >= 0 && l < 64 && abs((i&7) - (l&7)) < 3)
 449             StepAttackBB[j][i] |= (1ULL << l);
 450         }
 451       }
 452     }
 453   }
 454
 455
 456   Bitboard sliding_attacks(int sq, Bitboard block, int dirs, int deltas[][2],
 457                            int fmin=0, int fmax=7, int rmin=0, int rmax=7) {
 458     Bitboard result = 0ULL;
 459     int rk = sq / 8, fl = sq % 8, r, f, i;
 460     for(i = 0; i < dirs; i++) {
 461       int dx = deltas[i][0], dy = deltas[i][1];
 462       for(f = fl+dx, r = rk+dy;
 463           (dx==0 || (f>=fmin && f<=fmax)) && (dy==0 || (r>=rmin && r<=rmax));
 464           f += dx, r += dy) {
 465         result |= (1ULL << (f + r*8));
 466         if(block & (1ULL << (f + r*8))) break;
 467       }
 468     }
 469     return result;
 470   }
 471
 472
 473   void init_between_bitboards() {
 474     SquareDelta step[8] = {
 475       DELTA_E, DELTA_W, DELTA_N, DELTA_S, DELTA_NE, DELTA_SW, DELTA_NW, DELTA_SE
 476     };
 477     SignedDirection d;
 478     for(Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
 479       for(Square s2 = SQ_A1; s2 <= SQ_H8; s2++) {
 480         BetweenBB[s1][s2] = EmptyBoardBB;
 481         d = signed_direction_between_squares(s1, s2);
 482         if(d != SIGNED_DIR_NONE)
 483           for(Square s3 = s1 + step[d]; s3 != s2; s3 += step[d])
 484             set_bit(&(BetweenBB[s1][s2]), s3);
 485       }
 486   }
 487
 488
 489   Bitboard index_to_bitboard(int index, Bitboard mask) {
 490     int i, j, bits = count_1s(mask);
 491     Bitboard result = 0ULL;
 492     for(i = 0; i < bits; i++) {
 493       j = pop_1st_bit(&mask);
 494       if(index & (1 << i)) result |= (1ULL << j);
 495     }
 496     return result;
 497   }
 498
 499
 500   void init_sliding_attacks(Bitboard attacks[],
 501                             int attackIndex[], Bitboard mask[],
 502                             const int shift[2], const Bitboard mult[],
 503                             int deltas[][2]) {
 504     int i, j, k, index = 0;
 505     Bitboard b;
 506     for(i = 0; i < 64; i++) {
 507       attackIndex[i] = index;
 508       mask[i] = sliding_attacks(i, 0ULL, 4, deltas, 1, 6, 1, 6);
 509       j = (1 << (64 - shift[i]));
 510       for(k = 0; k < j; k++) {
 511 #if defined(USE_32BIT_ATTACKS)
 512         b = index_to_bitboard(k, mask[i]);
 513         attacks[index +
 514                  (unsigned(int(b) * int(mult[i]) ^
 515                            int(b >> 32) * int(mult[i] >> 32))
 516                   >> shift[i])] =
 517           sliding_attacks(i, b, 4, deltas);
 518 #else
 519         b = index_to_bitboard(k, mask[i]);
 520         attacks[index + ((b * mult[i]) >> shift[i])] =
 521           sliding_attacks(i, b, 4, deltas);
 522 #endif
 523       }
 524       index += j;
 525     }
 526   }
 527
 528
 529   void init_pseudo_attacks() {
 530     Square s;
 531     for(s = SQ_A1; s <= SQ_H8; s++) {
 532       BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
 533       RookPseudoAttacks[s] = rook_attacks_bb(s, EmptyBoardBB);
 534       QueenPseudoAttacks[s] = queen_attacks_bb(s, EmptyBoardBB);
 535     }
 536   }
 537
 538 #if defined(USE_COMPACT_ROOK_ATTACKS)
 539   void init_file_and_rank_attacks() {
 540     int i, j, k, l, m, s;
 541     Bitboard b1, b2;
 542     for(i = 0; i < 64; i++) {
 543
 544       for(m = 0; m <= 1; m++) {
 545         b1 = 0ULL;
 546         for(j = 0; j < 6; j++) if(i & (1<<j)) b1 |= (1ULL << ((j+1)*(1+m*7)));
 547         for(j = 0; j < 8; j++) {
 548           b2 = 0ULL;
 549           for(k = 0, s = 1; k < 2; k++, s *= -1) {
 550             for(l = j+s; l >= 0 && l <= 7; l += s) {
 551               b2 |= (m? RankBB[l] : FileBB[l]);
 552               if(b1 & (1ULL << (l*(1+m*7)))) break;
 553             }
 554           }
 555           if(m) FileAttacks[j][(b1*0xd6e8802041d0c441ULL) >> 58] = b2;
 556           else RankAttacks[j][i] = b2;
 557         }
 558       }
 559     }
 560   }
 561 #endif // defined(USE_COMPACT_ROOK_ATTACKS)
 562
 563 }