SBAMG - Completing Hyperbola Quintessence

[vittyvirus]

Well, it has been a year since I last posted! The cause was another PC crash, this time the problem was in the motherboard. A year ago, I came up with a method to complete Hyperbola Quintessence. As pointed out by Gerd Isenberg, some extra work needed to be done for sq = 0 case (due to msb() problem). Could I afford a branch for the case sq = 0? No! So I did some (actually a lot of) work and refined the method so that it works perfectly.
So ladies(?) and gentlemen, I present to you SBAMG: Subtraction based Attack Mask Generation. Here's the C code for it:

Code: Select all

uint64_t rank_attacks(int sq, uint64_t occ)
{
    static const uint64_t OuterSquares[64] = {
      0x0000000000000081ULL, 0x0000000000000081ULL, 0x0000000000000081ULL,
      0x0000000000000081ULL, 0x0000000000000081ULL, 0x0000000000000081ULL,
      0x0000000000000081ULL, 0x0000000000000001ULL, 0x0000000000008000ULL,
      0x0000000000008100ULL, 0x0000000000008100ULL, 0x0000000000008100ULL,
      0x0000000000008100ULL, 0x0000000000008100ULL, 0x0000000000008100ULL,
      0x0000000000000100ULL, 0x0000000000800000ULL, 0x0000000000810000ULL,
      0x0000000000810000ULL, 0x0000000000810000ULL, 0x0000000000810000ULL,
      0x0000000000810000ULL, 0x0000000000810000ULL, 0x0000000000010000ULL,
      0x0000000080000000ULL, 0x0000000081000000ULL, 0x0000000081000000ULL,
      0x0000000081000000ULL, 0x0000000081000000ULL, 0x0000000081000000ULL,
      0x0000000081000000ULL, 0x0000000001000000ULL, 0x0000008000000000ULL,
      0x0000008100000000ULL, 0x0000008100000000ULL, 0x0000008100000000ULL,
      0x0000008100000000ULL, 0x0000008100000000ULL, 0x0000008100000000ULL,
      0x0000000100000000ULL, 0x0000800000000000ULL, 0x0000810000000000ULL,
      0x0000810000000000ULL, 0x0000810000000000ULL, 0x0000810000000000ULL,
      0x0000810000000000ULL, 0x0000810000000000ULL, 0x0000010000000000ULL,
      0x0080000000000000ULL, 0x0081000000000000ULL, 0x0081000000000000ULL,
      0x0081000000000000ULL, 0x0081000000000000ULL, 0x0081000000000000ULL,
      0x0081000000000000ULL, 0x0001000000000000ULL, 0x8000000000000000ULL,
      0x8100000000000000ULL, 0x8100000000000000ULL, 0x8100000000000000ULL,
      0x8100000000000000ULL, 0x8100000000000000ULL, 0x8100000000000000ULL,
      0x0100000000000000ULL
    };
    occ = (occ & RankMaskEx[sq]) | OuterSquares[sq];
    return ((occ - ThisAndNextSq[msb(occ & PrevSquares[sq])]) ^ occ)
      & RankMaskEx[sq];
}

