Author: Dann Corbit
Date: 13:17:28 04/07/04
Go up one level in this thread
On April 07, 2004 at 13:52:18, rasjid chan wrote: > >Moves from TT can be illegal, ie castling and EP losing rights >in hash-probe node. > >For routine chess programming, I think almost impossible to have haskey >collision. By the birthday paradox, a collision (two different positions, but the same hash) will have a probability of approximately the square root of the hash size. See: http://burtleburtle.net/bob/hash/birthday.html http://www.pasta.cs.uit.no/thesis/html/ronnya/node21.html So if you use a 32 bit hash, you will see tons of collisions. About one in ~ 65000*1.17=76675.95 will collide once the hash table is full. Still, that's only .0013% If you use a 64 bit hash, one entry in 4 billion * 1.17 will be a hash collision. That is so rare it won't affect the search noticeably. If you used a 128 bit hash (and a good algorithm) you would basically never see a collision. With the collision rate he is seeing, something is definitely wrong, unless he uses a tiny 16 bit hash or something.
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.