Author: scott farrell
Date: 17:24:11 09/14/02
Go up one level in this thread
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.
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.