Author: KarinsDad
Date: 21:14:27 02/06/00
Go up one level in this thread
On February 06, 2000 at 14:02:58, William Bryant wrote: [snip] >What I would like is someone to explain a simple method for generating sliding >piece moves from bitboards. How to quickly determine where sliding pieces >stop moving because their path is blockes. > >William >wbryant@ix.netcom.com Ok, I will make an attempt. This algorithm is byte oriented. I'm sure someone has come up with a 64 bit one, but I have not gone down that path yet. You have a row, column, or diagonal. You represent it in 8 bits (you can have it represented in 64 bits, but you just use the 8 bits for the rows / columns / diagonals; i.e. mask the 8 bits out of the 64). For a given piece, you have two sets of information: 1) Location 2) Piece Type So, if you have a Rook on c2, then from the location and the piece type, you know to handle rows and columns only and specifically the C column and the number 2 row. You have multiple bitboards for the entire board: 1) White Pieces Column (8 bytes) 2) Black Pieces Column 3) White and Black Pieces Column (i.e. 1) and 2) XORed) 4) White Pieces Row 5) Black Pieces Row 6) White and Black Pieces Row (i.e. 4) and 5) XORed) 7) White Pieces Diagonal 45 (13 bytes, a8 and h1 not needed) 8) Black Pieces Diagonal 45 9) White and Black Pieces Diagonal 45 (i.e. 7) and 8) XORed) 10) White Pieces Diagonal 135 (13 bytes, a1 and h8 not needed) 11) Black Pieces Diagonal 135 12) White and Black Pieces Diagonal 135 (i.e. 10) and 11) XORed) Let's take the following #2 row for this example: . N R . . n P P The white rook is on c2, the white knight b2, the black knight f2, and a white pawn on g2 and h2. For a row calculation, we use bitboards 4 and 6 from above. We also use a table lookup based on the start location of the original piece (in this case the rook on c2) and the xored bitboard (#6). 01100011 row byte from white bitboard (#4) 00000100 row byte from black bitboard (#5) 01100111 row byte from white and black xored bitboard (#6) 01111100 row byte returned from table lookup 01100000 row byte returned ANDed with white row byte 00011100 row byte returned XORed with ANDed byte 00011100 indicates that the rook can move to d2, e2, or f2 and that's it. How you parse out that information from this bit structure is up to you. As can be seen, this is effectively a few lines of code per row, column, or diagonal. For example: table = TABLE(column, xorRowBB(row)); answer = (table & whiteRowBB(row)) ^ table; Now since it was white to move, the black bitboard was not used here (other than to create the xored bitboard). The TABLE lookup (which by the way is 256 bytes large) returns all bits turned on for the 8 bits from the start location to the left and the start location to the right INCLUDING the start location (which gets xored out). Since the table lookup is passed the xored byte, it does not know if the next piece over is the same color or not, hence, for this example, the following is returned: . N R . . n P P 0 1 1 1 1 1 0 0 The table knows that you cannot get to the A, G, or H file, but a calculation based on the white bitboard must be done to figure out if the piece on b2 and the piece on f2 are white or black. The same table is used for rows, columns, and diagonals. Hope this helps. KarinsDad :)
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.