Author: Sune Fischer
Date: 03:07:35 09/27/01
Go up one level in this thread
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.
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.