For doing an IDA* search, where we just need an admissible heuristic, this approach actually worksWhat you don't is precisely what you mentioned: execute hash_number modulo some_number = index, then visit database[index] and get your info. At database[index] you have multiple pieces of info, one of which is the FULL 32- bit or 64-bit number. So there is no 1-byte/entry version of a hash table.
*perfectly*; you ensure the single entry contains the minimum distance-to-solved from all values
that collide here, and your table then functions admirably. Further, if you use a fast hash function
(it doesn't have to be cryptographically secure), the elimination of collision detection, etc. cuts the
code down and the performance (with no inessential branching) can be excellent.
You can even use this idea with only one *bit* per entry that says a position is either at a distance
> d for some d, or "no information". I frequently use it with two bits per entry, giving me information
that the position is >d, >d+1, >d+2, and "no information" for a given d. Using 1.6 bits per entry also
works well, in which case you get >d, >d+1, and "no information".
Great writeup, Lucas; thanks! That clarifies things tremendously. I think the bulk of this prose shouldStory time:
be on a wiki somewhere for others to profit from.
Everyone on this thread: should we follow the sage advice of Lucas and go with SiGN exclusively, or
should we continue to use whatever we are using? In particular, if we plan to exchange positions
and compare solves it would be nice if we could just copy and paste.
Last edited by a moderator: