git.sesse.net Git - stockfish/blob - src/bitboard.h

   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
  12   Stockfish is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15   GNU General Public License for more details.
  16
  17   You should have received a copy of the GNU General Public License
  18   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21
  22 #if !defined(BITBOARD_H_INCLUDED)
  23 #define BITBOARD_H_INCLUDED
  24
  25 ////
  26 //// Defines
  27 ////
  28
  29 // Quiet a warning on Intel compiler
  30 #if !defined(__SIZEOF_INT__ )
  31 #define __SIZEOF_INT__ 0
  32 #endif
  33
  34 // Check for 64 bits for different compilers: Intel, MSVC and gcc
  35 #if defined(__x86_64) || defined(_WIN64) || (__SIZEOF_INT__ > 4)
  36 #define IS_64BIT
  37 #endif
  38
  39 #if defined(IS_64BIT) && (defined(__GNUC__) || defined(__INTEL_COMPILER))
  40 #define USE_BSFQ
  41 #endif
  42
  43
  44 ////
  45 //// Includes
  46 ////
  47
  48 #include "direction.h"
  49 #include "piece.h"
  50 #include "square.h"
  51 #include "types.h"
  52
  53
  54 ////
  55 //// Types
  56 ////
  57
  58 typedef uint64_t Bitboard;
  59
  60
  61 ////
  62 //// Constants and variables
  63 ////
  64
  65 const Bitboard EmptyBoardBB = 0ULL;
  66
  67 const Bitboard WhiteSquaresBB = 0x55AA55AA55AA55AAULL;
  68 const Bitboard BlackSquaresBB = 0xAA55AA55AA55AA55ULL;
  69 const Bitboard SquaresByColorBB[2] = { BlackSquaresBB, WhiteSquaresBB };
  70
  71 const Bitboard FileABB = 0x0101010101010101ULL;
  72 const Bitboard FileBBB = 0x0202020202020202ULL;
  73 const Bitboard FileCBB = 0x0404040404040404ULL;
  74 const Bitboard FileDBB = 0x0808080808080808ULL;
  75 const Bitboard FileEBB = 0x1010101010101010ULL;
  76 const Bitboard FileFBB = 0x2020202020202020ULL;
  77 const Bitboard FileGBB = 0x4040404040404040ULL;
  78 const Bitboard FileHBB = 0x8080808080808080ULL;
  79
  80 const Bitboard FileBB[8] = {
  81   FileABB, FileBBB, FileCBB, FileDBB, FileEBB, FileFBB, FileGBB, FileHBB
  82 };
  83
  84 const Bitboard NeighboringFilesBB[8] = {
  85   FileBBB, FileABB|FileCBB, FileBBB|FileDBB, FileCBB|FileEBB,
  86   FileDBB|FileFBB, FileEBB|FileGBB, FileFBB|FileHBB, FileGBB
  87 };
  88
  89 const Bitboard ThisAndNeighboringFilesBB[8] = {
  90   FileABB|FileBBB, FileABB|FileBBB|FileCBB,
  91   FileBBB|FileCBB|FileDBB, FileCBB|FileDBB|FileEBB,
  92   FileDBB|FileEBB|FileFBB, FileEBB|FileFBB|FileGBB,
  93   FileFBB|FileGBB|FileHBB, FileGBB|FileHBB
  94 };
  95
  96 const Bitboard Rank1BB = 0xFFULL;
  97 const Bitboard Rank2BB = 0xFF00ULL;
  98 const Bitboard Rank3BB = 0xFF0000ULL;
  99 const Bitboard Rank4BB = 0xFF000000ULL;
 100 const Bitboard Rank5BB = 0xFF00000000ULL;
 101 const Bitboard Rank6BB = 0xFF0000000000ULL;
 102 const Bitboard Rank7BB = 0xFF000000000000ULL;
 103 const Bitboard Rank8BB = 0xFF00000000000000ULL;
 104
 105 const Bitboard RankBB[8] = {
 106   Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB
 107 };
 108
 109 const Bitboard RelativeRankBB[2][8] = {
 110   { Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB },
 111   { Rank8BB, Rank7BB, Rank6BB, Rank5BB, Rank4BB, Rank3BB, Rank2BB, Rank1BB }
 112 };
 113
 114 const Bitboard InFrontBB[2][8] = {
 115   { Rank2BB | Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 116     Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 117     Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 118     Rank5BB | Rank6BB | Rank7BB | Rank8BB,
 119     Rank6BB | Rank7BB | Rank8BB,
 120     Rank7BB | Rank8BB,
 121     Rank8BB,
 122     EmptyBoardBB
 123   },
 124   { EmptyBoardBB,
 125     Rank1BB,
 126     Rank2BB | Rank1BB,
 127     Rank3BB | Rank2BB | Rank1BB,
 128     Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 129     Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 130     Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB,
 131     Rank7BB | Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB
 132   }
 133 };
 134
 135 const int BitTable[64] = {
 136   63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2,
 137   51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52,
 138   26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28,
 139   58, 20, 37, 17, 36, 8
 140 };
 141
 142 extern Bitboard SetMaskBB[65];
 143 extern Bitboard ClearMaskBB[65];
 144
 145 extern Bitboard StepAttackBB[16][64];
 146 extern Bitboard RayBB[64][8];
 147 extern Bitboard BetweenBB[64][64];
 148
 149 extern Bitboard PassedPawnMask[2][64];
 150 extern Bitboard OutpostMask[2][64];
 151
 152 extern const uint64_t RMult[64];
 153 extern const int RShift[64];
 154 extern Bitboard RMask[64];
 155 extern int RAttackIndex[64];
 156 extern Bitboard RAttacks[0x19000];
 157
 158 extern const uint64_t BMult[64];
 159 extern const int BShift[64];
 160 extern Bitboard BMask[64];
 161 extern int BAttackIndex[64];
 162 extern Bitboard BAttacks[0x1480];
 163
 164 extern Bitboard BishopPseudoAttacks[64];
 165 extern Bitboard RookPseudoAttacks[64];
 166 extern Bitboard QueenPseudoAttacks[64];
 167
 168
 169 ////
 170 //// Inline functions
 171 ////
 172
 173 /// Functions for testing whether a given bit is set in a bitboard, and for
 174 /// setting and clearing bits.
 175
 176 inline Bitboard bit_is_set(Bitboard b, Square s) {
 177   return b & SetMaskBB[s];
 178 }
 179
 180 inline void set_bit(Bitboard *b, Square s) {
 181   *b |= SetMaskBB[s];
 182 }
 183
 184 inline void clear_bit(Bitboard *b, Square s) {
 185   *b &= ClearMaskBB[s];
 186 }
 187
 188
 189 /// Functions used to update a bitboard after a move. This is faster
 190 /// then calling a sequence of clear_bit() + set_bit()
 191
 192 inline Bitboard make_move_bb(Square from, Square to) {
 193   return SetMaskBB[from] | SetMaskBB[to];
 194 }
 195
 196 inline void do_move_bb(Bitboard *b, Bitboard move_bb) {
 197   *b ^= move_bb;
 198 }
 199
 200 /// rank_bb() and file_bb() gives a bitboard containing all squares on a given
 201 /// file or rank.  It is also possible to pass a square as input to these
 202 /// functions.
 203
 204 inline Bitboard rank_bb(Rank r) {
 205   return RankBB[r];
 206 }
 207
 208 inline Bitboard rank_bb(Square s) {
 209   return rank_bb(square_rank(s));
 210 }
 211
 212 inline Bitboard file_bb(File f) {
 213   return FileBB[f];
 214 }
 215
 216 inline Bitboard file_bb(Square s) {
 217   return file_bb(square_file(s));
 218 }
 219
 220
 221 /// neighboring_files_bb takes a file or a square as input, and returns a
 222 /// bitboard representing all squares on the neighboring files.
 223
 224 inline Bitboard neighboring_files_bb(File f) {
 225   return NeighboringFilesBB[f];
 226 }
 227
 228 inline Bitboard neighboring_files_bb(Square s) {
 229   return neighboring_files_bb(square_file(s));
 230 }
 231
 232
 233 /// this_and_neighboring_files_bb takes a file or a square as input, and
 234 /// returns a bitboard representing all squares on the given and neighboring
 235 /// files.
 236
 237 inline Bitboard this_and_neighboring_files_bb(File f) {
 238   return ThisAndNeighboringFilesBB[f];
 239 }
 240
 241 inline Bitboard this_and_neighboring_files_bb(Square s) {
 242   return this_and_neighboring_files_bb(square_file(s));
 243 }
 244
 245
 246 /// relative_rank_bb() takes a color and a rank as input, and returns a bitboard
 247 /// representing all squares on the given rank from the given color's point of
 248 /// view. For instance, relative_rank_bb(WHITE, 7) gives all squares on the
 249 /// 7th rank, while relative_rank_bb(BLACK, 7) gives all squares on the 2nd
 250 /// rank.
 251
 252 inline Bitboard relative_rank_bb(Color c, Rank r) {
 253   return RelativeRankBB[c][r];
 254 }
 255
 256
 257 /// in_front_bb() takes a color and a rank or square as input, and returns a
 258 /// bitboard representing all the squares on all ranks in front of the rank
 259 /// (or square), from the given color's point of view.  For instance,
 260 /// in_front_bb(WHITE, RANK_5) will give all squares on ranks 6, 7 and 8, while
 261 /// in_front_bb(BLACK, SQ_D3) will give all squares on ranks 1 and 2.
 262
 263 inline Bitboard in_front_bb(Color c, Rank r) {
 264   return InFrontBB[c][r];
 265 }
 266
 267 inline Bitboard in_front_bb(Color c, Square s) {
 268   return in_front_bb(c, square_rank(s));
 269 }
 270
 271
 272 /// behind_bb() takes a color and a rank or square as input, and returns a
 273 /// bitboard representing all the squares on all ranks behind of the rank
 274 /// (or square), from the given color's point of view.
 275
 276 inline Bitboard behind_bb(Color c, Rank r) {
 277   return InFrontBB[opposite_color(c)][r];
 278 }
 279
 280 inline Bitboard behind_bb(Color c, Square s) {
 281   return in_front_bb(opposite_color(c), square_rank(s));
 282 }
 283
 284
 285 /// ray_bb() gives a bitboard representing all squares along the ray in a
 286 /// given direction from a given square.
 287
 288 inline Bitboard ray_bb(Square s, SignedDirection d) {
 289   return RayBB[s][d];
 290 }
 291
 292
 293 /// Functions for computing sliding attack bitboards. rook_attacks_bb(),
 294 /// bishop_attacks_bb() and queen_attacks_bb() all take a square and a
 295 /// bitboard of occupied squares as input, and return a bitboard representing
 296 /// all squares attacked by a rook, bishop or queen on the given square.
 297
 298 #if defined(IS_64BIT)
 299
 300 inline Bitboard rook_attacks_bb(Square s, Bitboard blockers) {
 301   Bitboard b = blockers & RMask[s];
 302   return RAttacks[RAttackIndex[s] + ((b * RMult[s]) >> RShift[s])];
 303 }
 304
 305 inline Bitboard bishop_attacks_bb(Square s, Bitboard blockers) {
 306   Bitboard b = blockers & BMask[s];
 307   return BAttacks[BAttackIndex[s] + ((b * BMult[s]) >> BShift[s])];
 308 }
 309
 310 #else // if !defined(IS_64BIT)
 311
 312 inline Bitboard rook_attacks_bb(Square s, Bitboard blockers) {
 313   Bitboard b = blockers & RMask[s];
 314   return RAttacks[RAttackIndex[s] +
 315                   (unsigned(int(b) * int(RMult[s]) ^
 316                             int(b >> 32) * int(RMult[s] >> 32))
 317                    >> RShift[s])];
 318 }
 319
 320 inline Bitboard bishop_attacks_bb(Square s, Bitboard blockers) {
 321   Bitboard b = blockers & BMask[s];
 322   return BAttacks[BAttackIndex[s] +
 323                   (unsigned(int(b) * int(BMult[s]) ^
 324                             int(b >> 32) * int(BMult[s] >> 32))
 325                    >> BShift[s])];
 326 }
 327
 328 #endif
 329
 330 inline Bitboard queen_attacks_bb(Square s, Bitboard blockers) {
 331   return rook_attacks_bb(s, blockers) | bishop_attacks_bb(s, blockers);
 332 }
 333
 334
 335 /// squares_between returns a bitboard representing all squares between
 336 /// two squares.  For instance, squares_between(SQ_C4, SQ_F7) returns a
 337 /// bitboard with the bits for square d5 and e6 set.  If s1 and s2 are not
 338 /// on the same line, file or diagonal, EmptyBoardBB is returned.
 339
 340 inline Bitboard squares_between(Square s1, Square s2) {
 341   return BetweenBB[s1][s2];
 342 }
 343
 344
 345 /// squares_in_front_of takes a color and a square as input, and returns a
 346 /// bitboard representing all squares along the line in front of the square,
 347 /// from the point of view of the given color.  For instance,
 348 /// squares_in_front_of(BLACK, SQ_E4) returns a bitboard with the squares
 349 /// e3, e2 and e1 set.
 350
 351 inline Bitboard squares_in_front_of(Color c, Square s) {
 352   return in_front_bb(c, s) & file_bb(s);
 353 }
 354
 355
 356 /// squares_behind is similar to squares_in_front, but returns the squares
 357 /// behind the square instead of in front of the square.
 358
 359 inline Bitboard squares_behind(Color c, Square s) {
 360   return in_front_bb(opposite_color(c), s) & file_bb(s);
 361 }
 362
 363
 364 /// passed_pawn_mask takes a color and a square as input, and returns a
 365 /// bitboard mask which can be used to test if a pawn of the given color on
 366 /// the given square is a passed pawn.
 367
 368 inline Bitboard passed_pawn_mask(Color c, Square s) {
 369   return PassedPawnMask[c][s];
 370 }
 371
 372
 373 /// outpost_mask takes a color and a square as input, and returns a bitboard
 374 /// mask which can be used to test whether a piece on the square can possibly
 375 /// be driven away by an enemy pawn.
 376
 377 inline Bitboard outpost_mask(Color c, Square s) {
 378   return OutpostMask[c][s];
 379 }
 380
 381
 382 /// isolated_pawn_mask takes a square as input, and returns a bitboard mask
 383 /// which can be used to test whether a pawn on the given square is isolated.
 384
 385 inline Bitboard isolated_pawn_mask(Square s) {
 386   return neighboring_files_bb(s);
 387 }
 388
 389
 390 /// first_1() finds the least significant nonzero bit in a nonzero bitboard.
 391 /// pop_1st_bit() finds and clears the least significant nonzero bit in a
 392 /// nonzero bitboard.
 393
 394 #if defined(USE_BSFQ) // Assembly code by Heinz van Saanen
 395
 396 inline Square __attribute__((always_inline)) first_1(Bitboard b) {
 397   Bitboard dummy;
 398   __asm__("bsfq %1, %0": "=r"(dummy): "rm"(b) );
 399   return (Square)(dummy);
 400 }
 401
 402 inline Square __attribute__((always_inline)) pop_1st_bit(Bitboard* b) {
 403   const Square s = first_1(*b);
 404   *b &= ~(1ULL<<s);
 405   return s;
 406 }
 407
 408 #else // if !defined(USE_BSFQ)
 409
 410 inline Square first_1(Bitboard b) {
 411   b ^= (b - 1);
 412   uint32_t fold = int(b) ^ int(b >> 32);
 413   return Square(BitTable[(fold * 0x783a9b23) >> 26]);
 414 }
 415
 416 extern Square pop_1st_bit(Bitboard* b);
 417
 418 #endif
 419
 420
 421 ////
 422 //// Prototypes
 423 ////
 424
 425 extern void print_bitboard(Bitboard b);
 426 extern void init_bitboards();
 427
 428
 429 #endif // !defined(BITBOARD_H_INCLUDED)