Most efficient way to generate legal king moves?

[H.G.Muller]

Ah, you are right, but I was thinking of the King moves. I often do take account of pins, if circumstances allow it. E.g. in Joker (of which I never published the source code, but which is based on qperft, which I did publish) I do determine pinned pieces in advance, to generate their moves along the pin line, and mark them as captured during the normal move generation. This does save time in the full-width search.

But in QS I often use 'reverse' move generation, where I loop through all possible opponent pieces from high to low, to test what can capture them, rather than through my own pieces to see what they can capture. This is slightly more difficult (because you have either to look in all 8 directions, or consider all 8 pieces in the piece list as attackers, rather than just in the directions the piece moves). But you usually have to do it for only a subset of the possible victims. Because you can stop when you reach victims not valuable enough to bring the score above beta even if you can capture them and they are not protected. And because you can immediately start searching as soon as you have generated the move of the most-valuable victim, a beta cutoff would save you the trouble of generating the captures on the remaining victims. Knowing what is pinned in that case is not very helpful. The pinned piece might just have one capture, or no captures at all, on any victim of interest.

I guess the lesson is that perft speed can be a very misleading measure for the speed of an engine. Because it puts far too much weight on generation of a complete move set, and ensuring their legality. While in an engine 85% of the nodes are QS nodes, where you only want to generate captures, and perhaps even a subset of those (with valuable-enough victims). Generating all moves, extracting the captures and sorting those is a very inefficient way to do that, no matter how efficiently you generated all moves.

My currently favorite design (that I am stillworking on) is to replace the move list in QS by a 'capture map', which has a a bit assigned to every (victim, attacker) pair (so 256 bits in total per side). These bits are assigned in the order QS would want to search them. Then to add ore remove captures one would just have to set or clear the corresponding bits, by OR and AND operations. And there would never have to be any sorting, as they would be extracted automatically in the desired order. Each piece would have a victimMask and an attackerMask that can be used to clear or isolate all moves that capture it, or all moves with it, (e.g. to remove these in case the piece gets captured, or moves elsewhere). This makes it easy to update the set of possible captures incrementally.

By also keeping such capture maps for captures of own pieces (i.e.protectors) a piece that captures another can simply inherit all the attacks on it. The moves of sliders that could capture a piece that moved away would have to be exteded to the target downstream, which is also easy if the capture map already tells which pieces attacked it, and you kept a view_distace table to immediately tell you where 'downstream' is.

[notachessplayer]

I see. Thanks for all your knowledge.

I wasn't interested in pseudo-legal moves until now, because it felt too simplistic, but there actually seems to be a lot of room for creativity in this field.
Though I guess, even though I first got into chess programming (2 months ago..) to have the pride of building my own AI, a fast move generation gave me the most satisfaction so far, which is why I'm not really considering search optimization in my posts.

Btw, I found your website and tried to execute "qperft", but it won't launch, and the code won't compile without errors. Also, you've been interested in chess programming for 40 years No wonder you have so much information to share!

[thevinenator]

There is so much info here I didn't know where to interject.

as part of the "super piece" idea, I also, prior to calling the code to see if a sliding piece can attack the king, do a "between[64][64]" lookup using the square of the king and the square of the possible attacking piece. if the lookup has nothing in between (not on same file/rank, based on piece type), then there is no reason to check to see if the king is really attacked. ya, I k now, bad, bad memory lookup, but it is overall faster.

I'm think there is a more compact way to represent this lookup for this specific test, but I haven't dived into that yet.

[thevinenator]

There is so much info here I didn't know where to interject.

as part of the "super piece" idea, I also, prior to calling the code to see if a sliding piece can attack the king, do a "between[64][64]" lookup using the square of the king and the square of the possible attacking piece. if the lookup has nothing in between (not on same file/rank, based on piece type), then there is no reason to check to see if the king is really attacked. ya, I k now, bad, bad memory lookup, but it is overall faster.

I'm think there is a more compact way to represent this lookup for this specific test, but I haven't dived into that yet.

one forgets one own code...here is how i use in-between...

