Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: hash entry replacement schemes (more)

Author: martin fierz

Date: 17:41:56 09/15/02

Go up one level in this thread


On September 15, 2002 at 10:24:40, Robert Hyatt wrote:

>On September 15, 2002 at 04:27:44, martin fierz wrote:
>
>>On September 14, 2002 at 23:37:59, Robert Hyatt wrote:
>>
>>>On September 14, 2002 at 23:34:58, Robert Hyatt wrote:
>>>
>>>>On September 14, 2002 at 19:19:43, martin fierz wrote:
>>>>
>>>>>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...
>>>
>>>This suggests a bug in your two-table approach.
>>>
>>>They really should be pretty close.  And if you copy the approach I use,
>>>it should be exactly as efficient.  If I replace the entry in the
>>>depth-preferred table, then I move the replaced entry to the always store
>>>table.  If not, I just store it in the always store.  In effect, I have a
>>>set of two entries, plus a third I need to add.  I keep the third plus the
>>>best of the other two.
>>>
>>>I hope that is what you are doing in your two-probe code...
>>
>>i wish i knew :-)
>>i've forgotten what exactly i did in my 2-table code. i think i kept my
>>"important table" relatively empty, and probed "forever" until i found a place
>>to store the entry. "forever" was usually once, but on occasion more.
>>i never quite figured out why this turned out to be less efficient than a single
>>table.
>
>A couple of things stand out.
>
>(1) the "loop".  I don't see how you could average only one probe before
>finding an empty position.  IE when I run for any length of time, my table
>gets well over 99% "saturated".  That is that more than 99 out of a hundred
>positions have something in them.  Your loop should therefore run a _long_
>time to find an empty slot, assuming you did reasonable length searches.
>
>(2) I'm not sure how you could keep your depth-preferred table relatively
>empty.  Typically it is 1/2 the size of the always-store table, but it should
>fill up pretty quickly as well...

you don't know that i clear my hashtable before every search :-)
right, that is probably not a good idea performance-wise. but i feel very
uncomfortable while testing when i know that i can't reproduce results because
different things are in the table... i guess i should add a compile switch for
that and only clear the hashtable on test runs.
since i was clearing the hashtable for both versions, i think my result that the
2-table approach was worse than the single table is still valid - of course, for
my implemenation, which, as you write...

>
>
>> it's well possible that my implementation was bad... the other thing i
>>thought about was that in checkers, you often have a situation where you can
>>reach the same position with variable depth - happens in any endgame with kings.
>>now, i was relying on the depth from root to select the table i was probing in.
>>if a position stored in the "important" table turned up deeper in the search, it
>>might not have been found because it was looked up in the wrong table.
>
>This sounds confusing.  You should _always_ probe both tables.  It is more
>than possible that you hit on the depth-preferred table, but the entry is
>useless.  You then also get a hit on the always-store table and that will
>cause a cutoff.

...may not have been that good. :-)
i think i'm not going to try again any time soon, because i really don't think
there is anything significant to be gained in this whole hashtable business. or
much less so than in other areas.

aloha
  martin


>
>> the whole
>>thing with two tables seemed more complicated than with one, so i threw it out -
>>besides, the difference is probably really small, even with a better
>>implementation.
>
>There you are probably right.  multiple-probe approaches are even better,
>in terms of tree-size.  Unfortunately, they also have a significant cost
>in terms of computation time.  Whether it pays off or not depends on the
>program it seems..
>
>
>>
>>aloha
>>  martin
>>
>>
>>
>>>In Cray Blitz, we probed 16 entries (vector machines are good for that
>>>kind of stuff.)
>>>
>>>
>>>
>>>>>
>>>>>aloha
>>>>>  martin
>>>>>
>>>>
>>>>
>>>>
>>>>The point of the two-table approach is "two entries".  A reasonable
>>>>hash storing algorithm will choose the "better" entry to replace.  The
>>>>depth-preferred/always-store tables do exactly the same thing.
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>>>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 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.