Author: Vasik Rajlich
Date: 11:20:40 12/02/04
Go up one level in this thread
On December 02, 2004 at 12:51:28, Gerd Isenberg wrote:
><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...
>
As far as I can see, in order to generate moves, you'll need to use the (1<<sq)
bitboards. Maybe it makes sense to keep the lookup tables for move gen, and the
fill routines when you need to "fill" starting with >1 bit.
>
>>
>>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...
>
Actually yes I can see a ton of ways to use this. The question is which ones are
really helpful eval terms.
>>
>>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
>
Aha, that's nice. You even have the pinning direction.
In fact you'd probably do:
pinnedRem[RIGHT_LEFT] =
(getRightRookAttacks (opprooks|oppqueens, empty)
& getLeftRookAttacks (ownKing, empty))
| (getLeftRookAttacks (opprooks|oppqueens, empty)
& getRightRookAttacks (ownKing, empty))
and ditto for UP_LEFT. I can't see a reason to keep RIGHT and LEFT separate.
>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.
>
True.
>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.
Ok here you lost me :)
But thanks for reminding me why I put bitboards into my program.
Vas
>
>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.