Author: Robert Hyatt
Date: 06:48:48 09/27/01
Go up one level in this thread
On September 27, 2001 at 06:07:35, Sune Fischer wrote: >On September 26, 2001 at 10:06:31, Robert Hyatt wrote: > >>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... > >Hmmm... >If Newton said to Einstein: >"Who cares about Lorentz effects, we never travel that fast anyway". >What should Einstein reply? ;) > >Cheers mate, >-S. "for today, it isn't a problem. For the next few centuries, it isn't a problem. It _will_ be a problem one day. But if you are asking me 'do I have to worry about it?' the answer is 'no'." :)
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.