Author: K. Burcham
Date: 14:14:57 11/21/03
Go up one level in this thread
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? kburcham
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.