Author: Antonio Dieguez
Date: 13:59:45 09/24/01
Go up one level in this thread
On September 24, 2001 at 16:24:01, Robert Hyatt wrote: >On September 24, 2001 at 15:31:58, Antonio Dieguez wrote: > >>On September 24, 2001 at 14:33:49, Uri Blass wrote: >> >>>On September 24, 2001 at 13:53:58, Antonio Dieguez wrote: >>> >>>> >>>>>Several hash into 2 X 32 bit values. You store one value, you use the other >>>>>to generate the hash index. This is not quite as safe as a true 64 bit hash >>>>>signature where all 64 bits are used, but it is pretty good. If you have >>>>>one million entries in the table, your hash key is 52 bits long, effectively, >>>>>which is not horrible. Not as good as 64, but not horrible. >>>> >>>>hi. isn't one million of entries around 2^20, so just 44 bits are used for the >>>>key, (not 52) ? >>> >>>no >>>My understanding is that in this case every chess position is practically >>>compressed to 52 bits(52=32+20) >>>20 bits are used for the index when 32 bits are used for the position. >> >>oops yes I "just" mixed up what Hyatt said... >>but what does this mean >>>>>one million entries in the table, your hash key is 52 bits long, effectively, >>>>>which is not horrible. Not as good as 64, but not horrible. >> >>who cares if it is 52 or other? what about more hash entries, then that will >>surpass 64, funny. We can't compare just that numbers. > > > > >Who cares about the number of hash entries? We aren't scanning the entire table >to find a false match. We index to one position only. Suppose the table was >2^64 in size so you could store the entire set of possible hash signatures. >Does that increase the chances of a collision? That's cheating. Let's refer to sizes that can be filled in a couple of moves. I supose with your quad crafty can fill a few GBs. > Suppose your table has 1 >entry. you can _still_ get a collision. > >I think you are trying to consider "time" in the equation here. The farther >apart two entries are stored in time, the less chance they will falsely match >since the first has a greater chance of getting overwritten before the second >is reached. The chances of a collision with 64 bits are so remote, I wouldn't >give it a moment's thought. Because even with a _full_ 64 bit address space >for the table, the probability of a false match is one out of 2^64. Very >small. Because for any 64 bit hash signature, there is only _one_ place I >will try to find it stored in the table, regardless of how large the table >is. With that small a chance to get a false match with a full address space, >smaller tables only reduce the chances further due to overwrites. > > >> >>>If you get another position with the same hash key then the chance that you get >>>the same number(hash collision) is practically 1/2^32 >>> >>>probability of 1/2^32 for hash collision is not bad and in the worst case if you >>>have a fast machine and a fast searcher you get an average of 1 or 2 hash >>>collisions in one hour. >>> >>>I believe that in more than 99% of these hash collisions the move in the game is >>>not changed but I do not know if I am right and it is only based on intuition >>>that says that changing the score of one random node in the tree is not going to >>>change the move when the tree is huge and have more than 2^26 nodes. >>> >>>Uri
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.