Most efficient way to generate legal king moves?

[notachessplayer]

I'm using a 12x10 board representation.
I'm currently stuck at 1.8s for a perft 6 (c++), but the way I generate king moves is highly inefficient.

For each king move, I execute it and loop through each enemy piece to see if I put it in check.
For both castlings, I loop through each enemy piece and see if they attack the two squares adjacent to the king.

The first problem is not as slow as the second, but is the most consistent and therefore the most time consuming.
The second is very slow but only occurs when all the squares between king and rooks are empty, and castling permissions are up. I still really want to completely change the logic.

I have a few ideas, mostly incremental, but they seem like a mess to implement and prone to errors, which I'm tired to fix. Does anyone have a clean solution for this problem?

As a bonus to not make another thread: is it, in your experience, more efficient to add a "dead" boolean to each piece and verify each time you loop, or place dead pieces at the end of your array and keep track of the count so you don't have to check if the piece is dead anymore?

This is a sample code that verifies that my king is not in check:

Code: Select all

Piece** board = game.getBoard();
Piece* enemyPieces = game.getPieces()[1 - piece.side];
board[toSquare] = &piece;
board[piece.square] = (Piece*)&piece::NO_PIECE;
for (int i = 0; i < 16; i++) {
	Piece& ePiece = enemyPieces[i];
	if (!ePiece.dead && ePiece != toPiece) {
		if (sqattack::attacksSquare(ePiece, toSquare, game)) {
			board[piece.square] = &piece;
			board[toSquare] = &toPiece;
			return true;
		}
	}
}
board[piece.square] = &piece;
board[toSquare] = &toPiece;
return false;

[H.G.Muller]

It depends on how you determine if the piece attacks the King. In qperft I loop through the opponent slider and leaper lists after performing the King move. But in stead of generating all moves for these pieces, I first check if they are aligned with the King in a way that they could give check. For this I test

match = capture_code[location[king] - location[piece]] & code[piece]

If this is zero, the piece cannot possibly capture the King, and I am done with that piece. If it is non-zero I test

match & C_DISTANT

to tell me if the move from piece to king is blockable; if not, I am in check. If it is blockable, I have to scan the ray between piece and King, to test if it is empty. For this I consult the table

vector_to_step[location[king] - location[piece]]

that tells me in which direction I have to step over the board to move along the ray, starting at the piece, to reach the King. Because you rarely reach this stage, it doesn't matter that it is slow. (But it is still 4 or 8 times faster than generating all moves of the piece, as you only move in one of the directions.)

For Pawn checks I just test the two squares from which they could possibly come for being occupied by an enemy Pawn.

Note this only works when the difference between two square numbers uniquely determines the board step. Which is not the case on a 10x12 board, where the difference between h5 and a6 (3) is the same as between a5 and d5, while the latter is a Rook move, and the former is no valid move for any piece. This is why I use a 16x12 board.

To indicate a piece is captured I do no use a separate variable, but an invalid square number (e.g. -1). Because when the piece is not dead, I must use its location, and it is faster to already have it than first having to fetch it from another memory location.

Note there is an alternative method, which generates all Queen and Knight moves starting from the King (like the latter is a 'super-piece' that combines the moves of all other pieces), and when I hit an enemy piece that way, test if it has the reciprocal move. This is as expensive as generating all moves of one Queen + one Knight. But that sounds worse than it is in practice, because the King is usually boxed in by his own pieces, so that Queen moves do not get very far.

[notachessplayer]

I already do all that

I might gain another 0.3s by adding an attack table for each piece, though.

But in stead of generating all moves for these pieces, I first check if they are aligned with the King in a way that they could give check.

I do not generate moves, I just move the king, and check for each piece if it attacks the king. Here is a sample code for the rook:

Code: Select all

