Author: Vasik Rajlich
Date: 08:05:31 12/02/04
Go up one level in this thread
On December 02, 2004 at 06:20:14, Gerd Isenberg wrote:
>On December 02, 2004 at 04:36:11, Vasik Rajlich wrote:
>
>>On November 30, 2004 at 16:33:20, Gerd Isenberg wrote:
>>
>>>On November 30, 2004 at 12:51:38, Andrew N. Hunt wrote:
>>>
>>>>Hi!
>>>>
>>>>I've recently implemented bitboards (standard and rotated) and have a question
>>>>about pre-computing moves which contain blocked squares. Let's say I have the
>>>>occupied rank:
>>>>
>>>>bQ, wN, _, wR, _, bP, bN, _
>>>>
>>>>and I want to find the valid moves for the white Rook. How do I handle modifying
>>>>its bitboard rank: 11010110 to remove the blocked squares and only store the
>>>>available squares: 01101100? (which I can then And with the white/black pieces
>>>>to find valid Rook moves)
>>>
>>>Additionally to the other posts i like to mention the x^(x-2) trick to generate
>>>rank attacks in msb direction:
>>>
>>> msb lsb
>>> occupied 11010110
>>>-attacker 00010000 (or &~attacker if attacker must not be a member of occupied)
>>> 11000110 => rook reset in occupied
>>>-attacker 00010000
>>> 10110110 => get some bits from next borrow
>>>^occupied 11010110
>>> 01100000 => attacks in msb direction
>>>
>>>Whether this is the left or right direction depends on your bitboard mapping - i
>>>call it right attacks. Similar to Steffan's Kogge-Stone algorithms this works
>>>with multiple rooks on a rank too. To perform the rank- or bytewise trick with
>>>the whole bitboard, one has to use SIMD instructions (vector of 8 bytes, eg.
>>>MMX/SSE2 psubb) or a SWAR algorithm with some 0x00ff...00ff and 0xff00...ff00
>>>masks.
>>>
>>>Cheers,
>>>Gerd
>>>
>>>
>>
>>Cool trick. But - is there also one for "left attacks"? If not, it's not really
>>useful, since you'll need a lookup anyway - so might as well get the whole rank.
>>
>>Or do I miss something?
>>
>>Vas
>
>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);
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.
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.
BTW I don't see how to get pins from this - unless you will manually unset bits
in the "empty" bitboard ...
Vas
>
>Instead i use this four mmx-assembly instructions:
>
> input: mm0 -> oocupied, mm1-rooks/queen (not necessarily member of occupied)
> output: mm2 -> all right attacks of all rooks/queen
>
> movq mm2, mm1 ; rooks
> pandn mm2, mm0 ; occupied & ~rooks
> psubb mm2, mm1 ; - rooks
> pxor mm2, mm0
>
>There are other approaches trying to take advantage of the x^(x-2) trick.
>First for a single sliding piece the trick may be applied for all "positive"
>directions with some ray masking and 64-bit subtraction.
>
>Additionally there was the reversed bitboard idea to use the trick in "negative"
>directions as well. The drawback is, that combining bitwise attack bitboards of
>"positive" and "negative" directions requires rather expensive bit reversals.
>
>Cheers,
>Gerd
>
>
>>
>>>
>>>>
>>>>Maybe I'm missing something obvious... :-?
>>>>
>>>>Many thanks!
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>ah.
>>>>
>>>>--------------------------------------------------------------------=
>>>>Andy Hunt
>>>>Manager, Electronic Documentation
>>>>Wolfram Research, Inc.
>>>>Voice: 217-398-0700 ext.260; Fax: 217-398-0747
>>>>Email: andy@wolfram.com; http://www.wolfram.com/
>>>>--------------------------------------------------------------------=
>>>>
>>>>Power corrupts. Absolute power is kind of neat.
>>>> -- John Lehman, Secretary of the Navy, 1981-1987
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.