Repetition detection question

[bob]

This is an interesting question. Has anyone actually collected any data as to which way works best in games?

-Sam

Somehow I don't think so. It is certainly easy enough to treat a null as if it were a pawn push. It is easy enough to ignore it completely. As to which is better, that is why I posed the question, because I have not given it a lot of thought, but in rewriting the repetition code in Crafty today, it made me think about it for a minute, since I don't allow repetitions after a null move to match with repetitions before a null move...

[Zach Wegner]

This is an interesting question. Has anyone actually collected any data as to which way works best in games?

-Sam

I don't remember exactly, but I don't think there was any difference when I put it in my engine. I just noticed that my null-move was theoretically incorrect after a discussion here, and changed it.

[hgm]

Recognizing null-move-spanning repeats subverts the effectivity of recursive null-move pruning: when you are ahead, after trying the first null move (which is going to fail high) and any reversible reply of your opponent, you cannot afford a second null move, as your opponent would then simply draw (making your second null move fail low) by reversing his earlier move, creating a repeat.

So the intended refutation line

NULL - passiveMove - NULL - passiveMove - NULL - passiveMove ...

can not occur, and you would have to do

NULL - passiveMove - neutralMove - passiveMove - NULL - passiveMove ...

in stead, with less reduction.

If missing this extra reduction on most moves makes you engine weker or stronger is hard to say. It might be that you partly 'pre-compensated' for this by using an extra large reduction on the null moves that you can afford. But it is hard to believe that such a pre-compensation would could fully solve it, as it would cause unjustified undeep search on branches where the null-move reply was an irreversible move (so you could afford an immediate second null move). And I cant think of a reason why irreversible moves would on the average be less dangerous than other passive moves. (The would mostly be Pawn pushes, as captures are likely to require a non-null response to stay above beta, but I don't think Pawn pushes are below-average dangerous.)

In Joker I didn't use to bother about this effect, as I only count the third occurrence as a draw, and by that time it would have collected already 3 null moves, which gives already so much reduction that the branch no longer significantly contributes to the search effort. But come to think of it, I might have activated the problem when I added code to top off scores of lines that contain a first repeat (second occurrence). I will have a look at this to make sure I

[BubbaTough]

I think there are two kinds of engines, whose results MAY differ (I have not thought deeply on it) on this issue: those that allow 2 null moves in a row, and those that don't.

I don't, so am only talking about that case.

My instinct is that both ways are equal, but an odd hybrid might be better than either: If draw >= beta, count null move as a pawn move; If draw < beta, don't.

The instinct is as follows: In the case of 1.Be2-d3 null move 2.Bd3-e2 null move 3.Be2-d3 it doesn't seem like it should fail high, but it also doesn't seem like it should keep searching the position (which is the same as one being searched deeper earlier in the tree). Using the hybrid, draw detection will prune this branch of analysis without failing high (which seems like the right thing to me).

Unfortunately, I don't have sufficient faith in this instinct, or sufficient faith in the delicacy of my testing mechanisms to develop confidence that this is the right answer.

-Sam

[hgm]

I guess there is a general principle here: If draw < beta, but current Eval >= beta, you could cut off on current eval. It can't be good for the side which is currently on the wrong side of the window to waste time by repeating, either through null move or through other moves.

I wonder if it really will save much to suppress a search from such nodes, though: all moves will lead to immediate hash hits on recently visited nodes.

[bob]

Here is something I have not seen asked or discussed previously. I found a serious repetition bug in Crafty that has been around for a couple of years. But in fixing it I looked carefully at how/when/where it was called, and came across the following issue.....

Do you still do repetition checks below a null-move? I have not yet concluded whether the answer should be yes or no. For me, I have been doing so, but it appears that it is wasted and might even break a null-move search here and there, because obviously there can be no repetition below a null-move that repeats a position prior to the null move. Actually there can be, but do we want it to terminate the null-move search? I am thinking "no" since the purpose of the null-move is to determine whether my current position is so good that even if I "pass" I am still winning, and a repetition might cause the answer to be "no" erroneously...

Has anyone given this any kind of thought??? If so, did you actually reach any kind of useful conclusion as a result?

Bob

I check(ed) for null moves in the history, because I use infinitely recursive null move and it could immediately return a draw. I didn't really think it through, I just needed to not return reps after null moves. Now I realize the Gerd's suggestion is a much better way of handling it.

I simply set the 50 move counter back to zero after a null. I use this counter to limit how far back I search when looking for repetitions, and setting it to zero does not let me look back beyond the null-move to compare against positions that occurred prior to that point... It has always seemed to be the right way to do this, but it did get me to thinking about it...

[Gerd Isenberg]

I simply set the 50 move counter back to zero after a null. I use this counter to limit how far back I search when looking for repetitions, and setting it to zero does not let me look back beyond the null-move to compare against positions that occurred prior to that point... It has always seemed to be the right way to do this, but it did get me to thinking about it...

I use following avoid repetition idea:
Before I start the usual repetition check at the very beginning of the search, I look whether the weaker side to move (beta <= DRAWSCORE) may force a direct repetition of moves by "unmaking" the last reversible move (ply-2) - while the stronger side already unmade move ply-3 at ply-1. That usually covers much more hits than the usual repetition test, also due detection of reps at horizon-nodes.

Code: Select all

if (   move50cnt >= 3
    && beta <= DRAW_SCORE
    && ply >= 3
    && move[ply-3].from == move[ply-1].to
    && move[ply-1].from == move[ply-3].to
    && move[ply-1].to isNotElement obstructed[move[ply-2].from][move[ply-2].to]
   )
       return DRAW_SCORE; // beta

The question is whether we can treat two consecutive nullmoves of the stronger side like making/unmaking a reversible move. It might be worth a try to avoid NULL by the stronger side if alfa >= DRAW_SCORE, after NULL and reversible move of the weaker side.

[Gerd Isenberg]

The question is whether we can treat two consecutive nullmoves of the stronger side like making/unmaking a reversible move. It might be worth a try to avoid NULL by the stronger side if alfa >= DRAW_SCORE, after NULL and reversible move of the weaker side.

Alternately, instead of setting count50 to zero after NULL, one may xor hashkey accordantly so that only even numbers of nullmoves per side cancel each other.

[bob]

I simply set the 50 move counter back to zero after a null. I use this counter to limit how far back I search when looking for repetitions, and setting it to zero does not let me look back beyond the null-move to compare against positions that occurred prior to that point... It has always seemed to be the right way to do this, but it did get me to thinking about it...

I use following avoid repetition idea:
Before I start the usual repetition check at the very beginning of the search, I look whether the weaker side to move (beta <= DRAWSCORE) may force a direct repetition of moves by "unmaking" the last reversible move (ply-2) - while the stronger side already unmade move ply-3 at ply-1. That usually covers much more hits than the usual repetition test, also due detection of reps at horizon-nodes.

Code: Select all

if (   move50cnt >= 3
    && beta <= DRAW_SCORE
    && ply >= 3
    && move[ply-3].from == move[ply-1].to
    && move[ply-1].from == move[ply-3].to
    && move[ply-1].to isNotElement obstructed[move[ply-2].from][move[ply-2].to]
   )
       return DRAW_SCORE; // beta

The question is whether we can treat two consecutive nullmoves of the stronger side like making/unmaking a reversible move. It might be worth a try to avoid NULL by the stronger side if alfa >= DRAW_SCORE, after NULL and reversible move of the weaker side.

I've never tried imprecise repetition avoidance as you mention. The best counter example is two rooks on the 7th chasing the king back and forth. There the move two plies back does not necessarily get undone at the current ply, as the sequence could go rh7 Kg7 rg7 kf8 rf7 Ke8 Re8 Kd8 and that could repeat this same position reached several moves ago...

My repetition check takes no measurable amount of time, particularly when the loop is limited by the 50 move counter, so that I have simply never been inclined to add special-case code to avoid doing that which has no cost anyway...

[Gerd Isenberg]

I simply set the 50 move counter back to zero after a null. I use this counter to limit how far back I search when looking for repetitions, and setting it to zero does not let me look back beyond the null-move to compare against positions that occurred prior to that point... It has always seemed to be the right way to do this, but it did get me to thinking about it...

I use following avoid repetition idea:
Before I start the usual repetition check at the very beginning of the search, I look whether the weaker side to move (beta <= DRAWSCORE) may force a direct repetition of moves by "unmaking" the last reversible move (ply-2) - while the stronger side already unmade move ply-3 at ply-1. That usually covers much more hits than the usual repetition test, also due detection of reps at horizon-nodes.

Code: Select all

if (   move50cnt >= 3
    && beta <= DRAW_SCORE
    && ply >= 3
    && move[ply-3].from == move[ply-1].to
    && move[ply-1].from == move[ply-3].to
    && move[ply-1].to isNotElement obstructed[move[ply-2].from][move[ply-2].to]
   )
       return DRAW_SCORE; // beta

The question is whether we can treat two consecutive nullmoves of the stronger side like making/unmaking a reversible move. It might be worth a try to avoid NULL by the stronger side if alfa >= DRAW_SCORE, after NULL and reversible move of the weaker side.

I've never tried imprecise repetition avoidance as you mention. The best counter example is two rooks on the 7th chasing the king back and forth. There the move two plies back does not necessarily get undone at the current ply, as the sequence could go rh7 Kg7 rg7 kf8 rf7 Ke8 Re8 Kd8 and that could repeat this same position reached several moves ago...

My repetition check takes no measurable amount of time, particularly when the loop is limited by the 50 move counter, so that I have simply never been inclined to add special-case code to avoid doing that which has no cost anyway...

This is a kind of redundant "pre"-make repetition detection. It is far from imprecise - if you accept rep-draws at second occurence with first occurence already inside the search tree. The additional precondition covers the most common rep-cases in search. Playing reversible 2. Rb1-a1 after 1. Ra1-b1 Ra8-b8 will not improve alfa, if already greater/equal draw score, since black has at least Rb8-a8. Interactions are covered by checking the obstruction as you may prove. The method might be redundant - but as said it get's draw-scores already the ply before making Rb8-a8, which one does not try at the horizon.

I mentioned it, because of the idea to treat pairs of consecutive nullmoves in the same way as making/unmaking reversible moves of the stronger side.