talk about repeation

[liuzy]

Is there any algorithm to solve chasing continuously in XiangQi? H.G.Muller, can you explain your algorithm in detail? Thanks.

In my opinion, XiangQi is much more complicated than chess, not only because the rules but also because the evaluation. In chess evaluation, you may only care about the material balance, maybe some kind of king safety in addition. The whole evaluation function is very simple, 1000 lines of code is enough to build a very strong one. But in XiangQi, 5000 lines of code is needed because there are many sacrifices. You must carefully evaluate the situation which is the most difficult part in computer chess.
If people who is a good programmer, he should try XiangQi. I suggest famous programmers, such as the authors of crafty, Stockfish and IPPLITE, to write a XiangQi engine.

[zamar]

If people who is a good programmer, he should try XiangQi. I suggest famous programmers, such as the authors of crafty, Stockfish and IPPLITE, to write a XiangQi engine.

I think writing XiangQi engine would be a bit boring task. Why? Because same techniques which are used to chess engines also apply to XiangQi engines. And writing strong evaluation function for XiangQi would be an extremely long (and IMO boring task).

But the day when I get bored with chess engines, I'll definetily try writing Go-engine (or improving some existing one), there lie the true challenge. The branching factor ~200 asks for inventing completely new techniques than traditional Negamax!!

[Don]

If people who is a good programmer, he should try XiangQi. I suggest famous programmers, such as the authors of crafty, Stockfish and IPPLITE, to write a XiangQi engine.

I think writing XiangQi engine would be a bit boring task. Why? Because same techniques which are used to chess engines also apply to XiangQi engines. And writing strong evaluation function for XiangQi would be an extremely long (and IMO boring task).

But the day when I get bored with chess engines, I'll definetily try writing Go-engine (or improving some existing one), there lie the true challenge. The branching factor ~200 asks for inventing completely new techniques than traditional Negamax!!

Do you realize that there has been a sudden and dramatic improvement of go programs over the last 5 years? They have basically become a little more like chess programs in that they are scalable with search - but they don't use traditional alpha/beta searching. But they are still doing a sophisticated best first style tree search. The evaluation is nothing like chess though, it's based on monte-carlo playouts.

Every top program now does something like this.

[hgm]

Is there any algorithm to solve chasing continuously in XiangQi? H.G.Muller, can you explain your algorithm in detail? Thanks.

In my engine HaQiKi D I do not test for perpetual chasing, only for perpetual checking. For this I use a similar algorithm as XQWLight: I put the in-check status of every node of the current branch on a stack, and when a repetition occurs if goes back through the stack up to the first occurrence of the position. For each side I determine if all positions of the repeat loop are checks. If one side has this, it loses. Otherwise, it is draw.

I put scores that were affected by repetitions in the hash table with a low depth.

Unlike perpetual checks, perpetual chases hardly occur. I played some 10,000 games without the engine being aware of the chasing rule, and only in about 2% of the cases one of the engines forfeited because it was chasing. That is 1% per side. Often this was the side that would lose anyway, so it would cost you less than 1% in score (say about 5 Elo) to completely ignore the problem, and suffer the occasional loss. (So this is what I did.) A time-consuming algorithm might prevent the losses, but slow you down so much that it costs you even more than 5 Elo.

I guess it would be best to avoid chasing in the root; this might prevent the majority of chases without doing too much damage. (Sometimes, there will be damage because the engine could not plan for the move being forbidden, and only discovers it when it was committed to playing the repetition as the only way to avoid losing material.)

In the root you can afford the complete test, as I also implemented it in WinBoard:
When you detect a repetition, for every move in the loop you determine the set of attacked pieces (of the opponent of the side making the move) both before the move and after the move. If there are pieces(not being a Pawn that has not yet crossed the River) that can be captured after the move, (by something different than Pawn or King), but cannot be captured by the same attacker before the move, they are potential chase victims.

For each capture of the potential chase victim I then test if a chase of this type is forbidden; if not, I discard the capture. HxR or CxR is always forbidden. If equal pieces attack each other (HxH, CxC, RxR), I test if the potential chase victim can legally capture its attacker (i.e. it must not be pinned or a Horse not be blocked), and if it can, I discard the capture, because such a chase is allowed. If it cannot, I count it as an atack of a high on a lower piece, so it goes to the next step of testing.

For every remaining potential chase capture, I then determine if the victim is defended, by performing the capture, and look if there is a legal recapture to that square. If there is, the chase was allowed, and the original capture is also discarded.

At this stage, captures that still remain are forbidden chases. On the first move of the loop I copy all the victims of such captures to a "prey stack". On later moves, I discard victims that were not already on the prey stack, and move chase victims that were already on the prey stack to the bottom of that stack. (They are chased on the new move and all moves before) That floats pieces that are not chased by the new move to the top of the prey stack, and after having treated all captures, I remove these from the prey stack.

After I have done that for all moves in the loop, if there is something left on the prey stack, it was perpetually chased. I then repeat the whole thing for the opponent, to see whether he perpetually chases, or not. If one chases, and the other not, the one who chases loses, and otherwise it i draw.

(There is actually one example of the Asian rules that is not covered by this procedure, but I thought this was such a ridiculous example that I ignored that. I think it was the case where you "chase" by pinning a defender.)

[liuzy]

Unlike perpetual checks, perpetual chases hardly occur. I played some 10,000 games without the engine being aware of the chasing rule, and only in about 2% of the cases one of the engines forfeited because it was chasing. That is 1% per side. Often this was the side that would lose anyway, so it would cost you less than 1% in score (say about 5 Elo) to completely ignore the problem, and suffer the occasional loss. (So this is what I did.) A time-consuming algorithm might prevent the losses, but slow you down so much that it costs you even more than 5 Elo.

Friend, thanks for your explanation, but I'm afraid your conclusion is not correct. If opponent knows all the asian rules and you know nothing, you will lose almost every game. And perpetual chases is not a time-consuming algorithm, some people declare that nps will slow 10% with supporting asian rules. 10% is not that bad.

[hgm]

Well, 10% slowdown is about 10 Elo. So if my measurement of the occurrence frequency is correct, the slowdown would lose you more Elo than the original problem, which only costs 5 Elo. And avoiding losing repetitions it in the root (where it does not cause measurable slowdown) might solve 80% of the cases, so that there is only 1 Elo to gain. In Chess, my minimalist engine micro-Max only recognizes repeats as draws when the repeated position occured in the game history, not when it occurred in the tree, (I alter the score in the hash table to 0 after the move is played at game level, and protect the entry from replacement), and this solves the rep-draw problem almost completely.

What you say does not necessarily contradict what I say:

You say: "if you know nothing". If that includes also not knowing the rule for perpetual checking, I fully agree: you would forfeit almost every game. I was talking only about the case where the programs knew the perpetual checking rule, but had the illusion that chasing other pieces than King would always be draw. It might be that the frequency would go up if the opponent knew that it would win when he gets chased, and go up even more when it knew that the opponent does not know the rule, so it will start to set traps to seduce the opponent to start chasing. But the latter is not a realistic assumption, and would backfire very badly if you were mistaken, and the opponent actually did know the rule.

I don't think many Xiangqi engines pay attention to perpetual chasing (as opposed to checking). The version of Elephant Eye I looked at did completely ignore it. I was told that some engines partially implement it, e.g. only test for attacks of C on R. This was one reason I was did the test with 10,000 games: I wanted to gather statistics on the occurrence frequency of various types of perpetual chasing.

[liuzy]

I prefer implement asian rules even if my engine may be weaker. It can play much more reasonable games, so 5 elo is not that bad. My engine knows nothing about chasing rules so far, many users reflect that it disobeys these rules from time to time. I treat it as a serious bug.
In my opinion, 10% nps is not equal to 10 elos, at least here. Because with supporting asian rules, many bad branchs will be cut off, so your engine will run a little faster in going to depth. As one falls, another rises, the end result may be that we get zero elo with supporting asian rules, but fix a serious bug.

[hgm]

That sounds reasonable.

I have been thinking some more about this, and I think that clever treatment of the problem can reduce the workload a lot: In the d=1 nodes a move can only lead to a repetition that wins for the side to move (in d=1) if the opponent did potential chasing moves at d=2 and d=4. So if we test for forbidden moves at d>=4 (which is quite cheap, as here are only very few such nodes), and the move was not a potential chase (which i the common case), we can at d=1 conclude that a move that causes a repetition is not a win. (Which is enough if alpha >= 0, as draws and losses both fail low.)

Likewise, if we test at d>=3 for potential chases, we can most of the time exclude that moves at d=1 that cause repetitions are losses. (Which is sufficient if alpha < 0, where draw and win both fail high.)

Another cheap filter could be to test if the move at d=2 was the reverse of that at d=4. If it was not, it will be impossible to create a repetition of the start position of d=4, and any forbidden repetition would have to involve potential chasing at d=5 and / or d=6.

[liuzy]

That sounds reasonable.

