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.
Xiangqi chase algorithm
Moderators: hgm, Rebel, chrisw
-
- Posts: 27866
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Xiangqi chase algorithm
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:
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
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.)
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.
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
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.
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)
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.
-
- Posts: 1447
- Joined: Wed Apr 21, 2010 4:58 am
- Location: Australia
- Full name: Nguyen Hong Pham
Re: Xiangqi chase algorithm
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.Evert wrote: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.
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.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Xiangqi chase algorithm
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.phhnguyen wrote: 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
If you could put it on a wiki others would be able to help out with it.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.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Xiangqi chase algorithm
I guess there's no harm in combining (b) & (c) in one test.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
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.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
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.
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?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),
Not that it matters, since the code to look for pieces that attack a particular square will always find all of them anyway.
I don't quite see it, but it'll probably make sense if I think on this foryou 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.)
a bit.
Ok.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.)
This step is done by testing squares...?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)
Urgh. That means I need a stack of positions that are part of the loop asSteps 1-4 are then repeated for all moves of that same side in the loop (1st-3rd occurrence).
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)?
In other words, when going through the cycle, make the moves on the "chase" board, but only if the piece is being chased?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.
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.
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?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.
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)?
-
- Posts: 27866
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Xiangqi chase algorithm
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:
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):
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.
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 . . .
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 . . .
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.
-
- Posts: 27866
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Xiangqi chase algorithm
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.
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.
(Q represents Cannon) Rd7-d8 activates Ca8, discovers Nc7 and Nd6, and checks itself.
,
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.
Note, however, that in in (b) the Pawn is teh attacker, while in (c) it is the victim.Evert wrote:I guess there's no harm in combining (b) & (c) in one test.
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).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.
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.
[d]Q3k3/2NR4/3N4/8/8/8/8/8 wReally? 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?
(Q represents Cannon) Rd7-d8 activates Ca8, discovers Nc7 and Nd6, and checks itself.
,
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.This step is done by testing squares...?
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.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)?
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.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 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.
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).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?
Indeed, this definitely is not 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)?
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Xiangqi chase algorithm
No problem, I've been having fun adding loads of other stuff to Sjaak.hgm wrote: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.
Ah. Yes, I did miss that.Note, however, that in in (b) the Pawn is teh attacker, while in (c) it is the victim.Evert wrote:I guess there's no harm in combining (b) & (c) in one test.
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).
True.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.
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...
Ah, I see. I mis-interpreted what you wrote. Makes sense, but requires a little bit of care.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, right - you can unblock two horses at the same time.[d]Q3k3/2NR4/3N4/8/8/8/8/8 w
(Q represents Cannon) Rd7-d8 activates Ca8, discovers Nc7 and Nd6, and checks itself.
I guess it's not very common.
Ok, but that's still 4-20 times per second or more.The up-side is that it seems to happen very infrequently. The repetition test finds a repetition once every 1000-8000 nodes.
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.
Indeed, I have that information already.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).
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.Indeed, this definitely is not 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)?