bool sqattack::rookAttacks(Piece& piece, int square, Game& game) {
	Piece** board = game.getBoard();
	int direction = square - piece.square;

	if (direction % 10 == 0) {
		direction = square > piece.square ? 10 : -10;
	}
	else if (RANKS[piece.square] == RANKS[square]) {
		direction = square > piece.square ? 1 : -1;
	}
	else {
		return false;
	}
	int nextSquare = piece.square + direction;
	Piece* nextPiece = board[nextSquare];
	while (nextSquare != square) {
		if (*nextPiece != piece::NO_PIECE) {
			return false;
		}
		nextSquare += direction;
		nextPiece = board[nextSquare];
	}
	return true;
}

What I should remove is the modulo test, and instead just create a table with the difference of the two squares as the index that contains the direction.

[H.G.Muller]

The modulo operation is sort of infinitely slow on most CPUs, and a single modulo per node in Crafty to derive the hash index from the key slow edit down by 30%. If statements cause branch mispredictions, which are also rather costly, time wise. So the fewer if-statements you have, the better. Looking up the direction in a table indexed by the square difference would be far faster then making separate tests for the different types of alignment. (But on 10x12 you would get false hits for moves that cross the edge.) Not having to figure out what type of piece you are dealing with would safe you a number of conditionals as well.

If you really want to make a career out of this, you could 'bulk test' which King moves are safe: you could prepare a table that lists all directions (e.g. as null-terminated lists) that would intersect the King neighborhood for a given difference of square numbers. For contact attacks you could make a table where each bit of a byte corresponds to a square next to the King that a certain piece type would hit. By OR'ing these bytes for different pieces together you would get a byte that marks all attacked squares. For distant (blockable) attacks you would have to verify the reachability of the squares.

[notachessplayer]

Ye, I will move to a 16x12 representation for this purpose, thanks.

I'm intrigued by your other suggestion. Do you have documentation about it?

[H.G.Muller]

I have no further documentation on that; it is just an idea that I have carried around in the back of my head for a long time, but ever got to actually working on it. But I can elaborate a bit on it here. It always bothered me that testing King-move legality does duplicate work. E.g. with a King on g2 and an enemy Rook on h8 you would test for emptiness of h7, h6, h5, h4 for each of the moves Kh1, Kh2 and Kh3. So it seems more efficient to do a one-time effort to determine which squares are attacked by Rh8, and then for each move just test the King to-square based on that information.

Contact attacks are quite easy to handle. You could assign a bit to each of the 8 King steps (e.g. 1 = forward, 2 = backward, 4 = left, 8 = right, 16 = left-forward, ...), and tabulate as a function of the relative position of the King (a 16x15 table 'contact_hits' if you use 16x12 board) which of these steps move into the check for the various piece types, packing that into an integer. E.g. the lowest 8 bits for orthogonal steps (R+Q+K), the next 8 bits for forward-diagonal (B+Q+K+wP), the next 8 for backward diagonal (B+Q+K+bP) and the higest 8 bits for Knight jumps. You would have a table indexed by piece type with masks that would clear the bits not relevant for that piece (e.g. 0xFF000000 for a Knight, 0x00FFFF00 for a Bishop), so that

hit = contact_hits[location[king] - location[piece]] & contact_code[piece];

would give you the set of directly attacked squares (actually four sets differentiated by attack type,packed in one int). For generating King move you would then loop through the 8 directions, and test

if( (hit & to_bit[direction])) == 0) GenerateOneMove(location[king], location[king] + king_step[direction]);

where to_bit would be an 8-entry table that contains 0x01010101, 0x02020202, 0x04040404, ... to test if the to-square is safe from attacks by all existing move types.

But sliders complicate this plan, as they require testing for a free path. Q can actually make distant attacks on the King neighborhood along 3 different rays. E.g. Ke4, Qd3 would attack d5 (dependent on occupation of d4) and f3 (dependent on e3). The attack on f5 in that case should really behandled as a contact attack, because although it will always be blocked by the King, the latter cannot hide behind itself. But unfortunately there are no bits left in the contact_hits table for indicating jumps of two. It depends a bit on whether you also want the scheme to work for positions where you already are in check. Of course you also could accept a small inefficiency here, treating the distant attack that X-rays the King (and thus checks it) as any other distant attack, but remove the King from the board before the whole procedure, so that it seems unblocked when you make the (redundant) test.

