Silly transposition table question...

[sparky]

Hi all

This is perhaps a very silly question:

When using transposition tables to speed up the main search routine, how often do you clear the hash table (either using looping/sequence number)?

1. At the end of every move the engine makes?
2. At the end of every move the engine and the opponent makes (assuming pondering filled the table as well)?
3. Only when a pawn is moved (inc. promotions) or a capture took place?
4. Periodically (every x moves)?
5. Combination of 3 and 4?

I haven't tried all these combinations with Vicki. Currently I am using [1] but I was wondering about the other 4 options. At the moment I'm inclined on trying [5] as it may avoid losing a lot of work already done by previous searches and keeping the table clean of outdated entries.

I am waiting anxiously to bathe in the forumites' vast wisdom and experience

[Tord Romstad]

When using transposition tables to speed up the main search routine, how often do you clear the hash table (either using looping/sequence number)?

1. At the end of every move the engine makes?
2. At the end of every move the engine and the opponent makes (assuming pondering filled the table as well)?
3. Only when a pawn is moved (inc. promotions) or a capture took place?
4. Periodically (every x moves)?
5. Combination of 3 and 4?

Hello Jaco,

I do:

6. Never

Tord

[hgm]

I think the "industry standard" is to store some time stamp in your hash entry, so that you can see how many searches ago it was made, and then use depth minus age as a basis to make the replacement decision. So there is no explicit pass through the hash table, but the cleanup is done as a side effect of ordinary replacement.

In Joker I do not do that, because:
1) normal replacement can already replace deep entries by less deep ones within a single search (if there are already too many of the former), so the problem of obsolete entries piling up is not so big.
2) I only had one spare bit left in my 9-byte entries, which is just too little for an unambiguous time stamp.

As a temporary measure, the single bit now marks if there was a hit on the entry in the last search (the value indicating this alternating between searches). And then I run through the table after every move, to delete entries that were not accessed. But I do that only once every 8 moves when time drops below 10 sec, and not at all after remaining time drops below 1 sec.

In the future I will get rid of this overhead, by ignoring the 'accessed' bit in the early iterations of a search (doing replacement on the assumption that all entries belong to the current search), and only use the information after starting an iteration when ~10% of the table size has been marked as accessed. By that time all entries close to the root should have been marked such, so that it is reasonably save to start overwriting deep entries that are not yet marked.

PS: you should have a look at how Vicky handles incremental time controls, as at (say) 5'+1", it only uses the 1", and never touches the 5'...

[mjlef]

I think most programs now only clear the hash table once, at program startup. After that, they use a replacement scheme that overwrites entries. Since my program might still have some root processing that assigns values on the root position, I use a "age" flag (actually 8 bits) that gets incremented with each new search.

When I write a new hash entry I store the new age flag with it. When I look into the hash, I compare the age info. If it matches, I use everything (best move, scores, etc). If it does not match, I just use the best move value and ignore the score.

I think NOW no longer has any more scoring based on root analysis, but I have been too lazy to check...the code is like a tangled spider web. I really should check this since it would make it search a lot better in blitz games.

Mark