Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: hash entry replacement schemes

Author: martin fierz

Date: 16:19:43 09/14/02

Go up one level in this thread


On September 14, 2002 at 18:27:13, Miguel A. Ballicora wrote:

>On September 14, 2002 at 15:39:54, martin fierz wrote:
>
>>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.
>>
>>
>>i don't know about most people. crafty does that. i tried it in my checkers
>>program, and it was always worse than using a single table. this is just an
>>observation, not an explanation :-)
>>i remember asking about this and IIRC dieter buerssner replied that he had also
>>toyed with 2 tables and it didnt work for him either.
>
>Do you probe more than once? if you probe twice, it is similar to have two
>tables.

i probe twice. why would that be similar to the two-table approach?
i always thought that the point of having two tables was to make sure that in
the table for the important entries (close to the root) nothing ever gets
overwritten. and in the second table you can use a simple scheme like always
overwrite, and it won't hurt you because there are no important entries there.
i'm always overwriting the less important of the two entries i probe. which can
still be important - although it's rather unlikely, i admit. BTW, my single
table needs 5-10% less nodes than the double table for my test set. and it's
much simpler...

aloha
  martin

>Regards,
>Miguel
>
>
>>
>>aloha
>>  martin
>>
>>
>>
>>>Tony
>>>
>>>PS I advise you to create a structure and create an array of that. Your
>>>implementation of serveral arrays kills the cache.
>>>
>>>>
>>>>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.01 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.