Incremental legality testing

[hgm]

I was faced with the problem of generating all legal moves, in the context where pseudo-legal moves could be virtually anything. Like sliders that move around corners, or pieces that can (or must) hop over other pieces. And it isn't know in advance what the pseudo-legal moves can be, as this was supposed to be generic code, applicable to any conceivable variant. The prescription for generating pseudo-legal moves is of course given, but it would be very hard to derive a method for retrograde move generation from it.

So pretty much the only way to test for check is to generate all pseudo-legal moves, and test if one of those happens to capture the king. The common case is that you are not in check, so that means you cannot bail out early either. Retrograde methods like the 'super-piece' method would be too complex, and quickly become expensive anyway when sliding moves can turn corners on empty squares, so that attacks could come from virtually everywhere.

Filtering pieces by 'footprint' of their move pattern, and testing whether the king is in it, before you actually generate all their moves, would be a possibility. But for pieces that turn corners in places dependent on other material on the board (e.g. when they collide with an obstacle) the set of potentially accessible squares can be very large, and not easy to obtain. Recording what they attack on an empty board would not be enough. Of course you could still use the filter to save work on 'simple' pieces like Rooks and Knights; any variant usually has a lot of those. But it is usually the complex pieces that have the largest number of moves.

I am now trying the following approach: instead of generating a two-ply tree (the first ply for generating all pseudo-legal moves, the second to test whether, after making one of those, the opponent can capture your king), I run the opponent move generator after null move, for an 'augmented check test'. This of course will tell me if I am currently in check. But in addition it will record the moves it tries to generate in a sort of attack map: every capture-capable move whose trajectory bumps into an enemy piece, but would have been able to continue its trajectory if that square had been empty, could conceivably be pinning the piece it bumped in to. So for the square of the obstacle, both the square the move was coming from, and the move itself (as a pointer into the table of move descriptors that is used for generating the moves) will be listed.

The idea is then, when I am not currently in check, to skip verifying the legality of moves that do not move such a 'potentially pinned' piece. And when the moving piece is potentially pinned, I will only try the reply moves of its potential pinners in the directions that were blocked by the moved piece before, to see if they can capture the king now that the former blocker is gone. Normally only a few pieces would block opponent moves, and for those, instead of having to try all opponent moves for capturing the king, I usually would have to try only the move of one opponent piece in one particular direction.

This also applies to moves that clear out a square as a side effect; if the piece on the cleared square had been blocking a slide, this slide could now potentially hit our King. The infamous example of this in orthodox Chess is e.p. capture. Usually moves with side effects make opponents disappear. So this is not really a pin, but a possibility for a discovered attack. To catch this, the attack map must also record the moves that are blocked by friendly pieces.

This is only one side of the coin, though; in general moves can also be altered by a piece appearing in their path. The archetypal example for that is the Cannon from Chinese Chess: if it is looking directly at your King along a file, putting a piece on any of the empty squares between them would 'activate' the Cannon by providing a 'mount' to hop over, and capture your King. Pieces that deflect (continuing in a different direction) from obstacles could also suddenly hit your King when you place a piece in their path. So the 'augmented check test' also records all moves that are on the way to a mount to hop over (or deflect from, which in the move generator is treated the same) and passing empty squares. Each of these empty squares could then become a mount when it got occupied, and make the move continue in a different way. So the hopping move passing over them would be recorded in the 'attack' map for these squares. (Even though they are not really attacks.)

Moves that end on an empty square marked as having hops passing over them, would then require that hop to be recalculated in a partial check test, to see if it now hits the king.

That still leaves moves of the king itself. When we ignore our King during the move generation for the augmented check test, every 'attack' that is encountered during generation (i.e. actual captures and capture-capable moves to an empty square, the latter not necessarily a pseudo-legal move in itself, e.g. for diagonal Pawn moves) can mark the square it attacks. It would then be illegal for a king move to end on a marked square. (And when it already is on one, it is in check!)

That is also not the whole story, though: the king could expose itself to a side-effect capture. E.g. when a piece like a Checker participated, it might be inadvisable to step diagonally in front of it. This is not a sure thing, though; the capture of a Checker can be 'blocked' behind the capture square. This can be solved by either letting the augmented check test, for every possibility to capture as side effect on a square that happens to be empty, imagine there would be a King there, and try to finish the move. It could then reliably mark the square as 'attacked' if it succeeds. This would likely be wasted effort, though, as the king might not be able to reach that square at all, so that theinformation is never needed. So it might be better to just record the move as potentially causing a check when a king would go there, just as for hopper moves passing over it. Except that in this case it can only be harmful if it gets occupied by a king, while hoppers could be activated by anything. You could then retry the recorded move to test the legality of any king move that steps on there.

When the side to move is already in check, the primary concern is that any move should resolve the check. King moves have that potential; other moves should at least alter the content of one square on the path of the checking move (including the location of the checker itself). We could mark the paths of all checking moves in the attack map, and immediately reject all moves that do not either start or end on a marked square as illegal. We could even be smart w.r.t. double checks, by using different marks for each pre-existing checking move (e.g. different bits in a word), and reject all moves that did nor touch the path of all checking moves. The non-rejected moves would then have to be tested in the normal way (for being pinned, etc.). We should also always re-run the pre-existing checking moves, as altering something in their path is no guarantee for resolving the check. E.g. a piece might be able to capture both as a Rook and as a Chinese Cannon, and then blocking the Rook move could just provide a mount for the Cannon move. OTOH, the Cannon move should be in the list of potential activations in that case, and be re-run for that reason.

[BlueStar]

Custom pseudo-legal moves... My engine in Prolog.... No, I'm not getting sidetracked...