D Sceviour wrote:Is this correct, that a four-entry hash table has to allocate four times as much memory as a single-entry (always overwrite) hash table to achieve the same or better results?
No, that is certainly not correct. You should always compare replacement schemes under the constraint that they use the same amount of total memory. The idea of the schemes is to make optimal use of the resources that you have, and their merit is how well they do that.
And when you are testing the schemes, you should always do it under conditions of very heavy table overloading. If your tree fits entirely in the hash table, replacement should have no effect, as it is never done. (So the most stupid algorithm, that doesn't need to waste any time on deciding what to replace, would probably come out as best.) Note that the number of unique positions in a tree is often an order of magnitude lower than the number of nodes the search reports, due to transpositions. In the graphs I showed earlier you can see that the search only starts to slow down when the overload factor gets above 10 (= total nodes in tree 10 times larger than the number of hash entries).
The proposed theory does not show in practice. The results for 40 games for two virtually identical 32-bit programs 1 CPU using a 32MB hash table show equal results (20-20). One program used a simplified double entry hash scheme similar to the one described by Alexandru Mosoi for Zurichess. No transposition age is used here. There is a wrap around and overwrite to two slots. The other engine used a single entry overwrite hash. Exactly equal results were also obtained for the first 4-entry test with transposition age (but it was 512MB hash).
Perhaps multiple cores might make a difference. It takes a long time to fill up a 1-4GB table. With today’s large amounts of memory available, the multi-entry system looks more like a fine-tuning adjustment for high performance engines with limited expected results. If memory is sufficient then there should be no need to decide what to overwrite. There should be room for everything.
I have difficulty visualizing the multiple entry hash. How does dividing the number of available entries by four, so four entries can be written to an allocation address, improve anything? It looks like another break-even scheme. On the other hand, other people are posting different results. At least multi-entry does not deteriorate matters.
D Sceviour wrote:
The proposed theory does not show in practice. The results for 40 games for two virtually identical 32-bit programs 1 CPU using a 32MB hash table show equal results (20-20). One program used a simplified double entry hash scheme similar to the one described by Alexandru Mosoi for Zurichess. No transposition age is used here. There is a wrap around and overwrite to two slots. The other engine used a single entry overwrite hash. Exactly equal results were also obtained for the first 4-entry test with transposition age (but it was 512MB hash).
With only 40 games, you might as well toss a coin to decide which is better. It's the wrong way to measure this anyway, you're better of measuring time to depth on a selection of test positions.
I would say though that if you have something that works, it's probably time to move on to something else for now...
When you have the choice which of 4 entries to write, you can choose to overwrite the least valuable of the four, and thereby keep the more valuable entries in the table. Having 4 entries instead of one is not expected to save you anything if you would just decide randomly which of them to overwrite.
hgm wrote:When you have the choice which of 4 entries to write, you can choose to overwrite the least valuable of the four, and thereby keep the more valuable entries in the table. Having 4 entries instead of one is not expected to save you anything if you would just decide randomly which of them to overwrite.
The only reason you are trying to decide what to overwrite is because the hash table size has been reduced by a factor of the number of entries. This type of math might work for the tax department, but perhaps Evert Glebbeek is correct - it is time to move on to something else.
Another idea for using more hash memory entries is to save the AttackBoards since they take considerable time to calculate.
The hash-table size has not been reduced at all. It is still just as many MB as it was, and each entry is still the same number of bytes. And when the tree is 100 or 1000 times larger than the number of available entries, after 1% or 0.1% of the search you would always have to overwrite someting, because the hash table completely filled up.
But with buckets of 4 you have a choice, and when used wisely, you can use that to limit the damage. With buckets of 1 your choice is much more limited, and to save the most recent entry you might have to sacrifice a very expensive older one.
Here's a thought that initially helped me to understand why using multiple buckets is useful. Note that I don't think the reasoning is valid, but it nevertheless helped me.
You have a limited selection of keys with which to build the hash signature (768 for the position, a few more for castling rights, side to move and en-passant square). You use the lower N bits of this signature to index the transposition table (the remaining bits are used as a verification). Now, ideally, you want the search to address all positions in the table evenly (what use are table entries that are not used?). Question: how do you know that the hash signatures you use will do this? Answer: you don't. But by not only considering the indexed position itself, but also the next (say) 3 entries you smooth out any peaks in the frequency with which particular indices are encountered.
As I said, I don't think this line of reasoning holds up to scrutiny (for one thing, I've never actually tested whether there is any discrepancy in the frequency with which particular indices are generated, but if there is then a different set of keys can probably eliminate it), but it originally helped me to see a point to doing things this way.
Evert wrote:Here's a thought that initially helped me to understand why using multiple buckets is useful. Note that I don't think the reasoning is valid, but it nevertheless helped me.
You have a limited selection of keys with which to build the hash signature (768 for the position, a few more for castling rights, side to move and en-passant square). You use the lower N bits of this signature to index the transposition table (the remaining bits are used as a verification). Now, ideally, you want the search to address all positions in the table evenly (what use are table entries that are not used?). Question: how do you know that the hash signatures you use will do this? Answer: you don't. But by not only considering the indexed position itself, but also the next (say) 3 entries you smooth out any peaks in the frequency with which particular indices are encountered.
As I said, I don't think this line of reasoning holds up to scrutiny (for one thing, I've never actually tested whether there is any discrepancy in the frequency with which particular indices are generated, but if there is then a different set of keys can probably eliminate it), but it originally helped me to see a point to doing things this way.
That would be the next step - to add debug counters to calculate the peak frequency of indices along with depth, hash type and age. However before doing so, there should be better tangible results reported that it will make any difference.
Evert wrote:Here's a thought that initially helped me to understand why using multiple buckets is useful. Note that I don't think the reasoning is valid, but it nevertheless helped me.
You have a limited selection of keys with which to build the hash signature (768 for the position, a few more for castling rights, side to move and en-passant square). You use the lower N bits of this signature to index the transposition table (the remaining bits are used as a verification). Now, ideally, you want the search to address all positions in the table evenly (what use are table entries that are not used?). Question: how do you know that the hash signatures you use will do this? Answer: you don't. But by not only considering the indexed position itself, but also the next (say) 3 entries you smooth out any peaks in the frequency with which particular indices are encountered.
As I said, I don't think this line of reasoning holds up to scrutiny (for one thing, I've never actually tested whether there is any discrepancy in the frequency with which particular indices are generated, but if there is then a different set of keys can probably eliminate it), but it originally helped me to see a point to doing things this way.
something along that line of reasoning certainly holds up. with single entry buckets when your table is half full, each new node has a 50% chance of pushing something out. With a multi-entry bucket half the buckets are certainly not full yet (as that'd make half the buckets completely empty - quite the statistical anomaly).
Of course this is not the normal operating point for a hashtable (close to 100% full is). In which case we go to HGM's reasoning of trying to pick the least damaging thing to push out of the table being preferable.
kbhearn wrote:something along that line of reasoning certainly holds up. with single entry buckets when your table is half full, each new node has a 50% chance of pushing something out. With a multi-entry bucket half the buckets are certainly not full yet (as that'd make half the buckets completely empty - quite the statistical anomaly).
That makes no sense. A fixed-size hash table has the same number of entries whether single or multi. They should fill up at exactly the same rate.
kbhearn wrote:Of course this is not the normal operating point for a hashtable (close to 100% full is). In which case we go to HGM's reasoning of trying to pick the least damaging thing to push out of the table being preferable.
A saturated hash table is exactly the normal operating point since the purpose of transposition age is to organize hash moves after every root move.
Evert wrote:Here's a thought that initially helped me to understand why using multiple buckets is useful. Note that I don't think the reasoning is valid, but it nevertheless helped me.
You have a limited selection of keys with which to build the hash signature (768 for the position, a few more for castling rights, side to move and en-passant square). You use the lower N bits of this signature to index the transposition table (the remaining bits are used as a verification). Now, ideally, you want the search to address all positions in the table evenly (what use are table entries that are not used?). Question: how do you know that the hash signatures you use will do this? Answer: you don't. But by not only considering the indexed position itself, but also the next (say) 3 entries you smooth out any peaks in the frequency with which particular indices are encountered.
As I said, I don't think this line of reasoning holds up to scrutiny (for one thing, I've never actually tested whether there is any discrepancy in the frequency with which particular indices are generated, but if there is then a different set of keys can probably eliminate it), but it originally helped me to see a point to doing things this way.
That's really not the issue. It is all about choices. The more choices you have when you do a replacement, the better the decision is... Only problem is that there is a computational cost for the number of entries in the bucket, and that cost can eventually outweigh the gain you get with better replacement accuracy.
