====== Chess - Programming - BitBoards ====== A BitBoard is comprised of a 64-bit word, which is used to store the positions of different Chess Pieces. 8 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 a b c d e f g h Every square on a Chess Board is represented by one bit in the 64-bit word. Since there are 12 different pieces in chess, 12 BitBoards are needed to store a chess position: * whiteKing - bitboard with the position bit of the white king set to 1 (and other bits set to 0). * whiteQueens - bitboard with the position bits of all white queens set to 1 (and other bits set to 0), etc * whiteRooks * whiteBishops * whiteKnights * whitePawns * blackKing * blackQueens * blackRooks * blackBishops * blackKnights * blackPawns ---- ===== Benefits of BitBoards ===== Bitboards offer speed advantages in two parts of the program. * First (and this is the main reason for using them) the move generator is going to be very fast. * There are no loops to slide a piece down a diagonal, or rank/file as you will see later in the section on the move generator. * Second, bitboards offer speed improvements in the evaluation function. * For example, we can check if the white pawn on square e4 is passed with a single bitboard operation, there is no need to loop over the squares d5, d6, d7, e5, e6, e7, f5, f6 and f7 to see if any square is occupied by black pawns. * The Board structure will contain the 12 bitboards, together with additional variables for e.g. castling rights. ---- ===== The bit-numbering convention for BitBoards ===== * bit #0 will be the rightmost bit in the 64-bit word (least significant bit, or LSB), and * bit #63 will be the leftmost bit in the 64-bit word (most significant bit, or MSB). * Furthermore, square a1 = bit #0, h1 = bit #7, a8 = bit #56 and h8 = bit #63. RANKS: 8 | 56 57 58 59 60 61 62 63 (MSB, 7 | 48 49 50 51 52 53 54 55 left) 6 | 40 41 42 43 44 45 46 47 5 | 32 33 34 35 36 37 38 39 4 | 24 25 26 27 28 29 30 31 3 | 16 17 18 19 20 21 22 23 2 | 8 9 10 11 12 13 14 15 1 | (LSB, 0 1 2 3 4 5 6 7 right) ------------------------------------------- FILES: a b c d e f g h **NOTE:** If FILE and RANK are numbered from 1..8, then SQUARE (0..63) can be calculated as follows: SQUARE = 8 * RANK + FILE - 9; ---- ===== Fast bitwise Operations ===== There are some fast bit-wise operations that we can perform on bitboards. For instance, if we want to have a bitboard of all white pieces, then we can get this by using the bit-wise OR operator: whitePieces = whiteKing | whiteQueens | whiteRooks | whiteBishops | whiteKnights | whitePawns; Or all occupied squares: occupiedSquares = whitePieces | blackPieces; ---- ===== Determine what pieces are on the board ===== The union of two sets is superset of both. * For instance the union of all white and black pieces are the set of all occupied squares: white pieces | black pieces = occupied squares . . . . . . . . 1 . 1 1 1 1 1 1 1 . 1 1 1 1 1 1 . . . . . . . . 1 1 1 1 . 1 1 1 1 1 1 1 . 1 1 1 . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . . . . . . . . . . . 1 . . . . . . . 1 . . . . . . . 1 . . . | . . . . . . . . = . . . . 1 . . . . . . . . 1 . . . . . . . . . . . . . . . 1 . . 1 1 1 1 . 1 1 1 . . . . . . . . 1 1 1 1 . 1 1 1 1 1 1 1 1 1 . 1 . . . . . . . . 1 1 1 1 1 1 . 1 **NOTE:** Since white and black pieces are always disjoint, one may use addition here as well. * But this fails for unions of attack sets, since squares may be attacked or defended by multiple pieces of course. ---- ===== Attacks ===== To determine opponent pieces a queen may capture: * 'and' the queen-attacks bitboard with the set of opponent pieces: queen attacks & opponent pieces = attacked pieces . . . . . . . . 1 . . 1 1 . . 1 . . . . . . . . . . . 1 . . 1 . 1 . 1 1 1 1 1 . . . . 1 . . 1 . . 1 . 1 . 1 . . . 1 . . . . . 1 . 1 . . . . . . . . 1 1 1 . . . . . . . . . . . . . . . . . . . 1 1 1 * 1 1 1 . & . . . * . . 1 . = . . . * . . 1 . . . 1 1 1 . . . . . . . . . . . . . . . . . . . . . . 1 . 1 . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . ---- ===== Determine Empty Squares ===== The set of empty squares for instance is the complement-set of all occupied squares and vice versa: ~occupied squares = empty squares 1 . 1 1 1 1 1 1 . 1 . . . . . . 1 1 1 1 . 1 1 1 . . . . 1 . . . . . 1 . . . . . 1 1 . 1 1 1 1 1 . . . . 1 . . . 1 1 1 1 . 1 1 1 ~ . . . . 1 . . . = 1 1 1 1 . 1 1 1 . . . . . 1 . . 1 1 1 1 1 . 1 1 1 1 1 1 . 1 1 1 . . . . 1 . . . 1 1 1 1 1 1 . 1 . . . . . . 1 . ---- ===== Determine Squares which are exclusively set in one of the two sets ===== Use XOR (Exclusive or). 1 . . . . . . 1 . . . . . . . . 1 . . . . . . 1 . 1 . . . . 1 . . . . . . . . . . 1 . . . . 1 . . . 1 . . 1 . . . . 1 1 1 1 . . . . . 1 1 . . . . . . 1 1 . . . . . 1 1 1 1 . . . . 1 . . 1 . . . . . 1 1 . . . ^ . . 1 1 1 1 . . = . . 1 . . 1 . . . . 1 . . 1 . . . . 1 1 1 1 . . . . . 1 1 . . . . 1 . . . . 1 . . . . . . . . . . 1 . . . . 1 . 1 . . . . . . 1 . . . . . . . . 1 . . . . . . 1 ---- ===== Determine Squares which are set in both BitBoards ===== Determine if one Bitboard is a subset of the other. * Use xor (or subtraction). super sub super &~ sub . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 1 1 . . . . . . . . . . 1 1 1 1 1 1 . . 1 1 1 1 1 1 . . . 1 1 1 1 . . . 1 . . . . 1 . . 1 1 1 1 1 1 . ^ . . 1 1 1 1 . . . 1 . . . . 1 . . 1 1 1 1 1 1 . . . 1 1 1 1 . . = . 1 . . . . 1 . . 1 1 1 1 1 1 . - . . 1 1 1 1 . . . 1 . . . . 1 . . 1 1 1 1 1 1 . . . . . . . . . . 1 1 1 1 1 1 . . . . . . . . . . . . . . . . . . . . . . . . . ---- ===== C++ Bitwise Operators ===== There are six bitwise operators in C++, that are used in combination with bitboards: |&|The AND operator, compares two values, and returns a value that has its bits set if, and only if, the two values being compared both have their bits set.| |||The OR operator, compares two values, and returns a value that has its bits set if one or the other value, or both, have their bits set.| |^|The XOR operator, compares two values, and returns a value that has its bits set if one or the other value has its corresponding bits set, but not both.| |~|The Ones Complement, or Inversion, operator acts only on one value and inverts it, turning all ones into zeros, and all zeros into ones.| |>>|The Right Shift operator, shifts the bits from the high bit (MSB) to the low bit (LSB), the number of bit positions specified.| |<<|The Left Shift operator, shifts the bits from the low bit (LSB) to the high bit (MSB), the number of bit positions specified.| ---- ===== Frequently used bitwise operations ===== ==== Bitwise set bits ==== Mask has all bits set that need to be set: Result |= Mask; ---- ==== Bitwise set bits ==== Mask has all bits cleared that need to be set: Result |= ~Mask; ---- ==== Bitwise clear bits ==== Mask has all bits set that need to be cleared: Result &= ~Mask; ---- ==== Bitwise clear bits ==== Mask has all bits cleared that need to be cleared: Result &= Mask; ---- ==== Logical test for bits set ==== Mask has bits set that need to be tested for all 1: if (Test & Mask) == Mask) **NOTE:** * 1 = all Test bits are 1. * 0 = not all Test bits are 1. ---- ==== Logical test for bits set ==== Mask has bits cleared that need to be tested for all 1: if ((Test & ~Mask) == ~Mask) **NOTE:** * 1 = all Test bits are 1. * 0 = not all Test bits are 1. ---- ==== Logical test for bits cleared ==== Mask has bits set that need to be tested for all 0: if ((~Test & Mask) == Mask) **NOTE:** * 1 = all Test bits are 0. * 0 = not all Test bits are 0. ---- ==== Logical test for bits cleared ==== Mask has bits cleared that need to be tested for all 0: if ((~Test & ~Mask) == ~Mask) **NOTE:** * 1 = all Test bits are 0. * 0 = not all Test bits are 0. ---- ===== References ===== http://graphics.stanford.edu/~seander/bithacks.html