Any good positions to test hash tables?

[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.

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.

However, when you break a "rule" you suffer the consequences. And in this case there _is_ a consequence in terms of Elo. You can reach a search deep enough where you _never_ replace anything and your search hits a wall, while a more correct implementation will not do that...

In Crafty I make multiple passes in HashStore().

1. Look for an exact signature match, overwrite if found regardless of draft or anything else.

2. Look for an "old" entry using the "age" trick I've used forever... I replace an entry with wrong age. If there are several, I replace the one with wrong age _and_ lowest draft.

3. I replace the entry with the lowest draft, period.

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.

There is no "type priority" in crafty. replace entry from previous search, or replace entry from current search with lowest draft, all in a bucket of 4. I tried several dozen alternatives before settling on this after lots of testing...

[bob]

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

This is _not_ the way to develop a chess engine. It is a way to turn into a lemming.

You should not make any design decision in your chess engine without having a good reason for doing so. And "XXX does it" is _not_ a good reason...

[hgm]

Agreed. And of course Stockfish does not use always-replace, as, although workable, this is far from optimal.

The point s that the number of end-leaves your tree has is proportional to the product of the hash-miss fractions at each ply level. And the longer you keep entries from a certain level around, the more hits they produce. But the hit frequency on a position decreases in time, after it is first visited. The transposition that can bring you to the same position first is by transposing the last two moves. To get revisits after that, you need to transpose with moves successively closer to the root, and the closer you are to the root, the slower the moves change.

So it is most efficient to distribute the available resource such that it is used most efficiently. Doubling the amount of hash devoted to a certain ply level will double the time a typical enry of that level stays around. But it will not double the number of hits, as the hit rate decreases during the storage time. So it is better to distribute the available space equally over all ply levels.

With pure always-replace, the distribution of drafts in the hash is the same as in the tree, i.e. almost all very low drafts. With pure depth-preferred, the low drafts have no chance to get in the table at all, as soon as you start overloading the table. In both cases, your number of leave nodes would decrease if you would reduce the number of abundant drafts, and give the space to the drafts that were virtually not present at all, as it has much effect on the hit-rate of the latter. This is why it works quite well to have both a depth-preferred and an always-replace table.

This works as long as the draft distributions in both tables sufficiently overlap. For very large loading factors you get a 'hole' in the middle of the distribution: the mid-range drafts will be squeezed out of both the depth-preferred table as well as the always-replace table. At that point a more advanced replacement scheme, which continues to allocate space to the intermediate drafts, has a real advantage.

[bob]

Agreed. And of course Stockfish does not use always-replace, as, although workable, this is far from optimal.

The point s that the number of end-leaves your tree has is proportional to the product of the hash-miss fractions at each ply level. And the longer you keep entries from a certain level around, the more hits they produce. But the hit frequency on a position decreases in time, after it is first visited. The transposition that can bring you to the same position first is by transposing the last two moves. To get revisits after that, you need to transpose with moves successively closer to the root, and the closer you are to the root, the slower the moves change.

So it is most efficient to distribute the available resource such that it is used most efficiently. Doubling the amount of hash devoted to a certain ply level will double the time a typical enry of that level stays around. But it will not double the number of hits, as the hit rate decreases during the storage time. So it is better to distribute the available space equally over all ply levels.

With pure always-replace, the distribution of drafts in the hash is the same as in the tree, i.e. almost all very low drafts. With pure depth-preferred, the low drafts have no chance to get in the table at all, as soon as you start overloading the table. In both cases, your number of leave nodes would decrease if you would reduce the number of abundant drafts, and give the space to the drafts that were virtually not present at all, as it has much effect on the hit-rate of the latter. This is why it works quite well to have both a depth-preferred and an always-replace table.

This works as long as the draft distributions in both tables sufficiently overlap. For very large loading factors you get a 'hole' in the middle of the distribution: the mid-range drafts will be squeezed out of both the depth-preferred table as well as the always-replace table. At that point a more advanced replacement scheme, which continues to allocate space to the intermediate drafts, has a real advantage.

This was one reason I chose to get rid of the dual table approach, and try to prefer max-draft while never refusing to store an entry. One simply has to be certain to not over-stress the table size. Fortunately, avoiding hashing the q-search, and given today's large memory sizes, I never see this as a problem in real games. Correspondence chess might be a different issue, but that will be an issue for any replacement strategy since no practical table size will be within a couple of orders of magnitude of being large enough...

[hgm]

Correspondence chess might be a different issue, but that will be an issue for any replacement strategy since no practical table size will be within a couple of orders of magnitude of being large enough...

Indeed. As you can see on the graph, at two orders of magnitude the more advanced replcement scheme already has an advantage over the standard one of 25% (in terms of search time). And it seems to scale quite wellwith overload, so for three ordersof magnitude the advantage might be even bigger.

[Chan Rasjid]

Agreed. And of course Stockfish does not use always-replace, as, although workable, this is far from optimal.

The point s that the number of end-leaves your tree has is proportional to the product of the hash-miss fractions at each ply level. And the longer you keep entries from a certain level around, the more hits they produce. But the hit frequency on a position decreases in time, after it is first visited. The transposition that can bring you to the same position first is by transposing the last two moves. To get revisits after that, you need to transpose with moves successively closer to the root, and the closer you are to the root, the slower the moves change.

So it is most efficient to distribute the available resource such that it is used most efficiently. Doubling the amount of hash devoted to a certain ply level will double the time a typical enry of that level stays around. But it will not double the number of hits, as the hit rate decreases during the storage time. So it is better to distribute the available space equally over all ply levels.

With pure always-replace, the distribution of drafts in the hash is the same as in the tree, i.e. almost all very low drafts. With pure depth-preferred, the low drafts have no chance to get in the table at all, as soon as you start overloading the table. In both cases, your number of leave nodes would decrease if you would reduce the number of abundant drafts, and give the space to the drafts that were virtually not present at all, as it has much effect on the hit-rate of the latter. This is why it works quite well to have both a depth-preferred and an always-replace table.

This works as long as the draft distributions in both tables sufficiently overlap. For very large loading factors you get a 'hole' in the middle of the distribution: the mid-range drafts will be squeezed out of both the depth-preferred table as well as the always-replace table. At that point a more advanced replacement scheme, which continues to allocate space to the intermediate drafts, has a real advantage.

This was one reason I chose to get rid of the dual table approach, and try to prefer max-draft while never refusing to store an entry. One simply has to be certain to not over-stress the table size. Fortunately, avoiding hashing the q-search, and given today's large memory sizes, I never see this as a problem in real games. Correspondence chess might be a different issue, but that will be an issue for any replacement strategy since no practical table size will be within a couple of orders of magnitude of being large enough...

I must have missed such discussions in the past. I think I'll move over to the 'Crafty_method' as it is well tested; probably not hashing qsearch should also be ok - at least a gain from having lesser bugs.

Thanks,
Rasjid.

[bob]

Agreed. And of course Stockfish does not use always-replace, as, although workable, this is far from optimal.

The point s that the number of end-leaves your tree has is proportional to the product of the hash-miss fractions at each ply level. And the longer you keep entries from a certain level around, the more hits they produce. But the hit frequency on a position decreases in time, after it is first visited. The transposition that can bring you to the same position first is by transposing the last two moves. To get revisits after that, you need to transpose with moves successively closer to the root, and the closer you are to the root, the slower the moves change.

So it is most efficient to distribute the available resource such that it is used most efficiently. Doubling the amount of hash devoted to a certain ply level will double the time a typical enry of that level stays around. But it will not double the number of hits, as the hit rate decreases during the storage time. So it is better to distribute the available space equally over all ply levels.

With pure always-replace, the distribution of drafts in the hash is the same as in the tree, i.e. almost all very low drafts. With pure depth-preferred, the low drafts have no chance to get in the table at all, as soon as you start overloading the table. In both cases, your number of leave nodes would decrease if you would reduce the number of abundant drafts, and give the space to the drafts that were virtually not present at all, as it has much effect on the hit-rate of the latter. This is why it works quite well to have both a depth-preferred and an always-replace table.

This works as long as the draft distributions in both tables sufficiently overlap. For very large loading factors you get a 'hole' in the middle of the distribution: the mid-range drafts will be squeezed out of both the depth-preferred table as well as the always-replace table. At that point a more advanced replacement scheme, which continues to allocate space to the intermediate drafts, has a real advantage.

This was one reason I chose to get rid of the dual table approach, and try to prefer max-draft while never refusing to store an entry. One simply has to be certain to not over-stress the table size. Fortunately, avoiding hashing the q-search, and given today's large memory sizes, I never see this as a problem in real games. Correspondence chess might be a different issue, but that will be an issue for any replacement strategy since no practical table size will be within a couple of orders of magnitude of being large enough...

I must have missed such discussions in the past. I think I'll move over to the 'Crafty_method' as it is well tested; probably not hashing qsearch should also be ok - at least a gain from having lesser bugs.

Thanks,
Rasjid.

There is a gain, and a loss. Not hashing in q-search is a big win for cache accesses. It will speed you up by 10-15%. Not hashing will make the tree larger, however, but not 10-15%, so there is a break-even/slight-gain for doing this. A side benefit is that you can use smaller hash tables for the same search space. My usual estimate is to have a hash table 10% of the total search space, and smaller will work since 90% of the tree is q-search, and of that remaining 10% the same positions are searched something like 10-20% of the time in the middle game...

A smaller hash table stresses cache less, and also stresses the TLB significantly less. Both of which will make your program faster... It also lets you get a bit more clever in hash probe/store code since you don't do it as often. If you do it everywhere, getting clever will slow you down more than it helps reduce the tree size.