Perpetual chasing in Xiangqi

[hgm]

I think the main problem we still have to face is whether a checking side can also chase, and how we determine it. A good example was sent to me two days ago:

[d] 4k4/9/3R5/4c4/2n6/4N4/9/4C4/9/5K3 w

Code: Select all

. . . . k . . . .
. . . . . . . . .
. . . R . . . . .
. . . . c . . . .
. . h . . . . . .
. . . . H . . . .
. . . . . . . . .
. . . . C . . . .
. . . . . . . . .
. . . . . K . . .

1.Hg5+ Cf6 2.Rf7 Cd6 3.Rd7 Cf6 4.He4+ Ce6 5.Hg5+ ...

Actually, this is about two cases: with or without Hc5. In the latter case the question is: is the black Cannon being chased. On 2.Rf7 and 3.Rd7 this is obvious, but how about 1.Hg5+ and 4.He4+? These moves do check, as well as attack the Cannon with a new attack by the Horse. In all cases the attack is resolved by withdrawing the Cannon.

If we decide this is a chase, then the next question is: what if an additional black Horse is on c5? Does the Cannon now count as protected, when it is of e6? (Which would then make it a non-chase.) The point is, how to determine it? Normally you would make the capture (2.Hg5xe6 Hc5xe6) after 1... null, and determine if it leaves black in check. In this case of course it does, because black was already in check even before the capture. So his null move was illegal to begin with. But how else can we determine if we attack something? We first have to get the turn back...

There seem to be the following possibilities:
1) We could ignore checking moves completely, like they do not belong in the cycle. This would mean you are already chasing when you attack a piece on all non-checking moves. It is logically equivalent to declare that all pieces are chased by a checking move.
2) The total opposite of this would be to declare that no piece should be considered chased on a checking move. This is equivalent to not testing for chasing violations for a side that also checks.
3) We could adopt the fiction that the null move would resolve the check, by discarding any check existing before it in further testing. This would require making a distinction between different kind of illegal (but pseudo-legal)moves.
4) We could replace the nullmove by an actual evasion, and further compute from there.

It seems (1) is out, as it directly contradicts diagram 12 of Asia rules, where a "one check, one chase" case is declared a draw. Ignoring the checking move, would make a "one chase" a perpetual chase, as this was the only move left.

I also do not like (4): it is quite problematic if there are several ways to resolve the check. The actual evasions could subvert protections, open lines for new protections, etc., even if there was only a single legal one. We would not pay attention to side effects of resolving chases (as opposed to checks), so it would be quite unnatural to do it for check evasions, where the only difference really is that the evasion is forced. Other examples of Asia rule tell us that it should be quite irrelevant if a certain move is the only legal one, or not.

That leaves (2) and (3). IMO (3) would be the most logical. Using (2) would make a chase of piece A together with a "one chase, one idle" against piece B, which is defined as forbiddedn, different from a chase of piece A together with a "once check, one idle" against the King, which I think is undesirable. Unfortuately, this is also the computationally most complex solution...

[hgm]

Note that the dilemma sketched above does occur in determining if a piece of the checked side is protected, (because determining that involves a nullmove), but not for if an attack is a sacrifice / offer to exchange. E.g. the following position:

Code: Select all

. . . . k . . . .
. . . . a . . . .
. . . . . . . . r
. . . . . . . . .
. . . . R . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . C . . . .
. . . . K A . . .

1. Ri5+ Re7 2.Re5 Ri7 3.Ri5+

Next to the check, Ri5+ creates a new attack on Ri7. Normally such an attack would be considered a sacrifice, because Ri7xi5 is possible. Now, however it is not legally possible, because it does not resolve the check. So the move s a chase. Tke move 2.Re5 creates a Cannon attack on Re7, and the fact that at the same time you offer to exchange Re7 does not absolve you of that (e.g. diagram 92). So this is a perpetual chase on the black Rook, and white loses.

As no null move is involved in the determination of the sacrifice status, (through 1.Ri5+ Rxi5 2.Cxe9), there is no need to involve any fictional resolution of the check.

[phhnguyen]

I think the main problem we still have to face is whether a checking side can also chase, and how we determine it. A good example was sent to me two days ago:

[d] 4k4/9/3R5/4c4/2n6/4N4/9/4C4/9/5K3 w

Code: Select all

. . . . k . . . .
. . . . . . . . .
. . . R . . . . .
. . . . c . . . .
. . h . . . . . .
. . . . H . . . .
. . . . . . . . .
. . . . C . . . .
. . . . . . . . .
. . . . . K . . .

1.Hg5+ Cf6 2.Rf7 Cd6 3.Rd7 Cf6 4.He4+ Ce6 5.Hg5+ ...

My implementation is somewhat to ignore the check (1) but not really completely. The variable protectedStatus has a special value PROTECTED_INCHECK which we can understand it as unclear or unidentified. This value can be set by searching previous or next position which is always not in check for concerning side.


Back to above game, my program will examine 5. Hg5+ as an attack to Cannon which protectedStatus is PROTECTED_INCHECK. To get the real value, the program will search the attackList after or before that move (in this case it is before) and see that protectedStatus of that Cannon is PROTECTED_YES: the Cannon is really protected and game is draw. All process is cheap because of finding stored data only.

[hgm]

It is not yet clear to me how this works. Normally we would check if a piece is protected against a specific capture. E.g.

Code: Select all

c . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
R . . . . . . . .
. . . . . . . . .
c . . . h . . . .
. . H r . . . . R
. . . . . . . . .

Ca2 is protected against Hxa2, but not against Rxa2. Hc1 is protected against Rxc2, but not against Hxc2.

So if you test if a piece is protected before the move that chases it, what exactly do you test. The capture against which it should be protected is not yet possible, or it would certanly not be a chase. How about this:

Code: Select all

. . . . k . . . .
. . . . . . . . .
. . . . . . . . .
. . h . H . . . c
. . . . R . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

White plays Hd8+, attacking Hc6. Is the latter Horse protected? Before the move the pseudo-capture Ci6xc6 existed...

[phhnguyen]

In check is a very special status in which we hardly identify protections (that why I set values as unidentified). Even by using some methods you can get some values, that result may be totally useless because in the end you can't use it alone but you have to connect it to other positions (which are not in check) and what you want for the game result.

I see that Asia Rule says too few about protection and none concerning with protection-in-check (even Diagram 12 somewhat deals with that). Unless having a new upgraded version, we are almost free to explain protection-in-check as we want. The good thing I guess that we can rule 99.99% games the same even having some difference on code / method of detecting that protection.

In short coming time I will stick to method of detecting protection-in-check by looking before and after attack lists because of cheap computing (I have posted in previous post).

I guess that the bellow game may be another trouble if you insist a "real" value for protection of Cf7

. . . . k r e . C
. . . . . . . . .
. . . . e c . . .
. . . . R . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . C . . . .
. . . . . . . . .
. . . . . . . . .
1. Rf6+

[hgm]

I would be inclined to consider Cf7 unprotected here. The algorithm I propose is this:

Just like in the case of non-checking we base 'attack after my move' on the fiction that it is my turn again, in stead of the opponent's, and 'protected' on him to recapture when I use that fictional right to move by capturing something, we base it on a slightly more complex fiction in the case of checking. This fiction is that it is again our turn to move, but now also that the pieces that were checking permanently lost the ability to capture to the square where the King is now.

So in the example you give, after Rf6, Ce2 is checking. So we give the turn to white, while Ce2 permanently loses the right to capture to e9. White can now capture Rf6xf7, showing Cf7 is attacked. Black cannot reply with Rf9xf7, because that would leave him in check by Ci9. And although Ce2 can no longer capture to e9, Ci9 still can, because it was not originally checking.

I don't think this is very hard to implement. The chasinf algorithm always start with making an attack list of the moving side (i.e. attacks by him) after his move. On a checking moves, there are King captures in this attack list, and we can set these apart. We must test for the King being victm anyway, to prevent effort being wasted on them by checking if the King was protected or not. Now for all other pseudo-legal captures in the attack list, we have to try the capture, and then try

1) if the opponent can capture our King
2) if not, if the opponent can recapture the piece with which we just captured
2-a) if he can, do it, and test if we can now capture his King

Now the only refinement that is needed is that at this point (2-a) we would have to check if any King capture that is found is not 'black-listed' as one of the original King captures. This could start with a test if the checked King is still in the original place (i.e. was not used to do the recapture). Only if it is, we would have to test the piece that can capture it against the list of original checkers.

Note that in a case like this:

Code: Select all

R . . H k a . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

1.He7+

this algorithm would not consider Af9, which is attacked by the Horse, as protected by the King: although after He7xf9 black is not in check, as Ra9xe9 is disabled, Ra9xf9 (after 2.Hxe9 Kxf9) is perfectly allowed. So black has no recapture, and the attack of He7 on Af9 could very well trn into a chase. (E.g. if black resolves the check by interposing something on b9, restoring the protection of Af9).

I think this is quite natural.

[hgm]

I discussed the matter of perpetual chasing at the ICGA Computer Olympiad in Japan with several Xiangqi participants. It seems there is a consensus about the way to handle checks during a chase, and it is different from what we converged upon here.

Basically it amounts to the following rule: when testing for chases in the presence of checks, always apply the fiction that the check (i.e. the move that actually captures the King in the position that is part of the loop) is disabled in the rest of the analysis. This applies not only for determining if a piece of the side that is in-check is a true protector, but also for if the in-check side attacks something before its move. So if a side that is in check has a pseudo-legal capture that he cannot do before the check-evasion (because it wold leave him in check), but can do after the check evasion, it does NOT count as a chase, because the pseudo-legal capture would become legal when ignoring the existing check in all daughter positions. So the capture is assumed to exist both before and after the check-evasion, and hence is not a chase.

There also surfaed a new interpretation of the fist position we discussed here:

3a1ke2/4a4/4e4/RH6p/p3c1p2/9/2C2h3/4H3E/4A4/1r1AK4 w 2 44



44. Kf0 Cf5+ 45. Ke0 Ce5 46. Kf0 Cf5+ 47. Ke0 Ce5
{Xboard adjudication: perpetual chasing} 1-0

Although the Advisor attacked by Ce5 does not attempt to escape the attack, it can still be considered a chase of that Advisor by Hf3 on that Advisor, through subverting the protection of that Advisor. Before the move the Advisor is protected by its King against Hf3xe1. But after Ce5 the Cannon is a second attacker of the Ae1, and thus, after Hf3xe1, Ke0xe1 is no longer possible. So the Advisor is in danger of being taken by Hf3. The move Kf0 then makes this capture impossible, by pinning Hf3. So all three conditions are satisfied, and Hf3 is chasing Ae1 on the move Ce5 (although the Cannon is not, because Ae1 does not flee from its range). As Hf3 is alsochasing Ae1 on Cf5+ (creating the attack by un-pinning He3, while the evasion Ke0 then protects the Advisor), this should be considered a perpetual chase after all!

[Ferdy]

In Xiangqi it is not allowed to force the opponent into repetition. So like in Chess, after the same position repeats for the 3rd time, the game can be claimed. But unlike Chess, the result is not always a draw. If, all the moves between the current position and the one two occurrences before were forcing moves, that side loses!

Now exactly which moves are forcing, and which not, depends on the local rules. Checks are considered forcing under any rule set, so perpetual checking is always forbidden. But on threatening mate-in-1, or threatening to gain material through deep tactic, like a skewer ("check and capture"), the rules differ. In "China mainland rule" all this is forbidden, making these rules practically unimplementable. Computer Xiangqi therefore usually follows Asia rules, which are highly simplified. Basically in Asia rules, only making a direct attack on a piece will be considered a forcing move. Mate threats, or material gains after an exchange of multiple moves does not count. Forcing moves that are not checks are referred to as chases.

Even with that simplification, Asia rules are highly complex. In the official description, 104 example diagrams are given of perpetual chases, or repeats that are not to be considered chases (and thus draws). The following set of rules seems to cover all these 104 cases, though:

1) Checking is considers a worse offence than chasing another piece. So if one side is perpetually checking, and the other is perpetually chasing, the checking side loses. All chases are equal, though: if one side perpetually chases a Rook, and the other a Pawn, it is draw.

2) To make a forbidden perpetual chase, you must really chase the same piece on every move of the repeat cycle. (And it does not matter which piece does the chasing: two (or multiple) pieces taking turns to chase one is still forbidden. ) Having a single non-forcing move in the cycle ("one check, one idle", "one chase, one idle") completely acquits you of chase charges. Also alternately chasing two different pieces (including "one check, one chase") is allowed.

3) A chase must be a _new_ attack on a piece. If you could already capture piece A with piece B before move M, then being able to capture A with B after M does not threaten anything new, and is not a chase. E.g. moving a Rook along the attack ray is not creating a new attack. (Checks, obviously, always are new.) Note that one move can result in mutiple chases, both on multiple targets, (e.g. forks) and by multiple perpetrators (e.g. discovered attacks). They all must be judged separately.

4) A newly created attack is in general only considered forcing (i.e. a chase) if the target is not protected. If it can be recaptured on the same square, the attack is not a chase. (Note that the possibility to recapture might depend on how the piece is captured, in case of multiple attackers, so this has to be judged per (attacker, victim)-pair, and is not an intrinsic property of the victim.) But there are some exceptions that are declared either always a chase or never a chase, irrespective of the protected status of the victim:
- Attacks of Horse or Cannon on Rook are always a chase
- Attacks on a Pawn that has not crossed the River are never a chase
- Attacks by a Pawn or King are never a chase
- Attacks on a King are of course always checks

5) An attack on a piece is also not considered a chase if the piece can capture its attacker (which must be of equal type) back. The possibility for such pre-emptive self-defence is considered as good as having a protector that can retaliate. Such attacks are called "sacrifices" or "offers to exchange", not chases. Note that it does not matter if you can pre-emptively capture the attacker with another piece than the chased one, or if the chase victim can capture a piece other than the one chasing it.

6) In all cases only legal moves are taken under consideration. Pseudo-legal captures that are not legal are to be completely ignored. This applies to the attacks itself, to recaptures by a protector, or to pre-emptive counter captures. On the other hand, if the move is legal, does not have to be a good one. Even if it gets you mated in one after making it, or loses you heavy material, the move should be taken into account. (E.g. when a piece is twice attacked, and only once protected, recapturing might be suicidal, but the piece still counts as protected.)

These are the rules according to which WinBoard adjudicates repetitive Xiangqi games. This thread was created to discuss cases where this might lead to controversion (or wrong) adjudications.

I encountered a game decided by perpetual chasing as adjudicated by winboard (profile-20110913). I am not sure here why winboard favors white.

Code: Select all

[Event "Computer Chess Game"]
[Site "test-PC"]
[Date "2011.12.22"]
[Round "9"]
[White "HaQiKi D 1.7d ana"]
[Black "Makulit v2.0.1"]
[Result "1-0"]
[TimeControl "40/60"]
[Variant "xiangqi"]
[Annotator "4. +0.28   4... -0.19"]

1. Hc2 c5 2. Ca2 Hc7 3. Rb0 Rb9 4. Rb4 {+0.28/10 0.9} Ch5 {-0.19/11 1.0} 5.
Afe1 {+0.08/10 1.6} Hg7 {+0.03/11 1.6} 6. Rb6 {+0.20/9 0.9} Ece7
{-0.03/10 1.6} 7. Rc6 {+0.44/10 0.8} Rc9 {+0.05/12 1.6} 8. g4
{+0.40/11 2.4} Cb1 {+0.32/12 1.6} 9. Hg2 {+0.48/10 0.9} Ri8 {+0.43/11 1.4}
10. Ege2 {+0.68/10 0.9} Rb8 {+0.27/11 1.6} 11. Hf4 {+0.84/11 1.2} Cf5
{+0.25/11 1.6} 12. Hd5 {+1.16/11 1.4} Rd8 {+0.11/13 1.6} 13. Hf6
{+0.88/11 1.2} Cc1 {+0.49/10 1.5} 14. c4 {+1.28/11 1.3} cxc4 {+1.08/11 1.4}
15. Exc4 {+1.12/10 1.1} Cc5 {+1.25/10 1.4} 16. E4e2 {+1.72/11 1.6} Ci5
{+0.87/11 1.8} 17. Rd6 {+1.64/12 1.6} Rcc8 {-0.22/12 1.6} 18. Rxd8
{+1.80/13 1.7} Rxd8 {-0.19/11 0.2} 19. Rf0 {+1.80/12 1.0} Cb5
{-0.35/11 1.7} 20. g5 {+3.00/12 1.7} e5 {-0.85/11 1.7} 21. gxg6
{+3.20/12 1.9} Hge6 {-1.30/12 1.7} 22. g7 {+3.36/11 1.3} Cb8 {-1.40/12 1.1}
23. Hb4 {+3.40/10 1.5} Cd1 {-1.47/11 1.6} 24. Ch6 {+3.72/10 1.1} Hc5
{-1.27/11 1.2} 25. Hc6 {+4.16/9 1.1} Cd6 {-2.12/11 1.7} 26. Ch9
{+3.92/10 0.9} Rh8 {-1.98/13 1.4} 27. Hd7+ {+3.32/11 2.1} Ke8
{-1.73/13 1.8} 28. Cxf9 {+2.72/11 0.9} Hb3 {-1.85/12 1.3} 29. Cf1
{+2.76/12 1.0} Kd8 {-1.27/12 1.5} 30. Cc2 {+3.44/11 1.5} Cc8 {-1.56/14 1.8}
31. Cxc7 {+2.52/12 1.1} Cxc6 {-1.15/13 1.8} 32. Cf3 {+1.92/12 1.8} Hd4
{-1.68/13 1.3} 33. Cf7 {+1.92/12 2.0} Ae8 {-0.90/12 1.9} 34. Cc8
{+1.76/11 1.0} Cc7 {-0.89/12 1.9} 35. Rf6 {+1.76/11 1.2} Hb5 {-1.27/12 1.9}
36. Af0 {+2.24/11 1.2} Rh1 {-0.77/14 1.9} 37. Cxe8 {+2.48/12 1.5} Kxe8
{-0.71/12 0.3} 38. Rxi6 {+2.48/11 2.0} Kd8 {-1.81/13 2.3} 39. Ri8+
{+2.72/12 2.3} Kd9 {-1.65/14 2.0} 40. Rb8 {+2.60/12 3} Rb1 {-1.58/13 3} 41.
Rb6 {+2.68/10 1.2} e4 {-1.67/12 1.5} 42. exe4 {+2.84/12 1.6} Hc3
{-1.72/11 1.5} 43. Rc6 {+2.92/12 1.5} Hb5 {-2.33/12 1.5} 44. Afe1
{+4.16/11 1.2} a5 {-2.25/10 1.5} 45. Rb6 {+4.64/11 1.7} Cd1 {-1.71/13 1.2}
46. Cf5 {+4.52/11 0.8} Rc1 {-2.50/15 1.5} 47. Cd5+ {+4.92/12 3} Hd6
{-1.38/4} 48. Ea2 {+5.00/12 1.3} Rc2 {-2.70/11 1.2} 49. Eac4 {+5.76/11 1.3}
Cd3 {-3.47/12 1.6} 50. Rc6 {+7.20/11 1.1} Rxe2 {-4.47/13 1.3} 51. Rxd6
{+7.28/13 1.7} Cxd6 {-4.66/12 0.2} 52. Exe2 {+7.32/14 3} Kd8 {-4.66/13 1.6}
53. e5 {+7.08/13 1.1} Ke8 {-5.12/15 1.6} 54. gf7 {+7.40/13 1.9} Cb6
{-5.62/15 1.6} 55. Kf0 {+7.40/13 1.2} Cb8 {-5.73/17 1.5} 56. e6
{+7.68/14 2.3} Ca8 {-5.61/15 1.6} 57. i4 {+8.36/13 1.5} Cb7 {-5.64/14 1.6}
58. i5 {+8.48/12 1.1} Cc7 {-5.59/14 1.2} 59. ih5 {+8.60/12 1.8} Cb7
{-5.76/14 1.4} 60. hg5 {+10.92/14 1.4} Cc8 {-6.04/13 1.2} 61. Ce5
{+399.72/13 0.5} Kd8 {-6.04/16 1.3} 62. Cd5+ {+399.92/3} Ke8 {-6.93/15 1.7}
63. Ce5 {+399.72/13} Kd8 {+0.00/35 1.2} 64. Cd5+ {+399.92/3} Ke8
{-6.93/15 1.7}
{Xboard adjudication: perpetual chasing} 1-0

Code: Select all

9  . . . . . . e . .
8  . . c . k . . . .
7  . c . H e s . . .
6  . . . . s . . . .
5  p . . C . . s . .
4  . . . . . . . . .
3  s . . . . . . . .
2  . . . . E . . . .
1  . . . . A . . . .
0  . . . A . K . . .

   a b c d e f g h i
6e2/2c1k4/1c1HeP3/4P4/p2C2P2/9/P8/4E4/4A4/3A1K3 w
s=pawn of white side

Perpetual moves:
Cd5e5 ke8d8 Ce5d5 kd8e8 ...

[hgm]

This is indeed a controversial case, and I recently changed WinBoard's treatment of it. The reason this is ruled a chase is the attack of Ee7 on Pg5. With the black King on e8 this move is not legal, because the Elephant is pinned by Ce5. But Kd8 unpins it, and thus counts as a new attack on Pg5. This part is not controversial.

Now white prevents the capture of Pg5 by Cd5+, forcing black to evadethe check first. So WinBoard does not consider Pg5 attacked in this position, as Exg5 is illegal. After Ke8, however, Exg5 becomes legal again, and is thus counted as a new attack. Hence Pg5 is being chased.

This interpretation where existing pseudo-legal captures are 're-activated' by evading a check and thus counted as new attacks is controversial, and after discussing this problem with other Xiangqi participants in Kanazawa it became clear to me it is not the preferred interpretation of Asia rule. Hence I introduced (in a more recent thread on this topic) the concept of 'quasi-legal moves'. Even with the King in check on d8 Exg5 is considered quasi-legal, because although it leaves Kd8 in check after the move, this is not a new check, as Cxd8 was already possible before the moves. So Ee7 is not pinned. So the quasi-legality of Exg5 before black's move is to be tested under the fiction that all pre-existing checks (here Cd5xd8) are permanently disabled, making the capture Exg5, and concluding that Kd8 cannot be taken through any non-disabled move. Exg5 is therefore not considered a new attack (by WinBoard 4.6.0), and there would be no chase.