Mailbox move gives check routine

[gaard]

Aside from make/check test/unmake, or copy/make/check test, what are the fastest move_gives_check routines for mailbox? This is easy enough to compute after the move, but I'm having trouble writing a method to do it beforehand. The most straightforward way I see is copying the board state (say) uint8_t mailbox[16 * 12], making the moves, and then using that, without incremental updates. Castling is easy enough to account for, so are the simple cases when from and to are not pseudo attacks, but all else looks ugly and inefficient.

[R. Tomasi]

Aside from make/check test/unmake, or copy/make/check test, what are the fastest move_gives_check routines for mailbox? This is easy enough to compute after the move, but I'm having trouble writing a method to do it beforehand. The most straightforward way I see is copying the board state (say) uint8_t mailbox[16 * 12], making the moves, and then using that, without incremental updates. Castling is easy enough to account for, so are the simple cases when from and to are not pseudo attacks, but all else looks ugly and inefficient.

I'm really no expert for mailbox (always used bitboards for my engines), but it seems to be very very expensive to me to copy the entire board state.

[hgm]

It only makes sense to test this without first making the move when you want to know it for the purpose of move sorting. If you would play the move anyway and the consequences of it delivering check only occur after that, it is easier to do the test after the making, as the first thing in any new node. And if you don't want to play the non-checks at all it is better to selectively generate the checks than to generate all moves and test them.

For mailbox check tests one typically uses a (16x15) table indexed by board step (= square-number difference) to detect alignment, which contains a set of flags indicating which piece types can potentially check along such a 'vector'. You can test the to-square of a move for the required alignment without making the move, and in most cases you would be done then, because there is no alignment. If there is, and the piece is a pawn or knight, you are also done, because it will alway be a check as pawns and knights cannot be blocked ('contact check'). And for a king it would be an illegal move, as checks are reciprocal. Only for sliders the path to the king could be blocked. This can be tested by scanning the board along the alignment ray; a second 16x15 table gives you the unit step belonging to that alignment. (This can be done before the move, because a potential slider checker could not have come from this ray, as it would have been already che king then.) I usually start at the king, because most of the game the king is safely tucked away, and the ray scan almost immediately bumps into a pawn. If the ray scan does not hit the to-square before it hits a piece, the moved slider will not deliver check.

