Author: Gerd Isenberg
Date: 00:07:31 04/06/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. Yes, i mean chess programming. Other applications may have similar issues of course. > ie also there is > no STANDARD WAY TO IMPLEMENT HASH TRANSPOSITION TABLE. With replacement, there are several standards schemes, like replace allways, depth prefered, expense (number of saved nodes) prefered, multiple slots per hashkey and to replace the slot with the lowest "worth". I use a two table approach, a big one with eight consecutive slots, shared by several hashkeys and replace the lowest "valuable" entry - and a smaller, faster one (a few K-entries only) with replace allways scheme. The huge one is restricted to full search, where the smaller is used everywhere. With multiple slots per hashkey one may reserve one slot as an always replacement slot and n-1 slots as prefered "value" replace slots. So there are a lot of ways to implement and combine hashing schemes in chess, specially how to consider the "worth" of an entry. One may count and store the number of hits per entry and prefere entries with frequent hits over entries with seldom hits... You may put "refutation" information inside the hash table. Each time a root move is done, you may have a PV (first or best move) or a refutation line, backed up in a triangular matrix. One may traverse (making moves) this line at the root and tag the traversed nodes as a kind of "PV" move (the most left path under one root leaf). Such entries are probably more worth than others and require a considerable higher depth to get overwritten. Of course with same depth one should prefere exact score over lower and higher bound values. And lower bounds values are probably more valuable than upper bounds without any best move... >2) Or are you refering to the specific case in my post. What specific case? > >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. Fine, you may try a lot and play around with several replacement schemes to look what is favorite for your program. And yes, hashing is a complicated affair, minor changes may have huge influence on the search... Cheers, Gerd > >Best Regards >Rasjid > > > <snip>
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.