Using a prior PV move even though it results in a draw

[JVMerlino]

No side branch should ever go through a repetition if you have a winning score.

Assuming you count a single repetition as a draw in the search...which you should.

[KhepriChess]

1. search finds a forced mate at some depth
2. opponent doesn't play exact same moves, so engine deviates from the above line
3. at some point, position gets back to a position that has the best move already found/stored from step 1, so that move is played even if that will result in a 3-fold draw.

This should not be possible in a properly working search. If you find a forced mate, it means that every possible deviation of the PV has been searched, and proven to result in a mate that is at least as fast. So it does not matter whether the opponent deviates from your PV; the move stored in the TT should result in the fastest mate. No side branch should ever go through a repetition if you have a winning score.

It might have something to do with me only storing the first mate found and not necessarily the best/fastest mate? By deviation I don't mean "deviate from a forced checkmate" but more "deviate from the initial found mate line". My engine might find a "mate in 14", so it plays that move. But then the opponent doesn't play a move in that line, so it searches again and finds a "mate in 9". And so on. And then, what I think sometimes happens, is that it gets to a position already stored from one of those previous mate lines and goes "hey, this move leads to a mate in X!" and selects it, even though it already tried that position and might lead to a repetition because it's not a forced mate line. I'm not sure why the repetition draw isn't considering since I check for that and normally it does work.

This game is an example: https://lichess.org/i3TXuxXV#102. Terrible play, but I don't know why. I can take that position (either the FEN or the full move sequence) and load it manually into my engine and it'll find the mate line. But it failed to do so in that game and I don't know why.

It's just very hard for me to replicate. I can take moves from a game that had this problem, but I can't get it to suggest the move that results in the draw. I really might just have to write something to play through the moves and do a search each time to see if I can reproduce it.

[op12no2]

Maybe I'm misreading your code, but, when there are no moves, your negamax function is returning a mate score based on .Inf but in the TT you use .Checkmate to check for a mate score. Should the former not also be using .Checkmate?

[KhepriChess]

Maybe I'm misreading your code, but, when there are no moves, your negamax function is returning a mate score based on .Inf but in the TT you use .Checkmate to check for a mate score. Should the former not also be using .Checkmate?

I don't think so? I've seen a number of other engines do it this same way.

.Inf is greater than .Checkmate, so a checkmate score in the TT will be .Inf and always larger than the .Checkmate value (which is what the condition checks). If I returned the Checkmate value in the negamax (and subsequently stored that in the TT), the TT comparison wouldn't work (because the entry.score value wouldn't be larger than the .Checkmate value).

[op12no2]

Maybe I'm misreading your code, but, when there are no moves, your negamax function is returning a mate score based on .Inf but in the TT you use .Checkmate to check for a mate score. Should the former not also be using .Checkmate?

I don't think so? I've seen a number of other engines do it this same way.

.Inf is greater than .Checkmate, so a checkmate score in the TT will be .Inf and always larger than the .Checkmate value (which is what the condition checks). If I returned the Checkmate value in the negamax (and subsequently stored that in the TT), the TT comparison wouldn't work (because the entry.score value wouldn't be larger than the .Checkmate value).

Oh I see, your mate scores are based on .Inf and .Checkmate is a value always < the minimum mate score. Ah well...

[KhepriChess]

So in digging around more, I found that sometimes the search would return longer mates at higher depths for a given position. That is, for one particular position, the search might find a "mate in 8" at depth 5, but then maybe return a "mate in 11" at depth 7, then a "mate in 9" at depth 10, etc. I think, maybe, hopefully, I solved that by:

1. not returning the score if "score >= beta" and instead simply "break" from that iteration.
2. not write to the TT in the "score >= beta" condition, and instead just set the hash flag (and let it be stored at the end of the negamax loop)
3. skip storing killer moves if in check

The search performs better and seems to find better mates faster. It still doesn't necessarily find the best mate line (once it finds a mate, the number of nodes search drops drastically, so I think it's not searching as well as it could at that point), but it's much better. I'll need to do some more comprehensive tests to see if it's an overall improvement or not though. And, because I don't have a reliable way to reproduce the original issue (about playing a move that draws), I have to just let it play games and see if that issue still happens.

