Using side to move as a separate bit in hash key

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Using side to move as a separate bit in hash key

Post by jwes » Sat Aug 06, 2016 6:31 am

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.

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Using side to move as a separate bit in hash key

Post by hgm » Sat Aug 06, 2016 7:21 am

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.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Splitting the table

Post by sje » Sat Aug 06, 2016 8:44 am

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.

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Splitting the table

Post by hgm » Sat Aug 06, 2016 9:29 am

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

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Splitting the table

Post by syzygy » Sat Aug 06, 2016 12:00 pm

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.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Using side to move as a separate bit in hash key

Post by syzygy » Sat Aug 06, 2016 12:04 pm

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.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Splitting the table

Post by sje » Sat Aug 06, 2016 5:48 pm

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.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Splitting the table

Post by syzygy » Sat Aug 06, 2016 6:52 pm

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?

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Splitting the table

Post by sje » Sat Aug 06, 2016 9:28 pm

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.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Splitting the table

Post by syzygy » Sat Aug 06, 2016 10:17 pm

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.

Post Reply