Author: Uri Blass
Date: 06:52:32 12/07/02
Go up one level in this thread
On December 07, 2002 at 09:10:59, David Rasmussen wrote: >On December 07, 2002 at 08:42:47, Uri Blass wrote: > >>On December 07, 2002 at 06:55:39, David Rasmussen wrote: >> >>>In my incremental move generator, I first check if there is a hash move, and if >>>there is, then I check it for pseudo-legality. If it's not pseudo-legal, I >>>conclude that there is a hash collision. The position that this move was stored >>>from cannot be the same as the current, and still they have the same hash >>>signature. In my program when this happens, I exit. I do this because this >>>basically never happens. Until now. >> >> >>If you think it never happens then you do not need to check if it is pseudo >>legal and your program may become faster. >> > >I know that, but I still like knowing what is going on. That's why I do it. I >don't care for 0.0000000000000001% speedup. If I didn't do it, I would have no >idea how often this happened. Now I do. I could of course just write to a log or >to stdout when it happened. > >>All the idea of checking if the move is pseudo legal is for doing something when >>it happens and not exit(you can simply decide that there is not a hash move and >>continue the search if you find that the hash move is not pseudo legal) >> > >I know... > >> It was playing a game on ICC, and it >>>suddenly exited. I could see from the log that this is what happened. So I was >>>wondering: How often does this kind of collision happen for your engines? >>>I think Bob Hyatt has mentioned that this happens in 1 of 100 games. It doesn't >>>for me. >> >>I think that it is dependent on the size of the hash tables. > >Certainly. > >>I expect it to happen more if you use big hash tables. >> > >Why? When there are more positions in the hash tables there is bigger probablility that the hash signature of a new position is going to be the same. If you have 64 bit signature and 2^24 positions in the hash tables then you can expect probability of 1/2^40 for every new position that you search. If your program searches 2^20 positions per second then you may expect average number of 2^20 seconds to see one hash collision and 2^20 seconds is few weeks. I assume that the hash signature of a position is a random number and I know that this assumption is not correct but I do not know of better model. It is simple math to see that if you increase the number of positions in the hash tables then you can expect more hash collision unless you play fast time control and have not enough time to fill the hash tables. 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.