Author: Dann Corbit
Date: 16:23:48 04/05/04
Go up one level in this thread
On April 05, 2004 at 19:03:52, rasjid chan wrote: >On April 05, 2004 at 16:13:15, Gerd Isenberg wrote: > >I may need to think a little more as the replies seem to indicate >more to hashing than I know. > >I hope you can clarify on this so that I may clear any misunderstanding >once and for all :- >"Replacement scheme is a big issue here" >1) Do you mean generally in chess programming,replacement scheme is > a big issue - meaning there are many ways to do hashing and each tries > to find the best way to implement hash tables. ie also there is > no STANDARD WAY TO IMPLEMENT HASH TRANSPOSITION TABLE. >2) Or are you refering to the specific case in my post. > >I use the simplest replacement scheme, whether a node is fresh or higher >/equal depth, maybe some etc... and I have everything in one TT, >full search, qsearch, null-move and they seem to be working ok. In some sense, the issues are generic. In other senses, they are specific. The idea of a hash is to store the computation so you don't have to do it again. But hash tables are finite and CPUs are fast. You will have cases where the same hash code is generated. So what to do now? 1. You can chain it (or otherwise store multiple copies). That means that you might keep both (or multiple) values. But that is just delaying the inevitiable. 2. Replacement time. Suppose that your chain is full for as long as you will allow it [maybe one entry for a single column hash table]. Now you *have* to replace one entry. Will you keep the one that you saved (or all of them) or will you keep the one that is calculated? A simple scheme is to replace always. But is it the best one? Suppose that the one you are replacing is 10 plies deep and has just been accessed multiple times; further that the one you now have is one ply deep. Which to keep? As you can see there are many possible decisions based upon many factors. So you need some kind of replacement scheme in mind. What kind of hash table you make and what sort of replacement scheme that you choose are further complications. Simple idea: Single element hash table, and replace always. Works well enough to start with. Complicated idea: First level hash table is large Second level hash table is log(big_table_size) Third level hash table is log(second_level_size) Fourth level hash table is log(third_level_size) Hash replacement scheme is a function that eats several parameters and decides heuristically which entries are the most important. I imagine that you can see that the simple idea is easiest to implement and debug. The second idea is harder to get right.
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.