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

[KhepriChess]

This has been an on-going issue for me, and one that I've had a very hard time pinning down.

What I think is happening, is something like:

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.

The problem I'm having in solving this is that it's hard to replicate. The issue doesn't happen every game. Even games with similar end-games and pieces don't always have this problem. So I've never reliably been able to reproduce the issue in testing.

I figure the problem stems from returning the move from the transposition table, but I'm not sure why the 3-fold verification isn't catching that and returning a draw value instead.

[Whiskers]

This has been an on-going issue for me, and one that I've had a very hard time pinning down.

What I think is happening, is something like:

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.

The problem I'm having in solving this is that it's hard to replicate. The issue doesn't happen every game. Even games with similar end-games and pieces don't always have this problem. So I've never reliably been able to reproduce the issue in testing.

I figure the problem stems from returning the move from the transposition table, but I'm not sure why the 3-fold verification isn't catching that and returning a draw value instead.

Two potential answers:
1. You should clear your transposition table after every move your engine makes, or if not you should age the entries or otherwise signify that they should not be used exactly like new entries (the first one is simpler, the second one is better if you can do it right).

2. Don't return on a hash hit in PV-nodes, instead just use that hit for move-ordering and search it first. That way if playing the PV move would be an immediate repetition draw, the search would catch that and score that move as a draw and look for other ones that can beat it.

Do either of those sound like they'd help you, or are you already doing them?

[KhepriChess]

This has been an on-going issue for me, and one that I've had a very hard time pinning down.

What I think is happening, is something like:

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.

The problem I'm having in solving this is that it's hard to replicate. The issue doesn't happen every game. Even games with similar end-games and pieces don't always have this problem. So I've never reliably been able to reproduce the issue in testing.

I figure the problem stems from returning the move from the transposition table, but I'm not sure why the 3-fold verification isn't catching that and returning a draw value instead.

Two potential answers:
1. You should clear your transposition table after every move your engine makes, or if not you should age the entries or otherwise signify that they should not be used exactly like new entries (the first one is simpler, the second one is better if you can do it right).

2. Don't return on a hash hit in PV-nodes, instead just use that hit for move-ordering and search it first. That way if playing the PV move would be an immediate repetition draw, the search would catch that and score that move as a draw and look for other ones that can beat it.

Do either of those sound like they'd help you, or are you already doing them?

1. I'm just using an "always replace" strategy for my TT (an old entry is replaced by the newer one).

2. Haven't tried that. Guess I could see if that has any benefit.

[Whiskers]

Well my point 1 was referring to clearing the whole table out once at the start of a search while playing the game.
You don't really want to have 4.e4 stuck in your table when you're on move 15 do you?

[KhepriChess]

Well my point 1 was referring to clearing the whole table out once at the start of a search while playing the game.
You don't really want to have 4.e4 stuck in your table when you're on move 15 do you?

Isn't that the entire point of a replacement strategy though? What does it matter if you have 4.e4 in the TT on move 15 if it will get replaced if that same index is used to store a new entry later on? It's obviously a useless entry by move 15, but it's not doing any harm other than taking up a few bits of memory.

[Whiskers]

Well my point 1 was referring to clearing the whole table out once at the start of a search while playing the game.
You don't really want to have 4.e4 stuck in your table when you're on move 15 do you?

Isn't that the entire point of a replacement strategy though? What does it matter if you have 4.e4 in the TT on move 15 if it will get replaced if that same index is used to store a new entry later on? It's obviously a useless entry by move 15, but it's not doing any harm other than taking up a few bits of memory.

