Subtraction based Attack Mask Generation

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
vittyvirus
Posts: 645
Joined: Wed Jun 18, 2014 12:30 pm
Full name: Fahad Syed

Subtraction based Attack Mask Generation

Post by vittyvirus » Wed Nov 16, 2016 1:25 pm

Hello!
You guys remember SBAMG: Subtraction based Attack Mask Generation? Matthew Brades has pointed out that it invokes undefined behaviour by calling msb(0) sometimes. So here is the fix, in a more concise way than before.

Code: Select all

uint64_t rank_attacks(int sq, uint64_t occ)
{
    occ = (occ & RankMaskEx[sq]) | RankOuterSquares[sq];
    return ((occ - ThisAndNextSq[msb(occ & PrevSquares[sq])]) ^ occ) & RankMaskEx[sq];
}
uint64_t file_attacks(int sq, uint64_t occ)
{
    occ = (occ & FileMaskEx[sq]) | FileOuterSquares[sq];
    return ((occ - ThisAndNextSq[msb(occ & PrevSquares[sq])]) ^ occ) & FileMaskEx[sq];
}
...where

Code: Select all

RankMaskEx[sq] = Bitboard of the rank mask excluding the bitboard of square 'sq' (same for FileMaskEx[sq]);
ThisAndNextSq&#91;sq&#93; = 3ULL << sq;
PrevSquares&#91;0&#93; = 1;
PrevSquares&#91;sq&#93; = &#40;1ULL << sq&#41; - 1 &#40;sq != 0&#41;
RankOuterSquares&#91;sq&#93; = (&#40;0x81ULL << &#40;sq & 56&#41;) & ~&#40;1ULL << sq&#41;) | 1;
FileOuterSquares&#91;sq&#93; = (&#40;0x100000000000001ULL << &#40;sq & 7&#41;) & ~&#40;1ULL << sq&#41;) | 1;

Dann Corbit
Posts: 9994
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Subtraction based Attack Mask Generation

Post by Dann Corbit » Wed Nov 16, 2016 6:41 pm

This is really interesting. I guess it performs well too. Maybe it should get put into the chess wiki.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Subtraction based Attack Mask Generation

Post by Evert » Wed Nov 16, 2016 7:08 pm

Dann Corbit wrote:This is really interesting. I guess it performs well too. Maybe it should get put into the chess wiki.
https://chessprogramming.wikispaces.com/SBAMG

User avatar
vittyvirus
Posts: 645
Joined: Wed Jun 18, 2014 12:30 pm
Full name: Fahad Syed

Re: Subtraction based Attack Mask Generation

Post by vittyvirus » Thu Nov 17, 2016 4:25 am

Evert wrote:
Dann Corbit wrote:This is really interesting. I guess it performs well too. Maybe it should get put into the chess wiki.
https://chessprogramming.wikispaces.com/SBAMG
First of all, a big thanks to Gerd Isenberg for explaining it so wonderfully!
Apparently I can't edit the wiki. Could someone please update the code? Here are the corrections you need to make:

Change

Code: Select all

int bsq = bsr64&#40;occ & pMask->lower&#41;;
to

Code: Select all

int bsq = bsr64&#40;&#40;occ & pMask->lower&#41; | 1&#41;;  // Avoid calling bsr64&#40;0&#41;
Thanks!

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Subtraction based Attack Mask Generation

Post by Gerd Isenberg » Thu Nov 17, 2016 8:46 am

hmm ... is the | 1 really necessary?

Lower (PrevSquares[sq]) should always intersect with outer (RankOuterSquares[sq]). Then argument of bsr is always not empty and bsr defined ...

assert ( pMask->outer & pMask->lower);
occ |= pMask->outer;
int bsq = bsr64(occ & pMask->lower);

Gerd

User avatar
vittyvirus
Posts: 645
Joined: Wed Jun 18, 2014 12:30 pm
Full name: Fahad Syed

Re: Subtraction based Attack Mask Generation

Post by vittyvirus » Wed Nov 30, 2016 4:10 am

Gerd Isenberg wrote:hmm ... is the | 1 really necessary?

Lower (PrevSquares[sq]) should always intersect with outer (RankOuterSquares[sq]). Then argument of bsr is always not empty and bsr defined ...

assert ( pMask->outer & pMask->lower);
occ |= pMask->outer;
int bsq = bsr64(occ & pMask->lower);

Gerd
Hi!
I'm sorry for the late reply.
An exception to this is sq = 0, in while case RankOuterSquare[0] & PrevSquares[0] can be 0, because RankOuterSquares[sq] mustn't contain the bit board of square sq.
And oh, thanks for giving SBAMG a wonderful CPW page!

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Subtraction based Attack Mask Generation

Post by Gerd Isenberg » Wed Nov 30, 2016 12:19 pm

vittyvirus wrote:
Gerd Isenberg wrote:hmm ... is the | 1 really necessary?

Lower (PrevSquares[sq]) should always intersect with outer (RankOuterSquares[sq]). Then argument of bsr is always not empty and bsr defined ...

assert ( pMask->outer & pMask->lower);
occ |= pMask->outer;
int bsq = bsr64(occ & pMask->lower);

Gerd
Hi!
I'm sorry for the late reply.
An exception to this is sq = 0, in while case RankOuterSquare[0] & PrevSquares[0] can be 0, because RankOuterSquares[sq] mustn't contain the bit board of square sq.
And oh, thanks for giving SBAMG a wonderful CPW page!
Simply let ...OuterSquares[0] = 1 and PrevSquares[0] = 1 as well and msb is always defined and ThisAndNextSq at least 3. MaskEx ensures rook or bishop on square zero is excluded from attacks anyway.

Some rank 0 samples with rook (r) on square 0
on otherwise empty rank 0

Code: Select all

index 7654 3210
      0000 000r
occ   0000 0001  1
pre   0000 0001  1 -> msb = 0
thine 0000 0011  3
-     1111 1110  1-3 = -2
^     1111 1111 -2 ^ 1 = -1
atta  1111 1110  & RankMaskEx
or with blocker (b) on next square

Code: Select all

      0000 00br
occ   0000 0011  3
pre   0000 0001  -> msb = 0
thine 0000 0011  3
-     0000 0000  3 - 3 = 0
^     0000 0011  0 ^ 3 = 3
atta  0000 0010  & RankMaskEx
or

Code: Select all

      0000 0b0r
occ   0000 0101  5
pre   0000 0001  -> msb = 0
thine 0000 0011  3
-     0000 0010  5 - 3 = 2
^     0000 0111  2 ^ 5 = 7
atta  0000 0110  & RankMaskEx
or

Code: Select all

      bbbb bbbr
occ   1111 1111  -1
pre   0000 0001  -> msb = 0
thine 0000 0011  3
-     1111 1100  -1 - 3 = -4
^     0000 0011  -4 ^ -1 = 3
atta  0000 0010  & RankMaskEx

Post Reply