TalkChess.com
Hosted by Your Move Chess & Games

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

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?

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: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
J. Wesley Cleveland Fri May 04, 2007 1:55 am
Gerd Isenberg Mon May 28, 2007 12:40 pm
Gerd Isenberg Mon May 28, 2007 3:16 pm
Gerd Isenberg Mon May 28, 2007 4:35 pm
Gerd Isenberg Wed May 30, 2007 5:55 pm
Pradu Kannan Wed May 30, 2007 10:51 pm
Re: Resource for bit twiddlers Gerd Isenberg Thu May 31, 2007 6:17 am
Pradu Kannan Fri Jun 01, 2007 12:16 am
Gerd Isenberg Fri Jun 01, 2007 8:19 am
Gerd Isenberg Mon Jun 04, 2007 2:58 pm

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
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