Improving TT replacement scheme

[hgm]

Even this very simple scheme of replacing entires just one search apart seemed to work quite well, and Blunder searched several positions faster. And while it looked good in testing at first (10+0.1s and a 32MB hash), indicating a gain of around 35 Elo, it slowly evaporated to a small, perhaps even negligible gain.

At 10+0.1 you will have about 0.25sec/move (assuming a game on average last 60 moves). So even at 1Mnps your search tree only has 250k nodes. A 32MB hash table can hold 2M entries (assuming 16 bytes/entry). A tree of 250k nodes typically contains 25k unique positions.

So your full tree only occupies 1.25% of the hash table. Under such conditions replacement will not be an issue, as it virtually never happens. You should not be able to see any difference between always-replace and more sophisticated schemes, as always -replace is already close to perfect: it will hardly overwrite anything. Any entry stored in the table will survive for about 80 moves, i.e. well into the next game.

[Henk]

Don't even understand why you use a TT at all. All information stored is always outdated. Maybe for move ordering but still outdated.
Maybe only store information in a table that is never outdated.

[algerbrex]

At 10+0.1 you will have about 0.25sec/move (assuming a game on average last 60 moves). So even at 1Mnps your search tree only has 250k nodes. A 32MB hash table can hold 2M entries (assuming 16 bytes/entry). A tree of 250k nodes typically contains 25k unique positions.

So your full tree only occupies 1.25% of the hash table. Under such conditions replacement will not be an issue, as it virtually never happens. You should not be able to see any difference between always-replace and more sophisticated schemes, as always -replace is already close to perfect: it will hardly overwrite anything. Any entry stored in the table will survive for about 80 moves, i.e. well into the next game.

Thanks for that breakdown of the math. I was too lazy to think through that myself, but that confirms my testing conditions were quite poor. As I said there was a significant difference for about the first 500 games, but the next 500 or so games confirmed no performance difference between the two methods.

[algerbrex]

Don't even understand why you use a TT at all. All information stored is always outdated. Maybe for move ordering but still outdated.
Maybe only store information in a table that is never outdated.

Not sure what you mean by all the information is always outdated Henk.

To my understanding, If a transposition table is used during the current search, the information is certainly not outdated, as it contains transpositions that were visited, and that will be visited again during the current search. Means you're able to get TT cutoffs. And the best move found in that transposition can be searched first, either leading to alpha being raised or getting a beta-cutoff.

Nor is the transposition table that outdated even after a couple of moves, depending on how deeply your engine can search and how fast it is, which is why I'll likely need to extend my counter to only start erasing moves after 3-4 different searches to see better performance. If transposition is encountered in the current position, and a single move is made, then the same transposition will likely be seen again, this time just closer to the root position. And again, the best move for the transposition can still be used.

Even from the earliest days of Blunder, a simple yet properly implemented, always-replace transposition table gained anywhere from 180-200 Elo in self-play, proving its usefulness.

[Henk]

You accept a history dependent search and higher draw rate.

I don't want to spend time on non reproducable errors. O wait I still use random generator to prevent it playing similar games.
Maybe randomness not needed in end game.

[jmcd]

Even this very simple scheme of replacing entires just one search apart seemed to work quite well, and Blunder searched several positions faster. And while it looked good in testing at first (10+0.1s and a 32MB hash), indicating a gain of around 35 Elo, it slowly evaporated to a small, perhaps even negligible gain.

This is exactly what happened to me when I initially implemented the bucket system. The new version was much faster, would win like 75% of the first 20 games, and then it would eventually bleed to a tie or loss overrall. I thought it might have just been a statistical anomaly, but I tried the same thing again the next day, and it happened again. Turns out I was failing to clear the transposition table between games properly. You may have the same problem.

[algerbrex]

This is exactly what happened to me when I initially implemented the bucket system. The new version was much faster, would win like 75% of the first 20 games, and then it would eventually bleed to a tie or loss overrall. I thought it might have just been a statistical anomaly, but I tried the same thing again the next day, and it happened again. Turns out I was failing to clear the transposition table between games properly. You may have the same problem.

Thanks, I made sure to go back and double-check I was clearing the table when the `ucinewgame` command is sent, and I am, so unfortunately I don't think that was the issue. I think HGM is right though with his analysis, my time controls were likely too short.

What time controls did you use to test your changes? And what Elo gain did you record in the end?

[jmcd]

Thanks, I made sure to go back and double-check I was clearing the table when the `ucinewgame` command is sent, and I am, so unfortunately I don't think that was the issue. I think HGM is right though with his analysis, my time controls were likely too short.

What time controls did you use to test your changes? And what Elo gain did you record in the end?

I got a ~25-50 elo gain after going from "always replace" to the bucket method, but this was tested using very short time controls, like 500ms per move. I would assume that for tt testing, higher time controls would give a more accurate picture of the gain. Especially when a big flaw of the always replace method is that it doesnt utilize high depth entries very well.

[algerbrex]

I got a ~25-50 elo gain after going from "always replace" to the bucket method, but this was tested using very short time controls, like 500ms per move. I would assume that for tt testing, higher time controls would give a more accurate picture of the gain. Especially when a big flaw of the always replace method is that it doesnt utilize high depth entries very well.

Ah, gotchu. Yep, long-time control testing would definitely be best, but unfortunately, I don't have the hardware or time to support such extensive testing

[Ras]

Ah, gotchu. Yep, long-time control testing would definitely be best, but unfortunately, I don't have the hardware or time to support such extensive testing

Or you could test at shorter time controls, but with only 1MB of hash.