Author: Robert Hyatt
Date: 13:24:01 09/24/01
Go up one level in this thread
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? 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.01 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.