Author: Juan Manuel Vazquez Gonzalez
Date: 07:24:54 05/10/99
Go up one level in this thread
On May 06, 1999 at 17:15:24, Kristo Miettinen wrote:
>I'm struggling to comprehend whether rotated bitboards are worth the grief.
>
>I currently populate bitboards for attacks by sliding pieces with the help of a
>4096-bitboard array "beyond[64][64]", a 512-bitboard array "ray[64][8]", and a
>pair of set-bit finders, one to find the highest-indexed set bit in a bitboard
>and one to find the lowest-indexed set bit.
>
>With these resources, the method for generating sliding piece attacks is to step
>through the 4 (R or B) or 8 (for Q) relevant rays, intersect them with populated
>squares, and depending on the ray use the appropriate set-bit finder to find the
>ray-intercepting piece closest to the sliding attacker. Then I can use the
>bitboard beyond[attacker][intercept] to clear bits from the ray that are not
>attacked by the attacker due to occlusion by the intercepting piece (if any).
>
>For instance, given a bishop on c3 and a piece on f6 (but nothing on d4 or e5,
>and anything on g7 or h8) I would start with ray[c3][northeast] (which is the
>set {d4, e5, f6, g7, h8}) to find squares attacked on an empty board, and
>intersect it with the set of occupied squares to generate a set with f6 and
>possibly g7 or h8 as well. Because my ray was northeast I choose the
>lowest-index set-bit finder to guarantee that I find f6 regardless of whether g7
>or h8 was set, and then I can use the bitboard beyond[c3][f6] (which is the set
>{g7, h8}) to clear the occluded squares from the ray of attacked squares.
>
>For other uses there is a companion array "between[64][64]" used, for among
>other purposes, in check evasion.
>
>Both arrays have plenty of uses in generating and breaking pins, skewers, and
>the like (I use a goal-seeking move generator).
>
>Can anyone advise whether rotated bitboards offer benefits in speed or utility
>that can't be achieved in this kind of framework?
I think the best choice to calculate the sliding piece attack is the use
of rotated bitboards and precalculated attack bitboards mask.
You can precalculate bitboards to clear bits from the ray that are not attacked.
For example, if the main a1h8 diagonal bit value is 101B0011, ( where B means
Bishop ), you can precalculate for this value a bitboard mask to clear not
attacked bits by the bishop. This bitboard mask is 00100010.
As you see, you can clear all the bits not attacked by the bishop in the a1a8
diagonal in only one bitboard operation and not in two, and you don't have to
use the beyond array.
So, you need to precalculate bitboard masks for every type of sliding piece
( bishop and rook ), in every possible position on the board (64) and for every
possible row, column or diagonal bit value (256). To do this you need to store
rotated bitboards to access quickly to columns an diagonals bit values.
I think precalculated bitboard mask offer benefits in speed, because you only
have make two "and" operations to calculate the attack of a sliding piece. And
this method has a lot of aplications too.
( Excuse me for my bad English, ... thanks )
This page took 0 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.