Author: Robert Hyatt
Date: 19:36:26 09/07/02
Go up one level in this thread
On September 07, 2002 at 20:37:57, Russell Reagan wrote: >In his book, The Practice of Programming, Brian Kernighan gives his >implementation of a hash table which differs from the hash tables we use in >chess engines for the transposition table. His approach is to keep a table of >linked lists, so that if two things hash to the same value, no data is lost, but >added to the end of that entry's linked list. I am curious about how this would >work in a chess engine. It won't work for several reasons... 1. You generally search more positions than you store. 2. lists lead to a problem known as "chaining". And the lists grow in length and cause more chaining... and running a chain takes time. 3. Hash signatures are not really uniformly distributed over the hash table address space. This causes further "chaining" to happen. (chaining is a well-known problem. Since you add entries to a list as the hash table addresses "collide" the chain grows. And as it grows, the probability of another positoin hashing into this "chain" grows, and as it happens, the chain grows...) > >Would the speed hit be enough to hinder the performance of the engine? Or would >it be negligible? Suppose the list grows to 50,000 entries? How would that impact your search speed? :) > >Obviously when using this method, nothing ever gets overwritten, which means >that every node that you visit gets saved in the table, so eventually you run >out of memory (probably very quickly on a lot of machines). So there must be >some method of limiting the size of the table. The idea you are talking of assumes that the table is "large enough". If it isn't, a replacement policy is needed, just as it is in what we are doing today. > >What kind of method could be used to limit the size of the table using the >Kernighan approach? > >Lastly, I would like to know where in the tree the search benefits the most from >the transposition table. For example, if the search benefits the most in the >shallow nodes, then it might be possible to limit the size of the table by using >a depth parameter. Then you would limit the size of the table, since you could >cut out the deeper levels of nodes, and (since the deeper levels contain the >most nodes) cut down the size needed for the table, and solve the problem of the >constantly growing table. The deeper the depth stored in the table, the more work you save when you get a hit... So depth-preferred is one important consideration. > >Any thoughts on using this alternative form of a hash table in a chess program? >I find it to be an interesting data structure as he describes it, mainly because >I have only known a hash table to be what we use it for in chess, which has the >drawback of being theoretically unstable. > >Thanks, >Russell
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.