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:14] – 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 75: 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 205: Line 319:
 ---- ----
  
 +===== References =====
 +
 +
 +http://graphics.stanford.edu/~seander/bithacks.html
  
chess/programming/bitboards.1633983293.txt.gz · Last modified: 2021/10/11 20:14 by peter
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki