Author: martin fierz
Date: 01:27:44 09/15/02
Go up one level in this thread
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. 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. 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.
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.