Author: Robert Hyatt
Date: 08:14:54 09/29/03
Go up one level in this thread
On September 28, 2003 at 07:41:03, Alvaro Jose Povoa Cardoso wrote: >On September 27, 2003 at 21:59:24, Robert Hyatt wrote: > >>On September 27, 2003 at 07:46:36, Alvaro Jose Povoa Cardoso wrote: >> >>> >>>I'm a bit confused about the index 'hwhich' computation on the >>>'htable->always[hwhich]' >>>Could someone please explain the following crafty code? >>> hwhich=((int)temp_hashkey>>log_hash)&1; >>> >>>Why do we need '>>log_hash' >>>Couldn't it also be done with: >>> hwhich=((int)temp_hashkey)&1; >>> >>>Thanks in advance, >>>Alvaro Cardoso >> >> >>The above change would work. However, when I converted from the old two-table >>approached to the current modified one-table approach, I wanted _exact_ node >>count matches. This guarantees that by using the same bit that the older >>approach used with a 1-bit larger table address... > >The bit that indexes always[] ends up being the MSB (left most bit) right? > >Alvaro Cardoso I didn't think very carefully. First a description of what I am now doing. Each addressable hash table entry actually contains three separate entries, the first is DP, (the depth-preferred entry) and the other two are AS[0] and AS[1] (the always-store entries). I probe to a bucket of the above three entries by simply taking the low order N bits of the hash signature, which points me to a bucket with one DP and two AS entries. Now for the bug in the suggested change. If I just AND with 1 to pick AS[i] where i = Hash_Signature & 1; then it will not work as planned. Each odd numbered bucket will _always_ use AS[1], while each even-numbered bucket will always use AS[0]. This is why I don't use any of the low order bits to select AS[i]. So the suggested change will _not_ work correctly, as using any bit of the low order N bits will effectively disable 1/2 of the AS entries, which will cut the size of the AS table to be the same as the DP table, while the "Thompson algorithm" has AS twice as big as DP. For the question posed above, I don't use the MSB. If I have 2^N buckets, then I use bits 0 through N-1 for the table index. I use bit N to select between AS[0] and AS[1]. Using the leftmost bit would work just as well.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.