Author: Vincent Diepeveen
Date: 09:12:39 09/16/02
Go up one level in this thread
On September 15, 2002 at 04:32:48, martin fierz wrote:
>On September 14, 2002 at 20:24:11, scott farrell 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...
>>
>>Martin,
>>
>>I am very interested in your approach to multi-probe.
>>
>>Can you give more more details?
>>
>>How to you calculate the index for the second probe.
>
>index++; :-)
>
>probably some people will say this is bad because of "clustering" - if you want
>to believe them just use something like (index+BIG_NUMBER)%tablesize. i don't
>believe it for a second though.
Yes i remember a few years ago the chaining argument a lot. In fact
chaining *happens* a lot. However the costs of not chaining with 8 probes
is like 7.400 = 2800 processor clocks or so EXTRA for a single lookup.
So the cost far outweighs the problem, especially a lot of probes completely
annihilate the problem.
The ++ construction is by far superior :)
>what is really important is that you have a test set which you let your program
>run on to fixed search depth and get some statistics on how it does compared to
>the old version. this has to be really simple to do, else you don't do it... and
>then you can check everything - what happens when you increase hashtable size?
>what happens when you use N probes? what happens when you change the replacement
>scheme? what happens when you change your move ordering? and so on.
>
>aloha
> martin
>
>
>>Scott
>>
>>>
>>>aloha
>>> martin
>>>
>>>>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.