Author: Robert Hyatt
Date: 20:37:59 09/14/02
Go up one level in this thread
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...
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.