Author: Dann Corbit
Date: 14:24:24 11/21/03
Go up one level in this thread
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.
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.