Author: Bas Hamstra
Date: 11:37:10 01/21/03
Go up one level in this thread
On January 21, 2003 at 12:11:20, Russell Reagan wrote:
>As far as I can tell, it boils down to this. Which of these will be faster?
>
>Let's define "version 1" to be computing attacks using rotated bitboards, and
>"version 2" using the fill routines (shown below). For this example, let's
>compute rook attacks. Computing rook attacks is a few table lookups, a few
>shifts, and a couple of ANDs.
>Do you think version 2 can compare to that? I'm doubtful. Table lookups are
>"free" basically, and you are doing WAY more shifting and bitwise operations in
>version 2. The only way version 2 could keep up is if you have multiple rooks
>that you want to compute attacks for. This doesn't help for things like move
>generation, but it would if you were calculating the attacks for one color.
>Even then, it only helps if you have more than one rook on the board.
I doubt it too, although the rotated BB lookup tables are relatively big, and
may suffer from cache misses, which are expensive. Also I am not sure you
couldn't use multiple slider attackmasks for move generation. Suppose you want
to generate captures. Generate a combined attackmask UP for all white queens and
rooks. AND that mask with all black pieces and you have the TO squares, which
will be few (if any). Now you can figure out the FROM squares, by simply
scanning the board down from each individual TO square (requires looping), or by
taking the attacked-piece mask, and filling it down until it hits white pieces.
Or by masking white pieces per file the attacked piece is on, and FirstOne will
give the attacker. This would be quite a bit faster than doing the BlockedFill
for each piece seperately. Could be competitive, no idea.
Best regards,
Bas.
>I'm not sure if the parallel speed up would be faster than doing two attack
>generations using rotated bitboards. The only place this might be a big gain is
>in generating pawn attacks since there can be up to eight of them, but I don't
>think generating pawn attacks are a big bottleneck for most people.
>
>// Version 2
>// To compute rook attacks, you have to call ALL FOUR of these. It will compute
>// attacks for any number of rooks on the board, but usually there will only
>// be two, so this will have to be twice as fast as Version 1, which is
>// a stretch.
>
>Bitboard FillRightBlocked (Bitboard Source, Bitboard Clear)
>{
> Clear &= NotFileA;
> Source |= Clear & (Source << 1);
> Clear &= Clear << 1;
> Source |= Clear & (Source << 2);
> Clear &= Clear << 2;
> Source |= Clear & (Source << 4);
> return Source;
>}
>
>Bitboard FillLeftBlocked (Bitboard Source, Bitboard Clear)
>{
> Clear &= NotFileH;
> Source |= Clear & (Source >> 1);
> Clear &= Clear >> 1;
> Source |= Clear & (Source >> 2);
> Clear &= Clear >> 2;
> Source |= Clear & (Source >> 4);
> return Source;
>}
>
>Bitboard FillUpBlocked (Bitboard Source, Bitboard Clear)
>{
> Source |= Clear & (Source << 8);
> Clear &= Clear << 8;
> Source |= Clear & (Source << 16);
> Clear &= Clear << 16;
> Source |= Clear & (Source << 32);
> return Source;
>}
>
>Bitboard FillDownBlocked (Bitboard Source, Bitboard Clear)
>{
> Source |= Clear & (Source >> 8);
> Clear &= Clear >> 8;
> Source |= Clear & (Source >> 16);
> Clear &= Clear >> 16;
> Source |= Clear >> 32;
> return Source;
>}
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.