[KhepriChess]

In testing those changes, it seems that #3 (not storing killer moves if in check) is a net loss. But, I think I'm going down the right path here. Out of the roughly 3100 games done in testing, the engine with the changes to the search never once lost due to a bad draw. The old engine I'm testing against had probably about 20-or-so games where it had a very clearly winning position and ended up doing a 3-fold draw.

The issue obviously has a very low occurance, <1%, and usually the engine even with the issue finds the mating line successfully. So even if I do fix this, it'll probably only be a very small net gain.

I'll have to do some longer time control tests now, as the issue is more likely to pop up in those, but keeping my fingers crossed.

[Ronald]

Hi,

I browsed through your code and I noticed 2 things. Don't know if they help you with your problem, but I thought I'd share them anyway.
First thing is that in negamax you increase depth by 1 when inCheck. That might be a good thing to do, but maybe not in the beginning of negamax, before your move loop, because hashprobing and all kinds of pruning you do before the move loop rely on the depth parameter, while the depth at time should not be tempered with. I guess you could move it inside your move loop, and increase depth + 1 when you're incheck after you made that move. not sure if this creates your current behavior, but it surely influences the hash usage, which you only use when enough "depth".
Second thing I noticed is in your repetition detection you use PositionHistory for checking, you update it when you make the move with

Code: Select all

this.PositionHistory[this.PositionHistory.length] = this.Position.Hash;

but I can't find the place where you increase the PositionHistory.length. Now I'm not really familiar with javascript, so I might not understand it correctly and it might happen elsewhere or automatically, but maybe every position is stored in [0] every time.

Hope this helps

[KhepriChess]

Hi,

I browsed through your code and I noticed 2 things. Don't know if they help you with your problem, but I thought I'd share them anyway.
First thing is that in negamax you increase depth by 1 when inCheck. That might be a good thing to do, but maybe not in the beginning of negamax, before your move loop, because hashprobing and all kinds of pruning you do before the move loop rely on the depth parameter, while the depth at time should not be tempered with. I guess you could move it inside your move loop, and increase depth + 1 when you're incheck after you made that move. not sure if this creates your current behavior, but it surely influences the hash usage, which you only use when enough "depth".
Second thing I noticed is in your repetition detection you use PositionHistory for checking, you update it when you make the move with

Code: Select all

this.PositionHistory[this.PositionHistory.length] = this.Position.Hash;

but I can't find the place where you increase the PositionHistory.length. Now I'm not really familiar with javascript, so I might not understand it correctly and it might happen elsewhere or automatically, but maybe every position is stored in [0] every time.

Hope this helps

For the depth extension, my understanding is sort of based of hgm's comment here: https://www.talkchess.com/forum3/viewto ... 31#p758059

While I am incrementing the depth before probing the TT (and other stuff), I'm also not decrementing the extension before storing the hash. I did try moving the extension into the move loop, but it's a significant net loss.

In

Code: Select all

this.PositionHistory[this.PositionHistory.length] = this.Position.Hash;

the length can be used like that to place an item in a new index at the end of the array. The length will always be 1 larger than the last index (if an array has 5 items, it's last index will be "4" but it's length will be "5").

I ran some more tests for the changes I mentioned above (minus the one about killer moves, that one was bad). At fast time controls (10s+0.1), there wasn't any noticeable improvement, but at 30s+0.5 it was a 40+\-20 gain. So I think the issue was what the search was doing when "score >= beta".

[Ronald]

If you put the check extension inside the moveloop, you can increase the depth if the move gives check (so the other color is incheck after the move). The effect should then be more or less the same. I don't mess with the depth when storing/retrieving hash entries (ie reductions/extensions are kept outside the hash entry depth).

So, if I understand you correctly "this.PositionHistory[this.PositionHistory.length] = this.Position.Hash;", is the same as something like "this.PositionHistory[this.PositionHistory.length++] = this.Position.Hash" in C.