Author: Heiner Marxen
Date: 10:09:18 09/16/99
Go up one level in this thread
On September 16, 1999 at 01:31:14, David Eppstein wrote: >On September 15, 1999 at 23:08:38, Robert Hyatt wrote: >>>Aha. While we are willing to accept very rare false hits, this technique >>>will work. If false hits are not at all acceptable, this will not work. >>>Heiner >> >>Note that if false hits are not at all acceptable, hashing can not be used at >>all... because there is _definitely_ a non-zero probability of collisions. > >You could still use hashing, if you stored the whole position instead of just >your key. Not very practical, though, even after the long threads here about >how to store a whole position in few bits. Much better to take the risk of a >very rare false hit. That depends. With the normal flavor of chess programs (i.e. they *play* chess) the above is true. I have a chess problem solver, where the context is different: the program has to solve an exact problem, and the answer is either right or wrong (as opposed to more or less good). And with a problem solver I would not accept (even rare) false answers: that would be a bug. Hence, I *do* store the whole position: my hash table entries are 40 bytes large. >>Tim's scheme does solve the issue by basically destroying entries where a race >>to store occurs... which is ok. And the performance improvement is >>non-trivial to boot... > >Tim's scheme is very cute. Yes, I like it very much! It is just, that *I* can't use it in *my* program :-( OTOH, I have not even started to think about SMP, so it is not much pain for me, just now. Heiner
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.