I have been thinking some more about this, and I think that clever treatment of the problem can reduce the workload a lot: In the d=1 nodes a move can only lead to a repetition that wins for the side to move (in d=1) if the opponent did potential chasing moves at d=2 and d=4. So if we test for forbidden moves at d>=4 (which is quite cheap, as here are only very few such nodes), and the move was not a potential chase (which i the common case), we can at d=1 conclude that a move that causes a repetition is not a win. (Which is enough if alpha >= 0, as draws and losses both fail low.)

Likewise, if we test at d>=3 for potential chases, we can most of the time exclude that moves at d=1 that cause repetitions are losses. (Which is sufficient if alpha < 0, where draw and win both fail high.)

Another cheap filter could be to test if the move at d=2 was the reverse of that at d=4. If it was not, it will be impossible to create a repetition of the start position of d=4, and any forbidden repetition would have to involve potential chasing at d=5 and / or d=6.

I fully agree your points.
I find your algorithm is very good.
I read your algorithm very carefully, and summarize it as follow:

for each side: (for example, white)
1. If moves within loop include pawn or king moves, it's not a chase. (not very accurate, but also OK).
2. Find all "pseudo chases" within loop. If we find a move within loop cann't give any new chase (direct chases and indirect chases), it's not a chase.
3. Analyse all "pseudo chases".
If every black piece chased by white is different from each other, it's not a chase. Now we know that white chases the same black piece.
If one of the "pseudo chases" uses the piece which is pinned by black, it's not a chase(white won't use king to chase here because of step 1). Now we know that white can apply every chase legally.
If one of the "pseudo chases" chases the piece which is well protected by black, it's not a chase.
Now we can conclude that it's a chase.

Have I made any mistakes? How to implement this algorithm effectively?

[hgm]

Well, like you already say, the rule that King or Pawn moves exclude a perpetual chase is not very accurate, because the King or Pawn could have revealed a discovered threat with Rook or Cannon behind it, or even by unblocking a Horse, and it could have activated a threat with a Cannon on its new square. Any piece that moves could do one of those things, which is what makes testing for it so cumbersome. And even worse: moving a piece could un-pin one of your own other pieces, so that this piece now attacks and undefended piece. So you would also have to check for alignment of your own King with the to-square of the move, and if you detect it, look if your opponent had a Rook or Cannon going over that square towards your King, and if so, if there are now 2 (R) or 3 (C) pieces along that line (including the new one). And if there are, look if any of those other pieces is our own, and now has a capture that qualifies as a chase...

By the way, just to make sure we are talking about the same thing: I use the term "chase" for "one-time chase", i.e. a move of the type that would be forbidden to play forever towards the same target (so that it becomes a "perpetual chase"). I think this is what you called "pseudo-chase" above. Chasing several targets is allowed, even if you do it perpetually. This is why you have to check that there is at least one piece that is chased on all moves of the loop.

The Asian rules do not specify what would happen if you attack King + piece on one move, and only that same piece on another move. One check + one chase is allowed (two different targets), but I would think if you combine check and chase on one move, it still is would count as perpetual chase even if the checking was allowed. But perhaps this is not possible at all, becaue one side can never solve a new threat (made through a non-capture) on a piece and a King at the same time. (Although I have no proof of that.) So I first look if checks are involved, and if they are, I do not look for chasing at all.

As for implementing: When you wait until you detect the repetition, you are in fact in the same position as that at the start of the loop. So you could immediately start testing if the move starting from that is chasing something. And if it is, you could store the result of that test with the node that started the loop, (at least 4 ply closer to the root as where you are now, but perhaps even 6 or 8 ply). So that if you encounter another branch of the sub-tree sprouting from it that also repeats this position, you don't have to redo the test. You could for instance store bitmaps on a stack where every bit of a 16-bit word represents a chased piece, and a special code (say 0xFF) indicates that the test has not been don yet. You could then AND all words on the stack between the first and repeated occurrence of the position (doing the test first for every 0xFF you encounter), and stop as soon as you arrive at 0. That way you might never need to actually do the test for nodes very close to the leaves (which would not last very long even if you stored them).

The test if a specific move in the loop is a chase will be quite complex, though. In almost all cases it involves either testing if the opponent can make a specific capture legally (when you attack an equal piece, to see if he can capture you back, so it is a sacrifice rather than a chase), or if he has just any legal capture to a given square (which could be done by repeating the other test for all his pieces). These tests are quite cumbersome, because you have to check the legality of the captures. I guess this would not only involve testing if the capturing piece is pinned, but also if you are in check to begin with. (In theory he could capture it while at the same time exposing your King to a discovered check.)

The only simple cases are when you attack R with C or H: this is always a chase, no matter if the R is defended or pinned, and it can never capture you back. And they are amongst the most common perpetual chases I observed. So some programs only detect thse cases.