Combining two of Bob's classic bitboard attack getters

[tcusr]

why is it faster if the table available at compile? what kind of optimization does the compiler do?

thank you for your tests! would my mind adding hyperbola quintessence?

I dont mind adding it. Do you have a repo where it is implemented?
Ideally i would have 1 file with this interface:

Code: Select all

void Init()
uint64_t Queen(int sq, uint64_t occ)

So please send me an URL!

https://github.com/abulmo/hqperft/blob/ ... rft.c#L437
i can do the translation to C++ if you want

it was faster because I replaced old msvc intrinsic the std::countlz.
constexpr does not make it faster when its unknown.

exactly, that's why i was wondering. you're penalizing code like kogge stone that doesn't use lookup tables.
will you publish the code of your tests?

[dangi12012]

https://github.com/abulmo/hqperft/blob/ ... rft.c#L437
i can do the translation to C++ if you want
...
will you publish the code of your tests?

Yes please - it should be one self contained file with Init()
Yes I will publish all lookups together with my new hypercube lookup on the other thread.

There will be the comparison of ALU usage - Thread scaling - and Memory consumption and the overall lookup performance.
All algos use a maximum of less than 1MB for lookup.

[tcusr]

https://github.com/abulmo/hqperft/blob/ ... rft.c#L437
i can do the translation to C++ if you want
...
will you publish the code of your tests?

Yes please - it should be one self contained file with Init()
Yes I will publish all lookups together with my new hypercube lookup on the other thread.

There will be the comparison of ALU usage - Thread scaling - and Memory consumption and the overall lookup performance.
All algos use a maximum of less than 1MB for lookup.

it's buggy, i don't know where the mistake is

Code: Select all

#include <cstdint>
#include <array>

constexpr uint64_t byteswap(uint64_t b)
{
	return __builtin_bswap64(b);
}

constexpr uint64_t to_bit(int s)
{
	return 1ULL << s;
}

constexpr bool safe_coord(int f, int r)
{
	return (0 <= f && f < 8) && (0 <= r && r < 8);
}

constexpr uint64_t init_mask(int s, int df, int dr)
{
	uint64_t b{};
	int f, r;

	f = s & 7;
	r = s >> 3;
	while (safe_coord(f, r)) {
		b |= to_bit(f + r * 8);

		f += df;
		r += dr;
	}

	return b;
}

template<typename F>
constexpr auto init_array(F&& f)
{
	std::array<uint64_t, 64> a{};

	for (int s = 0; s < 64; ++s)
		a[s] = f(s);

	return a;
}

constexpr auto file_mask{ init_array([](int s) {
		return init_mask(s, 0, 1) | init_mask(s, 0, -1);
}) };

constexpr auto a1h8_mask{ init_array([](int s) {
		return init_mask(s, 1, 1) | init_mask(s, -1, -1);
}) };

constexpr auto h1a8_mask{ init_array([](int s) {
		return init_mask(s, -1, 1) | init_mask(s, 1, -1);
}) };

constexpr int init_rank_table(int o, int f)
{
	int x, y;
	int b;

	y = 0;
	for (x = f - 1; x >= 0; --x) {
		b = 1 << x;
		y |= b;
		if ((o & b) == b) break;
	}
	for (x = f + 1; x < 8; ++x) {
		b = 1 << x;
		y |= b;
		if ((o & b) == b) break;
	}
	return y;
}

constexpr auto rank_table{ [] {
	std::array<int, 512> a{};

	for (int s = 0; s < 64; ++s) {
		for (int f = 0; f < 8; ++f)
			a[s * 8 + f] = init_rank_table(s * 2, f);
	}

	return a;
} () };

constexpr uint64_t sliding_attack(int s, uint64_t mask, uint64_t occ)
{
	occ &= mask;

	return ((occ - to_bit(s)) ^ byteswap(byteswap(occ) - to_bit(s ^ 56))) & mask;
}

constexpr uint64_t rank_attack(int s, uint64_t occ)
{
	int f{ s & 7 };
	int r{ s & 56 };
	uint64_t o = (s >> r) & 126;

	return (static_cast<uint64_t>(rank_table[o * 4  + f])) << r;
}

constexpr uint64_t bishop_attacks(int s, uint64_t occ)
{
	return sliding_attack(s, a1h8_mask[s], occ) | sliding_attack(s, h1a8_mask[s], occ);
}

constexpr uint64_t rook_attacks(int s, uint64_t occ)
{
	return sliding_attack(s, file_mask[s], occ) | rank_attack(s, occ);
}

