a question on perpetual chase

[liuzy]

There is a kind of chase caused by blocking opponent's protector. H.G.Muller, How do you detect such kind of chase?

I suggest Marc Halstern, Robert Hyatt, Richard, Dann Corbit, Steve B, and all of the good programmers to write a XiangQi engine.

[hgm]

I guess this requires a little change in the testing logic compared to what we discused so far (and what I use in WinBoard now). In stead of defining a (one-time) chase as

(not attacked before move && attacked after move) && not defended after move

we should define it as:

(not attacked before move || defended before move) && attacked after move && not defended after move

So in stead of only defining new attacks as potential chases, it should now also check if the move pins an opponent piece, and if it does, check of any of the pieces it was protecting is attacked and has no other protectors.

Note that Asia rules (which in fact are not rules at all, but just a bunch of examples) are very under-specified in this area. E.g. what happens if the protected piece whose protector we pin is a Rook, and the attacker was a Cannon? Does it count as an existing "forbidden attack" now (because for CxR it does not matter if R is protected), so that it does not violate any rules to allow its continued existence? And what if the piece whose protector we pin can capture its attacker back? (E.g. a Cannon attacked by a Cannon.) Does pinning the protector count as a chase or a sacrifice now? And what if there was a second attacker, say a Horse? (I.e. a protected C is attacked by C and H, and I immobilize the protector by pinning it.) In the "direct case", where I would have moved the Cannon to create the attack it would have been a sacrifice, but when I would have moved the Horse it would have been a chase (if there was no protector, or it was already pinned). Or at least, I think so. (The Asia rules are also not clear about that.)

No Xiangqi programmer or player I ever spoke could answer these questions. (Plus a bunch of other questions I had, such as if an attack with an Elephant or Adviser on a Rook would not count as a chase is the Rook was "protected". The Asia rules suggest that it would be OK to chase a Rook with Elephants if it is protected, but forbidden if it is not, which, considering the value difference of E and R makes no sense at all!)

What we really would need is to consult a professional referee about how he would handle this.

A much worse problem is that the use of a hash table tends to mask repetitions. So no matter how good your algorithm for deciding if a repetition is a win/draw/loss, the engine will make many wrong judgements because it does not realize it is planning a repetition, and thus never invokes the algorithm. This in particular will happen when two prositions in a repeat loop, where the side failing low has the move, can also be reached through a shorter path from the current position directly. The hash table will then be filled with the largest remaining depth with scores from those direct paths (where they are not repetitions), and then the search of path A will get a hash hit with sufficient depth on the position of path B, and vice versa, which will cause a hash cutoff. This problem is far greater than not having fully correct rules for cases that occur only once in a million games.

Perhaps only solving the problem only in the root is not such a bad idea after all. It would still prevent a Human opponent from ever being confronted with an illegal chase, and take negligible time no matter how complex you make the algorithm.

[liuzy]

Note that Asia rules (which in fact are not rules at all, but just a bunch of examples) are very under-specified in this area.

I'm afraid you are right. To allow blocking-chase and pinning-chase makes the concept of one-time-chase unclear and disordered. We can even lead the conflict results based on those asian rules(if they are), as you have mentioned above. It is unbelievable to use such confounded rules to guide people to play the game.
But I suggest you to use the algorithm which you implemented in WinBoard to handle the loops in the search tree. Your engine's nps won't slow down significantly. [/img][/quote]

[hgm]

Indeed, it really amazed me that people who play this game don't want to be aware of the exact rules. But no one I have spoken to so far seems to care much. They just shrug and say: "well, that is much too complicated". Perhaps most people do not care about Asia rules because they play by other rules? I understand that Chinese rules are different, and more difficult for computers to implement, because there it is also forbidden to do perpetual mate-in-one threats. But otherwise I know nothing about the Chinese rules, I could not find any website describing them in English.

I did get the impression that many of the examples given for the Asia rules are only of interest to highlight the difference with Chinese rules: they give lots of examples that are NOT forbidden perpetuals, where the formulated rules would not even make you suspect they could be forbidden perpetuals. But I guess these are all for cases that would be considered forbidden perpetuals under Chinese rules.

It would have been more useful to me if they had elaborated more on other points, which are totally unclear now, and also cannot be deduced by analogy. Such as a perpetual attack by Elephants on a Rook. According to the written rules this would constitute a chase if the Rook is unprotected, and no chase if it is protected, which makes little sense. But in analogy with a Pawn chasing a Rook you could argue it was always allowed (as an Elephant is about as weak as a Pawn, so it is hardly ever possibe to make such a chase and therefore not very disruptive to the game to allow it). But in analogy with Horse chasing Rook you could argue it should be always forbidden, no matter whether the Rook is protected or not, and the value difference is even larger, so protecting makes even less sense. Of course I would very much like to have more cases with simplified rules, where you don't have to check if the piece is protected or not.

I will certainly implement the algorithm in my engine (but probably not before January, as I am too busy now with other tuff), if only to measure how it affects the perpetual-chasing rate if one engine that knows the rules plays against an engine that doesn't.

[liuzy]