Yeah good point. I'm sick so not thinking the straightest rn
I know programs like Stockfish do keep their transposition tables intact between searches, but when I was implementing my TT I kept having problems with the engine using old searches with strange results. I don't think there's much to lose by clearing out the TT between moves (if there is I'd like to know because I could never get it to work!) and it would almost certainly solve your problem. At the very least it might be worth testing to see if it doesn't lose ELO?

[JVMerlino]

Well my point 1 was referring to clearing the whole table out once at the start of a search while playing the game.
You don't really want to have 4.e4 stuck in your table when you're on move 15 do you?

Isn't that the entire point of a replacement strategy though? What does it matter if you have 4.e4 in the TT on move 15 if it will get replaced if that same index is used to store a new entry later on? It's obviously a useless entry by move 15, but it's not doing any harm other than taking up a few bits of memory.

Yeah good point. I'm sick so not thinking the straightest rn
I know programs like Stockfish do keep their transposition tables intact between searches, but when I was implementing my TT I kept having problems with the engine using old searches with strange results. I don't think there's much to lose by clearing out the TT between moves (if there is I'd like to know because I could never get it to work!) and it would almost certainly solve your problem. At the very least it might be worth testing to see if it doesn't lose ELO?

There is, in fact, a lot to lose by clearing out the hash table between moves. If your search got up to depth N and made a move, and your opponent makes the expected reply, thanks to the TT your search should be able to vault straight up to depth N-2 practically instantly. This saves a LOT of time during a game.

Example from a logfile during a 1-minute game. Myrddin thinks about the current position; the opponent did not make the expected reply.
1 129 0 4 d4e6
2 145 0 175 d4e6!
2 158 0 319 d4e6 d7e6 d5e6
3 158 0 558 d4e6 d7e6 d5e6
4 142 0 860 d4e6?
4 126 0 1254 d4e6?
4 116 0 1980 d4e6 d7e6 d5e6 b8c6
5 132 0 2822 d4e6!
5 143 0 3252 d4e6 d7e6 d5e6 b8c6 g2d5 c7d6
6 127 0 4206 d4e6?
6 122 0 7863 d4e6 d7e6 d5e6 b8c6 d2d3 f6e5
7 138 0 12138 d4e6!
7 154 1 14302 d4e6! (893 KNPS)
7 180 1 18692 d4e6 d7e6 d5e6 c7c6 d2b4 d8b6 b4d6 f6b2 c1b2 b6b2 (1168 KNPS)
8 164 1 24894 d4e6? (1555 KNPS)
8 158 3 43430 d4e6 d7e6 d5e6 c7c6 e2e4 f6e5 d2c2 d8f6 (1400 KNPS)
9 168 3 57956 d4e6 d7e6 d5e6 c7c6 e2e4 f6e5 d2c2 d8f6 c2b3 (1869 KNPS)
10 152 6 109775 d4e6? (1770 KNPS)
10 138 9 173590 d4e6 d7e6 d5e6 b8c6 d2d3 d8e7 g2c6 b7c6 d3f5 f6b2 (1846 KNPS)
11 132 14 280961 d4e6 d7e6 d5e6 b8c6 d2d3 d8e7 g2d5 f6e5 d3c4 g8h8 c4c2 (1992 KNPS)
12 128 29 540581 d4e6 d7e6 d5e6 b8c6 e2e4 f6e5 e4f5 f8f5 d2d3 f5f8 d3b3 a8b8 b3b4 (1820 KNPS)
13 119 53 1036482 d4e6 d7e6 d5e6 b8c6 e2e4 f5e4 d2d5 d8e7 g2e4 a8e8 e4f5 f6d4 d5f3 (1951 KNPS)
14 103 112 2351694 d4e6? (2090 KNPS)
14 87 306 6153898 d4e6? (2009 KNPS)
14 92 756 14687199 d4e6 d7e6 d5e6 b8c6 e2e4 f5e4 g2e4 d8e7 f1e1 f6d4 e1e2 d4e5 d2d5 c6d4 (1942 KNPS)
15 92 760 14745600 d4e6 d7e6 d5e6 b8c6 e2e4 f5e4 g2e4 d8e7 f1e1 f6d4 e1e2 d4e5 d2d5 c6d4 (1937 KNPS)

Note how long it took to finish depth 14 search (7.5 seconds). Myrddin then plays d4e6, and the opponent DOES make the expected reply. Then Myrddin does this:

1 158 0 2 d5e6
2 142 0 36 d5e6?
2 126 0 70 d5e6?
2 89 0 132 d5e6 b8c6
3 89 0 194 d5e6 b8c6
4 89 0 256 d5e6 b8c6
5 89 0 318 d5e6 b8c6
6 89 0 1460 d5e6 b8c6
7 89 0 2745 d5e6 b8c6
8 89 0 4473 d5e6 b8c6
9 89 1 7790 d5e6 b8c6 (519 KNPS)
10 89 1 17020 d5e6 b8c6 (1134 KNPS)
11 89 1 28585 d5e6 b8c6 (1905 KNPS)
12 89 3 48657 d5e6 b8c6 (1569 KNPS)
13 89 3 78806 d5e6 b8c6 (2542 KNPS)
14 89 6 127906 d5e6 b8c6 (2063 KNPS)
15 95 67 1340351 d5e6 b8c6 a1b1 d8e7 d2d3 a8e8 b2b4 c6d4 c1e3 d4e6 g2b7 f6e5 b7d5 f8f7 b4b5 (1994 KNPS)
15 95 115 2293760 d5e6 b8c6 a1b1 d8e7 d2d3 a8e8 b2b4 c6d4 c1e3 d4e6 g2b7 f6e5 b7d5 f8f7 b4b5 (1984 KNPS)

0.06 seconds to reach depth 14, and the shortened PV is due to hash hits. This is a rather exaggerated example, but one that does occur frequently.

jm

[Bo Persson]

1. I'm just using an "always replace" strategy for my TT (an old entry is replaced by the newer one).

This is more about what happens before you replace it. For "aging" an entry, I understand that as having an age field in the table entry, so you can see if it is from the current search or from an old one. Increment a counter each time you start a new search, and store that with the new entries.

The move from an old entry can still be useful as a base for the current search, but an old score can probably not be trusted.

[KhepriChess]

1. I'm just using an "always replace" strategy for my TT (an old entry is replaced by the newer one).

This is more about what happens before you replace it. For "aging" an entry, I understand that as having an age field in the table entry, so you can see if it is from the current search or from an old one. Increment a counter each time you start a new search, and store that with the new entries.

The move from an old entry can still be useful as a base for the current search, but an old score can probably not be trusted.

My understanding is that aging is useful to "replace [old] entries by new ones, even if their draft and flags would otherwise protect them". But in my case, old entries are never protected; They will always be replaced by new entries. And I've come across comments here, from people much more knowledgeable than myself, that said "If you have a replace-always table, there is nothing you need the age for".

In my code, the only time I will return a TT score/move from the search node (and skip the full search on that move) is if the

Code: Select all

entry.depth >= search.depth

AND if the entry flag and score are within the bounds (like

Code: Select all

entry.flag = Alpha && entry.score <= search.alpha

). If those conditions aren't met, then the search wont return that TT move, but it will use that move in move ordering (to search it first).

[hgm]

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.