uint64_t Queen(int sq, uint64_t occ)
{
	return rook_attacks(sq, occ) | bishop_attacks(sq, occ);
}

void Init()
{
}

[dangi12012]

it's buggy, i don't know where the mistake is

Maybe you can the bug with this blocker config: 6822289156618217916?

Code: Select all

Occupy: 6822289156618217916
..XXXX.X
X..X.XX.
.X.XXX..
XXX....X
XXX.X.XX
XX...X.X
X.XX.X.X
.XXXX.X.

Solution:
XX.X....
.XXX....
X.X.....
..X.....
........
........
........
........

Error:
.X.XXXXX
........
........
........
........
........
........
........

So you have one example where it fails.

If the code wouldnt change much the performance would be like this: <436.17MOps> which is fast.

Code: Select all

Megalookups/s:
Expload:        105.99MOps
Reference:      122.87MOps
KoggeStone:     112.79MOps
BobMike:        204.84MOps
XorRookSub:     436.17MOps
FancyHash:      497.11MOps
Pext  :         845.92MOps
HyperLookup:    912.57MOps

Take with a grain of salt since XorRookSub is buggy code. (Maybe we find a better name???)
https://www.chessprogramming.org/Subtra ... king_Piece

[Mike Sherwin]

Update:
Sometimes I wonder how verbose the code is from other people. It hides the simple lookup code which is really just that:
Robert Hyatt's and Michael Sherwin's classical bitboard approach is this:

Code: Select all

uint64_t Queen(int sq, uint64_t occ) {
		uint64_t result = 0;
		occ |= 0x8000000000000001;

		result |= ray[sq].rayNW ^ ray[std::countr_zero(ray[sq].rwsNW & occ)].rayNW;
		result |= ray[sq].rayNN ^ ray[std::countr_zero(ray[sq].rwsNN & occ)].rayNN;
		result |= ray[sq].rayNE ^ ray[std::countr_zero(ray[sq].rwsNE & occ)].rayNE;
		result |= ray[sq].rayEE ^ ray[std::countr_zero(ray[sq].rwsEE & occ)].rayEE;

		result |= ray[sq].raySE ^ ray[63 - std::countl_zero(ray[sq].rwsSE & occ)].raySE;
		result |= ray[sq].raySS ^ ray[63 - std::countl_zero(ray[sq].rwsSS & occ)].raySS;
		result |= ray[sq].raySW ^ ray[63 - std::countl_zero(ray[sq].rwsSW & occ)].raySW;
		result |= ray[sq].rayWW ^ ray[63 - std::countl_zero(ray[sq].rwsWW & occ)].rayWW;

		return result;
	}

I see why this was done. Because 15 years ago the compilers didnt resolve the dependency chain in a good way.

This lookup is nice and clean. Just how it should be done. This can be improved by defining the rwsSE in a different way so that the inner 63 - will go away.
But that should be done by the original authors! - are they still active here or on other boards?

Hey Daniel,

Bob (Robert Hyatt) does not seem to be active anywhere. As for Michael Sherwin well that's me! Bob and I did not collaborate on this method. I took his "^" technique into my classical approach and used the idea of the stop bit so that _BitScan(Forward/Reverse)64 would never be given a zero source bitboard to work with thus cancelling the need for an "if" statement per bit scan. The reason I wrote it the way I did was to mimic the way I'd write it in assembler. Because that is my next goal. And I wanted to show visibly that there really are no dependency chains as every line of C code does not depend on another (except at the very beginning and end).

Really what I am trying to do is improve on this code from the CPW that I believe was written by (Gerd Isenberg?).

As mentioned by Robert Hyatt [2], instead of fetching four ray-attacks on the otherwise empty board, one may already use the rook- or bishop attacks to reset outer squares from that union set.

A further improvement was suggested by Michael Sherwin [3], to union the occupancy with the outer bits 0 and 63. Together with appropriate bits set in separate ray-masks, this yields to an efficient branchless solution with 13 64-bit operations in total and 4.5 KByte for the lookup tables for both rooks and bishops each.

Code: Select all

struct {
  U64 bitsN;  // bits North, including MSB (bit 63)
  U64 bitsE;  // bits East, including MSB
  U64 bitsS;  // bits South, including LSB (bit 0 == 1)
  U64 bitsW;  // bits West, including LSB 
} CACHE_ALIGN rayWstop[64]; 

U64 attacksEmpty[64];
U64 rayN[64];
U64 rayE[64];
U64 rayS[64];
U64 rayW[64];

