Perpetual chasing in Xiangqi

[hgm]

1) What is a chase?
Let me quote from AFX rules:
"Perpetual chase: Player A makes a succession of chasing moves, while player B answers each move by moving away the piece under attack, or resolving the chase with another piece. If A continues to attack the piece move after move, he is making a "perpetual chase"."

- So as I understand in a chase one piece should be attacked and then escape from that attacking. The second action is "escape" but not "become protected".

OK, it all hinges on how we interpret "escape". Even the formulation above points out that this has to be interpreted in a wide sense: it does not mean you actually have to move the chased piece to a safer location (1). It explicitly states that you can "resolve" the chase with another piece. In the detail examples many cases are given where this is done by interposing a piece (2), or withdrawing the piece that acted as Cannon mount for the attack (3). But there are other conceivable ways to "resolve" an attack by moving another piece than the one that was chased:

4) Pinning the attacker, so that he cannot make the capture anymore without exposing his King to check.
5) Deliver a counter check, so that the opponent cannot make the capture, bust must resolve the check first.

None of the detail examples use either of these methods. Of course the classical ways to resolve a threat also encompass capturing the attacker (which is not possible in a repeat loop, and therefore of no concern here), and

6) Protecting the attacked piece.

Now the Asia-rule detail examples, contain the following (unnumbered) diagram as an "appendix":

Appendix: Example of Perpetual Chase
P76 m1+3
P67 m3-1
P78 m5+3
P87 m3-5
P76 ....

Explanation:
Red keeps moving its Pawn to keep the Black Knight "unprotected". This constitutes the Red Rook perpetually chasing the unprotected Black Knight. Red is violating the rule.

This explicitly mentions (6) as a recognized method for resolving a chase. Unfortunately it also mentions subverting the protection of a piece as a method to convert a pre-existing attack on that piece to a chase, which contradics several of the other detail examples. So I am not quite sure how to treat this example without wrecking other examples, and WinBoard currently treats this wrong, and would call it a draw.

Fortunately protecting a piece to resolve a chase almost never occurs in a _perpetual_ chase, becuase it tends to be a method to permanently make the victim invulnarable to chasing. To be able to chase that same piece on the next move, that next move would indeed need to subvert the protection (by blocking or pinning the protector, or moving away its mount).

- The move Kf0 actually is an action to sacrifice the Advisor Ae1. By that action, White does not move away nor protect that piece

This is a good point, that might expose a flaw in my current WinBoard implementation of the chase test. I have defined a perpetual chase as an uninterrupted sequence of _new_ attacks on the same piece. I implicitly assumed that when the chased side would not resolve the attack, it would not be possible to make a _new_ attack on the next move, because the attack was already pre-existing. But I overlooked that it might be possible to create a new attack on the same victim with _another_ piece.

And this is exactly what happens here. Ce5 chases Ae1, and Kf0 does not resolve that attack. But then on the next move, Cf5+ does create an attack by the Horse on this Advisor, by resolving the pinning of it.

So it seems that for any capture by side A that exists after a move of side A, I must not only test if the capture already existed before that move, but also if it still exists after the reply move. (How awkward. Of course I would then have to test in most cases if the victim was protected before the move and after the reply as well, when the attack still existed.)

The case at hand would then fail to be a chase, because the threat Ce5xe1 is not resolved by Kf0: the capture remains possible, and the Advisor is still unprotected.

[hgm]

Oh WOW. I now have ChessV supporting all the Xiangqi rules except for this nasty, heinous chasing crap. Kinda makes my ill just thinking about it...

Well, don't worry about it too much just now. For my live XQ tourney ChessV will be playing in a group where none of the opponents does know about chasing either. Some even don't know about perpetual checking.

Avoiding repetitions that are not reached through check evasions (e.g. by scoring them as -500 cP) is a very satisfactory poor-man's solution.

I understand that you eventually would like to get it exactly right, but I hope you can provide me with a version of ChessV for the tourney much before that! Even some of the strongest engines don't get it right.

I have no idea how I'm going to do it, (probably a topic for a separate thread), but my first question is: amateur human players really understand all of this?!?

My experience is that most human player don't have a clue. I asked around a lot, and mostly you get answers that are in direct violation of explicitly given examples of Asia rules. (Like "it can never be a chase if you move your King".)

Perhaps we should indeed open a thread discussing implementation. But we better first agree on what exactly the rules are, or we would jsut be spreading around incorrect implementations.

[hgm]

I wonder how existing Xiangqi GUIs and internet Xiangqi servers enforce perpetual chasing. For instance, whether they follow "Asian" rules, or use a simpler algorithm, or what. I'm referring to both casual GUIs and sites (like Yahoo games HK) and the more serious ones as well. I guess they probably don't all do it the same way.

I am pretty sure that they don't, and some actually make very course approximations. From their rule descriptions they sometimes just put restrictions on the number of checks you can give in a row, like "6 checks by the same piece, 12 checks if you do it with 2 pieces, ...".

My variant ICS does not implement any of this yet, not even perpetual checking. Which is why I don't really consider it operational for XQ. But I intend to fully implement it, some day.

[phhnguyen]

1) What is a chase?
Let me quote from AFX rules:
"Perpetual chase: Player A makes a succession of chasing moves, while player B answers each move by moving away the piece under attack, or resolving the chase with another piece. If A continues to attack the piece move after move, he is making a "perpetual chase"."

- So as I understand in a chase one piece should be attacked and then escape from that attacking. The second action is "escape" but not "become protected".

OK, it all hinges on how we interpret "escape". Even the formulation above points out that this has to be interpreted in a wide sense: it does not mean you actually have to move the chased piece to a safer location (1). It explicitly states that you can "resolve" the chase with another piece. In the detail examples many cases are given where this is done by interposing a piece (2), or withdrawing the piece that acted as Cannon mount for the attack (3). But there are other conceivable ways to "resolve" an attack by moving another piece than the one that was chased:

4) Pinning the attacker, so that he cannot make the capture anymore without exposing his King to check.
5) Deliver a counter check, so that the opponent cannot make the capture, bust must resolve the check first.

Firstly I am not very clear about your point on (5). However, after studying some other games which are ruled by WB, I make a guess about your point:

A chase situation may be:
1) Black does a move to attack a piece
2) White does a move (a check in this case)
3) Black has to release the attack (not chase anymore) to that piece (to solve the check)
4) White does another move
5) Black does a move to attack that piece again

If I am correct, I think it is not a constant chasing but one chase one idle.
Am I missing something?

None of the detail examples use either of these methods. Of course the classical ways to resolve a threat also encompass capturing the attacker (which is not possible in a repeat loop, and therefore of no concern here), and

6) Protecting the attacked piece.

Now the Asia-rule detail examples, contain the following (unnumbered) diagram as an "appendix":

Appendix: Example of Perpetual Chase
P76 m1+3
P67 m3-1
P78 m5+3
P87 m3-5
P76 ....

Explanation:
Red keeps moving its Pawn to keep the Black Knight "unprotected". This constitutes the Red Rook perpetually chasing the unprotected Black Knight. Red is violating the rule.

This explicitly mentions (6) as a recognized method for resolving a chase. Unfortunately it also mentions subverting the protection of a piece as a method to convert a pre-existing attack on that piece to a chase, which contradics several of the other detail examples. So I am not quite sure how to treat this example without wrecking other examples, and WinBoard currently treats this wrong, and would call it a draw.

Fortunately protecting a piece to resolve a chase almost never occurs in a _perpetual_ chase, becuase it tends to be a method to permanently make the victim invulnarable to chasing. To be able to chase that same piece on the next move, that next move would indeed need to subvert the protection (by blocking or pinning the protector, or moving away its mount).

- The move Kf0 actually is an action to sacrifice the Advisor Ae1. By that action, White does not move away nor protect that piece

This is a good point, that might expose a flaw in my current WinBoard implementation of the chase test. I have defined a perpetual chase as an uninterrupted sequence of _new_ attacks on the same piece. I implicitly assumed that when the chased side would not resolve the attack, it would not be possible to make a _new_ attack on the next move, because the attack was already pre-existing. But I overlooked that it might be possible to create a new attack on the same victim with _another_ piece.

And this is exactly what happens here. Ce5 chases Ae1, and Kf0 does not resolve that attack. But then on the next move, Cf5+ does create an attack by the Horse on this Advisor, by resolving the pinning of it.

So it seems that for any capture by side A that exists after a move of side A, I must not only test if the capture already existed before that move, but also if it still exists after the reply move. (How awkward. Of course I would then have to test in most cases if the victim was protected before the move and after the reply as well, when the attack still existed.)

The case at hand would then fail to be a chase, because the threat Ce5xe1 is not resolved by Kf0: the capture remains possible, and the Advisor is still unprotected.

[hgm]

A chase situation may be:
1) Black does a move to attack a piece
2) White does a move (a check in this case)
3) Black has to release the attack (not chase anymore) to that piece (to solve the check)
4) White does another move
5) Black does a move to attack that piece again

If only happened what you write here, I would agree (and so would WinBoard). But it could be that while releasing the attack, black creates an attack with _another_ piece as a side effect. (Note that the sequence you describe here does not really apply to the example, where it is black that does the checking, not white.)

Perhaps we should go to a simpler case, that does not involve checking:

[x]3a1r3/5k3/e8/2h6/2e6/4P4/9/8C/2R1A4/4KA3 w

Code: Select all

9 . . . a . r . . .
8 . . . . . k . . .
7 e . . . . . . . .
6 . . h . . . . . .
5 . . e . . . . . .
4 . . . . P . . . .
3 . . . . . . . . .
2 . . . . . . . . C
1 . . R . A . . . .
0 . . . . K A . . .
  a b c d e f g h i

1. Cc2 {attacks Hc6} Ee7 {withdraws platform} 2. Ci2 {discovers attack of Rc1 on Hc6} Ec5 {blocks that attack}

I think we will agree that white is chasing Hc6 here, with C + R alternately. Although white was voluntarily withdrawing the Cannon with wich he made the original attack, the capture Cc2xc6 was not anymore possible at that moment, because black had already resolved the threat by withdrawing the Cannon mount.

Now replace the Rooks in the diagram by Cannons:

[x]3a1c3/5k3/e8/2h6/2e6/4P4/9/8C/2C1A4/4KA3 w

Code: Select all

9 . . . a . c . . .
8 . . . . . k . . .
7 e . . . . . . . .
6 . . h . . . . . .
5 . . e . . . . . .
4 . . . . P . . . .
3 . . . . . . . . .
2 . . . . . . . . C
1 . . C . A . . . .
0 . . . . K A . . .
  a b c d e f g h i

1. Cc2 {attacks Hc6} Ci9 {threatens Ci0#} 2. Ci2 {blocks mate} Cf9

Compared to the previous diagram there are several complications:
a) With 1... Ci9 black does not really solve the attack on Hc6. Cc2xc6 remains possible and legal. He just makes it unattractive, because you get mated when you make the capture. But the mate threat has the same status as an idle move in Asia rules.
b) The way that white choses to solve the mate threat, by blocking the mating move with Cc2-i2, accidentally releases the original attack on Hc6, so that in the end the threat disappears (due to action of white, not black), and can be renewed later.
c) Like in the previous example, 2. Ci2 also discovers a new attack on Hc6, this time by Cc1.
d) black also does not resolve this attack, going for the repeat, this time without a clear counter threat.

Now (d) seems a bit non-sensical, because normally, not resolving a threat would simply mean that white captures, rather than continuing the repeat loop (3. Cc1xc6 {end of story}). But there could be tactical considerations that make it unattractive to use Cc1 for the capture. It could, for instance, be sandwiched (soft-pinned) between opposing Rooks on b1 and d1, so that moving it would cost you a Rook. So the attack of Cc1 on Hc6 is really an imaginary threat, but Asia rules are quite clear that even imaginary threats should count as chases. It should not be important anyway why exactly white playes the moves he does; maybe he is just stupid. Fact is, he plays a repeat, and the GUI or ICS must adjudicate the game because of it based on the moves he played.

According to the current WB algorithm, white would be considered chasing Hc6: the Horse is unprotected, and on one move white can capture it with Cc2, which he could not do before (because that Cannon was still on i2), and on the other move he can capture it with Cc1, which he could not do before (because Cc2 was in the way). This is all WinBoard takes into account, so the situation is classified as two Cannons chasing one unprotected Horse, which is forbidden.

The key question now is: should the fact that on both moves black did not make these new captures (legally) impossible disqualify the original attacks as chases.

A subsidiary question would be: can we really say that throwing a counter threat (in this case the mate threat) is not a valid way to defend against the newly created attack? And what if this counter-threat had not been a mate threat, but a King capture (i.e., if black had checked, in stead of making a mate threat)? In that case the capture of the Horse by Cc2xc6 would have been truly illegal, because it would not have resolved the check.

[phhnguyen]

A chase situation may be:
1) Black does a move to attack a piece
2) White does a move (a check in this case)
3) Black has to release the attack (not chase anymore) to that piece (to solve the check)
4) White does another move
5) Black does a move to attack that piece again

If only happened what you write here,

It is good that we have some agreement. I see that it is not too hard to implement code to solve all Asian examples but solving real games is a big challenge.

I would agree (and so would WinBoard). But it could be that while releasing the attack, black creates an attack with _another_ piece as a side effect. (Note that the sequence you describe here does not really apply to the example, where it is black that does the checking, not white.)

Perhaps we should go to a simpler case, that does not involve checking:

[x]3a1r3/5k3/e8/2h6/2e6/4P4/9/8C/2R1A4/4KA3 w

Code: Select all

9 . . . a . r . . .
8 . . . . . k . . .
7 e . . . . . . . .
6 . . h . . . . . .
5 . . e . . . . . .
4 . . . . P . . . .
3 . . . . . . . . .
2 . . . . . . . . C
1 . . R . A . . . .
0 . . . . K A . . .
  a b c d e f g h i

1. Cc2 {attacks Hc6} Ee7 {withdraws platform} 2. Ci2 {discovers attack of Rc1 on Hc6} Ec5 {blocks that attack}

I think we will agree that white is chasing Hc6 here, with C + R alternately. Although white was voluntarily withdrawing the Cannon with wich he made the original attack, the capture Cc2xc6 was not anymore possible at that moment, because black had already resolved the threat by withdrawing the Cannon mount.

Now replace the Rooks in the diagram by Cannons:

[x]3a1c3/5k3/e8/2h6/2e6/4P4/9/8C/2C1A4/4KA3 w

Code: Select all

9 . . . a . c . . .
8 . . . . . k . . .
7 e . . . . . . . .
6 . . h . . . . . .
5 . . e . . . . . .
4 . . . . P . . . .
3 . . . . . . . . .
2 . . . . . . . . C
1 . . C . A . . . .
0 . . . . K A . . .
  a b c d e f g h i

1. Cc2 {attacks Hc6} Ci9 {threatens Ci0#} 2. Ci2 {blocks mate} Cf9

Compared to the previous diagram there are several complications:
a) With 1... Ci9 black does not really solve the attack on Hc6. Cc2xc6 remains possible and legal. He just makes it unattractive, because you get mated when you make the capture. But the mate threat has the same status as an idle move in Asia rules.
b) The way that white choses to solve the mate threat, by blocking the mating move with Cc2-i2, accidentally releases the original attack on Hc6, so that in the end the threat disappears (due to action of white, not black), and can be renewed later.
c) Like in the previous example, 2. Ci2 also discovers a new attack on Hc6, this time by Cc1.
d) black also does not resolve this attack, going for the repeat, this time without a clear counter threat.

Now (d) seems a bit non-sensical, because normally, not resolving a threat would simply mean that white captures, rather than continuing the repeat loop (3. Cc1xc6 {end of story}). But there could be tactical considerations that make it unattractive to use Cc1 for the capture. It could, for instance, be sandwiched (soft-pinned) between opposing Rooks on b1 and d1, so that moving it would cost you a Rook. So the attack of Cc1 on Hc6 is really an imaginary threat, but Asia rules are quite clear that even imaginary threats should count as chases. It should not be important anyway why exactly white playes the moves he does; maybe he is just stupid. Fact is, he plays a repeat, and the GUI or ICS must adjudicate the game because of it based on the moves he played.

According to the current WB algorithm, white would be considered chasing Hc6: the Horse is unprotected, and on one move white can capture it with Cc2, which he could not do before (because that Cannon was still on i2), and on the other move he can capture it with Cc1, which he could not do before (because Cc2 was in the way). This is all WinBoard takes into account, so the situation is classified as two Cannons chasing one unprotected Horse, which is forbidden.

The key question now is: should the fact that on both moves black did not make these new captures (legally) impossible disqualify the original attacks as chases.

A subsidiary question would be: can we really say that throwing a counter threat (in this case the mate threat) is not a valid way to defend against the newly created attack? And what if this counter-threat had not been a mate threat, but a King capture (i.e., if black had checked, in stead of making a mate threat)? In that case the capture of the Horse by Cc2xc6 would have been truly illegal, because it would not have resolved the check.

IMO, 1... Ci9 black does not really solve the attack on Hc6 either.

Therefore right after that move, I consider that attack as a static one and remove it from my chasing list. That is similar the above game we have discussed: the move Ci9 is actually to sacrifice Hc6 (the other meaning of that move is not clear - he may come there by mistake). Ci9 does nothing to improve the situation (in term of chasing) and can't blame White any more. I rule that White chases nothing after that move and the game will be a draw.

[phhnguyen]

I have found a very similar but real endgame from my database. Red can easily win but instead he is playing a "peaceful" game. Black is giving up his Elephant and Red can capture that piece whenever he wants. Clearly he doesn't has to chase (to capture). Why we punish him?


[Event "Edited game"]
[Result "0-1"]
[Variant "xiangqi"]
[FEN "2eakc3/4a4/8e/9/9/9/9/7R1/4A4/2R1K4 w 0 1"]
[SetUp "1"]

{--------------
. . e a k c . . .
. . . . a . . . .
. . . . . . . . e
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . R .
. . . . A . . . .
. . R . K . . . .
white to play
--------------}
1. Rhc2 Cf7 2. Rf2 Cf9 3. Rfc2 Cf7 4. Rf2 Cf9 5. Rfc2 Cf7 6. Rf2 Cf9 7.
Rfc2
{Xboard adjudication: perpetual chasing} 0-1

[hgm]

Well, in principle if a chase is forbidden or not does not depend on if you are winning or not. If a side that can easily win lets himself be needlessly checkmated, we will also not correct it to draw. Games where people do not play for a win are not good test cases. Because who says they are playing for a draw then? They might as well intentionally seek a loss.

But I agree that even when you would add two Rooks for black, so that it would now be in the interest of white to secure a draw by repetition, it would be strange to consider the Elephant chased. So this means the current WinBoard implementation is not complete. To identify a chase, we must:

Code: Select all

1) determine all (legal) captures after the move
2) remove all captures that were already legal before the move
3) remove all captures that were still legal after the reply of the opponent
4) verify the captures left to make sure the victim was unprotected after the move.

WB does (1) and (2), but not (3).

In fact the Appendix chase suggest that (4), which is also what WB does, is not good enough. One must not only pay attention to the protected status after the move, but also before. This would amount to:

Code: Select all

1) determine all legal captures after the move
2) remove all captures after which recapture to the same square is (legally) possible
3) remove all captures that were already legal before the move, AND
   for which no legal recapture (to the same square) existed at that time
4) remove all captures that were still legal after the opponent's reply, AND
   for which no legal recapture (to the same square) existed at that time

This is more cumbersome, because we will have to test if recapture is possible in all three cases separately (before and after the move and its reply), before we decide to add or remove them from the list of potential chases, rather than first do the addition / removal, and only then judge the possibility of recapture. (Note that recapture here is interpreted in a slightly twisted sense, where recaptures of C and H after an R capture do not count, and can also be done pre-emptively between equal piece types.)

Note that this allows protecting a piece as a recognized way to rescue the piece from attack (as is needed to get the Appendix chase).

Problem is that this new algorithm would get the Appendix position right, but would now make some of the 104 other examples fail...

[phhnguyen]

Hi Muller and all,

I will show the algorithm which I have implemented Asian rule for my program, in hope that may help and we can discuss further. I also hope that we all help each other so our implementation will become clearer and better.

I think the most important is that in the end we can have some same understanding as well as agreement about Asian rules, avoiding any conflict between engines-WB-Xiangqi servers.

[phhnguyen]

My algorithm as following:

I. Main steps

1) Detect loop/repeat
Similar to the chess. Use the hash key to detect any repeat seem be the fastest and easiest method

2) Identify any perpetual check
Usually for each position we know if any side is in check. Thus we can easily detect perpetual check in this step without doing any extra (and expensive) computing of next steps.

We should not stop here if see one check one idle because pieces can chase others beside doing the task of checking/solving check.

3) Identify chases
I will explain with more details in the second part

4) Identify legal chases
After detecting there is a chase, we need to review all moves in the loop. Any legal chase move (such as chasing by Pawn, chase a protected piece) will turn the whole chase to be legal - simply delete/empty the chase list.

5) Evaluate the result
This part is very simple:
- None or both sides chase: draw
- One side chases: loses the game


II. Identify chases
The algorithm is based on some following assumptions:
- Chasing a piece is a continuous attack: any idle after a move (of chasing side) will not be considered as a chase.
- Seriously count the opponent re-action: if after an opponent move, the attack on a given piece is not removed, that piece will be considered as a sacrifice (or getting a static attack) and be removed from the chase list.
- Any static attack will be ignored
- A move can do dual tasks such as chasing while doing check/solving check

I define attack list is simply a list of pairs: attacker and its victim. All computing here is based on legal captures only. That helps us to solve the problem of detecting real/unreal attacks as well as protected and pinned pieces. The side of an attack list is the side of their attackers.

There are two main functions/operators on that list:
- Subtract(list1, list2): remove from list 1 all items which are also in the list 2. This function is used to remove all static attacks which have the same attacker-victim.
- Interception (list1, list2): In the list 1, keep only items which their victims are also in the list 2. This function is used to keep track only victims which are continuously being attacked after moves.

I have been using C++ so for short I can define and use two operators by - and &

Now we need to follow all positions in the loop:

1) Starting point
We create two chase lists for both sides as (full) attack lists of these sides. We will maintain those lists after move by move.

Suppose we have ChaseList is a chase list of one side:

2) After a move of opponent side
Suppose A is the attack list of that side after that move. Take a note that the opponent is trying to escape its chased pieces: those pieces should be in the current ChaseList but not be in the A. We need also to remove all static attacks, including all sacrifice pieces of opponent. Thus we need to use a subtraction:

Code: Select all

ChaseList -= A;

or using the clear function:

Code: Select all

subtraction(ChaseList, A);

3) After a move of the given side
Suppose A is the attack list of that side after that move; B is the attack list before that move. The given side is trying to set back the attack to escaped pieces thus those pieces should be in the A but not in the B – that why we use the subtraction operator (A – B). Because of counting only continuously attacks, we need to find the common victims between that result and the last chase list – use interception operator. We have:

Code: Select all

ChaseList = (A - B) & ChaseList;

or using functions:

Code: Select all

ChaseList = interception( subtraction(A, B), ChaseList);

After all moves (in the loop) if any list is not empty, its side is chasing. We need to implement Step 4 to detect and delete any legal chases.

Some notes/tips to help implementation:
- Each time updating ChaseList, remember to copy it to an array to use later to detect if there is any legal chase (step 4)
- Generating legal attacks is so expensive so you may focus on optimize that. These attack lists can be re-used when you detect legal protected pieces later.
- The way to recognize/compare pairs of attacker-victim (for two main operators) depends much on your method of board presentation. I see the easiest way is assign each piece a unique index and then use them to compare. Other ways may be harder such as keeping attacker and victims with their positions but you have to maintain those positions after each move

Hope it can help.

/Pham

PS: I have been starting to write a sample program of implementing Asian rule to help new comers but can’t guaranty about release date.