On second thought, it could be reasonably efficient to do something like you do now after the King moves for testing slider attacks, but then before the King move. So basically generate slider moves, but in stead of testing whether they hit the King, you record where they intersect the King neighborhood. And you generate only moves in directions that could possibly intersect the King neighborhood. I normally base my move generation on a zero-terminated list of board steps, where the piece type determines which list will be used (and where for sliders each board step will then be applied repeatedly until you hit an obstacle). Instead of having this depend only on piece type, you could make separate lists for each (piece_type, location), i.e. a board-size table. I actually do that in my Xiangqi engine; it has the advantage that in edge squares you can omit directions that immediately stray over the edge, so that no time is wasted on them. (And in Xiangqi there are zone edges inside the board as well that certain piece types cannot cross, so you automatically take care of piece confinement that way,e.g.of the King to the Palace.) You could do something similar here, where each piece type has a 16x15 table indexed by the relative position to King that contains the (zero-terminated) list of possible board steps that set you on a course that intersects the King neighborhood.

You could then have a 16x15 table neighborhood[], which would tabulate which square in the King neighborhood corresponds to the relative position with which it is indexed. E.g. if you used '1' to indicate the square in front of the King in the 'hit' code, and a forward step adds 16 to the square number (as it would in a 16x12 board), you would initialize neighborhood[16] = 1. During the ray scans of the listed directions you would then calculate

hit |= neighborhood[to - location[king]];

so that all bits in 'hit' corresponding to squares attacked by sliders will also be set. You would have to remove the King while doing this, to prevent it from trying to hide in its own shadow. A problem is that the ray scans will overshoot the King neighborhood, which wastes time. You would want them to stop when you leave the King neighborhood again (if they ever get that far). For this you could make a second table that for each board step that can reach the King neighborhood would contain the last square of this intersection that you will reach (relative to King) if unobstructed, and terminate the ray scan when you reach it.

Most of the sliders would be positioned such that their moves would not even intersect the King neighborhood on an otherwise empty board, so that the zero-terminated list of board steps will be empty, and the amount of work will be limited to looking up their contact attacks as described above, and the first board step (concluding that it is zero). This work will then be shared by all King moves.

[H.G.Muller]

BTW, note that in mailbox engines (as opposed to perft calculators) it is a far bigger problem to efficiently generate captures, as it is to determine move legality. Only a small fraction of the moves are King moves that stumble into check, and even a small fraction of all King moves is illegal. Discovering this during full move (or capture) generation in the daughter node is not very much more expensive than running an optimized dedicated test for it. So on average always running the test, which in hindsight would have been a waste of time when the move was legal, just slows the engine down compared to occasionally aborting the move generation because of a King capture (making that move geeration a wasted effort).

There are ways to accelerate mailbox capture generation that would also affect how you would test for King-move legality. In particular, you could keep a view_distance[square_nr][direction] table, that for each occupied square would contain the distance to the nearest obstacle (edge or piece) in each of the 8 directions. Such a table would allow you to generate slider captures without doing any ray scan, as you can immediately locate the piece at the end of the ray. Such a table would also allow you to immediately determine how far a slider move penetrates into the King neighborhood. The view_distance can be maintained in an incremental way rather cheaply, as almost all nodes of a search tree are QS nodes, where you only search captures. And captures only evacuate squares, they never occupy them (well, except e.p., which is also very rare). For evacuating a square, you only have to add diametrically opposed view distances to get the new view distance of the neighbors in those directions, and the info in the table itself tells you where these neighbors are.

[notachessplayer]

