talk about repeation

[hgm]

OK, I think I have conceived an acceptable algorithm now. It is based on your idea, of working in "phases" for the whole loop, rather than immediately doing the full analysis for a single position. So it will run through the repeat loop multiple times, making the moves on the board to have the positions available for analysis. Because it is a loop, it will never have to unmake any moves, a it will end up in the original position. The fact that you would have to make all moves in the loop several times, for each phase, cause some overhead. But I think distributing the process over several phases on average saves much more than that, as the phases progressively get more complicated, and an early phase will often be decisive already, so that the later phases can be skipped.

The first phase checks for new captures, based on the fromSquare and toSquare of the move. New captures due to unpinning pieces can be left out initially: this almost never occurs, and can seasily be added later. So it just checks for discovered attacks with R,C,H over the fromSquare, C activation on the toSquare and the captures with the moved piece itself if that is no K or P. For each position on which this is done, a bitmap of attacked pieces is created in a 32-bit int. Each piece has its own bit (requiring 16 bits), but there are two extra bits for the Rooks, (one for each) which are set if the corresponding Rook is attacked by C or H. The regular Rook bit is set one every (new) attack on the corresponding Rook.

The first phase results in such a bitmap for every position in the loop, and we can AND those together to determine which piece was (newly) attacked on every move of the loop. As soon as the AND of the bitmaps hits zero, we can actually stop testing. (We still would have to finish the loop for restoring the position.) If it is zero after the loop, there could not have been a chase by that side. If the only non-zero bits correspond to Pawns that have not yet crossed the River, we can ignore those too (clear them).

If, after the loop, the variable is still non-zero, there is a piece that was perpetually "harrassed", and this might constitute a perpetual chase. If one of the extra Rook bits is still set, we already know it is a chase for sure, as the corresponding Rook was then newly attacked by Cannons or Horses on every move. So we can skip the later phases (for that side).

Even if the collected bitmap ends non-zero, and we cannot immediately conclude a C+H vs R chase, we have the big advantage that we now can limit our attention to those targets that were attacked on every move of the loop. So the expensive testing if potential chase victims were defended, and if the defender was not pinned, only needs to be done on those targets, not just on any piece that happened to be newly attacked on some move in the loop.

It will also be necessary to test pseudo-legal new attacks on a victim for legality: the attacker could be pinned. (E.g. RckeH on a rank leads to a new pseudo-legal attack of c on H when you move the e out of the way, but in fact the c is pinned.) As pieces are rarely pinned, such tests are in general a waste of time, and can be better postponed until after tests that have a much larger chance to rule out the chase (such as if that same piece is attacked on another move of the loop). So the first phase could ignore pinning, and if it seems we have a chase, a third phase could subject all the new attacks on pieces that we seem to be chasing to the legality test. (After the second had concluded there were no true protectors in any of the moves.) Again, this means that most of the time we don't have to do it at all, because we already established it cannot be a chase because on one of the moves the harrased piece was defended.

Intermediate results, in particular the bitmaps of newly attacked pieces, could be saved on a stack, for later use. After all, it could be that after testing a move M that would lead to repetition of a position 4 ply earlier, we try another move M' in the same node that would repeat a position 6 ply earlier; the bitmaps for the 3 positions we already tested could then be simply re-used. As we still have many bits to spare, we could use one bit to indicate the bitmap is not yet calculated. And another bit, to indicate if there were any non-zero other bits in the word. (Say the sign bit, so it can be easily tested.) On entering a new node we would initialize the corresponding stack variable to 0xC0000000. We could than even incorporate a pre-screening phase, before we would actually start testing for new attacks, where we would simply AND all words currently on the stack. (We would not have to update the board for this.) If there happened to be any zero bitmap within the loop (indicating a move in a position that was already analysed before and did not lead to any new attacks), we could immediately conclude that there was no chase. Of course when a later phase reveals that a new attack was not legal, or was directed aainst a defended piece, we would clear that bit in the bitmap on the stack immediately, to make it easier for later repeat loops to already rule out chases during the pre-screening.

[hgm]

One more thought:

To determine the new captures it will be beneficial to quickly switch to a method that only tests for new captures on a given piece. This would involve only testing for alignment between the given piece and the from and to square of the last move, (to detect discovered attacks by R, C or H, or C activation), or an attack with the mover, also starting with an alignment test. To get all new attacks would require to test alignment of the fromSquare with 6 pieces, (all R, C, H), and of the toSquare with two Cannons, so 8 alignment tests. And then it would have to generate all new captures with the moved piece.

On the first move of the loop, when there are still 16 possible chased victims, performing this test on all of them is not competitive. after the first move there are on the average probably not more than 2 newly attacked pieces left, and for the remaining moves you would only have to test for attacks on those (or even fewer when they are eliminated).

So an efficient way to implement it might be to put all attacked pieces on the first move in a small table, together with some bit flags indicating if it was a direct attack, a discovered attack, or a Cannon activation. Then on later moves we would just run through that table, to check if the piece is stil being chased, and remove it from the table otherwise.

[liuzy]

One more thought:

To determine the new captures it will be beneficial to quickly switch to a method that only tests for new captures on a given piece. This would involve only testing for alignment between the given piece and the from and to square of the last move, (to detect discovered attacks by R, C or H, or C activation), or an attack with the mover, also starting with an alignment test. To get all new attacks would require to test alignment of the fromSquare with 6 pieces, (all R, C, H), and of the toSquare with two Cannons, so 8 alignment tests. And then it would have to generate all new captures with the moved piece.

On the first move of the loop, when there are still 16 possible chased victims, performing this test on all of them is not competitive. after the first move there are on the average probably not more than 2 newly attacked pieces left, and for the remaining moves you would only have to test for attacks on those (or even fewer when they are eliminated).

So an efficient way to implement it might be to put all attacked pieces on the first move in a small table, together with some bit flags indicating if it was a direct attack, a discovered attack, or a Cannon activation. Then on later moves we would just run through that table, to check if the piece is stil being chased, and remove it from the table otherwise.

Good idea, but it's too complicated and difficult to implement correctly. I want to seperate the algorithm into two phases.
PHASE 1. make all the moves in the loop to find target piece if any.
PHASE 2. make all the moves in the loop to ensure it's a chase.

[liuzy]

Friend. Your idea is very excellent and effective, and a little complicated of course, at least for me. After implementation, I hope you can paste a piece of code to describe it and make it more clear.