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