In Chess engines you can gain a lot of efficiency in testing moves for legality by not just generating all pseudo-legal moves, and testing if you are in check afterwards, but by selectively generating or disabling generation of groups of moves. (e.g. "this knight is pinned, do not generate any moves for it" or "I am in double check, so I have to move my king").
For this to work, you have to know your in-check status, as which moves can leave you in check strongly depends on if you were in check before, and how (distant, contact or double). So it displaces the problem to determining which legal moves check you. And n Chess you only have discovered checks (with a non-moving piece) and direct checks (with a moving piece), and apart from castlings and e.p. captures (which require special handlng anyway, but fortunately are rare), only one piece moves. So in general, you only have to look for direct checks from the toSqr, or discovered checks over the fromSqr. And the latter can be cheaply detected by testing for alignment between your own sliders and the opponent's King, with only one of your pieces in between.
Now I am trying to do something similar for Xiangqi. But the situation there is quite horrible! XQ Horses move like Knights, but do not jump, and can be blocked on an orthogonally adjacent square. This not only means they can pin pieces or deliver discovered check: it also makes the concept of a 'pin ray' fuzzy, as their moves are bent. Two Horses can be blocked on the same square. which means that discoverd double-check by two Horses is possible. (Direct+discovered double-check by two Horses is also possible.) Unlike with Chess, this double check can be blocked by interposing, but capturing a checker does not help, as there are two.
[X]5k3/3HC4/4H4/9/9/9/9/4h4/4h4/3K5 w
White can deliver double check with two Horses
by moving its Cannon, black by playing He1-c2
It is also possible to be in double check along an orthogonal, by a Rook backed by a Cannon. Also here blocking is a possible remedy, but not capturing. Apart from discovered check, a Cannon can deliver the opposite form of Check, where it is activated by moving a platform in front of it (undiscovered check?). This is one way to bring about the R+C battery just described. And it can be combined with any discovered check. If the latter was the double-discovered check by two Horses described above, you are checked 4 times!
[X]5k3/3HR4/4H4/9/9/9/9/9/5C3/5K3 w
White plays Re8-f8 for a quadruple check!
A consequence of the hopper-like capture mode of the Cannon is that checks by it can be dealt with not only by interposing, but also by moving the pece it was using as platform out of the line of sight. As a consequence, even double checks coming through disoint paths can both be neutralized, if one of them was by a Cannon:
[X]C1h1k4/9/9/9/9/9/9/4R4/4C4/4K4 4
Black is in triple check, but solves it by Hc9-e8!
This really makes the situation for legal move eneration in case of check much more cumbersome!
Legality checking and in-check status
Moderator: Ras
-
hgm
- Posts: 28360
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
-
Greg Strong
- Posts: 388
- Joined: Sun Dec 21, 2008 6:57 pm
- Location: Washington, DC
Re: Legality checking and in-check status
Yes, there's a lot of ugliness! In addition, you mentioned logic such as "this knight is pinned, do not generate any moves for it." Pinning is also complicated, because, in addition to the reasons you mention, there's the fact that a cannon can pin two pieces at once, and the fact that the two kings can't face each other (which can effectively pin pieces!)
Or, to summarize: YUCK!
Have you looked at the open source Xiangqi programs to see if they can really detect this stuff, or if they are just generating pseudo-legal moves and checking for legality later? I'm betting they do the latter ...
Or, to summarize: YUCK!
Have you looked at the open source Xiangqi programs to see if they can really detect this stuff, or if they are just generating pseudo-legal moves and checking for legality later? I'm betting they do the latter ...
-
hgm
- Posts: 28360
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Legality checking and in-check status
I guess that is indeed what they do. (I never look at sources of other Chess programsam , I am afraid it would hamper my creative thinking to be presented with working, but possibly sub-optimal solutions on a platter.) Current program does that too: it simply plays all pseudo-legal moves, and only aborts the search on a King capture.
But that makes it comparatively blind to checks and checkmates near the horizon. It only becomes aware of checks at d>=1, if after null move its King is captured. It happily stands pat at d=0 in checkmated positions, and futility-prunds moves that checkmate at d=1 in anticipation. Check extension does not help against this, as it will not extend without being aware of the check. In micro-Max I take all that for granted, but it is a major source of weakness compared to other engines. It is really helpful to know if a moves checks in advance, so you can exempt it from futility pruning, or extend it. If you extend checks at the end of the full-width search (d=0), you will detect matesone level beyond the normal horizon, rather than only one ply before it, i.e. you see them two ply earlier. That really helps.
For this reason I still want to make the attempt to find an efficient way to recognize moves as checks before I make them. (So that I get this extra two-ply visibility for nearly free, rather than by reducing nps so much that it makes me lose two plies of depth in the first place.)
The most promising scheme I have designed so far is this: before generating moves I run through the K, R, C and H section of my piece list (these are the pieces that can pin or deliver discovered checks, maximally 7) to test them for alignment with the enemy King. If they align, I scan the 'ray' (for Horses that is only one square) to count the number of blockers. If it is one (for K, R and H) or 2 (for C), I mark each of them as pinned in a 32-bit bitmap. Each piece of white and black has its own private bit in this. As a side-effect of this process I will also discover Cannons eye-to-eye with the King, that can deliver the undiscovered checks by interposition of something, and would mark the directions (from King) in which this happens as bits in a 'gunPointMask', compatible with the bit asignment in my '0x88'-capture-test table.
This prelude consists overhead that is always done, but is cheap compared to pseudo-legal move generation that follows. (As most of the 6 tested pieces will not align, and I will only have to do a ray scan for each that does in one direction, while move generation would have to do ray scans for all pieces in all their directions.)
When the turn of a move comes up to be searched, I will test its bit in the map of check blockers. If it is a blocker, I will then clear that bit, set a discovered-check variable to the from square of the move, and partially redo the ray scan over the from square to know exactly what type of battery moving this piece out-of-the-way will release on the opponent's King. This leads to enabling of possible evasion types (interposing, capturing the checker, 'ducking' (= moving a way the platform of an enemy Cannon)), and specifying them (in which direction, on which square, etc.).
The idea is that you then only have to do this one time for each piece that can deliver a discovered check, (which is rare anyway), so that the effort can be shared by all its moves. As long as the discovered-check variable is set, you extract all moves with that piece that reveal the check (i.e. moves off the ray, or captures on the ray) from the move list, rather than looking at the next move of the list. If no moves fitting the requirements are found, you clear the discovered check variable.
For each move (revealed check or other) you always do a '0x88' test to see if it attacks the enemy King, and can use the gunPointMask to test if any alignment corresponds to a direction that activated a Cannon. Together this information allows you to classify the battery from the direct direction. This classification also results in a list of possible evasions (interposing, capturing the checker, ducking). Then you have to combine the info of the direct and the discovered battery. (Note that there is a danger for double counting here that you have to intercept: a Cannon can reveal a Rook check by jumping over it with a capture, and deliver a direct check using that Rook as platorm, so that the direct and indirect part merge into a single RC battery.)
If check occurred from only a single battery (be it direct or indirect), all the evasion types for that battery remain valid, and are passed to the Search call of the reply node, to inform it of the check, and assist it in move generation. If check comes from two batteries, the situation is still not hopeless: if one battery allows ducking as evasion type, moving away the platform takes care of it, and could capture the checker or interpose for the check by the other battery. This requires a special mode of the in-check move generator, "evade A with mandatory ducking of B". (Note that ducking only is a possible evasion when a piece friendly to the checked King acts as platform for a Cannon check, so in case of checking by two batteries, only the revealed part can involve ducking, simplifying the recognition of this special case somewhat.)
So in combining the evasions of checks by two batteries, either all evasion modes are cleared (except withdrawing the King, which, like in normal Chess, always remains an option, and thus does not need to be signalled), or the interposition and capturing of the checker for the direct battery survive in combination with mandatory ducking of the other. In case of checking by a single battery, all evasion modes for that battery are passed to the daughter node, and ducking would be an alternative next to possibly other specified evasion modes.
But that makes it comparatively blind to checks and checkmates near the horizon. It only becomes aware of checks at d>=1, if after null move its King is captured. It happily stands pat at d=0 in checkmated positions, and futility-prunds moves that checkmate at d=1 in anticipation. Check extension does not help against this, as it will not extend without being aware of the check. In micro-Max I take all that for granted, but it is a major source of weakness compared to other engines. It is really helpful to know if a moves checks in advance, so you can exempt it from futility pruning, or extend it. If you extend checks at the end of the full-width search (d=0), you will detect matesone level beyond the normal horizon, rather than only one ply before it, i.e. you see them two ply earlier. That really helps.
For this reason I still want to make the attempt to find an efficient way to recognize moves as checks before I make them. (So that I get this extra two-ply visibility for nearly free, rather than by reducing nps so much that it makes me lose two plies of depth in the first place.)
The most promising scheme I have designed so far is this: before generating moves I run through the K, R, C and H section of my piece list (these are the pieces that can pin or deliver discovered checks, maximally 7) to test them for alignment with the enemy King. If they align, I scan the 'ray' (for Horses that is only one square) to count the number of blockers. If it is one (for K, R and H) or 2 (for C), I mark each of them as pinned in a 32-bit bitmap. Each piece of white and black has its own private bit in this. As a side-effect of this process I will also discover Cannons eye-to-eye with the King, that can deliver the undiscovered checks by interposition of something, and would mark the directions (from King) in which this happens as bits in a 'gunPointMask', compatible with the bit asignment in my '0x88'-capture-test table.
This prelude consists overhead that is always done, but is cheap compared to pseudo-legal move generation that follows. (As most of the 6 tested pieces will not align, and I will only have to do a ray scan for each that does in one direction, while move generation would have to do ray scans for all pieces in all their directions.)
When the turn of a move comes up to be searched, I will test its bit in the map of check blockers. If it is a blocker, I will then clear that bit, set a discovered-check variable to the from square of the move, and partially redo the ray scan over the from square to know exactly what type of battery moving this piece out-of-the-way will release on the opponent's King. This leads to enabling of possible evasion types (interposing, capturing the checker, 'ducking' (= moving a way the platform of an enemy Cannon)), and specifying them (in which direction, on which square, etc.).
The idea is that you then only have to do this one time for each piece that can deliver a discovered check, (which is rare anyway), so that the effort can be shared by all its moves. As long as the discovered-check variable is set, you extract all moves with that piece that reveal the check (i.e. moves off the ray, or captures on the ray) from the move list, rather than looking at the next move of the list. If no moves fitting the requirements are found, you clear the discovered check variable.
For each move (revealed check or other) you always do a '0x88' test to see if it attacks the enemy King, and can use the gunPointMask to test if any alignment corresponds to a direction that activated a Cannon. Together this information allows you to classify the battery from the direct direction. This classification also results in a list of possible evasions (interposing, capturing the checker, ducking). Then you have to combine the info of the direct and the discovered battery. (Note that there is a danger for double counting here that you have to intercept: a Cannon can reveal a Rook check by jumping over it with a capture, and deliver a direct check using that Rook as platorm, so that the direct and indirect part merge into a single RC battery.)
If check occurred from only a single battery (be it direct or indirect), all the evasion types for that battery remain valid, and are passed to the Search call of the reply node, to inform it of the check, and assist it in move generation. If check comes from two batteries, the situation is still not hopeless: if one battery allows ducking as evasion type, moving away the platform takes care of it, and could capture the checker or interpose for the check by the other battery. This requires a special mode of the in-check move generator, "evade A with mandatory ducking of B". (Note that ducking only is a possible evasion when a piece friendly to the checked King acts as platform for a Cannon check, so in case of checking by two batteries, only the revealed part can involve ducking, simplifying the recognition of this special case somewhat.)
So in combining the evasions of checks by two batteries, either all evasion modes are cleared (except withdrawing the King, which, like in normal Chess, always remains an option, and thus does not need to be signalled), or the interposition and capturing of the checker for the direct battery survive in combination with mandatory ducking of the other. In case of checking by a single battery, all evasion modes for that battery are passed to the daughter node, and ducking would be an alternative next to possibly other specified evasion modes.