Perpetual-Chase Detection (XQ)

[H.G.Muller]

I still need to equip WinBoard with code to correctly adjudicate 3-fold repetitions in Xiangqi engine-engine games. Perpetual checking is already recognized, but currently every case that is not perpetual checking would be ruled a draw.

I have conceived the following algorithm for ruling repetitions, in an attempt to replicate Asian rules:

Code: Select all

Defined order: R > c,H > A,E,Q

clear preyStack;
for(all positions p with white to move within repeat loop)
    clear chaseStack;
    for(all white moves m from position p+1)
        if(move m is non-capture) continue;
        if(m moves K or P) continue; // K and P are allowed to chase
        if(m captures a P that has not crossed the river)
            continue; // chasing of non-crossed Pawns is allowed
        push move on chaseStack;
    // the chaseStack now contains all captures with A, E, H, R or C.
    for(all white moves m from position p)
        if(moving piece was piece that was moved in p in the repeat loop)
            correct fromSquare of move to position of piece in p+1;
            // (If we keep attacking with same piece, it is no chase)
        if(move m occurs in chaseStack)
            delete move m from chaseStack;
    // chasestack now contains only the captures newly created by the move
    for(all moves m on chaceStack)
        if(victim == attacker)
           if(victim x attacker is legal move in position p+1)
               delete move from chaseStack; // sacrifice is not a chase
               continue;
        if(victim > attacker) continue;     // LxH is always chase
        perform move m from position p+1 to create position q;
        if(black can recapture on same square in position q)
            delete move m from chaseStack;
     // chaseStack now only contains true chases
     if(first iteration) copy toSquares of moves on chaseStack to preyStack;
     for(every move m on chaseStack)
        find first occurrence i of the toSquare of m on preyStack;
        move this occurrence i towards bottom of preyStack;
     pop the top entries off preyStack;
     //preyStack now contains (location of) all black pieces chased on every move so far
     for(all squares s in preyStack)
        if(s is fromSquare of black move m played from p+1 in loop)
            adjust s to the toSquare of m;
// preyStack contains all black pieces that where perpetually chased
if(preyStack not empty) white is perpetually chasing;

Repeat the same procedure with reversed colors;

if(none or both are chasing) rule draw; else
if(white is chasing) rule win for black; else
if(black is chasing) rule win for white;


I hope that someone familiar with Asian rules could have a look at this pseudo-code, to see if this indeed correctly reproduces Asian rules.

[H.G.Muller]

I guess this algorithm is only covering the written rules on tha [url=http://www.clubxiangqi.com/rules/asiarule.htmAsia-rules website[/url]. I just discovered that there are also a few example positions given there that do not belong to any written rule, but are labeled 'Appendix'.

One of the cases my algorithm does not cover is this one:



Red is moving his Pawn between c6 and d6, black his Elephant between a7 and c5. According to the website, this should be considered as the black Rd1 chasing Hc1! The reasoning is that the Pawn moves compromise the protection of Hc1 by Cc9, by moving away the platform, and then blocking the Cannon when the opponent has substituted his Elephant for it as platform. This moves turns the pre-existng attack of the Rd1 on Hc1 from an attak on a protected Horse (which is ot a chase) into an attack on an unprotected Horse (which is a chase).

So identifying new captures, and then testing of they attack an unprotected piece, does not work. It will be necessary to thest the protected/unprotected status of the victim for every capture, even the pre-existing ones, to see if it changes.

I guess other means of changing the protected status (e.g. pinning the protector, rather than blocking it) would also count as chases then, although no examples are given of this.