EGT generation when perpetual check is a loss

[hgm]

Normal EGT generation would leave perpetual checks as draws. This is no good for games where perpetual checking is forbidden, such as in Xiangqi. In that case, we have to extend the normal EGT generation algorithm with a step that declares such loops as lost when the only moves that stop checking all bring the checking player to a verified loss.

There exists an algorithm for doing this, and this posting just describes in detail a attempt to efficiently execute this. The basic idea is to do the normal retrograde iteration, but after each iteration (say the one that identified the mate-in-N wtm and mated-in-N btm positions) identify all perpetual checking loops that black can only escape from by moving to a mate-in-N position. These loops will then be declared mate(d)-in-N too.

To efficiently identify the loops we introduce the label 'in-check' for undecided wtm positions where white is in check. These are already determined during the initialization of the EGT. Btm positions that only have no moves to positions labeled 'undecided' will be labeled 'problematic', if they are not 'lost' already. (In these black must lose or keep checking.) All wtm predecessors of a 'problematic' position where white is in check will be labeled 'promising'. Btm positions that only have moves to 'won' or 'promising' positions will be labeled 'desperate'; their wtm predecessors where white is in check are also 'promising'.

This labeling will happen in the course of the normal iteration process: when a wtm position improves its state, be it to 'won' or to 'in-check' or 'promising', all their predecessors will be examined for whether this has consequences for their own state, which could deteriorate from 'undecided' to 'problematic' to 'desparate' to 'lost'. If they become 'lost', calculating the further consequences of that will be postponed for the next iteration. If they become 'problematic' or 'desperate', however, we will immediately turn all their 'in-check' wtm predecessors into 'promising', which could further turn the btm predecessors of those from 'problematic' into 'desperate'. But that transition will never have any further consequences.

After the iteration all positions where black's only alternative to being mated-in-N is checking will then have been labeled 'problematic' or 'desperate'. In 'problematic' positions black must check to avoid a verified loss, but he can reach the 'in-check' wtm position, from which white cannot force him to check again (i.e cannot move to another 'desperate' or 'problematic' position). So these positions are (still) fine for black. The 'desperate' positions are not necessarily lost, as black might be able to stop checking after several checks. To determine whether that is the case we will work our (retrograde) way through the checking network, starting at the 'problematic' positions.

The 'promising' predecessors of 'problematic' positions will be examined to determine whether they have at least one move to a 'desperate' position. If not, they are relabeled 'disappointing', and their btm 'desperate' predecessors will be relabeled 'solved'. After such relabeling the same process will be run recursively on them as on the 'promising' positions. As there is only a finite number of 'desperate' position, and each recursive call destroys one, this process must terminate.

The 'desperate' positions can then be declared 'lost'. In particular, we declare those 'mated-in-N' as the only non-checking exits of the perpetual-check loop they are part of lead to 'mate-in-N' positions. (There are no faster mates found yet at this point.) Note that this effectively does not count the turns spent in the perpetual loop ('pointless checks') in the DTM. It is not possible to distinguish positions within the perpetual loop by DTM, as which one is closer to mate depends on where you entered the loop.

The 'promising' positions that were left are all predecessors of at least one 'desperate' position that was just turned into 'lost', and the next iteration will cause them to turn into 'won', and the further ocnsequences of that. The 'disappointing' and 'solved' positions will revert to 'promising' and 'desperate', respectively, as these are not permanent conditions, and they might not be so lucky after the next iteration deteriorated many positions for black by including the longer mates.

State encoding

We will use 1 byte per board position. The lowest bit in this byte will be used to indicate the position has been declared won with white to move. The other 7 bits in principle encode the DTM of the position with black to move.

This doesn't seem to provide for the multitude of states the algorithm needs for wtm positions. But we use a trick here, exploiting the fact that all wtm positions that are not 'won' or 'undecided' are positions where white is in check. Such positions cannot possibly be lost to black when black has the move, as he would simply capture the white King. Therefore these do not need a DTM. So we can set 3 of the DTM codes apart for indicating the wtm in-check, promising and disappointing state of that board position. Similarly, we can reserve 3 DTM codes for the desperate, problematic and solved states of btm positions.

In summary

Code: Select all

white to move:
won            predecessors of 'lost'
promising      predecessors of 'desperate' or 'problematic' that are not 'won'
disappointing  as 'promising' but proven to be part of a finite checking sequence
in-check       other positions where white is in check
undecided      all other positions

black to move:
lost         all successors are 'won'
desperate    one or more successors are 'promising', all others 'won' 
problematic  one or more successors are 'in-check', all others 'won' or 'promising'
solved       one or more successors are 'disappointing', all others 'won' or 'promising'
undecided    other positions

[Rein Halbersma]

Isn't it more economical to handle perpetual checks as a post-processing step after the regular EGT generation instead of after every iteration?

Here's what I do with the public information subset of Stratego endgames (not yet published) where perpetual chasing is forbidden.
First, generate an EGT in the regular way (WDL database). Then all unresolved states are marked as 'potential draws'. For all such states, check if there is at least one move that does not threaten to capture another piece that leads to such a potential draw. Those states are all marked as 'actual draws'. Then you iterate: for all as yet unresolved states, check if there is at least an 'actual draw' successor, but this time even threatening moves are considered since in the first iteration, the perpetual chase was already broken. You stop when no more states are resolved. The rest of the 'potential draws' are marked as losses. For DTM databases, you have to do slightly more work by also finding out the strongest defense, that can take a few more iterations on the remaining positions, I haven't tried that.

[hgm]

The process you describe sounds very much like the recursive tree-walk I described to turn 'desperate' positions into 'solved' (where the latter correspond to your 'actual draws'). It doesn't really matter whether this is implemented recursively, to directly continue from a position that was declared 'solved', or iteratively, finding those positions by scanning through the EGT until you run out of them.

But I think you would have to do that after every iteration, and not just at the end of the generation. Because declaring positions lost by perpetual checking or chasing will make all positions that can force the losing player to them (but not force a win directy) also won, and you would have overlooked that so far.

The following Xiangqi example illustrates that:

[d]9/3k5/3r5/9/9/9/4P4/4R4/4K4/9 w

This is won for white(*), but the only forceable mates occur after the Pawn enters the Palace. And for each step you advance the Pawn you have to last through a series of Rook checks on d0/d1. So an initial retrograde generation will never reach any positions where the Pawn still has to advance outside the Palace, as these would always be 'refuted' by perpetuals. Only after declaring that perpetual as a loss you see that the position before the Pawn advance was also won, and you can compute retrogradely from there. (Which will also run aground almost instantly, at the next perpetual you have to disarm.)

*) White advances the Pawn to e8, (unstoppable, since it is twice protected by the KR battery), and assuming the black King is still on the d-file then plays Rc2, threatening Rc9# (after Kd7 Re7# checkmates immediately). It doesn't matter that black can pick up the Pawn with his Rook through a check, as you then play Rc9+ to drive the black King to d8, after which you play Rc8 to skewer K + R.