Author: Gerd Isenberg
Date: 03:20:14 12/02/04
Go up one level in this thread
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);
}
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.01 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.