H. G. Muller wrote on Sun, Nov 17, 2019 04:50 PM UTC:
I still wanted to comment a bit on legality checking and game-end detection:
There is no need to assign illegal moves the same score as a legal losing game termination. You can assign it an even lower score. This reminds me of the fact that there are many Xiangqi engines that prefer losing by perpetual checking over being mated in 1. But the behavior can entirely be controlled by setting the score for the various kinds of game termination; minimax or alpha-beta doesn't require a binary game outcome. (Luckily, or the heuristic evaluation would not be any good.) If losing by illegal move gets a lower score than any form of losing by legal means, minimax should always avoid it. Unless the game rules themselves are incomplete, and allow you to manoeuvre by legal moves into positions where you have no legal moves, but which are not defined as terminal. (Most common case of this is failing to define stalemate as game end in games where the goal is King capture, under the false assumption that you will always have pseudo-legal moves.) Even in that case the illegal-move score will merely show up in the root as the most dishonorable form of losing.
It is useful to distinguish 'direct' termination conditions (detectable from the move or piece counts, such as King capture or baring) from 'indirect' ones (depending on the location of pieces and how they move). 'Check' is already a complex condition, defined in terms of pseudo-legal moves. 'Legal' (and thus illegal) are again defined in terms of check. And 'checkmate' is defined in terms of 'legal'. These definitions taken at face value often imply search, being of the form "there must not exist a move that ...". The definition of checkmate even involves a two-ply search, as it requires all pseudo-legal moves to be searched for legality, which again requires all replies to be examined for King capture.
Now it is very possible that there exist shortcuts for doing these searches, e.g. check detection through the super-piece method, or mate detection through estabishing that the checker(s) cannot (all) be captured, nothing can be interposed to block the check(s), and the King has nowhere to withdraw to. This is pretty well developed for orthodox Chess, but can get arbitrary complex in arbitrary variants. E.g. for determining whether a square is attacked when there are hoppers, bent sliders or locust capturers around (not to mention Coordinators, Immobilizers and Pincher Pawns). The super-piece method requires generation of retrograde captures, which must be handled by dedicated code, which can easily be inconsistent with the prograde move generator used in search. And for mate detection, what if there is a Lion around that can capture two checkers in one move? Or capture one, and block the other? What if there are bent sliders, that can both be blocked on a single square? What if the checkers involve a hopper, and its mount can move away, capturing or blocking another checker? How do I determine whether a locust capturer will attack me after the evasion? If I just stick to the official definition of these game concepts I only need prograde pseudo-legal-move generation, and there is not nearly as much that could go wrong.
You mentioned the 'beaten path', but you should keep in mind that this is the path used by developers of engines for orthodox Chess, and thus might not necessarily lead to where you want to be. No matter how much smartness you built into your engine for more efficient detection of the game-end conditions, it will never hurt to be prepared for game rules where these shortcuts fail, and some illegal moves escape your dedicated detection for those. So I would recommend to reserve a score for 'illegal move', (which, with checking rules, would be the negated score of capture or extinction of royal(s)), so that your engine will not crash if you inadvertantly run into a King capture. And in any node detect whether enough of the moves you thought to be legal are indeed legal, so that you would not have to declare game end after all (with an appropriate score different from the illegal-move score, like a draw or a distance-to-root-corrected losing or winning score). Which is pretty easy by starting bestScore at the illegal-move value, and see at the end if it stayed there. In cases where your dedicated game-end detection fails, your would then have a safety net in the engine. As for the GUI, you could always subject all moves to a search to make sure they are legal, and make the depth of this search a parameter of the variant, which can then be increased for variants with unusually complex game-termination rules.
I still wanted to comment a bit on legality checking and game-end detection:
There is no need to assign illegal moves the same score as a legal losing game termination. You can assign it an even lower score. This reminds me of the fact that there are many Xiangqi engines that prefer losing by perpetual checking over being mated in 1. But the behavior can entirely be controlled by setting the score for the various kinds of game termination; minimax or alpha-beta doesn't require a binary game outcome. (Luckily, or the heuristic evaluation would not be any good.) If losing by illegal move gets a lower score than any form of losing by legal means, minimax should always avoid it. Unless the game rules themselves are incomplete, and allow you to manoeuvre by legal moves into positions where you have no legal moves, but which are not defined as terminal. (Most common case of this is failing to define stalemate as game end in games where the goal is King capture, under the false assumption that you will always have pseudo-legal moves.) Even in that case the illegal-move score will merely show up in the root as the most dishonorable form of losing.
It is useful to distinguish 'direct' termination conditions (detectable from the move or piece counts, such as King capture or baring) from 'indirect' ones (depending on the location of pieces and how they move). 'Check' is already a complex condition, defined in terms of pseudo-legal moves. 'Legal' (and thus illegal) are again defined in terms of check. And 'checkmate' is defined in terms of 'legal'. These definitions taken at face value often imply search, being of the form "there must not exist a move that ...". The definition of checkmate even involves a two-ply search, as it requires all pseudo-legal moves to be searched for legality, which again requires all replies to be examined for King capture.
Now it is very possible that there exist shortcuts for doing these searches, e.g. check detection through the super-piece method, or mate detection through estabishing that the checker(s) cannot (all) be captured, nothing can be interposed to block the check(s), and the King has nowhere to withdraw to. This is pretty well developed for orthodox Chess, but can get arbitrary complex in arbitrary variants. E.g. for determining whether a square is attacked when there are hoppers, bent sliders or locust capturers around (not to mention Coordinators, Immobilizers and Pincher Pawns). The super-piece method requires generation of retrograde captures, which must be handled by dedicated code, which can easily be inconsistent with the prograde move generator used in search. And for mate detection, what if there is a Lion around that can capture two checkers in one move? Or capture one, and block the other? What if there are bent sliders, that can both be blocked on a single square? What if the checkers involve a hopper, and its mount can move away, capturing or blocking another checker? How do I determine whether a locust capturer will attack me after the evasion? If I just stick to the official definition of these game concepts I only need prograde pseudo-legal-move generation, and there is not nearly as much that could go wrong.
You mentioned the 'beaten path', but you should keep in mind that this is the path used by developers of engines for orthodox Chess, and thus might not necessarily lead to where you want to be. No matter how much smartness you built into your engine for more efficient detection of the game-end conditions, it will never hurt to be prepared for game rules where these shortcuts fail, and some illegal moves escape your dedicated detection for those. So I would recommend to reserve a score for 'illegal move', (which, with checking rules, would be the negated score of capture or extinction of royal(s)), so that your engine will not crash if you inadvertantly run into a King capture. And in any node detect whether enough of the moves you thought to be legal are indeed legal, so that you would not have to declare game end after all (with an appropriate score different from the illegal-move score, like a draw or a distance-to-root-corrected losing or winning score). Which is pretty easy by starting bestScore at the illegal-move value, and see at the end if it stayed there. In cases where your dedicated game-end detection fails, your would then have a safety net in the engine. As for the GUI, you could always subject all moves to a search to make sure they are legal, and make the depth of this search a parameter of the variant, which can then be increased for variants with unusually complex game-termination rules.