Author: Robert Hyatt
Date: 07:24:40 09/15/02
Go up one level in this thread
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...
> 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.
> 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.