U64 rookAttacks(U64 occ, unsigned int sq) {
   unsigned long ulN, ulE, ulS, ulW;
   occ |= C64(0x8000000000000001);
   _BitScanForward64(&ulN, occ & rayWstop[sq].bitsN);
   _BitScanForward64(&ulE, occ & rayWstop[sq].bitsE);
   _BitScanReverse64(&ulS, occ & rayWstop[sq].bitsS);
   _BitScanReverse64(&ulW, occ & rayWstop[sq].bitsW);
   return attacksEmpty[sq]^rayN[ulN]^rayE[ulE]^rayS[ulS]^rayW[ulW];
} 

Now that I know about std::count* (thanks!) I will investigate those instructions. Do they need a stop bit?

[dangi12012]

U64 rookAttacks(U64 occ, unsigned int sq) {
unsigned long ulN, ulE, ulS, ulW;
occ |= C64(0x8000000000000001);
_BitScanForward64(&ulN, occ & rayWstop[sq].bitsN);
_BitScanForward64(&ulE, occ & rayWstop[sq].bitsE);
_BitScanReverse64(&ulS, occ & rayWstop[sq].bitsS);
_BitScanReverse64(&ulW, occ & rayWstop[sq].bitsW);
return attacksEmpty[sq]^rayN[ulN]^rayE[ulE]^rayS[ulS]^rayW[ulW];
} [/code]
Now that I know about std::count* (thanks!) I will investigate those instructions. Do they need a stop bit?

Hey thats a really insightful comment!
No they dont need a stop bit. The result for 0ull is 64. So maybe that can be solved with an "empty" ray at index 64 that just has 0 stored?
What I was thinking of because this is a multiple of 4 - maybe all the bitscans can be looked up with AVX2 and a debrujin table in a bulk operation.

Something like this - but with all 8 rays in a few avx2 operations.

Code: Select all

	const int index64[64] = {
	0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6
	};

	int bitScanForward(uint64_t bb) {
		if (bb == 0) return 64;
		return index64[(_blsi_u64(bb) * 0x03f79d71b4cb0a89ull) >> 58];
	}

[Mike Sherwin]

Apparently a neural pathway has just connected in my brain because I finally understand Gerd's code using Bob's idea. Starting with all attacks on an empty board is better than looking up seperate rays for the operation. Okay back to work!

[dangi12012]

thank you for your tests! would my mind adding hyperbola quintessence?

Update: I translated your URL to C++ and it compiles. Here is "subtracting a rook from occupy" in its full glory:

Code: Select all

#include <stdint.h>
#include <array>

