Indeed, but this works because the while loop has excluded the possibility that the square would be EMPTY. For leaper captures-only it is more difficult, because you want to test purely for enemy pieces.
If you have bits to spare in the piece encoding, you can duplicate the WHITE and BLACK bits, and only set one of each pair in the border guards. When generating leaper captures you can then test for the enemy bit that is not set in the guards. The disadvantage is that piece lists will be wasting a lot of space this way.
An alternative is to encode the guard as the bit just above the color bits. Say EMPTY = 0, WHITE = 32, BLACK = 64, GUARD = 128. Then you would have:
00000000 empty
001nnnnn white pieces (use 32-62)
010nnnnn black pieces (use 64-94)
10000000 guard (128)
11000000 test mask for rejecting black any-moves
10100000 test mask for rejecting white any-moves
00100000 test mask for accepting black captures-only
01000000 test mask for accepting white captures-only
11100000 test mask for rejecting Pawn non-captures
Usually border guards would not be used to index any piece tables, so you won't care that it is an outlier. Such tables need often to be indexed by empty squares, however. So it wastes about 33% space that codes 1-31 are not in use. This can be ameliorated by interleaving all piece tables with elements of the same data size with a stride of 63, and not using nnnnn = 31 for any piece. Then the EMPTY slot of the next table maps into the hole between the white and black pieces of the one before it. Then only the first table still has some unused elements in it. But you can probably find a table that would never need to be indexed by an empty square (e.g. capture codes), and make that the first one, chopping off the first 32 entries entirely.
For having efficient capture generation in a mailbox engine it would be much more important to eliminate the entire while(board[to] == EMPTY) loop, though. (I guess this should qualify as a non-rookie topic!) This can be done by maintaining an array viewDistance[square][direction] that stores the distance to the nearest obstacle in each of the 8 directions for all occopied board squares and the border guards adjacent to the board. (The latter only for those directions that lead back to the board.) Then you can get the to-square of slider captures in a single branch-free step, to = from + viewDistance[direction]*step[direction].
Update of this viewDistance[][] is surprisingly cheap, and can be done just before you start move generation. For the evacuated square sq you can do
Code: Select all
for(d=0; d<4; d++) {
int upstream = sq + viewDistance[sq][d]*step[d];
int downstream = sq - viewDistance[sq][d+4]*step[d];
viewDistance[upstream][d+4] += viewDistance[sq][d+4];
viewDistance[downstream][d] += viewDistance[sq][d];
}
(where directions are numbered such that d+4 is the direction opposite to d), and for the UnMake the same with -= instead of +=. Because the large majority of moves in the tree are captures, an evacuated square is all you have to deal with, as the to-square was already blocked before the move by the capture victim, and will remain so.
For the comparatively rare non-captures you would need to account for the blocking, which is a bit more expensive, and does require a board scan, as the viewDistance did not hold any data on the previously empty square. So you would have to reconstruct the data for that square the hard way. (And save the old content, as it could still be relevant for UnMake of previous plies that evacuated it.) The cost would be comparable to generating captures of only a single Rook or Bishop through ray scans, however, as you would only have to scan in 4 directions to reach an occupied square, after which the viewDistance data found there will point you directly to the first obstacle in the opposite direction.
There is an alternative way for doing this blocking update, which becomes competitive for large boards that are close to empty (so that ray scans would usually continue all the way to the board edge). This would start at a border guard that looks in the direction of the newly occupied square (obtained from a table indexed by that square and the direction to be handled), and use the viewDistance info to hop from occupied square to occupied square, until you overshoot the newly occupied square. (On a nearly empty board the first try would likely already overshoot the target.) The last two squares visited would be the 'end stops' of the newly occupied square, and should get their viewDistance in the direction of the latter updated.
Code: Select all
for(d=0; d<4; d++) {
int oldHop, v = step[d];
int hop = edge[sq][dir]; // tabulated intersection of rays with border
do {
oldHop = hop;
hop += viewDistance[hop][d]*v; // hop to next obstacle
} while(baseStep[sq - hop] == v); // baseStep flips when we overshoot
viewDistance[sq][d] = viewDistance[hop][d+4] = distance[sq-hop]; // update
viewDistance[sq][d+4] = viewDistance[oldHop][d] = distance[sq-oldHop];
}
The UnMake is again simple, because then the table itself contains all info needed to do it. It is in fact the same code as given above for evacuating a square on MakeMove(). Followed by restoring the info on the square itself for all its directions. (As the distances easily fit in bytes, you can save and restore that as a single uint64.)
