SBAMG - Completing Hyperbola Quintessence
Posted: Wed Apr 13, 2016 9: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:
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.
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];
}
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.