Home 
Search 
Today's Posts 
#1




Hash table percentages
Question: What is a good percentage of hash table hits during a search?
10%, 50%, some other number? Details: My program does a standard (I assume) AB search with nullmoving (R=2) and iterative deppening. The hash table is 2^18 and I am using 18 bit keys (eg table size in bits and key size are the same). The only other quirk is that the first move at root is searched with a window of (prev_score100,prevscore+100) with the usual search fail high, search fail low detections and researches. Subsequent moves get searched with a window of (previous beta, previous beta+1) with a research window of (beta+1, +infinity) for a fail high. A hash table hit is one where the hash key and the checksum key match, although the returned value could be a bound and not an exact score. I am only getting between 7% and 12% hits from my hash table. This seems low. Is there something wrong with my implementation of either my search or my hashing? 
#2




Hash table percentages
Shaun Press wrote:
The hash table is 2^18 and I am using 18 bit keys (eg table size in bits and key size are the same). With an 18bit key, as soon as there are 2^9=512 positions in your hash table, there's a greater than 50% chance that two of them have the same key. (Google for "Birthday Paradox".) You do have some way of detecting this, don't you? Storing the whole board structure in the hash table so that you can detect collisions uses a lot of memory and a lot of time to do the comparison; storing a 64bit hash key in the table doesn't use up much memory and the critical "greater than 50% chance of collisions" point is sqrt(2^64) = 2^32 = approximately 4x10^9 positions, which is much bigger than the size of the hash table. Dave.  David Richerby Salted Technicolor Bulb (TM): www.chiark.greenend.org.uk/~davidr/ it's like a light bulb but it's in realistic colour and covered in salt! 
#3




Hash table percentages
"Shaun Press" wrote Details: My program does a standard (I assume) AB search with nullmoving (R=2) and iterative deppening. The hash table is 2^18 and I am using 18 bit keys (eg table size in bits and key size are the same). umh... why don't you use zobrist keys and the % operator? A zobrist key is (usually) a 64bit key which can be incrementally and quickly calculated from most board games. "zobrist_key % number_of_elements" returns an index that will fall within the allocated hashtable. A hash table hit is one where the hash key and the checksum key match, although the returned value could be a bound and not an exact score. yeah, because of the % operator, 2 different positions could map to the same location in the transposition table. This is why you then need to store the whole zobrist key as one of the elements in the hash table and compare the 2 zobrist keys to see if they are the same (the one you used to index the hash table and the one stored in the hash table). I am only getting between 7% and 12% hits from my hash table. This seems low. Is there something wrong with my implementation of either my search or my hashing? 7% seems not bad at all to me! Well, it greatly depends on the board position. Some positions are full of transpositions some others do not have many. Also, a 7% is a lot if they are all exact matches and many of them occur in the first plies (levels), in fact such a 7% would provide HUGE savings in the search. A 7% where all the matches are on the last plies or even worse leaves and maybe they are not even exact scores, well such 7% is not likely to provide any savings. Question: What is a good percentage of hash table hits during a search? 10%, 50%, some other number? 50% is a joke! As I said, 7% seems quite a lot to me, so.... Remeber that a 7% hitrate does not translate to 7% savings! Assuming that the branching factor from your position is 30 and this branching factor does not change during the search, and you are doing a 6 plysearch. 30^6 = 729,000,000 nodes to analyse. now if at the first ply you find an exact match for 15 of the first 30 childs, so, you only have 15 hits, this translates to: 15*30^5 = 364,500,000 So, with a 0.000004% hitrate you get a saving of 50% in the complexity of the search, from 729,000,000 nodes to 364,500,000. Of course the above example is very extreme, something like that is never going to happen, but it should give you the idea. A 7% of hits translate to 7% of savings only if those hits happen on terminal nodes, leaves. Now, considering most of the nodes are leaves, a good percentage of such 7% is likely to be leaves, but not all of them! A couple of them might in the first 2 plies, many others from ply 3 to 5. Have a look at: http://www.seanet.com/~brucemo/topics/zobrist.htm and: http://www.seanet.com/~brucemo/topics/hashing.htm Tommy 
#4




Hash table percentages
"David Richerby" wrote With an 18bit key, as soon as there are 2^9=512 positions in your hash table, there's a greater than 50% chance that two of them have the same key. (Google for "Birthday Paradox".) You do have some way of detecting this, don't you? Storing the whole board structure in the hash table so that you can detect collisions uses a lot of memory and a lot of time to do the comparison; storing a 64bit hash key in the table doesn't use up much memory and the critical "greater than 50% chance of collisions" point is sqrt(2^64) = 2^32 = approximately 4x10^9 positions, which is much bigger than the size of the hash table. Yes, exactly. 2^32 is 4 billion positions, which on most current computers translates to 1 hour of search (assuming 1M nodes/sec) and a transposition table of around 50GBytes in memory!!! So.... it is more than acceptable (at least for now.... probably in 15 years time it will not be!) Using a 18bit key is definately not acceptable, I forgot to mention that in my last post (in which i suggested to use 64bit zobrist keys). I am glad you made that clear. Tommy 
#5




Hash table percentages
"Shaun Press" wrote in message ... Question: What is a good percentage of hash table hits during a search? 10%, 50%, some other number? in diep about 4% of the probes give a cutoff, heavily depending upon position. using 64 bits zobrist would be wise instead of 18+18. Details: My program does a standard (I assume) AB search with nullmoving (R=2) and iterative deppening. The hash table is 2^18 and I am using 18 bit keys (eg table size in bits and key size are the same). The only other quirk is that the first move at root is searched with a window of (prev_score100,prevscore+100) with the usual search fail high, search fail low detections and researches. Subsequent moves get searched with a window of (previous beta, previous beta+1) with a research window of (beta+1, +infinity) for a fail high. A hash table hit is one where the hash key and the checksum key match, although the returned value could be a bound and not an exact score. I am only getting between 7% and 12% hits from my hash table. This seems low. Is there something wrong with my implementation of either my search or my hashing? 
Reply 
Thread Tools  
Display Modes  


Similar Threads  
Thread  Forum  
Which pawn positions go into a pawn hash table?  rec.games.chess.computer (Computer Chess)  
hash table collisions  rec.games.chess.computer (Computer Chess)  
Chessbase engines loses so easy!  rec.games.chess.computer (Computer Chess)  
Large Chess Variants and Type 1 hash table collisions  rec.games.chess.computer (Computer Chess)  
Hash Table and Quiescence Search  rec.games.chess.computer (Computer Chess) 