Xiangqi chase algorithm

[Evert]

I was looking into implementing chase detection (for Xiangqi), so I went back and read the long discussion on this form from a while back. I didn't get a clear sense that an accurate step-by-step algorithm was arrived at, so I'd like to know if there is (but it wasn't discussed here), or if anyone has some general pointers about how to approach the problem.
I currently just return a "worse than mate" score in the search whenever a repetition is detected, which sortof works, but it's a bit like nuking a mosquito.

[hgm]

What WinBoard currently does is this:

When the current position occurs for the 3rd time, you loop through all moves since the first occurrence, to judge if a move qualifies as a chase, and if so, what it chases. This uses the following algorithm:

Code: Select all

1) Run through all legal captures the side that moved has _after_ his move, (i.e. when the opponent would reply with null move) and treat them as follows:
  a) Captures with King => no chase (i.e. ignore)
  b) Captures with Pawn => no chase
  c) Captures of a Pawn that has not yet crossed the river => no chase
  d) CxR or HxR captures => candidate chase (i.e. save on chase stack)
  d) Equal captures (RxR, CxC, HxH):
      If the reverse capture is possible (for H it can be blocked) and legal => no chase
  e) If, after making the capture, no quasi-legal recapture (i.e. to the same square) is possible => chase candidate
  f) none of the above => no chase

A quasi-legal capture is a capture that does not put you in new checks. So if the move under scrutiny was a check, you mark the pieces that were attacking the King (there can be upto 4 in XQ), you try all pseudo-legal recaptures, and if after them their King is not in check by a non-marked piece, the recapture was quasi-legal. (The rationale is that you have to wait until it is your turn before you can actually make the initiating capture, and by that time the check must have been solved.)

You are now left with a stack containing zero or more capture moves, ((from,to) pairs), all chase candidates. Next thing you do is

Code: Select all

2) run through all quasi-legal captures the side that moved had _before_ its move.
  a) remove that move from the chase stack if it was there
  b) if the capture is with the piece that made the move under scrutiny, replace its from-square of the capture by the to-square of the moved piece before looking for it on the chase stack.

At this point the moves left on the chase stack are all chases. That is, the moves were too dangerous to ignore, and are newly created by the move under scrutiny, in the sense that they were not quasi-legal before that move, and became fully legal after it. (The quasi-legality is to make that merely resolving a check does notqualify allyour existing attacks as chases.)

Code: Select all

3) Collapse the set of chase moves to a set of pieces chased on this move, by ignoring the from squares.
4) Intersect this set of chased pieces with the set of perpetually chased pieces (which was initialized to contain all opponent pieces)

Steps 1-4 are then repeated for all moves of that same side in the loop (1st-3rd occurrence). When afterwards the set of perpetually chased pieces is non-empty, that side is perpetually chasing. Note that the chased pieces in general move around, so that when you store them by the square they are on, you will have to adapt the square on opponent moves to the new position before making the intersection.

Then repeat the entire process for the opponent. If both are chasing, or neither is chasing, the game is a draw. If oneof them was chasing, and the other not, the side that is chasing loses.

[phhnguyen]

I was looking into implementing chase detection (for Xiangqi), so I went back and read the long discussion on this form from a while back. I didn't get a clear sense that an accurate step-by-step algorithm was arrived at, so I'd like to know if there is (but it wasn't discussed here), or if anyone has some general pointers about how to approach the problem.
I currently just return a "worse than mate" score in the search whenever a repetition is detected, which sortof works, but it's a bit like nuking a mosquito.

Actually, Muller and me have already a long and interesting discussion about a full and serious implementation of perpetual check / chase rules for Xiangqi. In that discussion I have written step by step how to implement the rules.

You can take a look at:

http://talkchess.com/forum/viewtopic.php?t=35403

Three months ago, after "forgetting" every thing (to have a fresh view), I have tried to re-implement totally the algorithm in other programming language (Java instead of C++) and it works well. All steps and ideas in this discussion are still good.

Pham

PS: I have been writing a paper about the algorithm but because of lacking both time and English, speed of writing is too slow - I highly appreciate if anyone can help me to read and correct the paper.

[Evert]

Actually, Muller and me have already a long and interesting discussion about a full and serious implementation of perpetual check / chase rules for Xiangqi. In that discussion I have written step by step how to implement the rules.

You can take a look at:

http://talkchess.com/forum/viewtopic.php?t=35403

Yup, that's the thread I meant. I didn't get a sense that there was a complete and finalised step-by-step algorithm. I'll have another look.

I have been writing a paper about the algorithm but because of lacking both time and English, speed of writing is too slow - I highly appreciate if anyone can help me to read and correct the paper.

If you could put it on a wiki others would be able to help out with it.

[Evert]

When the current position occurs for the 3rd time, you loop through all moves since the first occurrence, to judge if a move qualifies as a chase, and if so, what it chases. This uses the following algorithm:

Code:
1) Run through all legal captures the side that moved has _after_ his move, (i.e. when the opponent would reply with null move) and treat them as follows:
a) Captures with King => no chase (i.e. ignore)
b) Captures with Pawn => no chase
c) Captures of a Pawn that has not yet crossed the river => no chase

I guess there's no harm in combining (b) & (c) in one test.

d) CxR or HxR captures => candidate chase (i.e. save on chase stack)
d) Equal captures (RxR, CxC, HxH):
If the reverse capture is possible (for H it can be blocked) and legal => no chase
e) If, after making the capture, no quasi-legal recapture (i.e. to the same square) is possible => chase candidate

Doesn't that generalise to some sort of winning capture (SEE>0)? (d1) is obviously a winning capture, (d2) is obviously not a winning capture, and (e) is again obviously a winning capture. Clearly we don't consider pawns or defending pieces.

This sounds like it would be a pretty large amount of work, which would be a lot easier if I could grab the information from attack tables. Unfortunately I disabled those because I couldn't make them worthwhile (it's close though). They might help for Xiangqi, but I'm not going to switch them on just for that (maybe if I go back to my stand-alone Xiangqi engine). On the other hand, I could gather attack/defence statistics during move generation for the side to move. I'd have to make that information available to other levels of the tree, but that's not a real issue. I've been thinking about doing that anyway for other reasons.

A quasi-legal capture is a capture that does not put you in new checks. So if the move under scrutiny was a check, you mark the pieces that were attacking the King (there can be upto 4 in XQ),

Really? It's fairly easy to get 3, but I have a hard time thinking up an example where it's 4. You get the piece that moves, a possible discovered check, and possibly a cannon that uses the checking piece as a mound (meaning that the checking piece has to be a rook). How do I get a 4th in there?
Not that it matters, since the code to look for pieces that attack a particular square will always find all of them anyway.

you try all pseudo-legal recaptures, and if after them their King is not in check by a non-marked piece, the recapture was quasi-legal. (The rationale is that you have to wait until it is your turn before you can actually make the initiating capture, and by that time the check must have been solved.)

I don't quite see it, but it'll probably make sense if I think on this for
a bit.

Code:
2) run through all quasi-legal captures the side that moved had _before_ its move.
a) remove that move from the chase stack if it was there
b) if the capture is with the piece that made the move under scrutiny, replace its from-square of the capture by the to-square of the moved piece before looking for it on the chase stack.


At this point the moves left on the chase stack are all chases. That is, the moves were too dangerous to ignore, and are newly created by the move under scrutiny, in the sense that they were not quasi-legal before that move, and became fully legal after it. (The quasi-legality is to make that merely resolving a check does notqualify allyour existing attacks as chases.)

Ok.

Code:
3) Collapse the set of chase moves to a set of pieces chased on this move, by ignoring the from squares.
4) Intersect this set of chased pieces with the set of perpetually chased pieces (which was initialized to contain all opponent pieces)

This step is done by testing squares...?

Steps 1-4 are then repeated for all moves of that same side in the loop (1st-3rd occurrence).

Urgh. That means I need a stack of positions that are part of the loop as
well? I guess that makes sense, but it's a LOT of data to keep around.
Can I make do with just attack information (I guess not)?

When afterwards the set of perpetually chased pieces is non-empty, that side is perpetually chasing. Note that the chased pieces in general move around, so that when you store them by the square they are on, you will have to adapt the square on opponent moves to the new position before making the intersection.

In other words, when going through the cycle, make the moves on the "chase" board, but only if the piece is being chased?
I wonder if there's a way to somehow keep track of this incrementally. Of course, that might mean I'm doing extra work I don't need to and slow everything down horribly, but I might still try it if it makes the code simpler.
Something to think about.

Then repeat the entire process for the opponent. If both are chasing, or neither is chasing, the game is a draw. If oneof them was chasing, and the other not, the side that is chasing loses.

You mean, I look at captures before and after the move my opponent just made, right? I guess I only need to do this when I'm not in check?

This algorithm follows the chased piece around the board, doesn't it? I ask, because the book I have on Chinese chess (by Lau) states that a chase is allowed if the chase involves more than two squares for each side (the example given is of a rook chasing a horse over three squares, or using three squares to do the chase). I know there are many different chase-rules in use, I'm guessing this is a different one (certainly one that seems much easier to implement, but I haven't thought this through all the way)?

[hgm]

Note that Nguyen Pham's algorithm is more restrictive than that used by WinBoard: the latter considers a move a chase when it creates a threat (i.e the thereat exists after the move, but not before). In Pham's algorithm there is an extra condition that the threatened side also resolves that threat on the next move. In practice this makes very little difference, because when the treat was not resolved, the one making it usually cashes in on it. In addition, the Asia rules are not explicit at all about what they would consider 'resolving' a threat.

In theory, it could make a difference, like in the following position:

Code: Select all

. . . . k a e . .
. . . . a . . . .
r . . . . . . . r
. . . . . . . . .
. . R . . . . . H
H . . . . . R . .
. . . . . . h . p
. . . . . . . . .
. . . . A . . h .
. . . . K A . . .

1. Rcg5 (-- 2. Rg5xg9 Rxi5) any 2. Rc5 (-- 3. Rg4xg9 Rxa4) -any 3. Rcg5 etc.

White alternately creates new attacks on Eg9 by one Rook or the other. Black ignores this, because although the Elephant is unprotected (formally turning the attack into a threat), the threat is imagined. Because both white Rooks are tied in defense to a Horse on the same Rank, and white is not going to give up a Horse for an Elephant. So black can afford to ignore the 'threats', and this brings us in the situation where white resolves his own threats in order to create new ones.

As there is no real threat, there would be no reason for black to stay in the repeat loop, unless he would like to exploit (one might say abuse) the chase rule to force white to play something different in the case this would be declared a chase. But then again, why would black want white to play something different, when the Rook move did not pose a real threat? Even more so, why would white want to play these pointless Rook moves? Nothing is lost if white would be under the (perhaps false) impression that this would be a chase, and thus avoid it in the first place.

Now the situation is a bit different here (black Rook on i1 rather than i7):

Code: Select all

. . . . k a e . .
. . . . a . . . .
r . . . . . . . .
. . . . . . . . .
. . R . . . . . H
H . . . . R . . .
. . . . . . h . p
. . . . . . . . .
. . . . A . . h r
. . . . K A . . .

1. Rcg5 (-- 2. Rg5xg9) Ri7 (2. Rxg9 Rxi5) 2. Rc5 (-- 3. Rg4xg9) Ra7 (3. Rxg9 Rxa4) 3. Rcg5 etc.

Now the threats are real, as the Rook making the attacks is not tied in defence to a Horse. So black 'resolves' the threat by attacking the Horse protected by this Rook. But it has to give up its attack of the other Horse for doing that, liberating the other Rook, so that it makes sense to switch Rook attacker, etc.

Now WinBoard would consider this a perpetual chase, and Pham's algorithm wouldn't, because the RxE threat is not formally solved by the counter-attackon the white Horses. It is still possible, and the Elephant is still not protected. The problem is that overloading or soft-pinning the attacker are not recognized by Asia rules as neutralizing a threat.

Now I wonder if this interpretation of Asia rules is really productive. As the second situation obviously has all the character of a perpetual chase: white is forcing black into a repeat loop or lose the Elephant. So to make extra, complex rules for no other purpose than to misqualify it is not very worthwile. The interpretation that black is implied to have resolved the threat because white did not make the capture, as WinBoard uses, is both simpler and more natural.

[hgm]

I see that this post more or less crossed mine, and I see it only now, because the ICGA Olympiad kept me busy the past few days.

I guess there's no harm in combining (b) & (c) in one test.

Note, however, that in in (b) the Pawn is teh attacker, while in (c) it is the victim.

Doesn't that generalise to some sort of winning capture (SEE>0)? (d1) is obviously a winning capture, (d2) is obviously not a winning capture, and (e) is again obviously a winning capture. Clearly we don't consider pawns or defending pieces.

Well, sort of. It is definitely the underlying theme. But it is not implemented exactly. E.g. AxR and ExR would have SEE>>0 even if the Rook is protected, but don't count as chases, and PxR would not even count as a chase if the Rook is unprotected. It also does not count a twice attacked and only singly defended piece as a chase. There is a strange mix here between being dangerous (making it forbidden) and if it is difficult (making it allowed).

Note that in d2 it could be a winning capture, but you don't get the chance to make it, because he captures you first. This is called a 'sacrifice or offer to exchange' rather than a chase, and is allowed.

Really? It's fairly easy to get 3, but I have a hard time thinking up an example where it's 4. You get the piece that moves, a possible discovered check, and possibly a cannon that uses the checking piece as a mound (meaning that the checking piece has to be a rook). How do I get a 4th in there?

[d]Q3k3/2NR4/3N4/8/8/8/8/8 w

(Q represents Cannon) Rd7-d8 activates Ca8, discovers Nc7 and Nd6, and checks itself.
,

This step is done by testing squares...?

In WinBoard I keep a stack of squares ('preyStack') where I store the squares of all pieces that are chased. So after each move of the opponent I have to search through this stack to see if the from-square is there, and then change it into the to-square. In an engine that maintains a piece list you could store the piece numbers.

Urgh. That means I need a stack of positions that are part of the loop as well? I guess that makes sense, but it's a LOT of data to keep around. Can I make do with just attack information (I guess not)?

The up-side is that it seems to happen very infrequently. The repetition test finds a repetition once every 1000-8000 nodes. What I do in HaQiKi D is just keep the move and hash key on every ply level in an array. When search through the hash keys reveals a repetition, it runs through the moves to reconstruct all the positions, and generates all attacks on there.

In other words, when going through the cycle, make the moves on the "chase" board, but only if the piece is being chased?
I wonder if there's a way to somehow keep track of this incrementally. Of course, that might mean I'm doing extra work I don't need to and slow everything down horribly, but I might still try it if it makes the code simpler.
Something to think about.

I think it happens too infrequently in the tree to make that pay off. Some chases, like CxH, are easy to detect, but for most it depends on the attacked piece being protected, and the protector being a 'true protector', i.e. indeed being able to recapture legally.

I try to save time by first checking if an attacked piece is already on the prey stack (in all but the first iteration). If it is not it cannot be perpetually chased, so it is not important whether it was chased on this move (and thus whether it was protected, or not). The first iteration is different; there it fully checks every piece, and if the piece is chased on that move, it is marked as chased in a bitmap. As soon as the bitmap is empty, there is no need to do test anything, and you can abort the loop.

You mean, I look at captures before and after the move my opponent just made, right? I guess I only need to do this when I'm not in check?

First you have to test for perpetual checks, and these could already decide the game. (I do save all inCheck flags in an array to make that easy in HaQiKi D). Only when there is no perpetual checking, you have to test for chasing. But there could be some checks in the chase loop, and you can check and chase at the same time (in Asia rules).

This algorithm follows the chased piece around the board, doesn't it? I ask, because the book I have on Chinese chess (by Lau) states that a chase is allowed if the chase involves more than two squares for each side (the example given is of a rook chasing a horse over three squares, or using three squares to do the chase). I know there are many different chase-rules in use, I'm guessing this is a different one (certainly one that seems much easier to implement, but I haven't thought this through all the way)?

Indeed, this definitely is not Asia rules.

[Evert]

I see that this post more or less crossed mine, and I see it only now, because the ICGA Olympiad kept me busy the past few days.

No problem, I've been having fun adding loads of other stuff to Sjaak.

I guess there's no harm in combining (b) & (c) in one test.

Note, however, that in in (b) the Pawn is teh attacker, while in (c) it is the victim.

Ah. Yes, I did miss that.
That's rather annoying because Sjaak doesn't distinguish between pawns before and after crossing the river (their move tables are obviously different, but the piece is the same).

Well, sort of. It is definitely the underlying theme. But it is not implemented exactly. E.g. AxR and ExR would have SEE>>0 even if the Rook is protected, but don't count as chases, and PxR would not even count as a chase if the Rook is unprotected. It also does not count a twice attacked and only singly defended piece as a chase.

True.
But I could add those as exceptions and keep track of winning captures as a side-effect of move ordering. That way it shouldn't take too much extra work (I hope).
I guess I'll certainly have to be conservative: treat chases as illegal in the search (and prune the tree accordingly) but never try to claim them. It will cost games every now and then if I get it wrong...

Note that in d2 it could be a winning capture, but you don't get the chance to make it, because he captures you first. This is called a 'sacrifice or offer to exchange' rather than a chase, and is allowed.

Ah, I see. I mis-interpreted what you wrote. Makes sense, but requires a little bit of care.

[d]Q3k3/2NR4/3N4/8/8/8/8/8 w

(Q represents Cannon) Rd7-d8 activates Ca8, discovers Nc7 and Nd6, and checks itself.

Ah, right - you can unblock two horses at the same time.
I guess it's not very common.

The up-side is that it seems to happen very infrequently. The repetition test finds a repetition once every 1000-8000 nodes.

Ok, but that's still 4-20 times per second or more.
Does it help to already sort lower in the list any move that reverses the last move by the side to move? I can imagine that in practice it wouldn't.

First you have to test for perpetual checks, and these could already decide the game. (I do save all inCheck flags in an array to make that easy in HaQiKi D).

Indeed, I have that information already.

This algorithm follows the chased piece around the board, doesn't it? I ask, because the book I have on Chinese chess (by Lau) states that a chase is allowed if the chase involves more than two squares for each side (the example given is of a rook chasing a horse over three squares, or using three squares to do the chase). I know there are many different chase-rules in use, I'm guessing this is a different one (certainly one that seems much easier to implement, but I haven't thought this through all the way)?

Indeed, this definitely is not Asia rules.

I'll see if I can find a second source for those rules. Not that it's of any use if everyone else implements a different set of rules, but it'd still be nice to have.