I implement the algorithm in my engine, and there is still one case it cann't handle, as follow:

R87 k3+2
R78 k2-3
R82 c89
R27 k3+2
R78 k2-3
R81 ....


When
"R87 k3+2
R78 k2-3"
have been played, it already forms a loop. My engine will handle the loop immediately and gives the result that white makes a perpetual-chase. But this example is a draw. I don't know how to fix this bug.

BTW, Chinese-Chess-Rule doesn't belong to us, it belong to XiangQi masters, it's so complicated that few people in the world can fully understand it. What we should care about is asian-rule.

[hgm]

The official rule is that the games are only judged after it has occurred two times before, (at least, I think; it could be three, the Asia rules are ambiguous about this, at least the English version), and you would have to judge all intermediate positions. Which in this case is one Rook chasing two pieces *Cannon + Horse), so allowed. This is what you would have to do after a move is made in the root, where you really want to claim the game.

Of course in the tree you don't want to wait to the second repetition, or you would hardly catch anything within the search depth. But in cases like this (and certainly in this example) I don't think it is a problem if the engine thinks the given sequence of moves is a loss for red, even at the first repetition. Because that simply means that red will play another sequence of moves that the engine does recognize as a draw. E.g.

1. Rc3, Hb0 {chase Horse}
2. Rh3, Ci0 {chase Cannon}
3. Rb3, Hc2 {chase Horse}
4. Ri3, Ch0 {chase Cannon}
{first position repeats}} 1/2-1/2

So if a draw would be a good result for red, it will correctly recognize the initial position as a forced draw, even though it will judge some of the sequences (erroneously) s a loss. But as long as there is one ordering of the moves that it would judge as a draw, that does not matter at all. The only thing that matters is that it recognizes the initial position as a forced draw. And I think that in cases where you chase more than one piece, there is always a possibility to play the moves in an order that aernately chaes one or the other.

A similar argument has led me to declare in the tree a repetition that is created by the side that evades the chases already as a win for that side. I think officially you would have to wait until the chasing side repeats the position, i.e. you can lose by repeating, but you can never win by repeating. But in the search tree it just wastes time to use that rule. Because it means that the opponent would have to break out of the loop (as this can never be worse than an immediate forfeit). And if he can do that, he could as well have done it in the initial position of the loop, which was repeated. By forcing him to do it there, you gain 4 ply of extra search depth on that exit of the loop, which helps greatly to reduce horizon effect.

In fact this is a big problem in Xiangqi search trees: If a forbidden perpetual is possible (ike at some stage of the game it usually is, checking with a Rook) the side that is losing starts to interject one check + one evasion between every pair of real moves, to push trouble over the horizon. If you would not declare a win for an evading side that repeats, it would even interject 4 moves:

{position A}
check - evasion -
check - evasion {repeated position A} -
one move progressing toward loss - move progressing towards win {new position B created}-
check - evasion
check - evasion {repeated position B} -
...

Even when you use a check extension of 1 ply, this effectively reduces search depth by a factor 2.

In Chess this problem does not exist: forcing the repetition is allowed, and when the losing side has a perpetual, the game is a draw by playing that perpetual. So there never is a need to play out the perpetual part by part without creating repetitions, as a stalling tactic for creating horizon effect.

[liuzy]

Do you think this problem should be fixed in the root position?
Supposing that opponent chased you twice, and now it's your turn to make a move, you evade and claim that opponent violated asian-rule, it's certainly not correct. How do you fix this problem in the initial position?

[hgm]

Well, in the root one definitely should use other criteria than in the tree. Even in Western Chess. There you can claim a draw only on the third occurrence of the position, but in the tree it i better to already core the second occurrence as a draw. And it is an unresolved question what is best if the tree sees the first repetition of a position that already occurred in the game. Would you go there assuming that the opponent did not now how to make progress from there before, so he is not likely to do it now? But the opponent will probably also know the rep-draw rule, and try something different. So if you have an alternative that seem better than the repeated position on its own merit, (but not as good as a draw), it could be better to go there. But you won't do that if you evaluate this first repeat of a game position as a draw.

In any case, after making a move in the game, the engine should only claim a win after the opponent created a position that is repeated for the second time (i.e. third occurrence), and only if all moves leading from the first occurrence to the third constitute a forbidden chase. (I also do that in WinBoard to adjudicate an engine-engine game.) If there is a third occurrence after your own move, while the opponent is chasing, it should not claim yet. (I guess in theory it could claim a draw here? Another ambiguity in the Asia rules!)

[liuzy]

About how to identify blocking-chase(chase caused by blocking opponent's protector(s)).
Asian-rules point out "One piece chasing two or more pieces is a draw. Two pieces chasing two or more pieces is also a draw." It seems that this item doesn't care about whether the chased pieces are protected or not. But when a move can result in one direct-chase and one blocking-chase, things become complicated, which is actually a mess. For examples:


figure 1

figure 2
One direct-chase and one blocking-chase maybe occur synchronously when using red rook to chase black cannon. If figure 1 matchs the rule "One piece chasing two or more pieces is a draw", what about figure 2?