Author: Uri Blass
Date: 05:54:13 09/23/01
Go up one level in this thread
On September 23, 2001 at 08:02:15, Sune Fischer wrote: >To simplify lets say we have a 2^63 size hash table, now you would have >a 50% chance of a "collision", but what you have been asking is: >the key that is here, is that the same as my key? >You are not asking if the key corresponds to the same position, how would you >even ask such a question without more detailed information about the position? >You would need e.g. a 128 bit position key to check that the 64 bit key was >valid and so on and so on. I agree that the computer cannot know if there is a hash collision If the computer can find it with 128 bit position key there is no problem so I do not define it as hash collision. > >I believed you had the same perseption of what a collision was as I. >Of cause some might consider it a collision if you go to the hash >entry and don't find the 64 bit key you hoped for. >However that is just "too bad", it is not dangerous in the same way as >when one 64 bit key gets to represent to different positions. > >If you zobrist table is perfect, >eg. it will generate all 64 bit keys with equal probability, >then the chance of a collision happening is less than a billion to 1!! Tha chances of collision with big hash tables is a significant chance. If the number of positions that their compression is stored in the hash tables is 2^32 and if the number of different positions that are calculated per move is 2^32 then you can expect an average of close to 1/2 hash collisions per move. I use the estimate 1/2^64+2/2^64+3/2^64+... 2^32/2^64~=1/2 I believe that in 2010 it is going to happen at tournament time control. Today the size of the hash tables on the best hardware can be at least 512 Mbytes that mean 2^29 bytes and 2^26 64 bits numbers. 2^32 nodes per hour is also possible for Deep Fritz on good machine and it means that 2^38 nodes per 64 hours is possible. Here my estimate is even bigger amd I estimate almost 1 hash collision per move if you use a good hardware for 64 hours per move. I do not say that this almost 1 hash collision per move is important and it is possible that it causes problem only in 1/100000 of the cases but I do not know a good estimate for it. 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.