Differences

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

--- chess:programming:bitboards [2021/10/11 21:37] – peter
+++ chess: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.
+<code>
+0 0 0 0 0 0 0 0
+0 0 0 0 0 0 0 0
+0 0 0 0 0 0 0 0
+0 0 0 0 0 0 0 0
+0 0 0 0 0 0 0 0
+0 0 0 0 0 0 0 0
+0 0 0 0 0 0 0 0
+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.
@@ Line 75: / Line 87: @@
 <code>
 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
+</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 . . . .     . . . . . . . .     . . . . . . . .
+</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 .
+</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
+</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>