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 RMask[64];
  28 Bitboard* RAttacks[64];
  29 int RShift[64];
  30
  31 Bitboard BMask[64];
  32 Bitboard* BAttacks[64];
  33 int BShift[64];
  34
  35 Bitboard SetMaskBB[65];
  36 Bitboard ClearMaskBB[65];
  37
  38 Bitboard SquaresByColorBB[2];
  39 Bitboard FileBB[8];
  40 Bitboard RankBB[8];
  41 Bitboard NeighboringFilesBB[8];
  42 Bitboard ThisAndNeighboringFilesBB[8];
  43 Bitboard InFrontBB[2][8];
  44 Bitboard StepAttacksBB[16][64];
  45 Bitboard BetweenBB[64][64];
  46 Bitboard SquaresInFrontMask[2][64];
  47 Bitboard PassedPawnMask[2][64];
  48 Bitboard AttackSpanMask[2][64];
  49
  50 Bitboard BishopPseudoAttacks[64];
  51 Bitboard RookPseudoAttacks[64];
  52 Bitboard QueenPseudoAttacks[64];
  53
  54 uint8_t BitCount8Bit[256];
  55
  56 #if defined(IS_64BIT)
  57
  58 static 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 static 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
 167 namespace {
 168
 169   CACHE_LINE_ALIGNMENT
 170
 171   int BSFTable[64];
 172   Bitboard RAttacksTable[0x19000];
 173   Bitboard BAttacksTable[0x1480];
 174
 175   void init_sliding_attacks(Bitboard attacksTable[], Bitboard* attacks[], Bitboard mask[],
 176                             int shift[], const Bitboard mult[], Square deltas[]);
 177 }
 178
 179
 180 /// print_bitboard() prints a bitboard in an easily readable format to the
 181 /// standard output. This is sometimes useful for debugging.
 182
 183 void print_bitboard(Bitboard b) {
 184
 185   for (Rank r = RANK_8; r >= RANK_1; r--)
 186   {
 187       std::cout << "+---+---+---+---+---+---+---+---+" << '\n';
 188       for (File f = FILE_A; f <= FILE_H; f++)
 189           std::cout << "| " << (bit_is_set(b, make_square(f, r)) ? 'X' : ' ') << ' ';
 190
 191       std::cout << "|\n";
 192   }
 193   std::cout << "+---+---+---+---+---+---+---+---+" << std::endl;
 194 }
 195
 196
 197 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
 198 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
 199 /// nonzero bitboard.
 200
 201 #if defined(IS_64BIT) && !defined(USE_BSFQ)
 202
 203 Square first_1(Bitboard b) {
 204   return Square(BSFTable[((b & -b) * DeBruijnMagic) >> 58]);
 205 }
 206
 207 Square pop_1st_bit(Bitboard* b) {
 208   Bitboard bb = *b;
 209   *b &= (*b - 1);
 210   return Square(BSFTable[((bb & -bb) * DeBruijnMagic) >> 58]);
 211 }
 212
 213 #elif !defined(USE_BSFQ)
 214
 215 Square first_1(Bitboard b) {
 216   b ^= (b - 1);
 217   uint32_t fold = unsigned(b) ^ unsigned(b >> 32);
 218   return Square(BSFTable[(fold * DeBruijnMagic) >> 26]);
 219 }
 220
 221 // Use type-punning
 222 union b_union {
 223
 224     Bitboard b;
 225     struct {
 226 #if defined (BIGENDIAN)
 227         uint32_t h;
 228         uint32_t l;
 229 #else
 230         uint32_t l;
 231         uint32_t h;
 232 #endif
 233     } dw;
 234 };
 235
 236 Square pop_1st_bit(Bitboard* bb) {
 237
 238    b_union u;
 239    Square ret;
 240
 241    u.b = *bb;
 242
 243    if (u.dw.l)
 244    {
 245        ret = Square(BSFTable[((u.dw.l ^ (u.dw.l - 1)) * DeBruijnMagic) >> 26]);
 246        u.dw.l &= (u.dw.l - 1);
 247        *bb = u.b;
 248        return ret;
 249    }
 250    ret = Square(BSFTable[((~(u.dw.h ^ (u.dw.h - 1))) * DeBruijnMagic) >> 26]);
 251    u.dw.h &= (u.dw.h - 1);
 252    *bb = u.b;
 253    return ret;
 254 }
 255
 256 #endif // !defined(USE_BSFQ)
 257
 258
 259 /// init_bitboards() initializes various bitboard arrays. It is called during
 260 /// program initialization.
 261
 262 void init_bitboards() {
 263
 264   SquaresByColorBB[DARK]  =  0xAA55AA55AA55AA55ULL;
 265   SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK];
 266
 267   for (Square s = SQ_A1; s <= SQ_H8; s++)
 268   {
 269       SetMaskBB[s] = (1ULL << s);
 270       ClearMaskBB[s] = ~SetMaskBB[s];
 271   }
 272
 273   ClearMaskBB[SQ_NONE] = ~EmptyBoardBB;
 274
 275   FileBB[FILE_A] = FileABB;
 276   RankBB[RANK_1] = Rank1BB;
 277
 278   for (int f = FILE_B; f <= FILE_H; f++)
 279   {
 280       FileBB[f] = FileBB[f - 1] << 1;
 281       RankBB[f] = RankBB[f - 1] << 8;
 282   }
 283
 284   for (int f = FILE_A; f <= FILE_H; f++)
 285   {
 286       NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
 287       ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f];
 288   }
 289
 290   for (int rw = RANK_7, rb = RANK_2; rw >= RANK_1; rw--, rb++)
 291   {
 292       InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1];
 293       InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1];
 294   }
 295
 296   for (Color c = WHITE; c <= BLACK; c++)
 297       for (Square s = SQ_A1; s <= SQ_H8; s++)
 298       {
 299           SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
 300           PassedPawnMask[c][s]     = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
 301           AttackSpanMask[c][s]     = in_front_bb(c, s) & neighboring_files_bb(s);
 302       }
 303
 304   for (Bitboard b = 0; b < 256; b++)
 305       BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
 306
 307   for (int i = 1; i < 64; i++)
 308       if (!CpuIs64Bit) // Matt Taylor's folding trick for 32 bit systems
 309       {
 310           Bitboard b = 1ULL << i;
 311           b ^= b - 1;
 312           b ^= b >> 32;
 313           BSFTable[uint32_t(b * DeBruijnMagic) >> 26] = i;
 314       }
 315       else
 316           BSFTable[((1ULL << i) * DeBruijnMagic) >> 58] = i;
 317
 318   int steps[][9] = {
 319     {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}
 320   };
 321
 322   for (Color c = WHITE; c <= BLACK; c++)
 323       for (Square s = SQ_A1; s <= SQ_H8; s++)
 324           for (PieceType pt = PAWN; pt <= KING; pt++)
 325               for (int k = 0; steps[pt][k]; k++)
 326               {
 327                   Square to = s + Square(c == WHITE ? steps[pt][k] : -steps[pt][k]);
 328
 329                   if (square_is_ok(to) && square_distance(s, to) < 3)
 330                       set_bit(&StepAttacksBB[make_piece(c, pt)][s], to);
 331               }
 332
 333   Square RDeltas[] = { DELTA_N,  DELTA_E,  DELTA_S,  DELTA_W  };
 334   Square BDeltas[] = { DELTA_NE, DELTA_SE, DELTA_SW, DELTA_NW };
 335
 336   init_sliding_attacks(RAttacksTable, RAttacks, RMask, RShift, RMult, RDeltas);
 337   init_sliding_attacks(BAttacksTable, BAttacks, BMask, BShift, BMult, BDeltas);
 338
 339   for (Square s = SQ_A1; s <= SQ_H8; s++)
 340   {
 341       BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
 342       RookPseudoAttacks[s]   = rook_attacks_bb(s, EmptyBoardBB);
 343       QueenPseudoAttacks[s]  = queen_attacks_bb(s, EmptyBoardBB);
 344   }
 345
 346   for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
 347       for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
 348           if (bit_is_set(QueenPseudoAttacks[s1], s2))
 349           {
 350               int f = file_distance(s1, s2);
 351               int r = rank_distance(s1, s2);
 352
 353               Square d = (s2 - s1) / Max(f, r);
 354
 355               for (Square s3 = s1 + d; s3 != s2; s3 += d)
 356                   set_bit(&BetweenBB[s1][s2], s3);
 357           }
 358 }
 359
 360
 361 namespace {
 362
 363   Bitboard submask(Bitboard mask, int key) {
 364
 365     Bitboard subMask = 0;
 366     int bitNum = -1;
 367
 368     // Extract an unique submask out of a mask according to the given key
 369     for (Square s = SQ_A1; s <= SQ_H8; s++)
 370         if (bit_is_set(mask, s) && bit_is_set(key, Square(++bitNum)))
 371             set_bit(&subMask, s);
 372
 373     return subMask;
 374   }
 375
 376   Bitboard sliding_attacks(Square sq, Bitboard occupied, Square deltas[], Bitboard excluded) {
 377
 378     Bitboard attacks = 0;
 379
 380     for (int i = 0; i < 4; i++)
 381     {
 382         Square s = sq + deltas[i];
 383
 384         while (    square_is_ok(s)
 385                &&  square_distance(s, s - deltas[i]) == 1
 386                && !bit_is_set(excluded, s))
 387         {
 388             set_bit(&attacks, s);
 389
 390             if (bit_is_set(occupied, s))
 391                 break;
 392
 393             s += deltas[i];
 394         }
 395     }
 396     return attacks;
 397   }
 398
 399   void init_sliding_attacks(Bitboard attacksTable[], Bitboard* attacks[], Bitboard mask[],
 400                             int shift[], const Bitboard mult[], Square deltas[]) {
 401
 402     Bitboard occupancy, index, excluded;
 403     int maxKey, offset = 0;
 404
 405     for (Square s = SQ_A1; s <= SQ_H8; s++)
 406     {
 407         excluded = ((Rank1BB | Rank8BB) & ~rank_bb(s)) | ((FileABB | FileHBB) & ~file_bb(s));
 408
 409         attacks[s] = &attacksTable[offset];
 410         mask[s]    = sliding_attacks(s, EmptyBoardBB, deltas, excluded);
 411         shift[s]   = (CpuIs64Bit ? 64 : 32) - count_1s<CNT64>(mask[s]);
 412
 413         maxKey = 1 << count_1s<CNT64>(mask[s]);
 414
 415         for (int key = 0; key < maxKey; key++)
 416         {
 417             occupancy = submask(mask[s], key);
 418
 419             index = CpuIs64Bit ? occupancy * mult[s]
 420                                : unsigned(occupancy * mult[s] ^ (occupancy >> 32) * (mult[s] >> 32));
 421
 422             attacks[s][index >> shift[s]] = sliding_attacks(s, occupancy, deltas, EmptyBoardBB);
 423         }
 424         offset += maxKey;
 425     }
 426   }
 427 }