namespace Chess_Lookup::XorRookSub {
typedef uint64_t Bitboard;
typedef uint64_t Random;

struct Mask {
	Bitboard diagonal;
	Bitboard antidiagonal;
	Bitboard vertical;
};

/* Generate rank attack to fill the RANK_ATTACK array. */
constexpr int generate_rank_attack(int o, int  f) {
	int x, y;
	int b;

	y = 0;
	for (x = f - 1; x >= 0; --x) {
		b = 1 << x;
		y |= b;
		if ((o & b) == b) break;
	}
	for (x = f + 1; x < 8; ++x) {
		b = 1 << x;
		y |= b;
		if ((o & b) == b) break;
	}
	return y;
}

/* Initialize some global constants */
constexpr std::array<Mask, 64> InitMask() {
	int r, f, i, j;
	int x, y;
	int d[64][64];

	std::array<Mask, 64> MASK{};

	for (x = 0; x < 64; ++x) {
		for (y = 0; y < 64; ++y) d[x][y] = 0;
		// directions
		for (i = -1; i <= 1; ++i)
			for (j = -1; j <= 1; ++j) {
				if (i == 0 && j == 0) continue;
				f = x & 07;
				r = x >> 3;
				for (r += i, f += j; 0 <= r && r < 8 && 0 <= f && f < 8; r += i, f += j) {
					y = 8 * r + f;
					d[x][y] = 8 * i + j;
				}
			}

		// bitboard mask
		Mask& mask = MASK[x];
		mask.diagonal = 0;
		for (y = x - 9; y >= 0 && d[x][y] == -9; y -= 9) mask.diagonal |= (1ull << y);
		for (y = x + 9; y < 64 && d[x][y] == 9; y += 9) mask.diagonal |= (1ull << y);
		mask.antidiagonal = 0;
		for (y = x - 7; y >= 0 && d[x][y] == -7; y -= 7) mask.antidiagonal |= (1ull << y);
		for (y = x + 7; y < 64 && d[x][y] == 7; y += 7) mask.antidiagonal |= (1ull << y);
		mask.vertical = 0;
		for (y = x - 8; y >= 0; y -= 8) mask.vertical |= (1ull << y);
		for (y = x + 8; y < 64; y += 8) mask.vertical |= (1ull << y);
	}
	return MASK;
}

constexpr std::array<uint8_t, 512> InitRank() {

	std::array<uint8_t, 512> rank_attack{};

	for (int x = 0; x < 64; ++x) {
		for (int f = 0; f < 8; ++f) {
			rank_attack[x * 8 + f] = generate_rank_attack(x * 2, f);
		}
	}
	return rank_attack;
}

constexpr std::array<Mask, 64> MASK = InitMask();
constexpr std::array<uint8_t, 512> RANK_ATTACK = InitRank();


/* Byte swap (= vertical mirror) */
Bitboard bit_bswap(Bitboard b) { 
#if defined(_MSC_VER)
	return _byteswap_uint64(b);
#elif defined(__GNUC__)
	return __builtin_bswap64(b);
#else
	b = ((b >> 8) & 0x00FF00FF00FF00FFULL) | ((b << 8) & 0xFF00FF00FF00FF00ULL);
	b = ((b >> 16) & 0x0000FFFF0000FFFFULL) | ((b << 16) & 0xFFFF0000FFFF0000ULL);
	b = ((b >> 32) & 0x00000000FFFFFFFFULL) | ((b << 32) & 0xFFFFFFFF00000000ULL);
	return b;
#endif
}

/* Generate attack using the hyperbola quintessence approach */
Bitboard attack(const Bitboard pieces, const uint32_t x, const Bitboard mask) {
	Bitboard o = pieces & mask;

	return ((o - (1ull << x)) ^ bit_bswap(bit_bswap(o) - (1ull << (x ^ 56)))) & mask;
}

/* Generate attack for ranks. */
Bitboard rank_attack(const Bitboard pieces, const uint32_t x) {
	uint32_t file_mask = x & 7;
	uint32_t rank_mask = x & 56;
	Bitboard o = (pieces >> rank_mask) & 126;

	return ((Bitboard)RANK_ATTACK[o * 4 + file_mask]) << rank_mask;
}

/* Generate attack for files. */
Bitboard vertical_attack(const Bitboard pieces, const uint32_t x) {
	return attack(pieces, x, MASK[x].vertical);
}

/* Generate diagonal attack */
Bitboard diagonal_attack(const Bitboard pieces, const uint32_t x) {
	return attack(pieces, x, MASK[x].diagonal);
}

/* Generate antidiagonal attack */
Bitboard antidiagonal_attack(const Bitboard pieces, const uint32_t x) {
	return attack(pieces, x, MASK[x].antidiagonal);
}

/* Generate bishop attack */
Bitboard bishop_attack(const Bitboard pieces, const uint32_t x) {
	return diagonal_attack(pieces, x) | antidiagonal_attack(pieces, x);
}

/* Generate rook attack */
Bitboard rook_attack(const Bitboard pieces, const uint32_t x) {
	return vertical_attack(pieces, x) | rank_attack(pieces, x);
}

uint64_t Queen(int sq, uint64_t occ) {
	return bishop_attack(occ, sq) | rook_attack(occ, sq);
}
}

Maybe we need a good name for the algorithm? Subtracting Rook from occupy is quite verbose.

The speed looks fine to me: <319.81MOps> and it produces correct result.
I like this assortment since these are all algorithms with completely different ideas.

Code: Select all

Megalookups/s:
Expload:        106.70MOps
Reference:      120.46MOps
KoggeStone:     113.22MOps
BobMike:        215.18MOps
XorRookSub:     319.81MOps
FancyHash:      502.68MOps
Pext  :         854.68MOps
HyperLookup:    919.23MOps

[dangi12012]

A clean sourcecode to "subtracting a rook from occupy"

Code: Select all

#include <stdint.h>
#include <array>
#include <type_traits>

namespace Chess_Lookup::XorRookSub {
	struct Mask {
		uint64_t diagonal;
		uint64_t antidiagonal;
		uint64_t vertical;
	};

