Author: Robert Hyatt
Date: 17:11:57 09/25/01
Go up one level in this thread
On September 25, 2001 at 13:06:32, Sune Fischer wrote: >On September 25, 2001 at 11:57:36, Robert Hyatt wrote: > >>>>>See, if you make a hash the size of 2^64 and fill it (!) >>>>>then you have no free keys left! >>>>>The next position key you generate will match one >>>>>of those in the table with 100% certainty! >> >> >>That is correct. But the way zobrist works, it is far more likely that >>that position is a _real_ match rather than a false match... So that once >>you fill the table, you can't assume that _every_ probe from that point >>forward is a false match. very few will be in fact... > >Well no, see my other post: >http://www.icdchess.com/forums/1/message.shtml?190349 >You forget that the problem here is, that you would not >be able to update any entries, and so as the game evolves, new positions will >occur and old ones will never be re-seached. This will lead to collisions. You overlook that positions get overwritten _all_ the time in the search. This is a two-way street. They get overwritten. They get reused. They will, on occasion, get incorrectly reused (collisions). But once it is full, the table is not just "full". It will still get overwritten furiously because of all the shallow leaf searches that demand to store information in the table... > >I think this discussion is a waste of our time now. > >Can we agree to the following: > >1) Double the hash size and you double the probability of a collision. Yes... assuming we agree that for today, double zero is still zero. IE today doubling the size of the hash has no real effect on collision rate, because it is already so very small with 64 bit keys... >2) With current computers it is still _extremely_ unlikely to have a collision, >much less one that would lead to a bad move. I agree with that too. I would really like to take the time to quantify just how often a collision has to occur before it does start to rip the search results apart. Sounds like a good student project somewhere. :) > > >It's just I have not seen you agree to number 1 anywhere. >Do you agree to number 1? > As amended for practical considerations, yes. With today's hash sizes, the 2^64 address space overlaps so many times collisions are very unlikely. Less than one per every 4 billion nodes searched according to testing a couple of years ago. IE I don't believe that doubling the hash size will double that collision rate. But that I can test when I have some time. It will be interesting to try. I might get time on a machine with 16 gigs of RAM so I can try doubling several times to see what happens. >-S.
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.