Author: Robert Hyatt
Date: 07:06:31 09/26/01
Go up one level in this thread
On September 26, 2001 at 06:52:32, Sune Fischer wrote: >On September 25, 2001 at 23:57:33, Robert Hyatt wrote: > >>On September 25, 2001 at 11:33:51, Antonio Dieguez wrote: > >>>>Note that I don't sign on to the theory that more ram increases the probability >>>>of a collision. >>> >>>Try it yourself, then. With different hashtable sizes. >>> >>>this is what I got in the initial position, with 16 bits total. With replacing >>>scheme always replace. >>> >>>with 128 entries: >>>[9] 978059 nodes, illegal moves=2416 >>> >>>with 256: >>>[9] 909888 nodes, illegal moves=3113 >>> >>>512: >>>[9] 944380 nodes, illegal moves=5450 >>> >>>1024: >>>[9] 847469 nodes, illegal moves=9062 >>> >>>2048: >>>[9] 915317 nodes, illegal moves=15875 >>> >>>4096: >>>[9] 1183890 nodes, illegal moves=38123 >>> >>>I think it will be obviously the same trying others positions too. > >What a beautiful experiment Antonio;) > >>But what if you use a 64 bit key, with absolutely no hope of searching >>1/4,000,000,000th of that search space? How many collisions then? And >>if you increase the hash size, how many collisions then? > >He would get the same result: double hash -> double number of collisions. >Of couse the actual count would be zero unless it ran for a very long time. > We are getting very near to the old "Chess is O(1) complexity because the size of the tree is definitely 'finite' in nature." Of course that overlooks the problem that the size is so large that it is not going to be searched before the sun turns into a red giant. Same with this problem. We are not going to be searching 16,000,000,000,000,000,000 nodes any time in the forseeable future. And until we get to an appreciable fraction of that search space, you can change the hash table size all you want and it is going to have zero influence on the collision rate. Which has been my point all along. Suggesting that 4 gigs of hash is worse than 2 gigs because it will cause more collisions is an accurate statement, but it is missing one important detail. The 2 gig hash table will have _zero_ collisions. So of course the 4 gig table will have 2*zero collisions as well. You say it will double. I say it will be unchanged. Thanks to that "zero" we are both correct here... >>I don't think the experiment is framed correctly to answer the question that >>is being asked: "With today's hardware, and 64 bit hashing, is a bigger hash >>table always better?" The answer is still yes, IMHO. > >Yes, I agree completely, but this thread sort of turned into a discussion of >whether or not doubling the hash size would also double the probability of a >collision. >It's the apples and oranges again, we agree on the apples, it was the orange >debate that was interesting ;) > >-S. Just so it doesn't deteriorate into "chess is O(1)" I'll be happy. :)
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.