Freecell Solver now calculates a secondary 32-bit hash value for storing
states and stacks in its internal hash. By secondary, I mean a value that
is only used to speed up element comparisons, and is not used for lookup
into the hash table. (I figured out 64-bit arithmetic on 32-bit machines
is something that should better be avoided).
The hash function that was used was Bob Jenkins' lookup2 hash:
http://burtleburtle.net/bob/hash/
He claims that it can also be used without moduling with a prime number
just by bit-anding the lower bits. Maybe I'll use it as the primary hash
function and get rid of the evil prime numbers growth code.
I made a small debugging and it turned out that this combination
eliminates all the false hits. The birthday paradox says that a collection
of elements out of a space become 1/2 at about the square root of its
size.[1]. sqrt(2^32) = 65,536, while sqrt(2^64)=2^32, which is a vast
improvement.
Regards,
Shlomi Fish
[1] -
http://burtleburtle.net/bob/hash/birthday.html
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_iglu.org.il
He who re-invents the wheel, understands much better how a wheel works.
Received on Thu Jun 20 2002 - 09:53:12 IDT