Author: Gerd Isenberg
Date: 09:51:28 12/02/04
Go up one level in this thread
<snip>
>>Hi Vas,
>>
>>yes, you are right. In a rotated bitboard environment the x^(x-2) trick doesn't
>>makes sense, because a lookup already provides attacks in both opposite
>>directions on one ray for one particular sliding piece.
>>
>>In my current mmx-implementation i don't use rotated attack lookups anymore but
>>fillbased direction wise attack getters (Kogge-Stone and dumb7fill).
>>As you can see, the fillbased attack getters work with bitboard parameters
>>instead of a singular square index, and are able to generate attacks of sets,
>>multiple pieces (rooks/queen for straight directions, bishops/queen for diagonal
>>directions).
>>
>>Those fill based routines are great to get sets of taboo squares for the
>>opposite king and to get pinned pieces - and to get something like a progessive
>>mobility, e.g. a set of squares rooks may reach in two or even more moves etc..
>>
>>I use the x^(x-2) trick to substitute following Kogge-Stone fill-routine, which
>>saves a few cycles for this particular direction:
>>
>>// Kogge-Stone implementation by Steffan Westcott
>>
>>BitBoard getRightRookAttacks (BitBoard rooks, BitBoard empty)
>>{
>> return shiftRight(fillRightOccluded(rooks, empty));
>>}
>>
>>BitBoard shiftRight (BitBoard b)
>>{
>> return (b<<1) & 0xfefefefefefefefe;
>>}
>>
>>BitBoard fillRightOccluded(BitBoard g, BitBoard p)
>>{
>> p &= 0xfefefefefefefefe;
>> g |= p & (g << 1);
>> p &= (p << 1);
>> g |= p & (g << 2);
>> p &= (p << 2);
>> return g |= p & (g << 4);
>>}
>
>Aha. So, you have also something like:
>
>BitBoard getALLRookAttacks (BitBoard rooks, BitBoard empty)
>{
>return
> getRightRookAttacks (rooks, empty) |
> getLeftRookAttacks (rooks, empty) |
> getUpRookAttacks (rooks, empty) |
> getDownRookAttacks (rooks, empty) ;
>}
>
>And then you can do things like:
>
>Bitboard two_moves_away = getALLRookAttacks (getALLRookAttacks (rooks, empty),
>empty);
That's the idea.
>
>etc ...
>
>I'd guess this is slower than a lookup for a one-bit bitboard, but more
>efficient once the mask starts to become more populated.
Yes. I even tried it with single pupulated pieces (1ULL<<sq) in my former
rotated lookup approach. Queen attacks (eight directions) is IIRC something like
100 cycles with mmx-assembly (branchless and up to four mmx-instructions
simultaniously).
Huge 64-bit register files are necessary (AMD64, MMX, SSE2, Altivec, Itanium).
Of couse it sucks on x86-32 with the few 32-bit gp-registers.
But of course, 1/1 replacement of rotated attack getters with fill-routines is
not the smartest way...
>
>This might be an interesting tool to do some sort of "strategic reasoning". For
>example, pass (!pawns) into the second parameter, or even (! (very fixed
>pawns)), etc.
Exactly - one may even "and" the "atacks in one set" with other taboo and
occupied by own sets...
>
>BTW I don't see how to get pins from this - unless you will manually unset bits
>in the "empty" bitboard ...
No - you have only to consider the king as meta-slider as well and then "and"
opposite directions, e.g. for one of eight possible pin-directions:
pinnedRem[RIGHT] = getRightRookAttacks (opprooks|oppqueens, empty)
& getLeftRookAttacks (ownKing, empty);
pinned[ownside][RIGHT] = pinnedRem[RIGHT] & ownPieces;
remChe[oppside][RIGHT] = pinnedRem[RIGHT] & oppPieces;
... all branchless stuff
In case of a sliding check on this direction, pinnedRem[RIGHT] contains a set of
empty squares between checking piece and checked king, which also is usefull.
With fillalgos it is important to keep disjoint directions.
In opposite to Steffan i like to keep separated attacks for each sliding piece
as well - therefore i'm playing with a quad-bitboard approach.
The idea is to pass a quad-bitboard to fill-routines and to distinguish between
attacks of 15 different pieces.
Gerd
>
>Vas
<snip>
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.