Author: Heiner Marxen
Date: 17:35:39 09/23/01
Go up one level in this thread
On September 23, 2001 at 16:45:08, Antonio Dieguez wrote:
>On September 23, 2001 at 16:00:26, Uri Blass wrote:
>
>>On September 23, 2001 at 14:17:18, Antonio Dieguez wrote:
>>
>>>On September 23, 2001 at 02:50:59, Uri Blass wrote:
>>>
>>>>On September 22, 2001 at 23:42:29, James Swafford wrote:
>>>>
>>>>>On September 22, 2001 at 22:17:06, Uri Blass wrote:
>>>>>
>>>>>>On September 22, 2001 at 19:08:06, Torstein Hall wrote:
>>>>>>
>>>>>>>On September 22, 2001 at 18:29:46, Andreas De Troy wrote:
>>>>>>>
>>>>>
>>>>>>If the hash tables are very big then the probability for hash collision can
>>>>>>increase and if there are enough hash collisions the result can be a bad move.
>>>>>>
>>>>>>Uri
>>>>>
>>>>>Why do you think the size of the table has any bearing on the number
>>>>>of collisions? The number of collisions is a function of the
>>>>>"uniqueness" of your key, not how many entries are in your table.
>>>>
>>>>let take an extreme case:
>>>>suppose there is only one entry in your hash tables and you use 64 bit numbers.
>>>>
>>>>The probability for wrong hash collision is 1/2^64 for every new node after the
>>>>first node.
>>>>
>>>>If you have 1000000 entries in your hash tables and the hash tables are full
>>>>then the probability for hash collision is 1000000/2^64 for every new node.
>>>
>>>Hi.
>>>
>>>Just one thing, not everybody use part of the key for the hash index, me not for
>>>example but I know a lot do.
>>
>>How do you use hash tables in this case
>>You have a position and you need to decide if it is in the hash tables.
>>
>>I assume that the first thing that you do is compressing the position to a 64
>>bit number
>>
>>Am I right?
>>
>>In this case you need to decide if the 64 bit number is in your hash tables.
>>How do you do it in a fast way?
>
>I don't know how much slower it is, but I maintain another number also for the
>index, the bigger the hashtable the bigger it is. I'm a bit surprised by your
>question because it is even more natural doing this way, and the other way is
>the one that looks like a trick.
Huh, now *I* am a bit surprised.
The natural/normal way to proceed is:
(1) Map the complete board into a single hash value (HV).
The HV usually is 64 bit wide.
With the Zobrist hash algorithm this value can be maintained incrementally,
and need not be recomputed from scratch.
(2) From the HV compute an index into the hash table (HI = hash index).
Basically a hash table is an array of some fixed size, say N.
HI is a value between 0 and HI-1. Mostly we do: HI = HV % N;
If N is a power of two, the mod operation can be replaced by masking
log2(N) low bits from HV: HI = HV & mask;
(3) Try to find the searched for info in hash_table[HI], first.
(4) If that hash table slot is filled with other data, we may decide to
search some more slots. Many different ways to do this.
Mostly, the HV is stored into the hash table entries.
Since part of the HV has already been used to select the entry, one may
try to reduce the stored value to the not yet used part of HV.
>>If you have no way to calculate the hash index from the key then I do not see
>>a fast way to do it.
>>
>>I understand that the hash tables is a list of 64 bit numbers
To Uri:
No, the most important aspect of a hash table is the direct addressing
of its elements. A "list" is something else.
>>if you have 2^20 64 bits number in your list then even if your list is ordered
>>by increasing order you may need 20 comparisons to find if a new 64 bit number
>>is in the list and I do not know how to put a new number in the list in the
>>right place without being too slow(O(2^20) steps in this case.
That is why this organization is not used for transposition tables.
Hash tables have only a (small) constant overhead for access.
Heiner
>>I do not know if it is possible to do the following algorithm for an array a in
>>less than m steps:
>>
>>a[m+1],a[m+2],....a[n] are not changed
>>a[0]...a[m-1] values become the previous values of a[1]...a[m]
>>a[m] is a new number.
>>
>>The only way that I know to do it in C is
>>for (i=m;i>0;i--)
>> a[i-1]=a[i];
>>a[m]=newnumber;
>>
>>Uri
This page took 0.02 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.