SBAMG - Completing Hyperbola Quintessence

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

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

SBAMG - Completing Hyperbola Quintessence

Post by vittyvirus » Wed Apr 13, 2016 7:58 am

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.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: SBAMG - Completing Hyperbola Quintessence

Post by cdani » Wed Apr 13, 2016 1:01 pm

Welcome back!! :D

Aleks Peshkov
Posts: 870
Joined: Sun Nov 19, 2006 8:16 pm
Location: Russia

Re: SBAMG - Completing Hyperbola Quintessence

Post by Aleks Peshkov » Wed Apr 13, 2016 3:07 pm

Code: Select all

    Bb attack&#40;SliderType type, Square from&#41; const &#123;
        const Directions& dir = direction&#91;type&#93;&#91;from&#93;;

        _t a = dir&#91;Horizont&#93; & _mm_sub_epi64&#40;this->_v & dir&#91;Horizont&#93;, singleton&#91;from&#93;);
        a ^=   dir&#91;Vertical&#93; & _mm_sub_epi64&#40;this->_v & dir&#91;Vertical&#93;, singleton&#91;from&#93;);
        a ^=   dir&#91;Diagonal&#93; & _mm_sub_epi64&#40;this->_v & dir&#91;Diagonal&#93;, singleton&#91;from&#93;);
        a ^=   dir&#91;Antidiag&#93; & _mm_sub_epi64&#40;this->_v & dir&#91;Antidiag&#93;, singleton&#91;from&#93;);

        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
Posts: 2125
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: SBAMG - Completing Hyperbola Quintessence

Post by Gerd Isenberg » Wed Apr 13, 2016 7:20 pm

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 ...

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

Re: SBAMG - Completing Hyperbola Quintessence

Post by vittyvirus » Tue Apr 19, 2016 12:08 pm

Gerd Isenberg wrote: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. :)

Post Reply