it could be reasonably efficient to do something like you do now after the King moves for testing slider attacks, but then before the King move. So basically generate slider moves, but in stead of testing whether they hit the King, you record where they intersect the King neighborhood.

This is actually an idea I had in mind. Since I check for pinned pieces every time (with enemy sliders), I could also verify which directions should be forbidden for the king. But since I plan on finding pinned pieces incrementally, I haven't bothered yet.

As for the rest of your explanation, I'm afraid everything is not too clear to me, and it seems like it would be a real pain to implement if you don't start from scratch Also not sure if it would be much faster?

Btw, the 16x12 representation allowed me to get to 1.50s for a perft 6!
Since it is my first try with c++, I'm sure I could gain another 0.1s or even more just by optimizing my code, but this is easier said than done.

This king problem is the last big one, and I'm sure there is something not so hard to do about it... so frustrating. The idea above is probably good (definitely better than what I do now) but not the best, and it doesn't fix my castling problem (to know if adjacent squares are being attacked).

Also, you speak of "king neighborhood". I assume you mean the 8 adjacent squares. This is one thing I was preoccupied with while thinking about how to determine which direction should be forbidden. It seems relatively hard to know instantly,cheaply if a slider goes through a neighboring square.
I thought about using a boolean array, reset it every time, and set every square that sliders go through to "true", which would instantly tell my king that a square is forbidden, but I hate the idea of looping through a whole array for every move generation. This is of course possible with a simple 64bits integer, but then the cost comes from bitwise operations.

[H.G.Muller]

With 'King neighborhood' I mean indeed the 8 adjacent squares.

Instead of a Boolean array, you could use an int array, and write the node count to every square that a slider attacks. Then there is no need to first clear it. I used this technique in my engine CrazyWa to determine the initiative bonus, which is based on the number of attacked squares next to the King of the side that doesn't have the move. So when I generate the moves, I also update this 'attacks board', and immediately afterwards I then examine the squares around the enemy King to determine how many of them were attacked.

In mailbox determining if a slider attacks something tends to be cumbersome, because the required information (square occupancy) is spread out over many memory cells. Keeping track of view distances ameliorates that, by grouping information for entire rays intoasinglememory cell, and concentrating it in cells corresponding to occupied squares. But it adds a fair amount of complexity in the design.

Without view distance, ray scans cannot be avoided. But there is a quick test to determine if you canot possibly attack the King neighborhood (and thus discard the piece without any ray scans). This would use the following 'British flag' table:

Code: Select all

char distant_hits[] = {
 2, 2, 2, 0, 0, 0, 1, 1, 1, 0, 0, 0, 2, 2, 2,     0,
 2, 2, 2, 2, 0, 0, 1, 1, 1, 0, 0, 2, 2, 2, 2,     0,
 2, 2, 2, 2, 2, 0, 1, 1, 1, 0, 2, 2, 2, 2, 2,     0,
 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2,     0,
 0, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 0,     0,
 0, 0, 2, 2, 2, 2, 3, 1, 3, 2, 2, 2, 2, 0, 0,     0,
 0, 0, 0, 2, 2, 2, 3, 1, 3, 2, 2, 2, 0, 0, 0,     0,
 1, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 1,     0,
 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,     0,
 1, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 1,     0,
 0, 0, 0, 2, 2, 2, 3, 1, 3, 2, 2, 2, 0, 0, 0,     0,
 0, 0, 2, 2, 2, 2, 3, 1, 3, 2, 2, 2, 2, 0, 0,     0,
 0, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 0,     0,
 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2,     0,
 2, 2, 2, 2, 2, 0, 1, 1, 1, 0, 2, 2, 2, 2, 2,     0,
 2, 2, 2, 2, 0, 0, 1, 1, 1, 0, 0, 2, 2, 2, 2,     0,
 2, 2, 2, 0, 0, 0, 1, 1, 1, 0, 0, 0, 2, 2, 2,     0
};

