bitboards like mailbox

[OliverBr]

btw i think the solution has been hiding under my nose all along. in the first post of this thread i linked a thread where a guy wrote a function to get sliding attacks on the fly that was as fast as kindergarten bitboards. olithink uses kindergarten bitboards and is rated 2900. this is proof that it's fast enough
i modified the code bit to use lookup tables instead of calculating the rank/file masks on the fly, they are small so it's not a problem

This is very intriguing. Could you replace the calculation completely with success?

[tcusr]

btw i think the solution has been hiding under my nose all along. in the first post of this thread i linked a thread where a guy wrote a function to get sliding attacks on the fly that was as fast as kindergarten bitboards. olithink uses kindergarten bitboards and is rated 2900. this is proof that it's fast enough
i modified the code bit to use lookup tables instead of calculating the rank/file masks on the fly, they are small so it's not a problem

This is very intriguing. Could you replace the calculation completely with success?

no i didn't try it because i'm starting a new engine from scratch and i will compare perft results later (the other one is using fancy magics)
if you want to try it in olithink here is the code https://talkchess.com/forum3/viewtopic. ... 33#p890486

[tcusr]

i found a way to generate captures without using any functions to generate sliding attacks
it's really simple, for each direction we use the ray mask from the starting square (without including it) and AND it with the enemy bitboard. if we're checking a positive direction (north, north east, north west, east) that means the "to" square is above "from" (https://www.chessprogramming.org/Square ... le_Mapping) and therefore it's the lsb, otherwise it's the msb (to get the square number relative to us we need to do 63 - msb(b).

Code: Select all

U64 rays[8][64];

enum {
	// positive directions (8, 1, 7, 9)
	north,
	east,
	northWest,
	northEast, // 3
	// other directions... (-8, -1, -7, -9)
};

void genCaptureForDir(int from, U64 enemy, int dir)
{
	U64 candidates = rays[dir][from] & enemy;
	int to;
	
	if (candidates) {
		// positive direction, "to" is above "from"
		if (dir < 4)
			to = bsf(candidates)
		else
			to = 63 - bsr(candidates);
		// use to
	}
}

what do you think? is there any way to improve it?
i would like to get rid of the rays table and use some calculation to find the rays, for example for north i can use this https://www.chessprogramming.org/Genera ... iplication

[hgm]

In the old days it could not be done like that, because there was no efficient way to get the most-significant 1 bit. I don't know how this is on modern CPUs.

[tcusr]

In the old days it could not be done like that, because there was no efficient way to get the most-significant 1 bit. I don't know how this is on modern CPUs.

on my 8 year old pc __builtin_clzll compiles to bsr with only -O3 on, it's not going to be a problem

besides this, do you see any improvements?
in my C++ implementation the direction is a template parameter so the only real branch is the one to check if there are enemies in the rays. with all optimizations on the whole function for 4 directions compiles to ~30 instructions, not bad i would say

[hgm]

One thing that I missed before: the closest opponent on a ray is not necessarly a capture. There could be a friendly piece that is even closer blocking that capture. So you would have to intersect with 'occupied' first, then determine the closest through bsf/bsr, and then test whether it is friend or foe.

In fact 30 instructions already sounds like a lot to me. But I don't have much experience with bitboards, and perhaps other bitboard methods are even slower.

[dangi12012]

i found a way to generate captures without using any functions to generate sliding attacks
it's really simple, for each direction we use the ray mask from the starting square (without including it) and AND it with the enemy bitboard. if we're checking a positive direction (north, north east, north west, east) that means the "to" square is above "from" (https://www.chessprogramming.org/Square ... le_Mapping) and therefore it's the lsb, otherwise it's the msb (to get the square number relative to us we need to do 63 - msb(b).

Code: Select all

U64 rays[8][64];

enum {
	// positive directions (8, 1, 7, 9)
	north,
	east,
	northWest,
	northEast, // 3
	// other directions... (-8, -1, -7, -9)
};

void genCaptureForDir(int from, U64 enemy, int dir)
{
	U64 candidates = rays[dir][from] & enemy;
	int to;
	
	if (candidates) {
		// positive direction, "to" is above "from"
		if (dir < 4)
			to = bsf(candidates)
		else
			to = 63 - bsr(candidates);
		// use to
	}
}

what do you think? is there any way to improve it?
i would like to get rid of the rays table and use some calculation to find the rays, for example for north i can use this https://www.chessprogramming.org/Genera ... iplication

Move dir to a template parameter!

Code: Select all

template<int dir>
void genCaptureForDir(int from, U64 enemy)

Suddenly the if else becomes runtime free with if constexpr (dir < 4)

Also U64 candidates = rays[dir][from] & enemy;
should be U64 candidates = rays[dir][from] & occupation;

Because sliders can be blocked by your own pieces too
The code may or may not be good for bitboards depending on the other code. Because the output is in 0..63 space and not in bitboard space.

BUT: There are instructions to get a true bitboard result from your code (with all intermediate squares set to 1) by just calling

Code: Select all

BEXTR (from, to - from, -1); //because -1 = 0xFFFF you get a true bitboard path 

[tcusr]

One thing that I missed before: the closest opponent on a ray is not necessarly a capture. There could be a friendly piece that is even closer blocking that capture. So you would have to intersect with 'occupied' first, then determine the closest through bsf/bsr, and then test whether it is friend or foe.

In fact 30 instructions already sounds like a lot to me. But I don't have much experience with bitboards, and perhaps other bitboard methods are even slower.

yep, you're right. i just change the condition to a bit test instead

Code: Select all

U64 candidates = rays[dir][from] & (friends | enemies);
int to = // bsf or (63 - bsr)....
if (enemies & (1ull << to)) // no shift, uses bt
{
}

[tcusr]

i found a way to generate captures without using any functions to generate sliding attacks
it's really simple, for each direction we use the ray mask from the starting square (without including it) and AND it with the enemy bitboard. if we're checking a positive direction (north, north east, north west, east) that means the "to" square is above "from" (https://www.chessprogramming.org/Square ... le_Mapping) and therefore it's the lsb, otherwise it's the msb (to get the square number relative to us we need to do 63 - msb(b).

Code: Select all

U64 rays[8][64];

enum {
	// positive directions (8, 1, 7, 9)
	north,
	east,
	northWest,
	northEast, // 3
	// other directions... (-8, -1, -7, -9)
};

void genCaptureForDir(int from, U64 enemy, int dir)
{
	U64 candidates = rays[dir][from] & enemy;
	int to;
	
	if (candidates) {
		// positive direction, "to" is above "from"
		if (dir < 4)
			to = bsf(candidates)
		else
			to = 63 - bsr(candidates);
		// use to
	}
}

what do you think? is there any way to improve it?
i would like to get rid of the rays table and use some calculation to find the rays, for example for north i can use this https://www.chessprogramming.org/Genera ... iplication

Move dir to a template parameter!

Code: Select all

template<int dir>
void genCaptureForDir(int from, U64 enemy)

Suddenly the if else becomes runtime free with if constexpr (dir < 4)

Also U64 candidates = rays[dir][from] & enemy;
should be U64 candidates = rays[dir][from] & occupation;

Because sliders can be blocked by your own pieces too
The code may or may not be good for bitboards depending on the other code. Because the output is in 0..63 space and not in bitboard space.

BUT: There are instructions to get a true bitboard result from your code (with all intermediate squares set to 1) by just calling

Code: Select all

BEXTR (from, to - from, -1); //because -1 = 0xFFFF you get a true bitboard path 

but i want to get a 0...63 value because i will add the from and to squares to the move list

[hgm]

All this still seems very slow compared to a neighbor table, from which you read the square numbers of the move targets directly. Then it would just be a matter of loading the from-square, and using it as an index register for 4 load instructions to fetch the to-squares, 5 instructions in total. Of course you would have the overhead of updating the neigbor table as a prequel to move generation, but for these 4 directions that would just require loading the square that the latest move evacuated, using it as an index to load the square numbers of its 4 neighbors, and store those 4 square numbers indexed by each other. That is only 9 instructions. (But it would also take 9 instructions to undo that during UnMake().)