Make engine stop repeating moves in a clearly won position

[mvanthoor]

well, why not do this inside qsearch?

Because QS should deal with capture moves which would reset the draw counter anyway. Doing the move history check in QS looks like a waste of time. That should only be done in main search before and instead of iterating any deeper. So, in the move loop after making the current move, but before the recursion.

Could this be the problem? I had this check just after "if depth == 0", so it would make the move, possibly hit depth 0, go into QSEARCH, and return a score from there, and thus never reach the repetition check.

but that's wrong. you should search the last 7 positions (or 6, depending on whether it comes before or after the reset)

Damn. So I was right. I've looked it up in the VICE tutorials again because I wasn't sure anymore (it's a long time I watched those). VICE implements it the way I described, or I'm understanding the explanation the wrong way. I was thinking I should be searching the list backwards for the length of the move counter, because the repetition can't come BEFORE the last 0.

I'll change it to work like that, and also put the check directly behind the make_move, instead of after the depth == 0 check.

[Ras]

Could this be the problem? I had this check just after "if depth == 0", so it would make the move, possibly hit depth 0, go into QSEARCH, and return a score from there, and thus never reach the repetition check.

That should auto-correct once the main search depth catches it, but it might lead to PV oscillation over the main depth iterations.

[Ras]

as for performance, I don't think that probing a rep hash/iterating history list in each qs node would be something you could even measure.

Given that by far most nodes are QS nodes, and that you can have positions where you don't have irreversible moves for quite some time, I'm not sure whether it's not noticeable. Keep in mind that it's loop code, i.e. a lot of branching. Why spending effort on something that shouldn't be necessary?

[mvanthoor]

I also just thought of the fact that if I check right after make-move and then go backwards through the list, I must not check the last position, because that will be the current one (i.e., the same one as is on the board that I pass into the function).

Hm... maybe BlueFever had it correct and I'm just messed up and understanding it wrong because of his variable names. (He gets them confused himself in the video I see )

So to recap... If the list of 50 move rule counts is this:

1 2 3 4 0 1 2 3 4 5

We have 10 ply. The one where the move count was reset, could be the first which can later be repeated. The current 50 move count is 5. So... List length = 10, half move clock = 5. So we have to start searching the list at 10 - 5 = 5. But because list counting starts at 0, this is actually element 4. Then we search to the end of the list, but excluding the last element, because that element contains our current position.

[mar]

Given that by far most nodes are QS nodes, and that you can have positions where you don't have irreversible moves for quite some time, I'm not sure whether it's not noticeable. Keep in mind that it's loop code, i.e. a lot of branching. Why spending effort on something that shouldn't be necessary?

feel free to prove me wrong, if you really believe that this simple check will consume a lot of time (I say that a lot of time will be spent elsewhere, i.e. eval or TT (I do TT in qs)). It should be obvious that captures are irreversible and thus reset move history, but somehow you didn't quote this back.
I say that anytime I can make early cutoff that may result in a more accurate assessment of a position, I'm willing to do it.

EDIT: the speedup of not doing a draw check in qs in ~0.14% overall in my engine, so it's measurable. a proper test would be to measure elo, however I'd probably have to play tens of thousands of games and I'm not willing to do that

[Ras]

It should be obvious that captures are irreversible and thus reset move history, but somehow you didn't quote this back.

Indeed, I overlooked that, and you're right. Do you have numbers how often the repetition detection in QS actually does detect a repetition? Because I think it should be about 0.

[mar]

Indeed, I overlooked that, and you're right. Do you have numbers how often the repetition detection in QS actually does detect a repetition? Because I think it should be about 0.

I not only detect draws by repetition by also draws by insufficient material and 50-rule draw.

it will be >0, because I got different node counts for both runs.
Also let's not forget I'm generating checks at depth 0

A 20 ply search from startpos has 178 qs draw cuts out of 24493689+178 qs nodes, so it's not 0, but in this position one wouldn't expect many anyway
one would have to test whether this is really beneficial elo-wise, I better don't make any claim here

[mvanthoor]

I've "fixed" the is_repetition function for now by just looking at the entire history except for the last element, and I put the check directly behind the "if depth == 0" condition (not inside it), so if it detects a repetition when not in a leaf node, it returns draw.

It seems to work.

I set the engine to analyze in the position that is in the first post. Up to ply 5 it suggest Rf4, attacking the queen, but at ply 6 it switches to Rb3b4.

Even if I try to force it into a repeat by playing Rf4 Qd1+, it now instantly suggests Kh2, where, in the tournament, it would have played Rf1 to block the check. (And the opponent would go back with Qg4, repeating the position). So it seems the engine does avoid repetitions now.

I'll start a quick 10s/move tournament (I know it's not the most efficient, but it'll work for now) to see what happens.

Tomorrow when I've not been programming for 15 hours straight, I'll check the is_repetition function again to not traverse the entire list.

@mar and @Ras: thanks for your assistance.

PS: If I put the call to is_repetition directly after make() (in the move loop), the engine instantly returns with minus infinity, 250 ply's in a row as soon as I type "go" or click analyze. (When I start from an FEN, the history is obviously empty, so it shouldn't find any repetitons.) I haven't looked into this further yet.

[No4b]

Indeed, I overlooked that, and you're right. Do you have numbers how often the repetition detection in QS actually does detect a repetition? Because I think it should be about 0.

I not only detect draws by repetition by also draws by insufficient material and 50-rule draw.

it will be >0, because I got different node counts for both runs.
Also let's not forget I'm generating checks at depth 0

A 20 ply search from startpos has 178 qs draw cuts out of 24493689+178 qs nodes, so it's not 0, but in this position one wouldn't expect many anyway
one would have to test whether this is really beneficial elo-wise, I better don't make any claim here

Well, weather you should try to detect 50mr and repetitions in the QSearch is the matter of what are you generating as moves for QSearch.
In the simpliest case (captures + pawn promotions) you shoulndt. But if you generate checks and check evasions or some other kinds of Quiet moves, than you should.
About elo gain. Some time ago i proposed such change (no draw check in QSearch) for the Weiss, it was ~0 at short TC, but at LTC it is possible that it gives elo ( 4.52 +- 4.23 (95%))

[hgm]

You were doing exactly the opposit from what was required. In ply 20 was irreversible, and you are now after 26, you should test after 20-25. Not after 0-19. The 0-19 are guaranteed to never be the same as 26, because 20 was irreversible. And that is what 'irreversible' means: you cannot recreate a position before it.