Author: Bas Hamstra
Date: 14:55:26 09/08/02
Go up one level in this thread
One problem is that a link list needs pointers. The pointers itsself eat a lot of memory. I have some experience with this, for use in a chess position database (in fact my book still works this way). It works well but for a performance critical thing like a hashtable I think - performance would be worse than the usual approach. Not in the last place because the actual data would be scattered through RAM, which is not the case with a standard hashtable. - it's not RAM efficient. If your hashrecord is for example 8 bytes, you waste 2 bytes (=25%) at pointer space. Bas. For databases it 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. > >Would the speed hit be enough to hinder the performance of the engine? Or would >it be negligible? > >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. > >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. > >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.