Any good positions to test hash tables?

[michiguel]

Here is some important advice that quite a few overlook: "NEVER, and I do mean NEVER fail to store a current position in the hash table. Let me repeat, NEVER. You can do whatever you want to choose what to replace, but you MUST replace something.

Quibble: if the hash table causes a cutoff, you don't want to store anything.

You mean, if the info got from HT causes a cut off, you do not want to store it back before return from search()?

It may or may not help, depending if the slot was brought "upfront" when was read. Now that information became current and that should be reflected in the HT, changing the age and the position in the table if several slots are being used. If this is not done when read, I disagree. It should be stored back to "refresh" it.

Miguel

[bob]

I never considered the idea of storing the same entry twice in a hash table, no more than I would want a cache to store the same memory block twice. As they used to write on old 14th century ocean maps, "here there be dragons..."

I would consider two copies of anything to be a bug. And failing to store something at every opportunity is almost as serious...

Yet there is a top engine that does exactly that.

To what possible purpose???

I could imagine two bounds, particularly for mtd(f) searches, but more than one hash entry? What is the justification?

[bob]

Here is some important advice that quite a few overlook: "NEVER, and I do mean NEVER fail to store a current position in the hash table. Let me repeat, NEVER. You can do whatever you want to choose what to replace, but you MUST replace something.

Quibble: if the hash table causes a cutoff, you don't want to store anything.

Not sure what you would show since you did no search and have no information other than what was in the table that caused the cutoff in the first place. But you_could_ store what you just found, if you want... Wasted work of course.

[bob]

Here is some important advice that quite a few overlook: "NEVER, and I do mean NEVER fail to store a current position in the hash table. Let me repeat, NEVER. You can do whatever you want to choose what to replace, but you MUST replace something.

Quibble: if the hash table causes a cutoff, you don't want to store anything.

You mean, if the info got from HT causes a cut off, you do not want to store it back before return from search()?

It may or may not help, depending if the slot was brought "upfront" when was read. Now that information became current and that should be reflected in the HT, changing the age and the position in the table if several slots are being used. If this is not done when read, I disagree. It should be stored back to "refresh" it.

Miguel

I update the "age" field on any hash hit, already...

[bob]

Looks like I have a serious flaw...
Nothing is better, then there is hope for an improvement

Is there a lot to gain on more complicated replacement schemes?

Hard to say. If you use a very simple replacement strategy, then going to a better approach can produce significant gains on fine 70 type positions. For normal middlegame, the gain will be modest at best. This is somewhat like the optimization problem. It is easy to get big speedups early in a program's life cycle, but very difficult as it is refined...

[Sven]

Here is some important advice that quite a few overlook: "NEVER, and I do mean NEVER fail to store a current position in the hash table. Let me repeat, NEVER. You can do whatever you want to choose what to replace, but you MUST replace something.

Quibble: if the hash table causes a cutoff, you don't want to store anything.

You mean, if the info got from HT causes a cut off, you do not want to store it back before return from search()?

It may or may not help, depending if the slot was brought "upfront" when was read. Now that information became current and that should be reflected in the HT, changing the age and the position in the table if several slots are being used. If this is not done when read, I disagree. It should be stored back to "refresh" it.

Miguel

I guess the term "cutoff" was not correct here, he obviously meant a node where search can be avoided by HT lookup.

Sven

[Chan Rasjid]

...
Here is some important advice that quite a few overlook: "NEVER, and I do mean NEVER fail to store a current position in the hash table. Let me repeat, NEVER. You can do whatever you want to choose what to replace, but you MUST replace something.

That seems counter-intuitive, but it is critical. I use a bucket of 4 entries and choose the best of the 4 (actually the worst, but you get my drift) to replace, and I always store the entry from a fail-high, a fail-low, or an EXACT search.

I think the 'NEVER' rule applies only to some 'standard' replacement schemes; in chess programming every other person is trying out all manner of tricks; my replacement scheme is this, in order of priority:
1) 'effective depth' - this is a combination of depth + age, to try to retain some old_high_depth positions if they are not too old; age =16 at start of game; at rootsearch(), age += 1 + !followPV; for every game move that moves a pawn, age+= const; for nullmove age -=const; etc
2) type - in order of priority exact, fail-low, fail high;
3) age == search sequence number.

With my scheme, ageing is by : depth | type | age.
All the four slots might have positions better than the current node in which case nothing is stored - the 'NEVER' rule is broken.

I don't understand why your type priority is FH/FL/EX. The main idea of transposition table is to store the 'most-helpful' positions; it is for this reason that higher depth has preference as it saves the most time. For type, exact is sure to cause a return (unless a scheme does not cutoff on pv); fail-low searches all nodes and is expensive to do, fail-high might just have searched 1/2 moves.

Rasjid.

[hgm]

I don't understand why your type priority is FH/FL/EX. The main idea of transposition table is to store the 'most-helpful' positions; it is for this reason that higher depth has preference as it saves the most time.

But that is a wrong assumption. How much good a slot in the hash table does depends not only on the search time you save _when_ you get a hit on it, but just as much on the _frequency_ with which you get hits on it. So the best entry to keep is that with the highest ratio savedSearchTime/timeToNextVisit.

Now recently visited positions with low draft (= close to the leaves) on averge have a much shorter average time to the next revisit than positions close to the root, because of the way a depth-first tree walk works. This is why pure always-replace works like a charm, while pure depth-preferred is a total bust.

[Chan Rasjid]

I don't understand why your type priority is FH/FL/EX. The main idea of transposition table is to store the 'most-helpful' positions; it is for this reason that higher depth has preference as it saves the most time.

But that is a wrong assumption. How much good a slot in the hash table does depends not only on the search time you save _when_ you get a hit on it, but just as much on the _frequency_ with which you get hits on it. So the best entry to keep is that with the highest ratio savedSearchTime/timeToNextVisit.

Now recently visited positions with low draft (= close to the leaves) on averge have a much shorter average time to the next revisit than positions close to the root, because of the way a depth-first tree walk works. This is why pure always-replace works like a charm, while pure depth-preferred is a total bust.

Yes, I forgot about frequency of hit.

Then which have more frequency- fh/fl/ex.

If Stockfish uses a pure _replace_always scheme, I''ll follow with no further question.

Rasjid

[bob]

Here is some important advice that quite a few overlook: "NEVER, and I do mean NEVER fail to store a current position in the hash table. Let me repeat, NEVER. You can do whatever you want to choose what to replace, but you MUST replace something.

Quibble: if the hash table causes a cutoff, you don't want to store anything.

You mean, if the info got from HT causes a cut off, you do not want to store it back before return from search()?

It may or may not help, depending if the slot was brought "upfront" when was read. Now that information became current and that should be reflected in the HT, changing the age and the position in the table if several slots are being used. If this is not done when read, I disagree. It should be stored back to "refresh" it.

Miguel

I guess the term "cutoff" was not correct here, he obviously meant a node where search can be avoided by HT lookup.

Sven

I do exactly the same thing when I get a hash hit that causes a cutoff or execute a search that terminates with a cutoff. Except I don't store the hash entry since I already have one that caused a cutoff, and it might have a better draft or a better bound than where I am at present...

But a hash hit does cause a cutoff to happen when the bound is good enough and the draft is deep enough...