Using side to move as a separate bit in hash key
Moderators: hgm, Rebel, chrisw
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Using side to move as a separate bit in hash key
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.
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Using side to move as a separate bit in hash key
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.
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.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Splitting the table
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.
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.
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Splitting the table
This would only have the "guaranteed cache hit" property if you interleave the tables, though. (e.g. odd entries wtm, even entries btm.)
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Splitting the table
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.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.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Using side to move as a separate bit in hash key
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.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.
Interesting, I can't think of any reason not to do this in SF.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Splitting the table
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 wrote: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.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.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Splitting the table
How did you test?sje wrote: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 wrote: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.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.
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Splitting the table
By activating the various metrics counters for utilization, inserts, probes, matches, etc.syzygy wrote:How did you test?sje wrote: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 wrote: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.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.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Splitting the table
So no tests of the effect on playing strength.sje wrote:By activating the various metrics counters for utilization, inserts, probes, matches, etc.syzygy wrote:How did you test?sje wrote: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 wrote: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.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.
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.