Subtraction based Attack Mask Generation

[vittyvirus]

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]

This is really interesting. I guess it performs well too. Maybe it should get put into the chess wiki.

[Evert]

This is really interesting. I guess it performs well too. Maybe it should get put into the chess wiki.

https://chessprogramming.wikispaces.com/SBAMG

[vittyvirus]

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(occ & pMask->lower);

to

Code: Select all

int bsq = bsr64((occ & pMask->lower) | 1);  // Avoid calling bsr64(0)

Thanks!

[Gerd Isenberg]

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

[vittyvirus]

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]

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