Author: leonid
Date: 18:02:39 02/07/00
Go up one level in this thread
On February 07, 2000 at 00:14:27, KarinsDad wrote: >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 :) Thanks for explanation! Was very curious for me to see your way of writing the logic and impress me by its difference. I don't use the bitboard or look up table. Everything goes after stright and "simple logic" that we usually use in all kind of games. It could be that your way is more efficent. Leonid.
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.