Author: Robert Hyatt
Date: 20:57:33 09/25/01
Go up one level in this thread
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. 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? 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. > >> The probability of a collision is 1 / 2^64 for a normal >>position. This means for a table that holds 2^64 entries in a 2^64 signature >>space. Smaller RAM improves that by overwriting/replacing entires before they >>can collide. But the base 1/2^64 is good enough for me. That is a very tiny >>number... > >If you don't like one of my conditions, try it yourself with that corrected. But >using 2^somethings as a hash capacity. > >>Since we will never see memories that large, the probabilities are going to be >>good enough for a long time, assuming that 1 collision every few billion nodes >>is acceptable... So far that seems to be ok... > >yes, okey but we are not discusing that. Actually we are. The original question was "Is bigger hash always better?" In the context of today's programs, with hardware available over the next 100 years, the answer is a simple "yes".
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.