Author: Dan Newman
Date: 04:21:30 05/16/00
Go up one level in this thread
On May 15, 2000 at 17:27:52, Bas Hamstra wrote:
>I have an idea but no time to measure it's performance. Maybe Dan and/or Bob can
>comment.
>
>With rotated bb's you keep 4 rotated bb's, that let you determine the "state" of
>a "ray". Knowing square and state you look up the attacked squares in an array.
>
>I have an alternative. Isolate a certain ray in Occupied, using a raymask, and
>AND it with OccupiedAll. Compute LastBitOfRay() and FirstBitOfRay() of the
>result in one run, returning as follows:
>
> RetVal = (FirstIdx<<3)|LastIdx;
>
>Lookup RayMask[Square][RetVal] in a table.
>
>Pro:
>
>a) no shifting of unsigned __int64's needed
>b) no need to keep rotated BB's
>c) lookuptables reduced to 25% of normal size, so supposedly better cash
>performance
>
>Con:
>
>a) cost of the FirstLastRay()'s. You would start with a combined
>FirstOne()/LastOne(), and then, for instance for the RankRay, do a FILE() extra
>to compute the FirstBitOfRay. Ditto for Diag's, and for the FileRay you do a
>RANK().
>
>Intuition says the cost of FirstLast() is considerable, but still worth to try?
>
>
>Regards,
>Bas Hamstra.
I'm not sure I follow exactly what you have in mind--I'll look at it some
more tomorrow. I did try something like this once (I think only for the
non-captures) and had about 10% slower node rate (according to my notes)
than when simply scanning the board. I had to add a special 64x8 bitboard
ray-mask array, and I suspect that was the biggest culprit in the slowdown.
What I did was something like this:
bitboard_t bishop = piece[W_BISHOP]; // copy the white bishop bitboard
while( bishop.occupied() ) {
int from = bishop.first_one(); // first_one() also clears the bit
bitboard_t to_squares;
bitboard_t b = occupied & ray_mask[from][NE_DIR];
if( b.occupied() ) {
int limit = b.first_one();
to_squares = block_mask[from][limit];
} else {
to_squares = ray_mask[from][NE_DIR];
}
b = occupied & ray_mask[from][SW_DIR];
if( b.occupied() ) {
int limit = b.last_one();
to_squares |= block_mask[from][limit];
} else {
to_squares |= ray_mask[from][SW_DIR];
}
// etc., for NW and SE directions.
while( to_squares.occupied() ) {
int to = to_squares.first_one();
mlist.add_move( from, to);
}
}
The main idea is to use either first_one() or last_one() depending on
which direction the ray goes to find the first blocking piece (if any),
and then to OR in the squares to which the piece can move. When there
is no blocking piece, I OR in the whole ray, otherwise I OR in the
block-mask which has the bits turned on between the from-square and
the first blocking piece's square.
(I think I tried this after seeing something similar in Bob's bitboard
paper in the ICCAJ...)
-Dan.
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.