Author: KarinsDad
Date: 15:10:58 05/07/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 use bitboards to determine legal moves and piece attack tables. My pieceattack
tables are different from yours in that they refer to all squares that any given
piece attacks (and are used for square control in the evaluation), not just the
squares that have enemy pieces on them.
However, I am glad you posted since I had not considered putting together a
structure of pieces which attack other pieces. I am also using a "goal-seeking"
move generator (a sort in my case) on my legal moves and I can see where this
may help (although, some of my other structures may do the same thing for me,
I'll have to think about it).
I have come to the conclusion that there is almost as many ways to use bitboards
in a chess program as there are programmers posting here.
My take on rotated bitboards is that they are probably just as fast as your
system (of course, this depends on other factors in your program). For example,
to calculate all legal bishop (for one bishop) diagonal moves requires 2 ANDs
and 2 XORs in my code (one for each of the two bishop diagonals). That is
probably faster than what you do to intersect multiple rows (columns?). However,
setting up the rotated bitboard in the first place sometimes takes up more time
than what you do. I use delta information for my creation of a rotated bitboard,
so if a particular bishop or queen diagonal is not affected by a move, then that
portion of the rotated bitboard does not get modified, so the net effect is
often minimal.
I also use my piece attack tables to create xraying piece attack (square attack)
tables for evaluation, so the direct use of the rotated bitboards helps me out
here as well (since I have come to the conclusion that instead of doing deltas
on the xraying tables, I may just want to calculate them from scratch each
time).
I should rename my piece attack tables to square attack tables or some such now
that I have read your post. Otherwise, I can now see why it would be confusing
for some people when I talk about them.
KarinsDad :)
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.