Author: Gerd Isenberg
Date: 10:20:35 11/22/02
Go up one level in this thread
On November 22, 2002 at 11:37:56, Sune Fischer wrote:
>On November 22, 2002 at 07:42:51, Gerd Isenberg wrote:
>
>>For move generation, or if i really need disjoint attack sets, i currently favor
>>attack bitboards for a single sliding piece as well for a knight. That is what
>>my program does before with rotated bitboards and now with dumbfill and
>>Kogge-Stone mmx-routines.
>
>There is another thing which bothers we with disjoint attack boards, namely that
>they are _disjoint_.
>
>Some parallelism seem to be lost here, like how do you quickly detect a knight
>attacking a certain square if your knight attack boards are split into 8?
>
Hi Sune,
Yes, maybe some binary union bitboard tree.
LRTD // all rook targets
or
LR TD // disjoint rank or file
or or
L R T D // disjoint for each rook direction
>If you knew the direction to look, you could of course build that attack
>direction, but you don't as far as I can tell, unless there is some modulo trick
>which works directly on bitboards and can give you the direction, as in 0x88.
>
>So assuming you don't know this direction, how do you check if one of your rooks
>attacks one of his queens, ie the RxQ pattern, without checking all 4
>directions?
>
>>It may be nice to suppress the bitscans and the further rebuiling of singular
>>bitboards by 1<<sq. Something like this:
>>
>> BitBoard rooksToTraverse = Rooks() & ownPieces();
>> while (rooksToTraverse)
>> {
>> BitBoard singleRook = rooksToTraverse & -rooksToTraverse;
>> BitBoard rookAttacks = getRookAttacks(singleRook);
>> BitBoard captureTargets = rookAttacks & enemyPieces();
>> while ( captureTargets )
>> {
>> BitBoard captureTarget = captureTargets & -captureTargets;
>> PushCapture(singleRook, captureTarget);
>> captureTargets ^= captureTarget; // resets bit
>> }
>> BitBoard moveTargets = attacks & ~Pieces();
>> ...
>> rooksToTraverse ^= singleRook; // reset bit
>> }
>
>But then you don't have parallel attack computation of multiple rook instances,
>might as well use rotated :(
>
Yes, but searching the source square for every generated targetsquare by
generating an inverse direction attack seems to be more work for me.
With 128bit xmm registers (P4 or hammer) you can do two at one time, what is
most often enaugh. But you have to consider positions from Leonid of course :)
There are a lot of other topics and pattern, where floodFill-parallelism is good
for. If the routines are fast enough and gain really from more registers and
more pipes, eg. dumbfill in eight directions or Kogge-Stone in four directions
simultaniously, one may call them on the fly, when needed.
>
>>To get an index eg. for history table or to get really the native square
>>coordinates without bitscans, some hashkey-function may help, as Steffan already
>>mentioned, that maps the two from and to bitboards to an integer range.
>>
>>I don't like div/mod, but had no better idea so far similar to Joel Veness
>>proposal to extract bits from a bitboard:
>>http://www.talkchess.com/forums/1/message.html?265543
>>
>> (fromBB - toBB) mod 7961
>>
>>gives unique numbers for each possible move. But the range is rather huge. There
>>should be something better...
>
>You have to know this trick for it to work, you need to know directions here.
I'm dreaming of a hell fast inline:
int func(BitBoard fromBB, BitBoard toBB)
to get an unique integer value with the range of 1792 (or up 2048), where 3 bits
indicate the direction (Ok the latter is not so important and i would also
accept a range of 4096 :-)
Then using a lookup table with from/to coordinates is a nice alternative to bit
scan.
My best one so far with some shifts and signed mod (which i like to avoid) with
6395 is a range from -6382..+6382, which is 12764/1792 or more than seven times
so much space, my math skills are overemployed )-:
Gerd
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.