Felicity EGTB generators and probers

[phhnguyen]

I have been rethinking my algorithm a bit. One of the tasks it would have to perform is identifying which black-to-move positions (black referring to the losing player) only have non-losing moves that qualify as chases. Originally I planned to mark the positions where a white piece (king or unprotected other) is under attack in the EGT itself, so that this information would be retrieved as a side effect of probing to see whether the position the move leads to is already declared won (for white).

But I now realized that this information can be obtained quite cheaply during the move generation itself. For a given constellation of the white pieces I could mark squares in a board-size array chase[sqr] from where the opponent could attack it, each white piece having a bit assigned to it. When generating moves from a position that is a candidate loss, we could then AND all these codes for the to-squares of moves that (by EGT probing) are found to be non-losing. As soon as the result is zero we could stop, and revert the position to 'undecided', as we would have found a save escape. If this doesn't happen, the resulting chase code will indicate which white piece has to be chased to keep any hope to survive.

When the EGT is scanned by displacing the black pieces in the inner loops, the chase[] board would only have to be re-initialized in an outer loop. E.g. if black has King + Rook once every 9*90 = 810 positions. So this would take only negligible time.

There is one problem with that, though: in some of the 810 black constellations the King might block the move that was marked as attacking a given target. So rather than assigning a single bit to each potential attack, we would need different bits depending on the square it originates from, in particular which Palace squares it crosses. A small table of masks indexed by the king location could then be used to clear the bits from the moves that are blocked.

We cannot plainly AND all resulting chase codes, though, as chases of the same target can now be indicated in different bits. This can be solves by subtracting 1 from the chase code, to see if the carry propagates to some higher bit. If any of the bits indicating the move chases would be set, it would not propagate. By OR-ing all such decremented chase codes we can then determine whether a particular piece must be chased to escape a loss. (Namely when the corresponding bit ends at 0.)

Maybe you take a look at how we generate endgames of both side-armed?

• In the first step we generate an endgame by using the “traditional” way: almost the same way as the one for chess. It works until there is no change on values of positions

• We will start running special algorithms for Chinese chess to detect perpetual check chase (PCC) AFTER the first step is completed. PCC positions are drawn for chess because of their repetitions. Those positions cannot be progressed and have the value UNSET after the first step. We will work mainly on those positions only. That means we don't generate PCC information on the fly when generating endgame with the traditional method

• We don’t separate between white and black positions but treat them equally since any side could do PCC

[hgm]

I always generate 'one-sided EGT', which distinguish win vs non-win for a particular player, but not draw vs loss. This allows for more compact representation of the states that positions can have, and thus for a lowering of the storage demands. One can obtain a two-sided EGT by combining two one-sided EGT for white wins and black wins, which were calculated separately, the remaining positions being the draws. But there is actually little advantage for making such a combination, and I keep them as separate EGT.

That also means that during generation, I only have to disarm perpetuals of the non-winning player. Without special measures perpetuals would remain in the 'undecided' state (I suppose this is what you call UNSET), and would never be confused with a win for the chasing player. And I don't care whether it is a loss or remains undecided forever.

I don't think traditional generation followed by some special PCC identification would work. In particular with end-games where the losing side has a Rook, and the winning side no defenders, perpetual checking would be an effective defence (had it been allowed) against any progress, and the traditional generation would run aground almost immediately, after identifying a few mate in 1 positions. You really have to alternate the PCC loop detection (and convert the exitless loops to wins/losses) with traditional retrograde iteration. You could do a PCC step after traditional iteration stops producin new decided positions, but I usually prefer to generate the DTx in an orderly fashion, only generating the next DTx. And then identify the perpetuals that have their last remaining non-losing exits plugged by this.

The latter will of course be done by the usual algorithm: identify 'must-chase' positions where all non-chasing moves lose, Identify the 'perpetuate' positions where the winning player is being chased and has a move to a must-chase (and does not win outright), consider all of these 'candidate wins/losses', and then clear those candidacies by retrogradely walking the network of those, starting from candidate losses that still have moves to undecided positions. And finally declaring all remaining candidates as win or loss with some DTx.

