Author: Robert Hyatt
Date: 14:57:41 09/24/01
Go up one level in this thread
On September 24, 2001 at 16:59:45, Antonio Dieguez wrote: >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. Assuming 3 minute searches? so 6 minutes total? I hash maybe 1/3 of the total search space (no q-search nodes hashed) so that turns into about 2 minutes of searching. at 1M nodes per second, that is 120M positions, or 1.44 gigs total. > >> 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.