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-2010 Marco Costalba, Joona Kiiski, Tord Romstad
   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 #include <iostream>
  21
  22 #include "bitboard.h"
  23 #include "bitcount.h"
  24
  25 // Global bitboards definitions with static storage duration are
  26 // automatically set to zero before enter main().
  27 Bitboard RAttacks[0x19000];
  28 Bitboard BAttacks[0x1480];
  29
  30 Magics RMagics[64];
  31 Magics BMagics[64];
  32
  33 Bitboard SetMaskBB[65];
  34 Bitboard ClearMaskBB[65];
  35
  36 Bitboard SquaresByColorBB[2];
  37 Bitboard FileBB[8];
  38 Bitboard RankBB[8];
  39 Bitboard NeighboringFilesBB[8];
  40 Bitboard ThisAndNeighboringFilesBB[8];
  41 Bitboard InFrontBB[2][8];
  42 Bitboard StepAttacksBB[16][64];
  43 Bitboard BetweenBB[64][64];
  44 Bitboard SquaresInFrontMask[2][64];
  45 Bitboard PassedPawnMask[2][64];
  46 Bitboard AttackSpanMask[2][64];
  47
  48 Bitboard BishopPseudoAttacks[64];
  49 Bitboard RookPseudoAttacks[64];
  50 Bitboard QueenPseudoAttacks[64];
  51
  52 uint8_t BitCount8Bit[256];
  53
  54 namespace {
  55
  56 #if defined(IS_64BIT)
  57
  58 const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL;
  59
  60 const uint64_t BMult[64] = {
  61   0x0440049104032280ULL, 0x1021023C82008040ULL, 0x0404040082000048ULL,
  62   0x48C4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL,
  63   0x0181011002E06040ULL, 0x9101004104200E00ULL, 0x1240848848310401ULL,
  64   0x2000142828050024ULL, 0x00001004024D5000ULL, 0x0102044400800200ULL,
  65   0x8108108820112000ULL, 0xA880818210C00046ULL, 0x4008008801082000ULL,
  66   0x0060882404049400ULL, 0x0104402004240810ULL, 0x000A002084250200ULL,
  67   0x00100B0880801100ULL, 0x0004080201220101ULL, 0x0044008080A00000ULL,
  68   0x0000202200842000ULL, 0x5006004882D00808ULL, 0x0000200045080802ULL,
  69   0x0086100020200601ULL, 0xA802080A20112C02ULL, 0x0080411218080900ULL,
  70   0x000200A0880080A0ULL, 0x9A01010000104000ULL, 0x0028008003100080ULL,
  71   0x0211021004480417ULL, 0x0401004188220806ULL, 0x00825051400C2006ULL,
  72   0x00140C0210943000ULL, 0x0000242800300080ULL, 0x00C2208120080200ULL,
  73   0x2430008200002200ULL, 0x1010100112008040ULL, 0x8141050100020842ULL,
  74   0x0000822081014405ULL, 0x800C049E40400804ULL, 0x4A0404028A000820ULL,
  75   0x0022060201041200ULL, 0x0360904200840801ULL, 0x0881A08208800400ULL,
  76   0x0060202C00400420ULL, 0x1204440086061400ULL, 0x0008184042804040ULL,
  77   0x0064040315300400ULL, 0x0C01008801090A00ULL, 0x0808010401140C00ULL,
  78   0x04004830C2020040ULL, 0x0080005002020054ULL, 0x40000C14481A0490ULL,
  79   0x0010500101042048ULL, 0x1010100200424000ULL, 0x0000640901901040ULL,
  80   0x00000A0201014840ULL, 0x00840082AA011002ULL, 0x010010840084240AULL,
  81   0x0420400810420608ULL, 0x8D40230408102100ULL, 0x4A00200612222409ULL,
  82   0x0A08520292120600ULL
  83 };
  84
  85 const uint64_t RMult[64] = {
  86   0x0A8002C000108020ULL, 0x4440200140003000ULL, 0x8080200010011880ULL,
  87   0x0380180080141000ULL, 0x1A00060008211044ULL, 0x410001000A0C0008ULL,
  88   0x9500060004008100ULL, 0x0100024284A20700ULL, 0x0000802140008000ULL,
  89   0x0080C01002A00840ULL, 0x0402004282011020ULL, 0x9862000820420050ULL,
  90   0x0001001448011100ULL, 0x6432800200800400ULL, 0x040100010002000CULL,
  91   0x0002800D0010C080ULL, 0x90C0008000803042ULL, 0x4010004000200041ULL,
  92   0x0003010010200040ULL, 0x0A40828028001000ULL, 0x0123010008000430ULL,
  93   0x0024008004020080ULL, 0x0060040001104802ULL, 0x00582200028400D1ULL,
  94   0x4000802080044000ULL, 0x0408208200420308ULL, 0x0610038080102000ULL,
  95   0x3601000900100020ULL, 0x0000080080040180ULL, 0x00C2020080040080ULL,
  96   0x0080084400100102ULL, 0x4022408200014401ULL, 0x0040052040800082ULL,
  97   0x0B08200280804000ULL, 0x008A80A008801000ULL, 0x4000480080801000ULL,
  98   0x0911808800801401ULL, 0x822A003002001894ULL, 0x401068091400108AULL,
  99   0x000004A10A00004CULL, 0x2000800640008024ULL, 0x1486408102020020ULL,
 100   0x000100A000D50041ULL, 0x00810050020B0020ULL, 0x0204000800808004ULL,
 101   0x00020048100A000CULL, 0x0112000831020004ULL, 0x0009000040810002ULL,
 102   0x0440490200208200ULL, 0x8910401000200040ULL, 0x6404200050008480ULL,
 103   0x4B824A2010010100ULL, 0x04080801810C0080ULL, 0x00000400802A0080ULL,
 104   0x8224080110026400ULL, 0x40002C4104088200ULL, 0x01002100104A0282ULL,
 105   0x1208400811048021ULL, 0x3201014A40D02001ULL, 0x0005100019200501ULL,
 106   0x0101000208001005ULL, 0x0002008450080702ULL, 0x001002080301D00CULL,
 107   0x410201CE5C030092ULL
 108 };
 109
 110 #else // if !defined(IS_64BIT)
 111
 112 const uint32_t DeBruijnMagic = 0x783A9B23;
 113
 114 const uint64_t BMult[64] = {
 115   0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL,
 116   0xBFED1A0B80F838C5ULL, 0x90561D5631E62110ULL, 0x2804260376E60944ULL,
 117   0x84A656409AA76871ULL, 0xF0267F64C28B6197ULL, 0x70764EBB762F0585ULL,
 118   0x92AA09E0CFE161DEULL, 0x41EE1F6BB266F60EULL, 0xDDCBF04F6039C444ULL,
 119   0x5A3FAB7BAC0D988AULL, 0xD3727877FA4EAA03ULL, 0xD988402D868DDAAEULL,
 120   0x812B291AFA075C7CULL, 0x94FAF987B685A932ULL, 0x3ED867D8470D08DBULL,
 121   0x92517660B8901DE8ULL, 0x2D97E43E058814B4ULL, 0x880A10C220B25582ULL,
 122   0xC7C6520D1F1A0477ULL, 0xDBFC7FBCD7656AA6ULL, 0x78B1B9BFB1A2B84FULL,
 123   0x2F20037F112A0BC1ULL, 0x657171EA2269A916ULL, 0xC08302B07142210EULL,
 124   0x0880A4403064080BULL, 0x3602420842208C00ULL, 0x852800DC7E0B6602ULL,
 125   0x595A3FBBAA0F03B2ULL, 0x9F01411558159D5EULL, 0x2B4A4A5F88B394F2ULL,
 126   0x4AFCBFFC292DD03AULL, 0x4A4094A3B3F10522ULL, 0xB06F00B491F30048ULL,
 127   0xD5B3820280D77004ULL, 0x8B2E01E7C8E57A75ULL, 0x2D342794E886C2E6ULL,
 128   0xC302C410CDE21461ULL, 0x111F426F1379C274ULL, 0xE0569220ABB31588ULL,
 129   0x5026D3064D453324ULL, 0xE2076040C343CD8AULL, 0x93EFD1E1738021EEULL,
 130   0xB680804BED143132ULL, 0x44E361B21986944CULL, 0x44C60170EF5C598CULL,
 131   0xF4DA475C195C9C94ULL, 0xA3AFBB5F72060B1DULL, 0xBC75F410E41C4FFCULL,
 132   0xB51C099390520922ULL, 0x902C011F8F8EC368ULL, 0x950B56B3D6F5490AULL,
 133   0x3909E0635BF202D0ULL, 0x5744F90206EC10CCULL, 0xDC59FD76317ABBC1ULL,
 134   0x881C7C67FCBFC4F6ULL, 0x47CA41E7E440D423ULL, 0xEB0C88112048D004ULL,
 135   0x51C60E04359AEF1AULL, 0x1AA1FE0E957A5554ULL, 0xDD9448DB4F5E3104ULL,
 136   0xDC01F6DCA4BEBBDCULL,
 137 };
 138
 139 const uint64_t RMult[64] = {
 140   0xD7445CDEC88002C0ULL, 0xD0A505C1F2001722ULL, 0xE065D1C896002182ULL,
 141   0x9A8C41E75A000892ULL, 0x8900B10C89002AA8ULL, 0x9B28D1C1D60005A2ULL,
 142   0x015D6C88DE002D9AULL, 0xB1DBFC802E8016A9ULL, 0x149A1042D9D60029ULL,
 143   0xB9C08050599E002FULL, 0x132208C3AF300403ULL, 0xC1000CE2E9C50070ULL,
 144   0x9D9AA13C99020012ULL, 0xB6B078DAF71E0046ULL, 0x9D880182FB6E002EULL,
 145   0x52889F467E850037ULL, 0xDA6DC008D19A8480ULL, 0x468286034F902420ULL,
 146   0x7140AC09DC54C020ULL, 0xD76FFFFA39548808ULL, 0xEA901C4141500808ULL,
 147   0xC91004093F953A02ULL, 0x02882AFA8F6BB402ULL, 0xAEBE335692442C01ULL,
 148   0x0E904A22079FB91EULL, 0x13A514851055F606ULL, 0x76C782018C8FE632ULL,
 149   0x1DC012A9D116DA06ULL, 0x3C9E0037264FFFA6ULL, 0x2036002853C6E4A2ULL,
 150   0xE3FE08500AFB47D4ULL, 0xF38AF25C86B025C2ULL, 0xC0800E2182CF9A40ULL,
 151   0x72002480D1F60673ULL, 0x2500200BAE6E9B53ULL, 0xC60018C1EEFCA252ULL,
 152   0x0600590473E3608AULL, 0x46002C4AB3FE51B2ULL, 0xA200011486BCC8D2ULL,
 153   0xB680078095784C63ULL, 0x2742002639BF11AEULL, 0xC7D60021A5BDB142ULL,
 154   0xC8C04016BB83D820ULL, 0xBD520028123B4842ULL, 0x9D1600344AC2A832ULL,
 155   0x6A808005631C8A05ULL, 0x604600A148D5389AULL, 0xE2E40103D40DEA65ULL,
 156   0x945B5A0087C62A81ULL, 0x012DC200CD82D28EULL, 0x2431C600B5F9EF76ULL,
 157   0xFB142A006A9B314AULL, 0x06870E00A1C97D62ULL, 0x2A9DB2004A2689A2ULL,
 158   0xD3594600CAF5D1A2ULL, 0xEE0E4900439344A7ULL, 0x89C4D266CA25007AULL,
 159   0x3E0013A2743F97E3ULL, 0x0180E31A0431378AULL, 0x3A9E465A4D42A512ULL,
 160   0x98D0A11A0C0D9CC2ULL, 0x8E711C1ABA19B01EULL, 0x8DCDC836DD201142ULL,
 161   0x5AC08A4735370479ULL,
 162 };
 163
 164 #endif // defined(IS_64BIT)
 165
 166   CACHE_LINE_ALIGNMENT int BSFTable[64];
 167
 168   void init_sliding_attacks(Bitboard attacks[], Magics m[], const Bitboard mult[], Square deltas[]);
 169 }
 170
 171
 172 /// print_bitboard() prints a bitboard in an easily readable format to the
 173 /// standard output. This is sometimes useful for debugging.
 174
 175 void print_bitboard(Bitboard b) {
 176
 177   for (Rank r = RANK_8; r >= RANK_1; r--)
 178   {
 179       std::cout << "+---+---+---+---+---+---+---+---+" << '\n';
 180       for (File f = FILE_A; f <= FILE_H; f++)
 181           std::cout << "| " << (bit_is_set(b, make_square(f, r)) ? 'X' : ' ') << ' ';
 182
 183       std::cout << "|\n";
 184   }
 185   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
 186 }
 187
 188
 189 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
 190 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
 191 /// nonzero bitboard.
 192
 193 #if defined(IS_64BIT) && !defined(USE_BSFQ)
 194
 195 Square first_1(Bitboard b) {
 196   return Square(BSFTable[((b & -b) * DeBruijnMagic) >> 58]);
 197 }
 198
 199 Square pop_1st_bit(Bitboard* b) {
 200   Bitboard bb = *b;
 201   *b &= (*b - 1);
 202   return Square(BSFTable[((bb & -bb) * DeBruijnMagic) >> 58]);
 203 }
 204
 205 #elif !defined(USE_BSFQ)
 206
 207 Square first_1(Bitboard b) {
 208   b ^= (b - 1);
 209   uint32_t fold = unsigned(b) ^ unsigned(b >> 32);
 210   return Square(BSFTable[(fold * DeBruijnMagic) >> 26]);
 211 }
 212
 213 // Use type-punning
 214 union b_union {
 215
 216     Bitboard b;
 217     struct {
 218 #if defined (BIGENDIAN)
 219         uint32_t h;
 220         uint32_t l;
 221 #else
 222         uint32_t l;
 223         uint32_t h;
 224 #endif
 225     } dw;
 226 };
 227
 228 Square pop_1st_bit(Bitboard* bb) {
 229
 230    b_union u;
 231    Square ret;
 232
 233    u.b = *bb;
 234
 235    if (u.dw.l)
 236    {
 237        ret = Square(BSFTable[((u.dw.l ^ (u.dw.l - 1)) * DeBruijnMagic) >> 26]);
 238        u.dw.l &= (u.dw.l - 1);
 239        *bb = u.b;
 240        return ret;
 241    }
 242    ret = Square(BSFTable[((~(u.dw.h ^ (u.dw.h - 1))) * DeBruijnMagic) >> 26]);
 243    u.dw.h &= (u.dw.h - 1);
 244    *bb = u.b;
 245    return ret;
 246 }
 247
 248 #endif // !defined(USE_BSFQ)
 249
 250
 251 /// init_bitboards() initializes various bitboard arrays. It is called during
 252 /// program initialization.
 253
 254 void init_bitboards() {
 255
 256   SquaresByColorBB[DARK]  =  0xAA55AA55AA55AA55ULL;
 257   SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK];
 258
 259   for (Square s = SQ_A1; s <= SQ_H8; s++)
 260   {
 261       SetMaskBB[s] = (1ULL << s);
 262       ClearMaskBB[s] = ~SetMaskBB[s];
 263   }
 264
 265   ClearMaskBB[SQ_NONE] = ~EmptyBoardBB;
 266
 267   FileBB[FILE_A] = FileABB;
 268   RankBB[RANK_1] = Rank1BB;
 269
 270   for (int f = FILE_B; f <= FILE_H; f++)
 271   {
 272       FileBB[f] = FileBB[f - 1] << 1;
 273       RankBB[f] = RankBB[f - 1] << 8;
 274   }
 275
 276   for (int f = FILE_A; f <= FILE_H; f++)
 277   {
 278       NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
 279       ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f];
 280   }
 281
 282   for (int rw = RANK_7, rb = RANK_2; rw >= RANK_1; rw--, rb++)
 283   {
 284       InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1];
 285       InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1];
 286   }
 287
 288   for (Color c = WHITE; c <= BLACK; c++)
 289       for (Square s = SQ_A1; s <= SQ_H8; s++)
 290       {
 291           SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
 292           PassedPawnMask[c][s]     = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
 293           AttackSpanMask[c][s]     = in_front_bb(c, s) & neighboring_files_bb(s);
 294       }
 295
 296   for (Bitboard b = 0; b < 256; b++)
 297       BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
 298
 299   for (int i = 1; i < 64; i++)
 300       if (!CpuIs64Bit) // Matt Taylor's folding trick for 32 bit systems
 301       {
 302           Bitboard b = 1ULL << i;
 303           b ^= b - 1;
 304           b ^= b >> 32;
 305           BSFTable[uint32_t(b * DeBruijnMagic) >> 26] = i;
 306       }
 307       else
 308           BSFTable[((1ULL << i) * DeBruijnMagic) >> 58] = i;
 309
 310   int steps[][9] = {
 311     {0}, {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0}, {9,7,-7,-9,8,1,-1,-8,0}
 312   };
 313
 314   for (Color c = WHITE; c <= BLACK; c++)
 315       for (Square s = SQ_A1; s <= SQ_H8; s++)
 316           for (PieceType pt = PAWN; pt <= KING; pt++)
 317               for (int k = 0; steps[pt][k]; k++)
 318               {
 319                   Square to = s + Square(c == WHITE ? steps[pt][k] : -steps[pt][k]);
 320
 321                   if (square_is_ok(to) && square_distance(s, to) < 3)
 322                       set_bit(&StepAttacksBB[make_piece(c, pt)][s], to);
 323               }
 324
 325   Square RDeltas[] = { DELTA_N,  DELTA_E,  DELTA_S,  DELTA_W  };
 326   Square BDeltas[] = { DELTA_NE, DELTA_SE, DELTA_SW, DELTA_NW };
 327
 328   init_sliding_attacks(RAttacks, RMagics, RMult, RDeltas);
 329   init_sliding_attacks(BAttacks, BMagics, BMult, BDeltas);
 330
 331   for (Square s = SQ_A1; s <= SQ_H8; s++)
 332   {
 333       BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
 334       RookPseudoAttacks[s]   = rook_attacks_bb(s, EmptyBoardBB);
 335       QueenPseudoAttacks[s]  = queen_attacks_bb(s, EmptyBoardBB);
 336   }
 337
 338   for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
 339       for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
 340           if (bit_is_set(QueenPseudoAttacks[s1], s2))
 341           {
 342               int f = file_distance(s1, s2);
 343               int r = rank_distance(s1, s2);
 344
 345               Square d = (s2 - s1) / Max(f, r);
 346
 347               for (Square s3 = s1 + d; s3 != s2; s3 += d)
 348                   set_bit(&BetweenBB[s1][s2], s3);
 349           }
 350 }
 351
 352
 353 namespace {
 354
 355   Bitboard submask(Bitboard mask, int key) {
 356
 357     Bitboard subMask = 0;
 358     int bitNum = -1;
 359
 360     // Extract an unique submask out of a mask according to the given key
 361     for (Square s = SQ_A1; s <= SQ_H8; s++)
 362         if (bit_is_set(mask, s) && bit_is_set(key, Square(++bitNum)))
 363             set_bit(&subMask, s);
 364
 365     return subMask;
 366   }
 367
 368   Bitboard sliding_attacks(Square sq, Bitboard occupied, Square deltas[], Bitboard excluded) {
 369
 370     Bitboard attacks = 0;
 371
 372     for (int i = 0; i < 4; i++)
 373     {
 374         Square s = sq + deltas[i];
 375
 376         while (    square_is_ok(s)
 377                &&  square_distance(s, s - deltas[i]) == 1
 378                && !bit_is_set(excluded, s))
 379         {
 380             set_bit(&attacks, s);
 381
 382             if (bit_is_set(occupied, s))
 383                 break;
 384
 385             s += deltas[i];
 386         }
 387     }
 388     return attacks;
 389   }
 390
 391   void init_sliding_attacks(Bitboard attacks[], Magics m[], const Bitboard mult[], Square deltas[]) {
 392
 393     Bitboard occupancy, index, excluded;
 394     int maxKey, offset = 0;
 395
 396     for (Square s = SQ_A1; s <= SQ_H8; s++)
 397     {
 398         excluded = ((Rank1BB | Rank8BB) & ~rank_bb(s)) | ((FileABB | FileHBB) & ~file_bb(s));
 399
 400         m[s].offset = offset;
 401         m[s].mult   = mult[s];
 402         m[s].mask   = sliding_attacks(s, EmptyBoardBB, deltas, excluded);
 403         m[s].shift  = (CpuIs64Bit ? 64 : 32) - count_1s<CNT64>(m[s].mask);
 404
 405         maxKey = 1 << count_1s<CNT64>(m[s].mask);
 406
 407         for (int key = 0; key < maxKey; key++)
 408         {
 409             occupancy = submask(m[s].mask, key);
 410
 411             index = CpuIs64Bit ? occupancy * mult[s]
 412                                : unsigned(occupancy * mult[s] ^ (occupancy >> 32) * (mult[s] >> 32));
 413
 414             attacks[offset + (index >> m[s].shift)] = sliding_attacks(s, occupancy, deltas, EmptyBoardBB);
 415         }
 416         offset += maxKey;
 417     }
 418   }
 419 }