I am just trying to find an efficient implementation for doing this.

[phhnguyen]

I always generate 'one-sided EGT', which distinguish win vs non-win for a particular player, but not draw vs loss. This allows for more compact representation of the states that positions can have, and thus for a lowering of the storage demands. One can obtain a two-sided EGT by combining two one-sided EGT for white wins and black wins, which were calculated separately, the remaining positions being the draws. But there is actually little advantage for making such a combination, and I keep them as separate EGT.

That also means that during generation, I only have to disarm perpetuals of the non-winning player. Without special measures perpetuals would remain in the 'undecided' state (I suppose this is what you call UNSET), and would never be confused with a win for the chasing player. And I don't care whether it is a loss or remains undecided forever.

Your method is quite different from ours. So far, all authors (including me) who published their work ignored PCC when generating one-side-armed endgames (one side has attackers such as Rooks, Cannons, Horses, and Pawns, and the other side has no attacker).

I don't think traditional generation followed by some special PCC identification would work. In particular with end-games where the losing side has a Rook, and the winning side no defenders, perpetual checking would be an effective defence (had it been allowed) against any progress, and the traditional generation would run aground almost immediately, after identifying a few mate in 1 positions. You really have to alternate the PCC loop detection (and convert the exitless loops to wins/losses) with traditional retrograde iteration. You could do a PCC step after traditional iteration stops producin new decided positions, but I usually prefer to generate the DTx in an orderly fashion, only generating the next DTx. And then identify the perpetuals that have their last remaining non-losing exits plugged by this.

The latter will of course be done by the usual algorithm: identify 'must-chase' positions where all non-chasing moves lose, Identify the 'perpetuate' positions where the winning player is being chased and has a move to a must-chase (and does not win outright), consider all of these 'candidate wins/losses', and then clear those candidacies by retrogradely walking the network of those, starting from candidate losses that still have moves to undecided positions. And finally declaring all remaining candidates as win or loss with some DTx.

I am just trying to find an efficient implementation for doing this.

I have an example from my paper about the position you mentioned above: one side (White) with Rook + an Advisor, losing the other side (Black) with Rook only. The following image is from the paper:



By generating traditionally, the white Rook has only one "Draw" move which checks the black King (denoted by a yellow circle). All other moves are lost (denoted by red circles). That turns out that move will lead to a repetition of perpetual check. My PCC algorithm can detect that move/position and assign it a special value, -PERPETUAL_CHECK, to denote it is a losing perpetual check move.

[hgm]

These are examples of what I called 'must-chase' positions: the only moves that do not lose in 1 or 2 moves are chases. (Where for briefness I consider checks as a chase of the King.) My point was that it is probably not possible to find any losses in 3 or more moves by traditional generation before you first have concluded that this particular position is a loss by the chasing rule. Because it is so easy to chase with a Rook, that as soon as white makes any non-checking move black has the possibility to launch a perpetual again. That you have any mate in 2 in the left position from traditional generation is only by virtue of the fact that the first move is a check, so that black has to interpose (and lose) his Rook rather than use it for checking himself. And it is unlikely that all positions that are won to white can be won by checking only; in general repeated checking with the same piece just leads to a repetition.

In KRAKR this might not matter so much, as it seems to me that black has a fortress draw (with R in front of K on the central file) which he can very easily reach. So that there probably are no long wins at all, and the only wins are fast ones where black is under immediate mate threat, and has no time to reach the fortress.

But in end-games that are generally won where you need (say) to advance Pawns to the opponent Palace to break through his defences and force the checkmate, you will need many Pawn moves to get there. And none or those will be checking before they get there. So after each Pawn move you must face another barrage of Rook checks by the losing side, until he has exhaused all non-repeating possibilities. In the initial traditional EGT generation you will never get the positions with the far-away Pawns identified as wins. Positions that need five Pawn moves to win will only be found after you have determined that all the checking sequences starting from positions where you only need four Pawn moves lead to perpetuals. So you will have to alternate traditional generation and PCC detection many times to find all wins.