Code: Select all

	while (BSF64(&From, brq))
		{
		//BSF64(&From, brq);
		//PrintBitboard(bbInBetween[From][sqr], "in between");
		if (!(bbInBetween[From][sqr] & occupied))
			return true;

		brq &= brq - 1;
		}

brq bitboard is first populated with the locations of opponents queens and bishops
the loop grabs the next 'on' bit (location of either a queen or bishop) and then the in-between squares are masked with the occupied (white and black pieces). if the result is zero, then the piece on From is attacking the square.

brq is then set to the location of the rooks and queen and the check is done again.

[notachessplayer]

I think the super piece is a slower alternative, but I might have missed a good idea while explorating this option.

What I ended up doing, even if still not the best, was to check both squares that an enemy pawn could occupy to put the king in check (while also checking if it's anything except a rook or knight, because they wouldn't attack the king there). Only then do I try my other pieces, starting with leapers, and then sliders (no need for pawns).

A simple look up can be done to see if an attack is possible (all pieces have an attack table that gives the direction of attack, or 0), only if it's not 0 do I check if the squares are not occupied.

This solution really improved the speed, rather than looping through all my alive pieces and doing the same test (I stopped at 965ms for perft 6, because it was becoming an obsession lol).

What exactly is stored in your bbInBetween table? Does it need to be updated every move?

[thevinenator]

What exactly is stored in your bbInBetween table? Does it need to be updated every move?

it is defined as this:

const U64 bbInBetween[64][64];

it is static, it never changes. I store the pre-calculated values in the array in code. The code I used to generate this is hiding somewhere, but I don't generated it each time the program starts up. I have a LOT of bitboards, as most do, and I didn't want to have them all generated each time the program starts, so I wrote code to generate the data which I store in a module. it actually saves program space since I don't need to keep the generating code active.

it is only used for sliding pieces, so it is very sparse. "between" also means there has to be a space between two pieces to allow for a bit to be set. So, if there is a piece on square 0 (a1), and a piece on square 1 (b1), the lookup will return 0 because there isn't any squares between them. but for square 0 (a1) and square 2 (c1), the bit representing b1 (value of 2 because it is the 2nd square) will be set.

here is an example for Square 0 (a1). the index gets bigger reading left to right, top to bottom. so, to answer the question, what are the squares between square 0 and square 2, you use bbInBetween[0][2], and the third element of this array is the value 0x0000000000000002ULL (2). this corresponds to square b1. this is valid because rooks slide along ranks and files (in this case). so if the king is on a1 and the rook is on c1, b1 is the square between them.

for bishops, only the diagonal bits are set. so a king on a1, a bishop on d4, we look up [0][27] and get 0x0000000000040200ULL, which in binary is
0100 0000 0010 0000 0000 with the low bits on the right. so for this value, bits 9 and 18 are set, representing squares b2, and c3, the two squares between a1 and d4.

the nice thing is, that there isn't any overlap, because there aren't any situations where a any pairs of squares can have both bishop and rook moves at the same time.

it isn't difficult to generate the data. I did it the non-bitboard way using rank/file tests to see if the square pairs are valid. I think there are some ideas of how to do it on the wiki pages

Code: Select all

const U64 bbInBetween[64][64] = {
	// Square:0
	0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000002ULL, 0x0000000000000006ULL, 
	0x000000000000000EULL, 0x000000000000001EULL, 0x000000000000003EULL, 0x000000000000007EULL, 
	0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000000000100ULL, 0x0000000000000000ULL, 0x0000000000000200ULL, 0x0000000000000000ULL, 
	0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000000010100ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000040200ULL, 
	0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000001010100ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000008040200ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000101010100ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000000000000ULL, 0x0000001008040200ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000010101010100ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000201008040200ULL, 0x0000000000000000ULL, 
	0x0001010101010100ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 
	0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0040201008040200ULL,

It is used in the "is square attacked" code, but I also use it to determine if rooks are connected. you use the array to fetch an element using the locations of the two rooks as indices, and then take that value and "and it" with the occupied bits, and if it is zero, they are connected.

hope this helps