	/* Init */
	constexpr std::array<Mask, 64> InitMask() {
		int r, f, i, j, y;
		int d[64];

		std::array<Mask, 64> MASK{};

		for (int x = 0; x < 64; ++x) {
			for (y = 0; y < 64; ++y) d[y] = 0;
			// directions
			for (i = -1; i <= 1; ++i)
				for (j = -1; j <= 1; ++j) {
					if (i == 0 && j == 0) continue;
					f = x & 07;
					r = x >> 3;
					for (r += i, f += j; 0 <= r && r < 8 && 0 <= f && f < 8; r += i, f += j) {
						y = 8 * r + f;
						d[y] = 8 * i + j;
					}
				}

			// uint64_t mask
			Mask& mask = MASK[x];
			for (y = x - 9; y >= 0 && d[y] == -9; y -= 9) mask.diagonal |= (1ull << y);
			for (y = x + 9; y < 64 && d[y] == 9; y += 9) mask.diagonal |= (1ull << y);

			for (y = x - 7; y >= 0 && d[y] == -7; y -= 7) mask.antidiagonal |= (1ull << y);
			for (y = x + 7; y < 64 && d[y] == 7; y += 7) mask.antidiagonal |= (1ull << y);

			for (y = x - 8; y >= 0; y -= 8) mask.vertical |= (1ull << y);
			for (y = x + 8; y < 64; y += 8) mask.vertical |= (1ull << y);
		}
		return MASK;
	}
	constexpr std::array<uint8_t, 512> InitRank() {

		std::array<uint8_t, 512> rank_attack{};

		for (int x = 0; x < 64; ++x) {
			for (int f = 0; f < 8; ++f) {
				int o = 2 * x;
				int x2, y2;
				int b;

				y2 = 0;
				for (x2 = f - 1; x2 >= 0; --x2) {
					b = 1 << x2;
					y2 |= b;
					if ((o & b) == b) break;
				}
				for (x2 = f + 1; x2 < 8; ++x2) {
					b = 1 << x2;
					y2 |= b;
					if ((o & b) == b) break;
				}
				rank_attack[x * 8 + f] = y2;
			}
		}
		return rank_attack;
	}
	constexpr std::array<Mask, 64> MASK = InitMask();
	constexpr std::array<uint8_t, 512> RANK_ATTACK = InitRank();



	/* Start of Code */
	constexpr uint64_t bit_bswap_constexpr(uint64_t b) {
		b = ((b >> 8) & 0x00FF00FF00FF00FFULL) | ((b << 8) & 0xFF00FF00FF00FF00ULL);
		b = ((b >> 16) & 0x0000FFFF0000FFFFULL) | ((b << 16) & 0xFFFF0000FFFF0000ULL);
		b = ((b >> 32) & 0x00000000FFFFFFFFULL) | ((b << 32) & 0xFFFFFFFF00000000ULL);
		return b;
	}

	constexpr uint64_t bit_bswap(uint64_t b) {
		if (std::is_constant_evaluated()) { return bit_bswap_constexpr(b); }
	#if defined(_MSC_VER)
		return _byteswap_uint64(b);
	#elif defined(__GNUC__)
		return __builtin_bswap64(b);
	#else
		return bit_bswap_constexpr(b); 
	#endif
	}

	/* Generate attack using the hyperbola quintessence approach */
	constexpr uint64_t attack(uint64_t pieces, uint32_t x, uint64_t mask) {
		uint64_t o = pieces & mask;

		return ((o - (1ull << x)) ^ bit_bswap(bit_bswap(o) - (1ull << (x ^ 56)))) & mask;
	}

	constexpr uint64_t horizontal_attack(uint64_t pieces, uint32_t x) {
		uint32_t file_mask = x & 7;
		uint32_t rank_mask = x & 56;
		uint64_t o = (pieces >> rank_mask) & 126;

		return ((uint64_t)RANK_ATTACK[o * 4 + file_mask]) << rank_mask;
	}

	constexpr uint64_t vertical_attack(uint64_t pieces, uint32_t x) {
		return attack(pieces, x, MASK[x].vertical);
	}

	constexpr uint64_t diagonal_attack(uint64_t pieces, uint32_t x) {
		return attack(pieces, x, MASK[x].diagonal);
	}

	constexpr uint64_t antidiagonal_attack(uint64_t pieces, uint32_t x) {
		return attack(pieces, x, MASK[x].antidiagonal);
	}


	constexpr uint64_t bishop_attack(int sq, uint64_t occ) {
		return diagonal_attack(occ, sq) | antidiagonal_attack(occ, sq);
	}

	constexpr uint64_t rook_attack(int sq, uint64_t occ) {
		return vertical_attack(occ, sq) | horizontal_attack(occ, sq);
	}

	constexpr uint64_t Queen(int sq, uint64_t occ) {
		return bishop_attack(sq, occ) | rook_attack(sq, occ);
	}
}

more infos in post above.

[tcusr]

are you sure the code is correct?
i used your cleaned up code

Code: Select all

for (int i = 0; i < 64; ++i)
		_map(XorRookSub::Queen(i, 0xffull<<6)),getchar();