I think this is the algorithm that was described by Fang et al. Except that in the paper I have seen they only discussed perpetual checks, not chases.

[phhnguyen]

These are examples of what I called 'must-chase' positions: the only moves that do not lose in 1 or 2 moves are chases. (Where for briefness I consider checks as a chase of the King.) My point was that it is probably not possible to find any losses in 3 or more moves by traditional generation before you first have concluded that this particular position is a loss by the chasing rule. Because it is so easy to chase with a Rook, that as soon as white makes any non-checking move black has the possibility to launch a perpetual again. That you have any mate in 2 in the left position from traditional generation is only by virtue of the fact that the first move is a check, so that black has to interpose (and lose) his Rook rather than use it for checking himself. And it is unlikely that all positions that are won to white can be won by checking only; in general repeated checking with the same piece just leads to a repetition.

In KRAKR this might not matter so much, as it seems to me that black has a fortress draw (with R in front of K on the central file) which he can very easily reach. So that there probably are no long wins at all, and the only wins are fast ones where black is under immediate mate threat, and has no time to reach the fortress.

But in end-games that are generally won where you need (say) to advance Pawns to the opponent Palace to break through his defences and force the checkmate, you will need many Pawn moves to get there. And none or those will be checking before they get there. So after each Pawn move you must face another barrage of Rook checks by the losing side, until he has exhaused all non-repeating possibilities. In the initial traditional EGT generation you will never get the positions with the far-away Pawns identified as wins. Positions that need five Pawn moves to win will only be found after you have determined that all the checking sequences starting from positions where you only need four Pawn moves lead to perpetuals. So you will have to alternate traditional generation and PCC detection many times to find all wins.

I think this is the algorithm that was described by Fang et al. Except that in the paper I have seen they only discussed perpetual checks, not chases.

IMHO, your thinking is in the right direction. However, you have been distracted by many details.

Let me show my way. It works for both checks and chases.

We start at positions with UNSET values (after a traditional generator stops due to data becoming stable/no change). All those positions are untouched/un-progressed (typically they will be replaced by DRAW value at the end by the traditional generator). Each position from them sooner or later must lead to a repetition. That is why we check only them if they are PCC or not. If one is PCC, we will set its score as -PERPERTUAL_CHECK/-PERPERTUAL_CHASE.

From a given UNSET position and a side:
1) check if that side is checking or chasing (some opposite pieces), ignore if not. That side is suspected of violating the PCC rules. We need to check further with the following step
2) we need to create a kind of search/minimax tree. The tree has multiple levels. Each level is one side, changed alternatively.
- The node of the given side is called the attack. If a node does not attack any more (stop checking or chasing) or if it has any better children moves, say, to be a draw (it cannot be a win) the node can avoid losing. The tree stops at that branch - no PCC. Otherwise, expand all its children with UNSET values, if there is any child node not PCC, the node is not PCC
- The node on the opposite side is called the evasion. On one hand, it must evasion/rescue its King (from checking) or pieces (from chasing). However, on the other hand, that is also a good way to win. Unless it has a clear move to win (in that case, the tree stops at that branch - no PCC), any evasion-UNSET move is good to expand. The node is not PCC only when all children are not PCC

We expand and travel down/up the tree until getting a repetition. We check all moves/states in that repetition if it is PCC and if yes, set the score (-PERPERTUAL_CHECK/-PERPERTUAL_CHASE) for the root. Evasion nodes will have positive scores (+PERPERTUAL_CHECK/+PERPERTUAL_CHASE - they are winning perpetual scores). Depending on the methods we may stop now or continue exhausting all cases.

3) After all, we must propagate PCC positions to find all leading ones and set scores, say, +/-(PERPERTUAL_FORWARD - n)...

That is the basic algorithm. Pushing Pawns, capturing, winning, and losing moves... are all counted when we examine children's moves. There are still so many other details. The code for detecting perpetual chases is so complicated and slow.

[hgm]

IMHO, your thinking is in the right direction. However, you have been distracted by many details.

Well, the strategy of the algorithm is known. (Fan et al.) But before I can covert it to code, I must solve the implementation details.