That leaves discovered checks. You can 'bulk test' for those: if the from-square of the proposed move is aligned (which it usually isn't, so that you are immediately done with a no-discovered-check verdict) you can do the ray scan king to from-square to see if these 'connect'. And when it does (not often...), continue the ray scan in the same direction. If it hits a slider of the stm that matches the alignment, moves from that from-square can deliver a discovered check. If the moving piece is a pawn or king it can keep the ray blocked, however, so you would have to test for the to-square not having the same alignment or unit step. If a slider would be able to move along a ray that could be a discovered check, it can capture the king by itself, and the question of whether it has other moves that deliver check is probably no longer important. So you might as well do this test for staying on the ray for every type of moving piece.

I see no reason for making board copies.

[Rebel]

Aside from make/check test/unmake, or copy/make/check test, what are the fastest move_gives_check routines for mailbox? This is easy enough to compute after the move, but I'm having trouble writing a method to do it beforehand. The most straightforward way I see is copying the board state (say) uint8_t mailbox[16 * 12], making the moves, and then using that, without incremental updates. Castling is easy enough to account for, so are the simple cases when from and to are not pseudo attacks, but all else looks ugly and inefficient.

[fen]rnbqkbnr/ppppp1pp/5p2/8/4P3/8/PPPP1PPP/RNBQKBNR w KQkq -[/fen]

Consider this position.

The only move that can give check is Qd1-h5.

Procedure for Queens:
1. Subtract the square h5 from the king square e8
2. Check the value with 256 bytes queen_table which either returns a zero (no check possible) or the offset to the square e8.
3. Loop through the (empty) squares g6 / f7 / e8 and you have a hit.

So you have to create 4 x 256 bytes tables with the directions, zero if not possible for the knight, bishop, rook and queen.

The move Ng1-f3 (f3-e8) should return a zero in the knight_table. No check possible.
The move Bf1-e2 (e2-e8) should return a zero in the bishop_table. No check possible.
However the move Bf1-b5 (b5-e8) should return the offset to square e8. But while looping to e8 it finds the black pawn d7 on its way, no check possible.

Pawn moves don't need a table.

[fen]4k3/8/8/8/8/4B3/8/4R1K1 w - -[/fen]

You are still not there

You have to solve cases like Be3-d2 etc. But basically it's the same code, only now you need to subtract the squares e1-e8.

It's fast, in 90% of the cases the queen/rook/bishop/knight table will return a zero, no check possible.

BTW, my mailbox size is 10*8.

[hgm]

With 10 x 8 you would get some false alignments; e.g. a4 and h8 would have the same difference as h5 and e8. This is not fatal, because the ray scan from a4 would bump into the edge when it attempts to reach h8, but it still means you occasionally do a ray scan that could have been avoided. As soon as the board width gets >= 15 you can no longer have false hits for alignment.

You don't use a table for Pawn?

Having a different table for each piece type works fine, but I usually try to collapse those to just two tables. (Because I am naturally stingy, I suppose...) You can store all the offsets ('unit steps') in one table, used for all piece types, but then you cannot use that table anymore for determinig whether that piece type is actually able to move in that direction. So you need separate tables for that, but because these just contain yes/no information, they can all be put in different bits of a table of bytes. The 8 available bits could be used for

* white Pawn captures
* black Pawn captures
* adjacent orthogonal squares
* Knight captures
* distant squares on the same rank
* distant squares on the same file
* distant squares on the same diagonal
* distant squares on the same anti-diagonal

Each piece would have a mask associated with it (captMask[piece]) that tells you which bits to test. E.g. for a Rook you would test the distant rank and file bits, and the adjacent orthogonals. For a King you could set the first 3 bits. (But you might as well not bother, because all the checks are illegal.)

The reason for separating adjacent and distant squares is to make it easy to test whether a match is a contact check or a distant check. If it is a contact check you don't have to bother with the ray scan, and can ignore the unit step.

The reason for separating the slider ray by orientation is to make it easier to detect whether a King or Pawn that could potentially deliver a discovered check indeed do.
[fen]4k3/8/8/1R6/B7/8/8/4K3 w[/fen]
In the above diagram Rb5-h5 keeps the Rook diagonally aligned with the King, but because it is a diagonal of different orientation it does not spoil the discovered check. If the Rook had been a King, and moved Kb5-c6, it would have landed on the same diagonal, and we would not have had a discovered check.

[dangi12012]

Aside from make/check test/unmake, or copy/make/check test, what are the fastest move_gives_check routines for mailbox? This is easy enough to compute after the move, but I'm having trouble writing a method to do it beforehand. The most straightforward way I see is copying the board state (say) uint8_t mailbox[16 * 12], making the moves, and then using that, without incremental updates. Castling is easy enough to account for, so are the simple cases when from and to are not pseudo attacks, but all else looks ugly and inefficient.

There are 5 unique ways to give check:
Moving a piece and it gives check
Moving a piece and it gives a discovered check
Enpassant Check
Promoting a piece and it gives check (pawn converts to knight check)
Castling Check

The last is not so obvious
Pieces are technically not pinned in the sense that there is 1 blocker. So normal XRay doesnt work. (2 blockers) Enpassant check:
Also diagonal case with bishops is possible
Also the pawn that does enpassant (and normally couldnt move on that diagonal) can give check
[fen]8/8/8/1k1pP1R1/8/8/3K4/8 w - - 0 1[/fen]



So think of these 5 cases:

• Normal Check

• Discovered Check

• Enpassant Check (By pawn or indirectly)

• Promotion Check

• Castling Check

Doing them all beforehand in mailslots will be a tall ask. With Bitboards its already done and described in my signature link below.

[dangi12012]

That leaves discovered checks. You can 'bulk test' for those: if the from-square of the proposed move is aligned (which it usually isn't, so that you are immediately done with a no-discovered-check verdict) you can do the ray scan king to from-square to see if these 'connect'. And when it does (not often...), continue the ray scan in the same direction. If it hits a slider of the stm that matches the alignment, moves from that from-square can deliver a discovered check. If the moving piece is a pawn or king it can keep the ray blocked, however, so you would have to test for the to-square not having the same alignment or unit step. If a slider would be able to move along a ray that could be a discovered check, it can capture the king by itself, and the question of whether it has other moves that deliver check is probably no longer important. So you might as well do this test for staying on the ray for every type of moving piece.

Yeah but you still have the one and only very nasty case of this check:
Alignments wont help you here since the white pawn has neither from nor to aligned with the enemy king. Yet after enpassant takes (by white) there is a check.

[fen]6B1/8/8/3pP3/8/1k6/8/4K3 w - - 0 1[/fen]

[R. Tomasi]

[fen]6B1/8/8/3pP3/8/1k6/8/4K3 w - - 0 1[/fen]

It is obvious what you mean in that example, but the FEN string does not match (according to that e.p. capture isn't possible). I think the right FEN would be

[fen]6B1/8/8/3pP3/8/1k6/8/4K3 w - d6 0 1[/fen]

[hgm]

Yeah but you still have the one and only very nasty case of this check:
Alignments wont help you here since the white pawn has neither from nor to aligned with the enemy king. Yet after enpassant takes (by white) there is a check.

[fen]6B1/8/8/3pP3/8/1k6/8/4K3 w - - 0 1[/fen]

True, e.p. capture and castling would need special treatment, and we did not mention that. But these moves will need special treatment anyway, so one can assume they are easy to recognize. You would not only need a special code section in MakeMove to treat them (removing the Pawn or moving the Rook), but also for testing whether they deliver check. For promotions one would have to test for direct check using the promotion piece rather than the moved piece.

Note, however, that it is unlikely that delivering check would be a more important criterion during move sorting than being a promotion or e.p. capture, so that you might not be intersted in obtaining this info for captures or promotions in the first place. (Well, perhaps with the exception of under-promotion to Knight, which you might only want to consider when it delivers check.) And that castling is usually not possible at all, as you would already have lost the right to do so while still in book. And even if not, that castlings which deliver check are virtually never encountered. So having a different treatment for those is not expected to affect Elo, or even alter a single game out of the millions the engine will play during its existence.

[Rebel]

With 10 x 8 you would get some false alignments; e.g. a4 and h8 would have the same difference as h5 and e8. This is not fatal, because the ray scan from a4 would bump into the edge when it attempts to reach h8, but it still means you occasionally do a ray scan that could have been avoided. As soon as the board width gets >= 15 you can no longer have false hits for alignment.

You don't use a table for Pawn?

Trs80 - 16Kb, saving 256 bytes

Only 2 compares vs one table lookup.

Having a different table for each piece type works fine, but I usually try to collapse those to just two tables. (Because I am naturally stingy, I suppose...) You can store all the offsets ('unit steps') in one table, used for all piece types, but then you cannot use that table anymore for determinig whether that piece type is actually able to move in that direction. So you need separate tables for that, but because these just contain yes/no information, they can all be put in different bits of a table of bytes. The 8 available bits could be used for

* white Pawn captures
* black Pawn captures
* adjacent orthogonal squares
* Knight captures
* distant squares on the same rank
* distant squares on the same file
* distant squares on the same diagonal
* distant squares on the same anti-diagonal

Each piece would have a mask associated with it (captMask[piece]) that tells you which bits to test. E.g. for a Rook you would test the distant rank and file bits, and the adjacent orthogonals. For a King you could set the first 3 bits. (But you might as well not bother, because all the checks are illegal.)

The reason for separating adjacent and distant squares is to make it easy to test whether a match is a contact check or a distant check. If it is a contact check you don't have to bother with the ray scan, and can ignore the unit step.

The reason for separating the slider ray by orientation is to make it easier to detect whether a King or Pawn that could potentially deliver a discovered check indeed do.
[fen]4k3/8/8/1R6/B7/8/8/4K3 w[/fen]
In the above diagram Rb5-h5 keeps the Rook diagonally aligned with the King, but because it is a diagonal of different orientation it does not spoil the discovered check. If the Rook had been a King, and moved Kb5-c6, it would have landed on the same diagonal, and we would not have had a discovered check.