char slider_hit_code[NPIECES];

void
Init ()
{
  slider_hit_code[BISHOP] = 2;
  slider_hit_code[ROOK]   = 1;
  slider_hit_code[QUEEN]  = 3;
}

When looping through the piece list you can then test

Code: Select all

if(slider_hit_code[piece] & distant_hits[location[piece] - location[king] + (7*16 + 7)]) {
  ... // do ray scan(s) to mark attacked squares
}

You would still have to figure out in which direction(s) you would have to scan when you do have proper alignment for the given piece type. Usually this is just in one direction, but if you are very close to the King it can be two directions for a Rook, and up to three for a Queen. Note that the table is not set up to detect unblockable attacks (which do not require a ray scan), but that sliders do also have such attacks, assumed here to be detected by other means.

One way to handle the ray scans would be to have two other 16x15 tables containing the board step towards the King neighborhood: one for Rooks (containing 1, -1, 16 or -16) and one for Bishops (containing 15, 17,-15 or -17). Depending on the piece type you wil use one or the other, or both. The only problem is that a Rook diagonally next to the King will need two ray scans. To handle that, you could for instance incorporate the scan along the rank in the regular table, and detect the exception of an extra (file) scan by setting the '8' or '32' bit in the distant_hits[] array for the squares in the corners of the King neighborhood, and testing those when doing orthogonal scans. Depending on which one wheter the '32' bit was set you could then make a second scan in the +16 or -16 direction (i.e. with step (distant_hits[] & 32) - 16). In fact this would not so much be a scan as well as testing the first square along the file to determine if you can reach the second, because after that you would have left the King neighborhood.

[H.G.Muller]

ote that if you had view distance available, you could tabulate the numbers of the directions in which to scan, instead of board steps, and in addition how far you have to go to reach the King neighborhood. E.g.for the Rook scans:

Code: Select all

char orth_scan_dir[] = {
 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,     0,
 3, 3, 3, 3, 3, 3, 3, 0, 7, 7, 7, 7, 7, 7, 7,     0,
 3, 3, 3, 3, 3, 3, 3, 0, 7, 7, 7, 7, 7, 7, 7,     0,
 3, 3, 3, 3, 3, 3, 3, 0, 7, 7, 7, 7, 7, 7, 7,     0,
 0, 0, 0, 0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 0,     0,
};

char orth_scan_dist[] = {
 0, 0, 0, 0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 4, 4, 4, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,     0,
 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5,     0,
 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5,     0,
 5, 4, 3, 2, 1, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5,     0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 4, 4, 4, 0, 0, 0, 0, 0, 0,     0,
 0, 0, 0, 0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 0,     0,
};

int king_steps[] = { 0, 16, 15, -1, -17, -16, -15, 1, 17 };

In case the alignment test indicates you have a Rook move to the King neigborhood, you can then first test if you have a free view to it:

Code: Select all

int fromSqr = location[piece];
int kingSqr = location[king];
int vector = fromSqr - kingSqr;
hit = distant_hits[vector + (7*16+7)] & slider_hit_code[piece];
if(hit) {
  if(hit & 1) { // Rook move
    int direction = orth_scan_dir[vector + (7*16+7)];
    int distance = orth_scan_dist[vector + (7*16+7)];
    if(view_distance[fromSqr][direction] >= distance) { // free path to neighborhood
      int step = king_step[direction];
      int toSqr = fromSqr + step * distance; // first square in King neighborhood
      toSqr += step;
      do {
        attacks[toSqr] = nodeCount; // mark square as attacked on 'attacks' board
        if(board[toSqr] != EMPTY) break; // blocked
        toSqr += step;
      } while(distance[king - toSqr] <= 1); // stop when we left neighborhood
    }
    // scan in second direction
    if(distant_hits[vector + (7*16+7)] & 8+32) { // second scan needed
      ...
    }
  }
  if(hit & 2) { // Bishop move
    ...
  }
}