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