TalkChess.com

I was thinking of using one bit of the hash key for side to move. The advantage would be that the same position with the other side to move would be in the same bucket. This would mean that a hash probe after a null move would generally not cause a cache miss, and it might also be useful to have access for making search decisions.

There are indeed some engines that do this. The stm key doesn't have to be 1; it is enough that all bits from which the bucket index is derived are zeros. Downside is that you will effectively be allocating the entries in pairs, (as nullmoves are very common),so that a bucket can contain only half the number of independent entries. This increases the probability that important entries flush each other out of the TT.

It might be more space-efficient to enlarge the entry with a second score field, to hold the score after null move. Then you would not score duplicate signature and depth.

Another idea is to split the table into two equal size tables; one for WTM, the other for BTM. I've done this and it has worked well. In a program with a variable search depth, both tables see about the same usage regardless of the root STM.

Bonus #0: No need for an extra XOR operation for position STM.

Bonus #1: Essentially, a free extra bit to guard against false positive matches.

Bonus #2: For move storage, the colors of the moving man and any captured man need not be stored in a table entry.

This would only have the "guaranteed cache hit" property if you interleave the tables, though. (e.g. odd entries wtm, even entries btm.)

sje wrote:Another idea is to split the table into two equal size tables; one for WTM, the other for BTM. I've done this and it has worked well. In a program with a variable search depth, both tables see about the same usage regardless of the root STM.

Pre-determining which half of the hash table will be used for white and which for black will decrease the efficiency of the hash table. "about" the same usage is not enough.

hgm wrote:There are indeed some engines that do this. The stm key doesn't have to be 1; it is enough that all bits from which the bucket index is derived are zeros. Downside is that you will effectively be allocating the entries in pairs, (as nullmoves are very common),so that a bucket can contain only half the number of independent entries. This increases the probability that important entries flush each other out of the TT.

In SF the idea would lack this disadvantage: SF stores two 32-byte buckets in one cache line, so the side-to-move bit could be chosen to toggle between the two buckets.

Interesting, I can't think of any reason not to do this in SF.

syzygy wrote:

sje wrote:Another idea is to split the table into two equal size tables; one for WTM, the other for BTM. I've done this and it has worked well. In a program with a variable search depth, both tables see about the same usage regardless of the root STM.

Pre-determining which half of the hash table will be used for white and which for black will decrease the efficiency of the hash table. "about" the same usage is not enough.

Actually, it is; at least in my tests. And it will be true in any program with a variable depth search regardless of the origin(s) of the variability.

sje wrote:

syzygy wrote:

sje wrote:Another idea is to split the table into two equal size tables; one for WTM, the other for BTM. I've done this and it has worked well. In a program with a variable search depth, both tables see about the same usage regardless of the root STM.

Pre-determining which half of the hash table will be used for white and which for black will decrease the efficiency of the hash table. "about" the same usage is not enough.

Actually, it is; at least in my tests. And it will be true in any program with a variable depth search regardless of the origin(s) of the variability.

How did you test?

syzygy wrote:

sje wrote:

syzygy wrote:

sje wrote:Another idea is to split the table into two equal size tables; one for WTM, the other for BTM. I've done this and it has worked well. In a program with a variable search depth, both tables see about the same usage regardless of the root STM.

Pre-determining which half of the hash table will be used for white and which for black will decrease the efficiency of the hash table. "about" the same usage is not enough.

Actually, it is; at least in my tests. And it will be true in any program with a variable depth search regardless of the origin(s) of the variability.

How did you test?

By activating the various metrics counters for utilization, inserts, probes, matches, etc.

sje wrote:

syzygy wrote:

sje wrote:

syzygy wrote:

sje wrote:Another idea is to split the table into two equal size tables; one for WTM, the other for BTM. I've done this and it has worked well. In a program with a variable search depth, both tables see about the same usage regardless of the root STM.

Pre-determining which half of the hash table will be used for white and which for black will decrease the efficiency of the hash table. "about" the same usage is not enough.

Actually, it is; at least in my tests. And it will be true in any program with a variable depth search regardless of the origin(s) of the variability.

How did you test?

By activating the various metrics counters for utilization, inserts, probes, matches, etc.

So no tests of the effect on playing strength.

It is intuitively obvious that splitting the table in two and dedicating one half to white-to-move and the other to black-to-move is suboptimal, because white-to-move hash pressure and black-to-move hash pressure will not always be equal. Testing is not really needed to confirm this. Only if you could get a speed up by splitting the table might it be different, but a speed up you won't get.

Statistics suggesting that things tend to average out somewhat don't really convince me, I'm afraid.