uint64_t file_attacks(int sq, uint64_t occ)
{
    static const uint64_t OuterSquares[64] = {
      0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL,
      0x0800000000000000ULL, 0x1000000000000000ULL, 0x2000000000000000ULL,
      0x4000000000000000ULL, 0x8000000000000000ULL, 0x0100000000000001ULL,
      0x0200000000000002ULL, 0x0400000000000004ULL, 0x0800000000000008ULL,
      0x1000000000000010ULL, 0x2000000000000020ULL, 0x4000000000000040ULL,
      0x8000000000000080ULL, 0x0100000000000001ULL, 0x0200000000000002ULL,
      0x0400000000000004ULL, 0x0800000000000008ULL, 0x1000000000000010ULL,
      0x2000000000000020ULL, 0x4000000000000040ULL, 0x8000000000000080ULL,
      0x0100000000000001ULL, 0x0200000000000002ULL, 0x0400000000000004ULL,
      0x0800000000000008ULL, 0x1000000000000010ULL, 0x2000000000000020ULL,
      0x4000000000000040ULL, 0x8000000000000080ULL, 0x0100000000000001ULL,
      0x0200000000000002ULL, 0x0400000000000004ULL, 0x0800000000000008ULL,
      0x1000000000000010ULL, 0x2000000000000020ULL, 0x4000000000000040ULL,
      0x8000000000000080ULL, 0x0100000000000001ULL, 0x0200000000000002ULL,
      0x0400000000000004ULL, 0x0800000000000008ULL, 0x1000000000000010ULL,
      0x2000000000000020ULL, 0x4000000000000040ULL, 0x8000000000000080ULL,
      0x0100000000000001ULL, 0x0200000000000002ULL, 0x0400000000000004ULL,
      0x0800000000000008ULL, 0x1000000000000010ULL, 0x2000000000000020ULL,
      0x4000000000000040ULL, 0x8000000000000080ULL, 0x0000000000000001ULL,
      0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
      0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL,
      0x0000000000000080ULL
    };

    occ = (occ & FileMaskEx[sq]) | OuterSquares[sq];
    return ((occ - ThisAndNextSq[msb(occ & PrevSquares[sq])]) ^ occ)
      & FileMaskEx[sq];
}

Note that RankMaskEx[sq] = Bitboard of the rank mask excluding the bitboard of square 'sq'. For example, RankMaskEx[0] = 0xFE. Similar for the FileMaskEx. ThisAndNextSq[sq] is simply 3ULL << sq. PrevSquares[0] = 1, and PrevSquares[sq] = (1ULL << sq) - 1 for sq > 0. OuterSquares[] is just the bitboard of two (file/rank) edges, but has only the other edge bit set in case the square itself is a edge. This has the exception in case of rank, for OuterSquares[0] = 0x81 not 0x80.

My benchmarks show that this method is at least as fast as HQ, and since it is fully calculation based it'd serve as a good method to complete HQ for completely calculated slider attack mask generation. If you get the idea, then you can easily apply this method to diagonals as well, so it'd work independently of HQ. I have struggled to describe this idea, and the smart ones would understand it anyway.

[cdani]

Welcome back!!

[Aleks Peshkov]

Code: Select all

    Bb attack(SliderType type, Square from) const {
        const Directions& dir = direction[type][from];

        _t a = dir[Horizont] & _mm_sub_epi64(this->_v & dir[Horizont], singleton[from]);
        a ^=   dir[Vertical] & _mm_sub_epi64(this->_v & dir[Vertical], singleton[from]);
        a ^=   dir[Diagonal] & _mm_sub_epi64(this->_v & dir[Diagonal], singleton[from]);
        a ^=   dir[Antidiag] & _mm_sub_epi64(this->_v & dir[Antidiag], singleton[from]);

        return Bb&#123; static_cast<Bb&#58;&#58;_t>( _mm_cvtsi128_si64&#40;hyperbola&#40;a&#41;) ) &#125;;
    &#125;

No branches, no exceptions.

[Gerd Isenberg]

Nice! Since OuterSquares[sq] is forced to be subset of occ, and is guaranteed to intersect PrevSquares[sq], occ & PrevSquares[sq] is always not empty and msb defined. Six instructions + bitscan and some L1 reads - not bad!

You already posted the code in June, 2015
http://www.talkchess.com/forum/viewtopic.php?t=56616
but some more explanations is always fine. Your approach will soon get a cpw-page ...

[vittyvirus]

Nice! Since OuterSquares[sq] is forced to be subset of occ, and is guaranteed to intersect PrevSquares[sq], occ & PrevSquares[sq] is always not empty and msb defined. Six instructions + bitscan and some L1 reads - not bad!

You already posted the code in June, 2015
http://www.talkchess.com/forum/viewtopic.php?t=56616
but some more explanations is always fine. Your approach will soon get a cpw-page ...

Thank you! The CP community is lucky to have people as smart as you.