Computer Chess Club Archives




Subject: hash entry replacement schemes

Author: scott farrell

Date: 10:00:09 09/14/02

I have been reading plenty on hash replacement schemes.

I have read Breuker's thesis, and done some (slow) searching through the CCC

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.

Here is some of my code

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
        //       store2nd(_depth, _value, _best, _flag, _reqSE, _b,

This page took 0.03 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.