TalkChess.com :: View topic - Resource for bit twiddlers

TalkChess.com
Hosted by Your Move Chess & Games

FAQ

Memberlist

Usergroups

Profile

Resource for bit twiddlers

TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

View previous topic :: View next topic

Author

Message

Gerd Isenberg

Joined: 08 Mar 2006
Posts: 1785
Location: Hattingen, Germany

Post subject: Re: Resource for bit twiddlers Posted: Thu May 31, 2007 6:17 am

Pradu wrote:

From what I can understand this subtraction technique can only be used for right fills and left fills. Here's what I could infer from your filling algorithm:

I'll term rooks as squares.

so basically the concept is to use the fact that

Code:

(LSB at left, looking at only first rank for now)
HFile "rooks" Result
00000001 - 00001000 = 00001110
Result HFile Fill
00001110 ^ 00000001 = 00001111

Now lets add an occupancy to see if it still works:

Code:

(LSB at left like for the first rank)
HFile|occ "rooks" Result
00000011 - 00001000 = 00001101
Result HFile|occ Fill
00001101 ^ 00000011 = 00001110

Works perfect! But because of the subtraction, we have to make sure the occupancy and the rook don't coinside eg:

Code:

(LSB at left like for the first rank)
HFile|occ "rooks" Result
00001001 - 00001000 = 00000001 (BAD)
Result HFile|occ Fill
00000001 ^ 00000011 = 00000010 (WRONG)

So we have to make sure we take the rooks out of the occupancy. Assuming the same occupancy as before:

Code:

((HFile|occ)&~rooks) - "rooks" Result
00000001 - 00001000 = 00001110
Result ^ ((HFile|occ)&~rooks) = Fill
00001110 00000001 = 00001110

From the above we can make an easy right fill:

Code:

U64 rightFill(U64 squares, U64 occ)
{
occ = (occ|FILEHBB)&~squares; //occupancy without squares
return ((occ - squares)^occ) | squares; //xor to get rid of unused occupancy
}

I hope my iterpretation is correct? Is it also possible to to do fills other than left and right with the subtraction technique?

Hi Pradu,

no, the o^(o-2r) trick with r is subset of o, unfortunately works only for "positive" directions, in this setwise case for the a->h direction (east, right from white points of view on the chessboard) with mapping a1==0, h8==63. For all other seven directions one has to use Steffan Westcott's Kogge-Stone routines.

The bytewise or rankwise o^(o-2r) works setwise even with multiple rooks per rank. The first substraction of -2r == - r - r can be done by xor or "andnot" to clear the whole rook-bits in the occupancy, while the substration does the carry propagation, and the final xor leaves the attacks. Simd instructions with MMX or SSE2 are nice for that bytewise-substraction, but it turned out that the SWAR-trick is as quite effective as well.

With single rooks/bishops by square metric, one can use this trick for four positive vertical and diagonal directions with pre- and post-masks of the complete file or diagonal. For bishops and file-attacks one can use vertical flips (bswap) to do the negative directions. But a bishop attack-getter based on this technique was a bit slower than kindergarten, not to mention magic:

Code:

u64 bishopAttacks(u64 occ, u32 sq) {
u64 rvsdia, rvsant, bishop;
u64 occdia = occ, occant = occ;
occdia &= smsk[sq].diagonalMaskEx;
occant &= smsk[sq].antidiagMaskEx;
bishop = smsk[sq].bitMask;
rvsdia = _byteswap_uint64(occdia);
rvsant = _byteswap_uint64(occant);
occdia ^= occdia - bishop;
occant ^= occant - bishop;
bishop = _byteswap_uint64(bishop);
rvsdia ^= rvsdia - bishop;
rvsant ^= rvsant - bishop;
occdia ^= _byteswap_uint64(rvsdia);
occant ^= _byteswap_uint64(rvsant);
occdia &= smsk[sq].diagonalMaskEx;
occant &= smsk[sq].antidiagMaskEx;
return occdia ^ occant;
}

Gerd

Display posts from previous:

Subject	Author	Date/Time
Resource for bit twiddlers	J. Wesley Cleveland	Fri May 04, 2007 1:55 am
Re: Resource for bit twiddlers	Gerd Isenberg	Mon May 28, 2007 12:40 pm
Re: Resource for bit twiddlers	Gerd Isenberg	Mon May 28, 2007 3:16 pm
Re: Resource for bit twiddlers	Gerd Isenberg	Mon May 28, 2007 4:35 pm
Re: Resource for bit twiddlers	Gerd Isenberg	Wed May 30, 2007 5:55 pm
Re: Resource for bit twiddlers	Pradu Kannan	Wed May 30, 2007 10:51 pm
Re: Resource for bit twiddlers	Gerd Isenberg	Thu May 31, 2007 6:17 am
Re: Resource for bit twiddlers	Pradu Kannan	Fri Jun 01, 2007 12:16 am
Re: Resource for bit twiddlers	Gerd Isenberg	Fri Jun 01, 2007 8:19 am
Re: Resource for bit twiddlers	Gerd Isenberg	Mon Jun 04, 2007 2:58 pm

TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum