Perpetual chasing in Xiangqi

[hgm]

I am not sure I completely understand everything you wrote (I will continue to study it), but a quick reading sparked some concerns:

If chase is perpetual, is determined by the fact if it is on the same piece, but not necessarily by the same piece. So only doing operations on (attacker, victim) pairs cannot be enough. In WinBoard / HaQiKi D I keep both a chaseList (containing moves, i.e. (attacker, victim) pairs) and a preyList (containing chased pieces). The first step, spanning one move, does operations like you mention on the chaseList, to determine if an attack is new. (I can leave out attacks on pieces that are not in the preList, because they can never become perpetual anymore, and thus are not interesting.) That decides which attacks were chases, and thus which pieces must stay in the preyList, and which can be removed.

[hgm]

OK, with "attack list" of player P you mean the lst of attacks _on_ the pieces of A. Not _by_ the pieces of A. Right?

The problem I signaled above is that after a move of white (say), you cannot simply remove all white pieces from the chase list that are still under (forbidden) attack by black. They must be under attack by the _same_ piece as that was attacking them before. If they move voluntarily to a place where _another_ black piece can capture them, but not the original attacker, it would still be chase if the original attacker would renew its attack.

So I think the propagation of the lists must work as follows:

preyList[0] = all pieces
preyList[n] = preyList[n-2] & VICTIM(chaseList[n])
chaseList[n] = attacks[n] - attacks[n-1] - attacks[n+1]

where I index the lists for player P such that 0 would be just _before_ a move of that player, and the indexes would wrap around over the repeat loop. (So I could put 0 anywhere in the loop.)

So prey:ist only has to be updated every 2 ply, for even n, i.e. just before the player which is (potentially) being chased moves. we take the (forbidden) attacks on his pieces from attacks[n], remove the (forbidden) attacks after his move (the ones he did not try to escape from), remove the (forbidden) attacks before the previous move of his opponent (because these were static), so that we finally are left with the novel attacks that he tried to escape.

Thuis is all done at the level of captures, i.e. (attacker, victim) _pairs_. Two captures are different if either the attacker or the victim is different, and would then not be removed by the '-' operator. After the subtraction, we now take the victim field (indicated by the function VICTIM), to convert it to a set of _pieces_.

In practive, determining if a capture constitutes a 'forbidden' attack is rather expensive. Because we know that we will take the intersection with the old preyList later, can already throw out all captures that do not have their victim in that preyList. i.e. define a mixed operator &' that acts between lists of captures and lists of pieces:

preyList[n] = VICTIM((attacks[n] &' preyList[n-2]) - attacks[n-1] - attacks[n+1])

A capture is a forbidden attack (and thus belongs to attacks[n]) if all of the following conditions are met
1) the attacker is not K or P
2) the victim is not unpassed P
3) the attacker is not of the same type as the victim, OR
the the victim cannot (legally) capture the attacker
4) the attacker is C or H and the victim R, OR
there is no (legal) recapture after the capture to the victim square

Note that because both attacks[n-1] and attacks[n+1] are used to calculate preyList[n], and n is incremented in steps of 2, we use each of these twice. So per iteration, we only calculate one, and then remember the other for the next iteration. The fact that we have to try pre-emptive (3) or retaliatory (4) re-captures, and then check if these are legal, makes this expensive.

One other remark: the chase detection does not have to take place if both sides are perpetually checking. In real games this probably never occurs, but in the search, it does occur occasionally (and is the reason that MaxQi crashes, because the check-extension leeds to infinite recursion in that case).

[Graham Banks]

HG - please check your PMs.

[phhnguyen]

OK, with "attack list" of player P you mean the lst of attacks _on_ the pieces of A. Not _by_ the pieces of A. Right?

I define my chase/attack list as a list of pairs: attacker+victim.
There are few little tricks here: my subtraction operator works based on comparison of both attacker+victim (remove pairs which are same attacker and victim). But the interception operator works based on comparison of victims only.

Thus the attack list of White is the list of pairs attacker-victim which attackers are White.

A in my previous post is name of the attack list which is calculated After a move when B is one Before.

The problem I signaled above is that after a move of white (say), you cannot simply remove all white pieces from the chase list that are still under (forbidden) attack by black. They must be under attack by the _same_ piece as that was attacking them before.

Actually my list items are pairs, not only one. That helps me identify easily which one is attacking which one.

If they move voluntarily to a place where _another_ black piece can capture them, but not the original attacker, it would still be chase if the original attacker would renew its attack.

So I think the propagation of the lists must work as follows:

preyList[0] = all pieces
preyList[n] = preyList[n-2] & VICTIM(chaseList[n])
chaseList[n] = attacks[n] - attacks[n-1] - attacks[n+1]

where I index the lists for player P such that 0 would be just _before_ a move of that player, and the indexes would wrap around over the repeat loop. (So I could put 0 anywhere in the loop.)

So prey:ist only has to be updated every 2 ply, for even n, i.e. just before the player which is (potentially) being chased moves. we take the (forbidden) attacks on his pieces from attacks[n], remove the (forbidden) attacks after his move (the ones he did not try to escape from), remove the (forbidden) attacks before the previous move of his opponent (because these were static), so that we finally are left with the novel attacks that he tried to escape.

Thuis is all done at the level of captures, i.e. (attacker, victim) _pairs_. Two captures are different if either the attacker or the victim is different, and would then not be removed by the '-' operator. After the subtraction, we now take the victim field (indicated by the function VICTIM), to convert it to a set of _pieces_.

In practive, determining if a capture constitutes a 'forbidden' attack is rather expensive. Because we know that we will take the intersection with the old preyList later, can already throw out all captures that do not have their victim in that preyList. i.e. define a mixed operator &' that acts between lists of captures and lists of pieces:

preyList[n] = VICTIM((attacks[n] &' preyList[n-2]) - attacks[n-1] - attacks[n+1])

A capture is a forbidden attack (and thus belongs to attacks[n]) if all of the following conditions are met
1) the attacker is not K or P
2) the victim is not unpassed P
3) the attacker is not of the same type as the victim, OR
the the victim cannot (legally) capture the attacker
4) the attacker is C or H and the victim R, OR
there is no (legal) recapture after the capture to the victim square

I have implemented above tasks in a separate step (Step 4). Only after knowing which side is chasing, I will review all chase lists of that side which I have stored after each move to see if any chase list is legal (such as attackers is K or P). Of course we can combine Step 4 to other steps to work on fly but that is kind of code optimizing only (actually I see in most cases, I need to work until Step 3 only - it finishes when the chase list be empty, in rare cases I need to do Step 4).

Note that because both attacks[n-1] and attacks[n+1] are used to calculate preyList[n], and n is incremented in steps of 2, we use each of these twice. So per iteration, we only calculate one, and then remember the other for the next iteration. The fact that we have to try pre-emptive (3) or retaliatory (4) re-captures, and then check if these are legal, makes this expensive.

One other remark: the chase detection does not have to take place if both sides are perpetually checking. In real games this probably never occurs, but in the search, it does occur occasionally (and is the reason that MaxQi crashes, because the check-extension leeds to infinite recursion in that case).

In my program, I have solved it in Step 2. Detect perpetually checking is quite cheap since for each position usually we have known already if any one side is in check.

[hgm]

I define my chase/attack list as a list of pairs: attacker+victim.

Yes, I understood that. It was initially just not clear which side was the attacker, and which he victim, when you speak about "the attck kist of player P".

There are few little tricks here: my subtraction operator works based on comparison of both attacker+victim (remove pairs which are same attacker and victim). But the interception operator works based on comparison of victims only.

OK, that is a crucial detail you had not mentioned. If you have a non-standard definition of the operator &, I must know what it is to understand your algorithm. When it acts on two lists of (attcker, victim) pairs, say

{(A,X), (B,X), (C,Y), (D,Z)} & {(A,X), (D,X), (D,T)}

(where all pieces indicated by different letters are different), what would be in the resulting list? Obviously (A,X), since it occurs in both. And probably not (D,Z) and (D,T), as there is no matching victim. But would (D,X) or (B,X) (or both) be in the result?

Thus the attack list of White is the list of pairs attacker-victim which attackers are White.

Oh. That is the opposite from what I initially thought. So I have to re-think. In my notation attacks[n] were the attacks _on_ the player that has to move.

I have implemented above tasks in a separate step (Step 4). Only after knowing which side is chasing, I will review all chase lists of that side which I have stored after each move to see if any chase list is legal (such as attackers is K or P). Of course we can combine Step 4 to other steps to work on fly but that is kind of code optimizing only (actually I see in most cases, I need to work until Step 3 only - it finishes when the chase list be empty, in rare cases I need to do Step 4).

I wonder how you can get the Appendix chase coorect, then.There you see an attack of the Rook on the Horse both before and after the move. So your subtraction operator would remove the move from the list altogether. So it would not be subjected to step (4), and you would never know that it has to be added, because before the move the Horse was protected, but after the move it was not. I don't see how you could ever get that correct without applying this filtering immediately on the attack lists.

Now in some cases this would be desirable anyway, because the tests are cheap, and dragging them along to go through the & and - operations (which, presumably, would have to be done by looping over the lists with two nested loops) before removing them would be much more expensive. This applies to the K, P attacker and unpassed P victim case. For the protected and legal status it is a pain, however, but I don't see how you could avoid it.

In my program, I have solved it in Step 2. Detect perpetually checking is quite cheap since for each position usually we have known already if any one side is in check.

True. this is how I do it in HaQiKi D too. I just store the inCheck satus flag with the hash keys in the array for repeat checking. But what I wanted to point out (because you did not mention it explicitly) is that the chase test only has to be performed when neither side has a _perpetual_ check (but, like you say, they could have one-check, one idle). Not in every case where the check test concludes a draw (as this also includes the mutual perpetual checking).

[phhnguyen]

To avoid some confuse how to calculate list A and B and be easy for me to illustrate, I little re-write the algorithm:

II. Identify chases

I use an array attackList[side][nmove] (list of pairs: attacker and its victim) to calculate and store all attacks for both sides for each position.

1) Starting position

ChaseListW = attackList[W][0];
ChaseListB = attackList[ B ][0];

Suppose ChaseList is the chase list for a given side and we are in the position nth
2) If the lattest move is from opponent side

Code: Select all

ChaseList = ChaseList - attackList[side][n];

3) If the lattest move is from the given side

Code: Select all

ChaseList = (attackList[side][n] - attackList[side][n-1]) & ChaseList;

/Pham

[phhnguyen]

I will illustrate my algorithm by some examples.

Example 1 (provided by H. Muller)
C r . a k . e . .
. . . . a . . . .
. . . . e . . . .
. . . . . . . r p
. . . . . . . . .
. . R . . H . . .
. . . . P . . . c
. . . . . . . . .
. . . . A . . c .
. . E A K . E R .
white to play
Fen: Cr1ak1e2/4a4/4e4/7rp/9/2R2H3/4P3c/9/4A2c1/2EAK1ER1 w - - - 1
29. Ca1 Rb1 30. Ca9+ Rb9

At starting position, the ChaseListW and ChaseListB are calculated as the all attacks. Each item of the list is a pair of attacker and victim, I denote by => and use Capitalized letter for White(W), lowercase letter for Black(B):

ChaseListW = attackList[W][0] = { C=>a, R=>c }
ChaseListB = attackList[ B ][0] = = { r=>C }

1) Move 29. Ca1
. r . a k . e . .
. . . . a . . . .
. . . . e . . . .
. . . . . . . r p
. . . . . . . . .
. . R . . H . . .
. . . . P . . . c
. . . . . . . . .
C . . . A . . c .
. . E A K . E R .

attackList[W][1] = { C=>c, R=>c }
attackList[ B ][1] = { c=>C }

ChaseListW = (attackList[W][1] - attackList[W][0]) & ChaseListW = ({ C=>c, R=>c } - { C=>a, R=>c }) & { C=>a, R=>c }
= { C=>c } & { C=>a, R=>c } = { C=>c }
ChaseListB = ChaseListB - attackList[ B ][1] = { r=>C } - { c=>C } = { r=>C }

2) Move 29. ... Rb1
. . . a k . e . .
. . . . a . . . .
. . . . e . . . .
. . . . . . . r p
. . . . . . . . .
. . R . . H . . .
. . . . P . . . c
. . . . . . . . .
C r . . A . . c .
. . E A K . E R .

attackList[W][2] = { R=>c }
attackList[ B ][2] = { r=>C, r=>A }

ChaseListW = ChaseListW - attackList[W][2] = { C=>c } - { R=>c } = { C=>c }
ChaseListB = (attackList[ B ][2] - attackList[ B ][1]) & ChaseListB = ({ r=>C, r=>A } - { c=>C }) & { r=>C }
= { r=>C, r=>A } & { c=>C } = { r=>C }


3) 30. Ca9+
C . . a k . e . .
. . . . a . . . .
. . . . e . . . .
. . . . . . . r p
. . . . . . . . .
. . R . . H . . .
. . . . P . . . c
. . . . . . . . .
. r . . A . . c .
. . E A K . E R .

attackList[W][3] = { C=>k, R=>c }
attackList[ B ][3] = { }; // Empty

ChaseListW = (attackList[W][3] - attackList[W][2]) & ChaseListW = ({ C=>k, R=>c } - { R=>c }) & { C=>c }
= {C=>k } & { C=>c } = {} // Empty
ChaseListB = ChaseListB - attackList[ B ][1] = { r=>C } - {} = { r=>C }

4) 30. ... Rb9
C r . a k . e . .
. . . . a . . . .
. . . . e . . . .
. . . . . . . r p
. . . . . . . . .
. . R . . H . . .
. . . . P . . . c
. . . . . . . . .
. . . . A . . c .
. . E A K . E R .

attackList[ B ][4] = { r=>C }
ChaseListB = (attackList[ B ][4] - attackList[ B ][3]) & ChaseListB = ({ r=>C } - {} } & { r=>C }
= { r=>C } & { r=>C } = { r=>C }

We don't need to calculate attackList[W][4] and ChaseListW because ChaseListW is empty already.

When we come here, it is full loop. ChaseListW is empty when ChaseListB is not. Black is chasing White Cannon.

[phhnguyen]

I define my chase/attack list as a list of pairs: attacker+victim.

Yes, I understood that. It was initially just not clear which side was the attacker, and which he victim, when you speak about "the attck kist of player P".

There are few little tricks here: my subtraction operator works based on comparison of both attacker+victim (remove pairs which are same attacker and victim). But the interception operator works based on comparison of victims only.

OK, that is a crucial detail you had not mentioned. If you have a non-standard definition of the operator &, I must know what it is to understand your algorithm. When it acts on two lists of (attcker, victim) pairs, say

{(A,X), (B,X), (C,Y), (D,Z)} & {(A,X), (D,X), (D,T)}

(where all pieces indicated by different letters are different), what would be in the resulting list? Obviously (A,X), since it occurs in both. And probably not (D,Z) and (D,T), as there is no matching victim. But would (D,X) or (B,X) (or both) be in the result?

I keep only item in the list 1 which victims are also in the list 2. From your given lists, X is common victim between two lists. So the result of interception operator:

{ (A,X), (B,X) }

Thus the attack list of White is the list of pairs attacker-victim which attackers are White.

Oh. That is the opposite from what I initially thought. So I have to re-think. In my notation attacks[n] were the attacks _on_ the player that has to move.

I have implemented above tasks in a separate step (Step 4). Only after knowing which side is chasing, I will review all chase lists of that side which I have stored after each move to see if any chase list is legal (such as attackers is K or P). Of course we can combine Step 4 to other steps to work on fly but that is kind of code optimizing only (actually I see in most cases, I need to work until Step 3 only - it finishes when the chase list be empty, in rare cases I need to do Step 4).

I wonder how you can get the Appendix chase coorect, then.There you see an attack of the Rook on the Horse both before and after the move. So your subtraction operator would remove the move from the list altogether. So it would not be subjected to step (4), and you would never know that it has to be added, because before the move the Horse was protected, but after the move it was not. I don't see how you could ever get that correct without applying this filtering immediately on the attack lists.

It is too late here. I will illustrate how I calculate for Appendix tonight.
/Pham

Now in some cases this would be desirable anyway, because the tests are cheap, and dragging them along to go through the & and - operations (which, presumably, would have to be done by looping over the lists with two nested loops) before removing them would be much more expensive. This applies to the K, P attacker and unpassed P victim case. For the protected and legal status it is a pain, however, but I don't see how you could avoid it.

In my program, I have solved it in Step 2. Detect perpetually checking is quite cheap since for each position usually we have known already if any one side is in check.

True. this is how I do it in HaQiKi D too. I just store the inCheck satus flag with the hash keys in the array for repeat checking. But what I wanted to point out (because you did not mention it explicitly) is that the chase test only has to be performed when neither side has a _perpetual_ check (but, like you say, they could have one-check, one idle). Not in every case where the check test concludes a draw (as this also includes the mutual perpetual checking).

[hgm]

OK, that is a crucial detail you had not mentioned. If you have a non-standard definition of the operator &, I must know what it is to understand your algorithm. When it acts on two lists of (attcker, victim) pairs, say

{(A,X), (B,X), (C,Y), (D,Z)} & {(A,X), (D,X), (D,T)}

(where all pieces indicated by different letters are different), what would be in the resulting list? Obviously (A,X), since it occurs in both. And probably not (D,Z) and (D,T), as there is no matching victim. But would (D,X) or (B,X) (or both) be in the result?

I keep only item in the list 1 which victims are also in the list 2. From your given lists, X is common victim between two lists. So the result of interception operator:

{ (A,X), (B,X) }

OK. In that case it seems that indeed our algorithms are the same. By allowing (B,X) in the set, which is essentially a new capture, because B did not occur as attacker before (the left-hand side of the & operator is the new attackList in the recursion you defined, and the right-hand side the old chaseList), you allow additions to the list. This was what I worried about; normally subtraction and intersection can only remove elements of a set, so it was not clear to me how you could allow a new piece to take over the role as chaser of a piece that was previously chased by another piece. But this prescription takes care of that.

You still should take care, though, to start the calculation for the chaseList of white in a position where black is to move, and vice versa. If white is to move, it could very well be that white has no attacks at all, and starts with an empty attacList[W][0], and thus an empty chaseListW. But he can still start chasing by attacking something with his move.

Further note that the white and black chaseList calculations are completely independent. This makes it best to do them one after another in the engine. This is a good optimisation, because chases are rare amongst repeats. So you can set it up in such a way that in most cases, you only have to calculate the chaseList for one side. E.g. if 0 <= alpha, and the opponent is not chasing (as usually will be the case), you cannot win, so you will lose (if you are chasing) or draw (if you are not), and both would fail low. So you take the fail low immediately. If 0 >= beta, you would start with your own chaseList, so you can call it quits when you are not chasing.

Where to classify attacks as forbidden or not (on the attackLists before you use them, or only afterwards) remains an issue, though.

[phhnguyen]

Sorry all, I may need to change my algorithm to solve the method of solving chase by setting protection to the victim.

But before showing the modified algorithm, I would like to discuss some examples of Asia rule.

Here is the 1st game:

Code: Select all

