Author: K. Burcham
Date: 14:26:09 11/21/03
Go up one level in this thread
On November 21, 2003 at 17:24:24, Dann Corbit wrote: >On November 21, 2003 at 17:14:57, K. Burcham wrote: > >>On November 21, 2003 at 17:02:13, Dann Corbit wrote: >> >>>On November 21, 2003 at 16:48:10, K. Burcham wrote: >>> >>>> >>>> >>>>I think you could answer this for me Dann. >>>> >>>>When we set hash at 64 megs and the program ends up needing more than this, is >>>>it your understanding that the program keeps the same assigned addresses on the >>>>ram as the original hash setting and just writes over the top of it? >>>>OR >>>>Do you think that as the program needs more than 64 megs it fills this and >>>>starts assigning new addresses in ram separate from original hash setting and >>>>does not write over the top of the original 64 megs and then will fill as much >>>>ram as the operating system will allow it to? >>> >>>What you are describing is called a hash collision. Let's take a ridiculous >>>example that will hopefully make it clear. >>> >>>Suppose that we allocate a total of 4 hash slots, each consuming 20 bytes of >>>RAM. So our hash table uses 80 bytes. We map chess positions by a final hash >>>of h64bit % 4, to move the hash into slots 0, 1, 2 or 3. Now, as soon as we >>>have a 5th position to store in our hash table it will have to write over top of >>>some other position (assuming that we don't chain to a secondary table or use >>>some other work-around). >>> >>>So I will have to decide on a replacement scheme. One simple scheme is to >>>always replace. >>> >>>No matter how big the hash table is, if the program thinks long enough it will >>>eventually get filled. >>> >>>Now, a hash miss is not important. It just means that we have to recalculate >>>the position instead of using the hash value. The danger with hash tables is a >>>hash collision, where the total hash information (typically the hash slot itself >>>and some key in the position) are identical, but the position is not. >>> >>>However, in practice this is very rare. If you use a 64 bit hash, it is so rare >>>that you can completely ignore it without any worry. Even with 32 bits, it >>>won't affect play much. >> >>OK, I think I understand. you are saying if we set the hash at 64 megs and the >>program uses 94 megs then the program will write over the top of the original 64 >>megs hash setting, and we will lose 30 megs of the original info. although I >>think the 30 megs that was last entered would be more accurate for that point in >>the game or position. >> >>do you agree with this? > >The program can't use more hash than you specify. So if you specify a smaller >amount than is needed for searching without collisions, then collisions will >occur. > >It's really not a worry. If you have 32 megs of hash or more, the additional >memory won't add a whole lot anyway. is the word collision the same as writing over the top of?
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.