Author: José Carlos
Date: 14:03:14 02/07/06
Go up one level in this thread
On February 06, 2006 at 18:03:12, Dann Corbit wrote: >A hash table is an O(1) data structure. That means that hash table lookups are >proportional to the number 1. Which means that no matter how large the hash >table is, the lookup requires constant time. > >So if I have a trillion has slots in my hash table, a lookup take about the same >time as if I have a total of one hundred hash slots. And if the lookup fails, >then it fails. It does not look at additional entries. > >There are some hash table designs that "chain" a number of entries. Generally, >for chess programs, the chains are one or two additional entities (if chaining >is even implemented). Even so, the largest chain sequence I have ever seen >allowed in a chess program is 8 entries [I would recommend against using 8 >entries]. I have successfully (according to my tests) used 20 slots in my program (not Averno but another one which is not public). It's a very slow searcher and the additional slowness is not much harm compared to the advantages of finding every position (with every bound) that has been searched. However, I must admit it didn't work in Averno. José C. >Now, in such cases, you are far more likely to scan longer chains in >small hash tables than large ones anyway. > >Here is an explanation of hash table: >http://en.wikipedia.org/wiki/Hash_table > >Bear in mind that chess programs do not generally chain more than one or two >entries -- they simply over-write old data with new. So the explanation on that >page is not fully correct for the usage in a chess program. But the >explanations on that page do show the general principles for how they work as >far as computation of the hash, storage into the table, and retrieval of the >stored data.
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.