[Event "Asia Rules Appendix 3"]
[Site "Pham"]
[Date "2010.08.10"]
[Round "-"]
[White "-"]
[Black "-"]
[Result "1/2-1/2"]
[Variant "xiangqi"]
[FEN "3aka3/c2R1R2c/4e4/9/9/9/9/4E4/4K4/2E6 w 0 1"]
[SetUp "1"]

{--------------
. . . a k a . . .
c . . R . R . . c
. . . . e . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . E . . . .
. . . . K . . . .
. . E . . . . . .
white to play
--------------}
{--------------
. . . a k a . . .
c . . R . R . . c
. . . . e . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . E . . . .
. . . . K . . . .
. . E . . . . . .
white to play
--------------
--------------
. . . a k a . . .
c . . R . R . . c
. . . . e . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . E . . . .
. . . . K . . . .
. . E . . . . . .
white to play
--------------}
1. Rf6 Ade8 2. Rf8 Ad9 3. Rf6 Ade8 4. Rf8 Ad9 5. Rf6 Ade8 6. Rf8


{Red's R4-2 is to allow the Rook on the 6th file to chase the Black's Cannon on the 9th file. 
In the next move, R4+2, Red is using the Rook on the 4th file to chase the Black Cannon on 
the 9th file. This is two pieces perpetually chasing a piece.
As to the Black side, each time it moves the Guard it is threatening the Red Rook on the 6th 
file with a Cannon. This is a perpetual chase.
Since both sides violate the rule, the game will be a draw if neither side wants to change 
its move.}
1/2-1/2

Why can Red's R4-2 (1. Rf6) be considered to help the other to chase Black's Cannon (Ci8)? Clearly that Rook (Rf8) itself can capture that Cannon but he has been leaving the victim untouched when in turn.

In the view of a player, I see that White doesn't want to use that Rook (Rf8) to capture the Cannon (Ci8) because of avoiding threat from Cannon Ca8 - or Ci8 is protected by Ca8. If you agree with that though, it becomes the problem of protection/un-protection). Take a note that the pattern of protection is c-R-R-c (or Cannon-Cannon mount-Attacker-Victim). We will compare with the next game:

Game 2:

Code: Select all

[Event "Asia rules 19"]
[Site "FOM-RHKA8J2A5WY"]
[Date "2010.05.07"]
[Round "39"]
[White "-"]
[Black "-"]
[Result "0-1"]
[Variant "xiangqi"]
[FEN "2eaka3/C4rH2/4e1h2/1Rp5p/6p2/2P6/4c1P1c/4E3C/4A4/4KAE2 w 0 1"]
[SetUp "1"]

{--------------
. . e a k a . . .
C . . . . r H . .
. . . . e . h . .
. R p . . . . . p
. . . . . . p . .
. . P . . . . . .
. . . . c . P . c
. . . . E . . . C
. . . . A . . . .
. . . . K A E . .
white to play
--------------}
{--------------
. . e a k a . . .
C . . . . r H . .
. . . . e . h . .
. R p . . . . . p
. . . . . . p . .
. . P . . . . . .
. . . . c . P . c
. . . . E . . . C
. . . . A . . . .
. . . . K A E . .
white to play
--------------}
1. Rb8 Afe8
(1... Rxg8 2. Cxg8)
2. Rb5 Af9
(2... Rxg8 3. Cxg8)
3. Rb8 Afe8 4. Rb6 Af9 5. Rb8
{The Cannon is chasing the Rook. 
That the Rook is pinned by the Horse, 
and this Horse is protected is then immaterial.}
0-1

Focus only Black Rook and White Horse?
1) Starting: Black Rook can capture Horse without any protection => Chase
2) 1. Rb8 White solves the chase by protecting the Horse by Cannon
3) 1. ... Af9 Black is trying to capture Horse again by cutting off the protection from the Cannon

=> Rook chases the Horse. Both sides chase => Draw (?)

If you don't want to agree with Draw result, you should probably refuse 2) (it may be in the comment of the game). It also mean that you have to refuse the protection pattern C-R-r-H (or Cannon-Cannon mount-Attacker-Victim - which is similar to game 1)

What is your point?

/Pham