Author: TEERAPONG TOVIRAT
Date: 10:36:15 10/03/01
Go up one level in this thread
On October 03, 2001 at 02:54:32, Uri Blass wrote: >On October 02, 2001 at 20:52:13, TEERAPONG TOVIRAT wrote: > >> >>Dear Dr.Hyatt, >> >>I think the number of total _possible_ positions in chess is beyond >>the question. However,I'd like to know how they calculate it ? >> >>A few months ago,I tried to work out the number in _checkers_ >>game. My logical assumption is that if the hash signature is too >>small there would be a high incidence of type 1 collision and if >>the hash signature is large enough the collision would be 0. >>So,my experiment started with 32 bit hash table ,after 1 million >>entries are fully occupied I started counting the incidence of >>type 1 collision. Each time I got type 1 error,I increase another >>bit to the hash table.I saw the incidence is lowered by half too. >>Until one point the incidence is zero ,of course after a few >>games test. >> >>Could I claim that at that point the hash signature is approximately >>equal to the number of legal(possible) positions? > Hi, >I do not know what is type 1 collision I mean Zobrist type 1 error,2 different positions having the same hash signature. I read about this from Dennis Breuker's papers. and I also do not understand what hash >tables can do with the number of legal positions because it is known that the >search trees of programs contains only a very small part of the number of legal >positions. In checkers,it's said that there are 10^18 possible positions. For a 64 bit hash table (1.6x10^19) ,if we have a good hash function, we will never get type 1 error. It seems like you have 10 tennis balls in 100 baskets,we can expect any position has its own unique signature. -> Do you agree here? if we decrease number of bit of hash table one after another. What would happen? (You start to decrease the number of baskets.) We would get more risk of type one error,approximately by factor of 2 for each decreasing bit,because there must be some positions sharing the same hash signature. ->Do you agree here? By experiment, we can test the incidence of the error when collision of position occur. I admit that if the number of test is small it's difficult to say the incidence is zero or just close to zero .This is the main drawback. I started with 32 bit hash table. If the error happened,I gradually increased the number of bit. Until the incidence is touching zero. I think at that point the number of positions and hash signature is roughly equal. Any comment is welcome. Teerapong
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.