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.