Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: hash entry replacement schemes

Author: scott farrell

Date: 10:47:16 09/14/02

Go up one level in this thread


On September 14, 2002 at 13:27:12, Tony Werten wrote:

>On September 14, 2002 at 13:00:09, scott farrell wrote:
>
>>I have been reading plenty on hash replacement schemes.
>>
>>I have read Breuker's thesis, and done some (slow) searching through the CCC
>>archives.
>>
>>I am going over my code and redoing the hashing parts, only to realise I have
>>borken IID (internal iterative deepening).
>>
>>Now I am unsure of what I should be aiming at in relation to hashing code.
>>
>>I am also unsure of exactly what multi-probing the hash tables is. I am guessing
>>there is still only one hashtable, and different equations to go from
>>key/checkkey to the hashtable index, so that there can be several alternative
>>slots that a hash entry for a position could appear at. Is Multi-probe just
>>aiming at reducing collisions - or is the idea to store more than one hash entry
>>for popular positions (say 1 for "depth based", and one for "replace always")?
>>
>>I think I am correct that I need atleast one of the probes as "replace always"
>>to get IID to work. What else do I need to guarantee that I get the best moves
>>from IID backed up to the main search?
>>
>>When people say "replace always" do that mean literaly, just store it all the
>>time? It seems over simplistic - but I tried it, and it works pretty much the
>>same as my code below that tries to keep the deeper entries.
>>
>>Any help apprecated.
>
>What most people do is have 2 tables. In the first you only store if the
>searchdepth >= table depth (and you move the former entry to the second table).
>If not then store in 2nd table.

Thanx for that Tony. I'll give it a go.

>
>Tony
>
>PS I advise you to create a structure and create an array of that. Your
>implementation of serveral arrays kills the cache.

Java is a bit slack at arrays of objects, hence multiple arrays of primitives.

>
>>
>>Here is some of my code
>>
>>//////////////////////////////////////////////////////////////////////////////////////////////////////
>>// SET A TABLE ENTRY
>>//////////////////////////////////////////////////////////////////////////////////////////////////////
>>public final static void store(
>>    int _depth,
>>    int _value,
>>    Move _best,
>>    char _flag,
>>    boolean _estOnly,
>>    short _reqSE,
>>    Board _b,
>>    boolean usingSecondTE_notbeingused,
>>    boolean _dontNullMove)
>>{
>>    int key= 0;
>>    long checkKeyt= 0;
>>
>>    if (_b.sideToMove == Board.BLACK)
>>        {
>>        key= ~_b.key & (size - 1);
>>        checkKeyt= ~_b.checkKey;
>>    } else
>>        {
>>        key= _b.key & (size - 1);
>>        checkKeyt= _b.checkKey;
>>    }
>>
>>    boolean collision=
>>        checkKeyt != checkKey[key] && checkKey[key] != 0 && stale[key] == false;
>>
>>    if (_best != null)
>>        {
>>            s1[key]= (byte) _best.s1;
>>            s2[key]= (byte) _best.s2;
>>        }
>>
>>    }
>>
>>    if (stale[key]
>>        || (_depth > (int) depth[key])
>>        || (_depth == (int) depth[key] && _flag > flag[key]))
>>        {
>>
>>        depth[key]= _depth;
>>        value[key]= _value;
>>        flag[key]= _flag;
>>        SERequired[key]= _reqSE;
>>        stale[key]= false;
>>        checkKey[key]= checkKeyt;
>>        dontNullMove[key]= _dontNullMove;
>>
>>    } // end if replace
>>    else
>>        {
>>        //       store2nd(_depth, _value, _best, _flag, _reqSE, _b,
>>_dontNullMove);
>>    }
>>}



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.