Let me show my way. It works for both checks and chases.

We start at positions with UNSET values (after a traditional generator stops due to data becoming stable/no change). All those positions are untouched/un-progressed (typically they will be replaced by DRAW value at the end by the traditional generator). Each position from them sooner or later must lead to a repetition. That is why we check only them if they are PCC or not. If one is PCC, we will set its score as -PERPERTUAL_CHECK/-PERPERTUAL_CHASE.

In the EGT I want to build I would have no special score for perpetual checking, as I consider this the worst outcome of the game. If the worst outcome of a non-checking move is to be checkmated in 30, I would prefer to play that rather than lose immediately by violating the perpetual rule. After all, the opponent might not find the mate in 30. So I would set the score of the PCC nodes to mated in 30 in that case

I am aware that some of the positions in the PCC cycle might actually take longer to mate, even if the first repetition is already forbidden, as the defender might stay within the cycle for a few moves before it repeats. But which positions take the longest depends on where you entered the loop, so it cannot be tabulated. Strictly speaking the positions in the loop have a range of DTM. So it could be better to add the number of allowed checks in the longest cycle to the DTM of all of them. Disadvantage is that you get very large DTM, not fitting in 1 byte.

From a given UNSET position and a side:
1) check if that side is checking or chasing (some opposite pieces), ignore if not. That side is suspected of violating the PCC rules. We need to check further with the following step
2) we need to create a kind of search/minimax tree. The tree has multiple levels. Each level is one side, changed alternatively.
- The node of the given side is called the attack. If a node does not attack any more (stop checking or chasing) or if it has any better children moves, say, to be a draw (it cannot be a win) the node can avoid losing. The tree stops at that branch - no PCC. Otherwise, expand all its children with UNSET values, if there is any child node not PCC, the node is not PCC
- The node on the opposite side is called the evasion. On one hand, it must evasion/rescue its King (from checking) or pieces (from chasing). However, on the other hand, that is also a good way to win. Unless it has a clear move to win (in that case, the tree stops at that branch - no PCC), any evasion-UNSET move is good to expand. The node is not PCC only when all children are not PCC '.

You can indeed do the 'verification' of 'potential losses' through a multi-ply forward search. This is a logical extension of the traditional generation, where 1-ply forward searches are used to see if any moves to an UNSET position exist. (In which case the current position is not yet lost.) This was how I wanted to do it before I read the Fan et al. paper. The problem is that the seach could be very deep. Not so much for checking, due to poor King mobility and confinement, but for chasing. A Rook can chase a Horse or a Cannon all over the board before you get a repetition.

The problem is that this will often lead to nothing, with the conclusion that the winning side cannot yet force a repetition no matter which of the zillion of paths it Cannon traverses the board, because at any stage of the sequence the losing side can escape to an UNSET position. So the suspect position will in the end stay UNSET, so that in the next iterations you will have to repeat the search over and over again, until finally the traditional retrograde propagation has turned all the non-chased positions to which the chasing player could leave the tree to 'regular' losses for him.

I think this also touches on an issue we still need to resolve, that generation in the presence of perpetual ban needs PCC identification and traditional retrograde propagation to alternate, many times. After traditional propagation runs out of new wins/losses, you can run the PCC identification algorithm, which turns some of the left UNSET positions to wins/losses. But these new wins and losses will act as new seeds for traditional propagation, which will then resolve some more non-PCC positions before that runs out of steam. And this will cause some PCC candidate positions that were previously declared to be false alarms and remained UNSET to now become wins/losses. Etcetera.

We expand and travel down/up the tree until getting a repetition. We check all moves/states in that repetition if it is PCC and if yes, set the score (-PERPERTUAL_CHECK/-PERPERTUAL_CHASE) for the root. Evasion nodes will have positive scores (+PERPERTUAL_CHECK/+PERPERTUAL_CHASE - they are winning perpetual scores). Depending on the methods we may stop now or continue exhausting all cases.

3) After all, we must propagate PCC positions to find all leading ones and set scores, say, +/-(PERPERTUAL_FORWARD - n)...

That is the basic algorithm. Pushing Pawns, capturing, winning, and losing moves... are all counted when we examine children's moves. There are still so many other details. The code for detecting perpetual chases is so complicated and slow.

[hgm]

To get back to my algorithm:

Because of the need to repeatedly investigate the same PCC candidates for being 'forced' perpetuals, I want to keep as much info from one iteration to the next. E.g. whether an UNSET position counts as being chased (i.e. the side to move's king or unprotected piece is under attack) and has an evasion move to a position where the opponent only has moves that either are already known to be losing, or chase the same piece, takes quite some effort to determine. But once it has been established that this is the case, it will remain the case in subsequent iterations, until the position will be declared 'won'. (Either because one of the other evasions now are determined to be winning, or because the continued chase will get trapped in a perpetual cycle.) So I want to mark such positions in the EGT-under-construction with a special code in its DTM field ('PERPETUATE'), which is a special case of UNSET.

The most efficient way to do this is not systematically examining all UNSET positions to determine whether these happen to be chases, and then examine all the positions they can evade to to see if they qualify, but to start from the 'forced chases', and then retrogradely determine the evasions that lead to those. The forced chases appear cheaply as a side effect of the traditional generation: initially there are very few, because almost every move goes to an UNSET position that is not a chase. In a previous posting I described an efficient test for these moves to UNSET positions for being chases (and then what they chase).

If an UNSET position only has non-losing moves that are chases of the same piece, it can be declared 'MUST_CHASE' (yet another special case of UNSET). When this happens (which should be only rarely) retromoves to positions where the same piece is chased can be selectively generated, to immediately label the latter as PERPETUATE.

If at the end of the iteration some positions have been changed to PERPETUATE we have to run the PCC detection. To do that there must be two sub-states of PERPETUATE and MUST_CHASE: candidate perpetual and cleared. Initially they are all candidates. We then run through all MUST_CHASE positions to test whether any of their chasing moves goes to a position that is not a candidate-PERPETUATE. (Note that not all chases need be PERPETUATE; only the chases that have an evasion to a MUST_CHASE position are that.) If there is such a chasing move the MUST_CHASE is changed to the cleared form. (It is no longer a candidate.)

We also run through the candidate-PERPETUATE positions, to see if they still have any evasions to a candidate MUST_CHASE. If they haven't, because the MUST_CHASE position that originally gave them the status PERPETUATE has been cleared, and there are no other evasions to a MUST_CHASE that still is a candidate, they are also reverted to the cleared state. We have to keep repeating that as long as candidates have been cleared. If finally there is nothing that can be cleared anymore all remaining candidates become wins (the PERPETUATEs) or losses (the MUST_CHASEs).

Then we are ready for the next traditional iteration.

Note that after a traditional iteration all PERPETUATE and MUST_CHASE positions are candidates, while after the PCC detection all the remaining ones are in the cleared state. It thus makes sense to swap the encoding for the candidate and the cleared version of these states (which is basically used to detect repetitions during the PCC detection) every traditional iteration. Then you don't actually have to do anything to the positions in these states themselves.

[phhnguyen]

IMHO, your thinking is in the right direction. However, you have been distracted by many details.

Well, the strategy of the algorithm is known. (Fan et al.) But before I can covert it to code, I must solve the implementation details.

Not really. Fang worked on perpetual check only and ignored completely perpetual chase rules. IMHO, he described his work at a high level, not deep nor detailed enough for practising/implementation.

In the EGT I want to build I would have no special score for perpetual checking, as I consider this the worst outcome of the game. If the worst outcome of a non-checking move is to be checkmated in 30, I would prefer to play that rather than lose immediately by violating the perpetual rule. After all, the opponent might not find the mate in 30. So I would set the score of the PCC nodes to mated in 30 in that case

I am aware that some of the positions in the PCC cycle might actually take longer to mate, even if the first repetition is already forbidden, as the defender might stay within the cycle for a few moves before it repeats. But which positions take the longest depends on where you entered the loop, so it cannot be tabulated. Strictly speaking the positions in the loop have a range of DTM. So it could be better to add the number of allowed checks in the longest cycle to the DTM of all of them. Disadvantage is that you get very large DTM, not fitting in 1 byte.

You pondered so deeply. Instead of 1 step only like me, you thought in advance several steps, in both views of an EGTB developer and an engine developer!!!

Since you have understood well my way, we could discuss more easily later.

IMO, there are still many open issues, named some of them:
- Which metric should we use: DTM, DTC, DTZ or something new?
- Should we use non-deterministic scores (such as PERPETUAL_CHECK/CHASE or convert them into standard metric (DTM)? Advantages/disadvantages of each way?
- Which type of endgames can be generated fast? Which one is slow?
- How to speed up the PCC detections? How to reuse data/computation?
- Create a test set
...

[noobpwnftw]

At least hgm did indeed read that paper and understood the abstraction.

Checks and chases don't even cross each other in practice, or it'll be draw. Use two seperate sets of flags for each and chases are just having extra ways to filter out(i.e. must have overlapping attacked bitboards or fake). Also the 'correct' name for a secondary metric that counts distance to such loss by rule 'capturing' terminals is probably DTR.

DTM won't be large if you don't count the distance in loops(with check/chase flags), but you'll be needing two bytes and a second pass anyways, help yourself with a precomputed WDL. If you are down on the route that it'll require runtime forward search to find the actual distance, then you shouldn't be counting those in DTM in the first place or you risk search explosion and unable to minimize. Get a distance lowerbound from tablebases, perform search which may end up resulting a larger distance and try to improve that, not the other way around.

It is not like proof number searches cannot solve the problem given infinite resources. You are just dealing with some trivial tables that can be easily 'corrected' using forward searches. Those 'longest win' numbers in your current scheme are already absurd.

[hgm]

Not really. Fang worked on perpetual check only and ignored completely perpetual chase rules. IMHO, he described his work at a high level, not deep nor detailed enough for practising/implementation.

Indeed the paper did not reveal many details. But the described method can be easily generalized to also include chases. The MUST_CHASE and PERPETUATE positions that form the chasing networks need to be diversified by the set of pieces that they chase. For MUST_CHASE positions this can only be a single piece, because the rules allow chasing of multiple pieces (e.g. 1-check, 1-chase cycles). So even if a position can only escape a direct loss by a chasing move, when it has a choice for what piece to chase, it cannot be part of a forbidden perpetual, and should not be relabeled MUST_CHASE. The PERPETUATE position can offer the chased player the choice of evasions that force the opponent to chase one piece or another. So I guess the flag that distinguishes the cleared/candidate states must be specific for the piece that is chased. So that it can be cleared for chasing one piece, but remain candidate (and eventually become a win) for chasing another.

IMO, there are still many open issues, named some of them:
- Which metric should we use: DTM, DTC, DTZ or something new?
- Should we use non-deterministic scores (such as PERPETUAL_CHECK/CHASE or convert them into standard metric (DTM)? Advantages/disadvantages of each way?
- Which type of endgames can be generated fast? Which one is slow?
- How to speed up the PCC detections? How to reuse data/computation?
- Create a test set
...

Metric is a problem, as it is not clear how to count distance to mate in Xiangqi. (I.e. whether pointless checks have to be included in the count.) One could adopt a new metric that consists of a pair of numbers: number of aborted perpetuals the winning player has to suffer, and distance to the next perpetual. I expect that winning with a Cannon against a player that still has a Rook would be the slowest in your algorith: Rooks can chase Cannons in such a way that the Cannon cannot immediately retreat to the square it came from (because the Rook is now there). So it takes 8 ply befor you can have a repetition, and since these involve Cannon moves in opposit directions searching the moves in generated order is unlikely to find those without trying very many other moves first. Speedup can be achieved by not just trying forward moves from every position to see whether its state has changed, but by using retro-moving from changed positions to determine which positions are worth re-examining (which usually is a very small fraction). Keeping a separate to-do list might greatly speed up things (at the expense of some extra storage requirement).