Author: Uri Blass
Date: 07:24:49 09/25/01
Go up one level in this thread
On September 25, 2001 at 09:46:05, Robert Hyatt wrote: >On September 25, 2001 at 08:41:25, Dieter Buerssner wrote: > >>I made a small, not very scientific experiment, to get a feeling >>for the significance of hash collisions. >> >>For this, I tested 22 positions of WAC (the ones, that I would call the >>most difficult ones). I tested those for 2 million nodes. Yace will use >>HTs in quiescence search, so the table gets filled very fast (on average >>almost 80% of the searched nodes get stored). I used only a small HT >>for this test - 1e6 bytes, which is about 80000 entries - to make sure, >>that the table really gets overloaded. I made 4 runs of the test positions: >>with a 32/16/12 and 8-bit hash-values (the hash index is calculated >>independently of these). Here are the results. I hope, it is more or >>less self explaining. The number of hash errors given, is just the >>ones that were detected by checking for the legality of the move. This is >>only done, when the hash info would give a cutoff, or an adjustment of >>the search window. When the move is not legal, no cutoff/adjustement of search >>bound is allowed. >> >>TEST test.ci by Yace 0.99.56 32-bit hash search_nodes 2000000 Tue Sep 25 >>14:14:58 2001 >>table_add=30392714, table_store=30392714, table_probe=38930034, 29.22% found >>hash_errors 0, egtb_probe=0, egtb_found=0 >> 22 tested, 19 found, 3 not found, mates 4, time 118.71 >>test nodes 17047943 win nodes 11047915 mate nodes 2601918 >>win time 78.65 mate time 17.41 av depth 8.045 (nm 8.222) maxdepth 32 tu 74 > > > >Remember what I said earlier. The collision probability is not the only >thing you have to deal with. You have to have _enough_ collisions so that >the root score changes. This is a harder thing to cause. Your very small >table is probably helping you avoid this rather than hurting. Because you >are probably depth-preferred and are not adding much to the table after the >first few seconds, at a guess... No In dieter's case the hash index is calculated independently of the hash value so the probability to get hash collision is at most 1/(2^n) when n is the number of bits of the hash value(32,16,12,8 in dieter's expperiment). It is 1/2^n if the hash tables are full. It is less than it if the hash tables are not full because in order to get an hash collision you need 2 conditions: 1)the hash index was used in the past for a position 2)the hash key is exactly the same as the previous position that was stored. The probability that 1 happens is 100% only if the hash tables are full. The probability that 2 happens when you know that 1 happened is a fix number that is 1/(2^n) if the hash algorithm simulate succesfuly random numbers(if it does not simulate generating random numbers succesfuly than it may be bigger than 1/(2^n) but still a fixed number). The probability that both 1 and 2 happen for a new position get the maximal value when the hash tables are full. 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.