TT open addressing

[rjgibert]

Why isn't open addressing used in TTs? Instead of always replace or depth preferred or a combination of the 2, why not continue to probe until a not so useful entry is encountered where replacing does not cost as much? The algorithms that can do this are very simple and very fast. For example, you can manage all entries of a particular depth or draft separately using a small array giving you a lot of control. You can guarantee TT properties such as for example, never overwriting the PV positions, never overwriting positions occurring near the root, never overwriting positions that are frequently trasposed to from many parts of the search tree, etc.

I think the cost of doing this sort of thing is minimal and might have a useful impact on performance. To take just one example, let say you decide to never overwrite positions within 6 ply of the root. The amount of space those positions occupy in the table is very small e.g. assuming an EBF of 6, EBF**depth*TT_entry_size = 6**6*16 = 746496 bytes. That's nothing and those positions are a lot of work to generate, so chances are you will save yourself a lot of work for a little cost.

The only real cost would be to expend 1 byte in each TT entry to help manage the TT. In that byte you can store the entries age or whether it is a PV node or whatever. These days there is more than enough memory for the TT, so increasing the size of the TT entries is not the big deal it used to be.

[Gian-Carlo Pascutto]

I think a lot of engines are using multiple buckets and replacing the cheapest one.

[hgm]

You have to be careful not to exceed the cache line, as doing a second memory access for the probe would be very expensive. Note that d=20 entries are not very valuable when all d=19 daughters are still in the table: a 1-ply search would recover it. So the draft of an entry might in practice not say all that much. Also, entries with a bound score might be completely useless despite a very high draft.

In Joker I use 9 entries per 64-byte cache line: 8 depth-preferred slots and one always-replace slot. Each probe only considers two of the eight depth-preferred entries; if the least valuable entry of the two is more valuable than the position I want to store, the latter goes to the always-replace slot of the bucket.

Note that what ' least-valuable' means is not purely determined by the draft: I also overwrite entries irrespective of their draft when that draft already occupies more than its fair share of the hash table. Such overrepresented drafts are treated like they were d=0 entries.

[bob]

Why isn't open addressing used in TTs? Instead of always replace or depth preferred or a combination of the 2, why not continue to probe until a not so useful entry is encountered where replacing does not cost as much? The algorithms that can do this are very simple and very fast. For example, you can manage all entries of a particular depth or draft separately using a small array giving you a lot of control. You can guarantee TT properties such as for example, never overwriting the PV positions, never overwriting positions occurring near the root, never overwriting positions that are frequently trasposed to from many parts of the search tree, etc.

I think the cost of doing this sort of thing is minimal and might have a useful impact on performance. To take just one example, let say you decide to never overwrite positions within 6 ply of the root. The amount of space those positions occupy in the table is very small e.g. assuming an EBF of 6, EBF**depth*TT_entry_size = 6**6*16 = 746496 bytes. That's nothing and those positions are a lot of work to generate, so chances are you will save yourself a lot of work for a little cost.

The only real cost would be to expend 1 byte in each TT entry to help manage the TT. In that byte you can store the entries age or whether it is a PV node or whatever. These days there is more than enough memory for the TT, so increasing the size of the TT entries is not the big deal it used to be.

\

Speed. The cost for hashing is already higher than you might guess, because you go to a random address. If you try to use a "chain" by simply probing successive entries until you find one to replace, you run into a real performance problem, because chains tend to grow faster as they get bigger. Bad news.