📝Greg Strong wrote on Sat, Nov 19, 2022 02:41 AM UTC:
This is a technical follow-up to recent discussion in otherthreads. Overview: there are cases where whether a move is legal depends on what other moves are available. These follow the general pattern where a certain class of moves are only legal if there is nothing else that is legal, in which case this class of moves all become legal.
I originally raised this in response to the Golem Chess rule that "a Golem or Half-Golem may not capture an opposing Golem or Half-Golem if the opposing Golem or Half-Golem is two squares away and defended by a piece on its own side" ... UNLESS there is no other legal move. I then realised this was similar to the Losing/Giveaway Chess rule that non-capturing moves are only legal if there are no captures. We discussed a plan for implementation, which I have started implementing. While doing this, I found a place in ChessV where I had already encountered this problem and "hacked" it in a less general way and forgot about it ... That is the Jumping Chess rule that if there is a piece on an edge square that can make a capture, the player must make one of those moves (their choice) but nothing else is legal. Having come up with these three cases already, I must assume there are more. So, on to how these can be solved in a universal chess engine ...
Typically, moves are either legal or not. It is true that a move generator generates so-called "pseduo-legal" moves they might turn out not to be legal when made (if, for example, they expose your King to check or leave him in check.) But when these pseudo-legal moves that are not really legal are actually made, it is detected that they aren't actually legal and they are skipped. Details of how this happens varies but it doesn't really matter. This is simple and doesn't depend on any other moves. ChessV handles it like this: whenever a move is made, a MoveBeingMade message is routed to every Rule in the Game that receives that message. The rule can then return an IllegalMove result code to rule the move illegal. Besides exposing your King to check, other reasons exist such as a LocationRestrictionRule stopping your King from leaving the castle or your Elephant from crossing the river, or the TradePreventionRule making Lion "iron" by preventing captures after you've captured the opponent's Lion. (As an irrelevant aside, MoveBeingMade messages are also handled just for the purpose of updating game state - such as the EnPassantRule determing when a pawn push creates the possibility of an en passant capture.)
But now we have pseudo-legal moves who's legality depends on what other legal moves exist. This presents a new challenge. The general idea is this: allow the MoveBeingMade function to return a new code, which I originally called IllegalUnlessOnly but am now calling FallbackLegality. Moves of FallbackLegality are all legal if and only if all pseudo-legal moves are either FallbackLegaltity or IllegalMove. These moves could be temporarily set aside and tried again later if appropriate, or, if appropriate, a new node could be launched with tail recursion wherein FallbackLegality moves would be accepted. For purposes of this discussion, the implemention details don't matter.
So now that I'm actually implementing this, of course I've found an issue - which is the reason for this post. What we have so far is straight-forward ... until we get to Quiescent Search. I won't define QSeach in detail since I've explained it several times before, and since this conversation is only really of interest to implementers of chess variant engines who should know this anyway. But in qsearch we only try captures so we don't actually know what all the legal moves are. For purposes of determining the impact of this issue, a quick revisit of the three known use cases of FallbackLegality:
1. Losing/Giveaway Chess: If a player can make a capture, he must (although he can choose which). So all moves which are not captures are FallbackLegality.
2. Jumping Chess: If a player can make a capture with a piece that is on a boarder square, he must (although he can choose which). So all moves which are not captures of a pice on a border square are FallbackLegality.
3. Golem Chess: a Golem or Half-Golem may not capture an opposing Golem or Half-Golem if the opposing Golem or Half-Golem is two squares away and defended unless there is no other legal move.
Impact on qsearch? For cases 1 and 2, I think there is no impact. These rules already consider everything that is not a capture to be of FallbackLegality. Easy peasy. But #3 is a problem. Here a capture can be ruled illegal if there is a legal non-capture, which we won't know in quiescent search. We could generate and test them all, but that would be way, way too expensive. (Something like 90% of nodes are qsearch nodes.) So, if we treat this case like 1 and 2 and sweep it under the rug, we can consider a golem capture of the enemy golum legal when it is not. This could have a dramatic impact on the score. So I think we should not consider this capture in qsearch, since the circumstances where it would be legal are quite rare.
We could rule out all FallbackLegality moves in qsearch ... That would not affect case #1 at all and it is what we want in case #3, but it would be bad in case #2. In case #2, we want to do exactly what we normally do - generate all captures and use our normal rules for FallbackLegality.
I think this is solved by adding another Game variable. As I have variables for things like whether Static Exchange Evaluation should be enabled, I plan to add a Game variable called "ConsiderFallbackLegalityMovesInQSearch" to control whether normal rules for FallbackLegality should be applied in qsearch or if we should just rule all these moves out. In case #1, the setting wouldn't matter. In case #2, we would want the setting to be true. In case #3, we would want the setting to be false. (This will result in an incorrect evaluation on occasion, but qsearch isn't perfect. This is the lesser of the two evils.)
This is a technical follow-up to recent discussion in other threads. Overview: there are cases where whether a move is legal depends on what other moves are available. These follow the general pattern where a certain class of moves are only legal if there is nothing else that is legal, in which case this class of moves all become legal.
I originally raised this in response to the Golem Chess rule that "a Golem or Half-Golem may not capture an opposing Golem or Half-Golem if the opposing Golem or Half-Golem is two squares away and defended by a piece on its own side" ... UNLESS there is no other legal move. I then realised this was similar to the Losing/Giveaway Chess rule that non-capturing moves are only legal if there are no captures. We discussed a plan for implementation, which I have started implementing. While doing this, I found a place in ChessV where I had already encountered this problem and "hacked" it in a less general way and forgot about it ... That is the Jumping Chess rule that if there is a piece on an edge square that can make a capture, the player must make one of those moves (their choice) but nothing else is legal. Having come up with these three cases already, I must assume there are more. So, on to how these can be solved in a universal chess engine ...
Typically, moves are either legal or not. It is true that a move generator generates so-called "pseduo-legal" moves they might turn out not to be legal when made (if, for example, they expose your King to check or leave him in check.) But when these pseudo-legal moves that are not really legal are actually made, it is detected that they aren't actually legal and they are skipped. Details of how this happens varies but it doesn't really matter. This is simple and doesn't depend on any other moves. ChessV handles it like this: whenever a move is made, a MoveBeingMade message is routed to every Rule in the Game that receives that message. The rule can then return an IllegalMove result code to rule the move illegal. Besides exposing your King to check, other reasons exist such as a LocationRestrictionRule stopping your King from leaving the castle or your Elephant from crossing the river, or the TradePreventionRule making Lion "iron" by preventing captures after you've captured the opponent's Lion. (As an irrelevant aside, MoveBeingMade messages are also handled just for the purpose of updating game state - such as the EnPassantRule determing when a pawn push creates the possibility of an en passant capture.)
But now we have pseudo-legal moves who's legality depends on what other legal moves exist. This presents a new challenge. The general idea is this: allow the MoveBeingMade function to return a new code, which I originally called IllegalUnlessOnly but am now calling FallbackLegality. Moves of FallbackLegality are all legal if and only if all pseudo-legal moves are either FallbackLegaltity or IllegalMove. These moves could be temporarily set aside and tried again later if appropriate, or, if appropriate, a new node could be launched with tail recursion wherein FallbackLegality moves would be accepted. For purposes of this discussion, the implemention details don't matter.
So now that I'm actually implementing this, of course I've found an issue - which is the reason for this post. What we have so far is straight-forward ... until we get to Quiescent Search. I won't define QSeach in detail since I've explained it several times before, and since this conversation is only really of interest to implementers of chess variant engines who should know this anyway. But in qsearch we only try captures so we don't actually know what all the legal moves are. For purposes of determining the impact of this issue, a quick revisit of the three known use cases of FallbackLegality:
1. Losing/Giveaway Chess: If a player can make a capture, he must (although he can choose which). So all moves which are not captures are FallbackLegality.
2. Jumping Chess: If a player can make a capture with a piece that is on a boarder square, he must (although he can choose which). So all moves which are not captures of a pice on a border square are FallbackLegality.
3. Golem Chess: a Golem or Half-Golem may not capture an opposing Golem or Half-Golem if the opposing Golem or Half-Golem is two squares away and defended unless there is no other legal move.
Impact on qsearch? For cases 1 and 2, I think there is no impact. These rules already consider everything that is not a capture to be of FallbackLegality. Easy peasy. But #3 is a problem. Here a capture can be ruled illegal if there is a legal non-capture, which we won't know in quiescent search. We could generate and test them all, but that would be way, way too expensive. (Something like 90% of nodes are qsearch nodes.) So, if we treat this case like 1 and 2 and sweep it under the rug, we can consider a golem capture of the enemy golum legal when it is not. This could have a dramatic impact on the score. So I think we should not consider this capture in qsearch, since the circumstances where it would be legal are quite rare.
We could rule out all FallbackLegality moves in qsearch ... That would not affect case #1 at all and it is what we want in case #3, but it would be bad in case #2. In case #2, we want to do exactly what we normally do - generate all captures and use our normal rules for FallbackLegality.
I think this is solved by adding another Game variable. As I have variables for things like whether Static Exchange Evaluation should be enabled, I plan to add a Game variable called "ConsiderFallbackLegalityMovesInQSearch" to control whether normal rules for FallbackLegality should be applied in qsearch or if we should just rule all these moves out. In case #1, the setting wouldn't matter. In case #2, we would want the setting to be true. In case #3, we would want the setting to be false. (This will result in an incorrect evaluation on occasion, but qsearch isn't perfect. This is the lesser of the two evils.)