In bitboard engines limiting the generation to evasions is pretty easy: you just calculate a bitboard mask that indicates all squares on the checking ray, including the checker. Then you do the normal move generation, but before extracting the moves you AND with this mask. (For non-royal pieces; king moves are automatically good evasion candidates, and have to be checked for legality in their own way.)
In mailbox engines this is more tricky. King moves can be generated as always, and would have to be tested for legality in the usual way, as always, e.g. through the IsSquareAttacked() routine described earlier in this discussion. For double checks it would remain at that. Captures of the checker could be generated by a very similar routine, which stores the moves rather than just returning TRUE if it finds one (either in a conventional move list, or by creating an attack-map element just for the checker).
The nasty part occurs with distant (slider) checks, where you have to generate the interpositions. This could be done with the aid of a table that lists all potential interposition squares as a function of king location, checker location, location of the piece we try to interpose, and type of that piece. That would be a huge table: there are 5 basic types (R, B, N and two kind of Pawns), so it would require 64 x 64 x 64 x 5 = 1280k entries. But we can economize on that by indicating the location of the piece relative to king, so that we don't have to use king location as index. Relative locations (i.e. sqr - kingSqr) will require a 240-entry (16 x 15) table rather than 64, however. But the checker has to be on a ray through the king (or it could not be a distant checker), and we could specify its location as one of 8 directions, and a distance 1-7.
For the moment, let us forget about the distance. Then we have a 240 x 8 x 5 table indexed by relative location of piece w.r.t. king, direction of the check ray, and piece type. Each entry would have to indicate where we can interpose, which is potentially on multiple squares. (E.g. a Queen might interpose on 3 different squares of the check ray.) We could of course use a list of 3 square numbers for that (relative to King), but that is a bit bulky. More compact is to associate a bit flag with each square of the check ray, and set the bit to 1 when the piece can be interposed there. On an 8x8 board there can at most be 6 empty squares between checker and king, so this would require only 6 bits. One could call this a 'bit ray', similar in spirit to a bitboard, but encoding a much smaller area. In fact, the 5 bit rays for the different piece types can all be packed into a 32-bit integer (5x6 = 30), and extracted through ANDing with a piece-dependent mask. So we have a 240 x 8 table of 4-byte integers. This is still a bit larger than I would prefer, but we will get to that later. For now assume that during detection of the check we determine its direction, and set a pointer to the corresponding 240-entry table interpose[240] of packed bit rays.
The bit rays are all initialized as if the checker is indeed 7 squares away from the king. In reality it might be closer, meaning that some of the moves to the ray indicated in the bitrays of the interpose[] table are actually not interpositions at all, because they land on the wrong side of the checker. During check detection we can figure out how far away the checker is (e.g. distance[checker - kingSqr]), and use this in a 7-entry table to retrieve a mask 'between' in bitray format that indicates the squares on the ray that are between king and checker. We are then set for generating evasions.
For each non-royal piece in the piece list we would then fetch interpose[location[piece] - kingSqr], and AND it with 'between', and with a rayMask[piece], which picks out the part relevant for the piece under consideration. (A Queen would leave both the Rook and the Bishop bits.) That way we get all squares on the check ray between king and checker that the piece might be able to reach if it is not blocked. We can extract the remaining bits one by one, and look up the corresponding to-square (relative to king) in a 30-entry table for the check direction. (So there would have to be 8 such tables. Or we would need a single table that just encodes the distance to the king, and multiply that with the unit step in the check direction.)
For sliders we would still have to test if the extracted to-square is reachable. This can be done in the standard way: look up the direction in which the to-square lies (w.r.t. the piece), consult the neighbor table to get the nearest obstacle in that direction, look up the direction of the to-square w.r.t. that obstacle. If the directions are different, the obstacle is on the other side of the to-square, and the move is not blocked. leapers would not have to be tested this way, as they could never be blocked.
Code: Select all
// evasion generator
// assumes in-check detection set 'interpose', 'between' and 'checkStep' based on direction and distance of check
// sliders
for(i=3; i<=7; i++) { // loop over sliders
int fromSqr = location[stm + i]; // square slider is on
int bitray = interpose[fromSqr - kingSqr]; // full ray maps for 5 piece types
bitray &= between; // limit to squares between king and checker
bitray &= rayMask[stm + i]; // limit to moves this slider can make
while(bitray) {
int n = bsf(bitray); // extract next bit
int dist = nr2dist[n]; // get the distance to king
int toSqr = kingSqr + dist * checkStep; // calculate square number
int d = direction[fromSqr - toSqr]; // direction of interposition move
int obstacle = neighbor[fromSqr][d]; // nearest obstacle in that direction
if(d != direction[obstacle - toSqr]) // is on other side of toSqr
EmitMove(fromSqr, toSqr); // so move is valid
bitray &= bitray - 1; // remove trated bit
}
// knights
for(i=1; i<=2; i++) { // loop over leapers (but not king, who can never interpose)
int fromSqr = location[stm + i]; // square slider is on
int bitray = interpose[fromSqr - kingSqr]; // full ray maps for 5 piece types
bitray &= between; // limit to squares between king and checker
bitray &= rayMask[stm + i]; // limit to moves this slider can make
while(bitray) {
int n = bsf(bitray); // extract next bit
int dist = nr2dist[n]; // get the distance to king
int toSqr = kingSqr + dist * checkStep; // calculate square number
EmitMove(fromSqr, toSqr); // so move is valid
bitray &= bitray - 1; // remove trated bit
}
Code: Select all
if((toSqr - fromSqr & 1) == 0) { // move is double push
if((fromSqr & 0xF0) != secondRank) continue; // Pawn doesn't have one
if(board[fromSqr ^ 0x30] != EMPTY) continue; // double-push is blocked
}
Code: Select all
int sqr = checker;
while((sqr -= checkStep) != kingSqr) { // loop over check ray
int fromSqr = sqr - forward; // square below it
int piece = board[fromSqr]; // look what is there
if(!piece & (fromSqr & 0xF0) == 0x30) { // square was empty but on 3th rank
fromSqr -= forward; // one more below it
piece = board[fromSqr];
if(piece & 16) // it is a Pawn! (exact test depends on piece numbering)
Emit(fromSqr, toSqr); // double-push interposes
} else if(piece & 16) // it is a Pawn! (exact test depends on piece numbering)
Emit(fromSqr, toSqr); // normal move interposes
}
