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.