Wiki

User Tools

Site Tools

Trace: • routing_from_server_to_client • minimax_algorithm
chess:programming:bitboards

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
chess:programming:bitboards [2021/10/11 20:07] – peterchess:programming:bitboards [2021/10/29 00:56] (current) – peter
Line 2: Line 2:
  
 A BitBoard is comprised of a 64-bit word, which is used to store the positions of different Chess Pieces. A BitBoard is comprised of a 64-bit word, which is used to store the positions of different Chess Pieces.
 +
 +<code>
 +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
 +</code>
  
 Every square on a Chess Board is represented by one bit in the 64-bit word. Every square on a Chess Board is represented by one bit in the 64-bit word.
Line 20: Line 32:
   * blackPawns   * blackPawns
  
-The bit-numbering convention for the bitboards:+---- 
 + 
 +===== 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 #0 will be the rightmost bit in the 64-bit word (least significant bit, or LSB), and
Line 46: Line 72:
  
 ---- ----
 +
 +===== Fast bitwise Operations =====
  
 There are some fast bit-wise operations that we can perform on bitboards. There are some fast bit-wise operations that we can perform on bitboards.
Line 59: Line 87:
 <code> <code>
 occupiedSquares = whitePieces | blackPieces; occupiedSquares = whitePieces | blackPieces;
 +</code>
 +
 +----
 +
 +===== 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:
 +
 +<code>
 +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
 +</code>
 +
 +<WRAP info>
 +**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.
 +
 +</WRAP>
 +
 +----
 +
 +===== Attacks =====
 +
 +To determine opponent pieces a queen may capture:
 +
 +  * 'and' the queen-attacks bitboard with the set of opponent pieces:
 +
 +<code>
 +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 . . . .     . . . . . . . .     . . . . . . . .
 +</code>
 +
 +----
 +
 +===== Determine Empty Squares =====
 +
 +The set of empty squares for instance is the complement-set of all occupied squares and vice versa:
 +
 +<code>
 +~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 .
 +</code>
 +
 +----
 +
 +===== Determine Squares which are exclusively set in one of the two sets  =====
 +
 +Use XOR (Exclusive or).
 +
 +<code>
 +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
 +</code>
 +
 +----
 +
 +===== Determine Squares which are set in both BitBoards =====
 +
 +Determine if one Bitboard is a subset of the other.
 +
 +  * Use xor (or subtraction).
 +
 +<code>
 +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 .
 +. . . . . . . .     . . . . . . . .     . . . . . . . .
 </code> </code>
  
Line 189: Line 319:
 ---- ----
  
 +===== References =====
 +
 +
 +http://graphics.stanford.edu/~seander/bithacks.html
  
chess/programming/bitboards.1633982861.txt.gz · Last modified: 2021/10/11 20:07 by peter
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki