Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Fixed

Author: Robert Hyatt

Date: 09:34:27 02/21/02

Go up one level in this thread


On February 20, 2002 at 23:11:08, Angrim wrote:

>On February 20, 2002 at 19:28:42, Vincent Diepeveen wrote:
>
>>On February 20, 2002 at 16:10:01, Frank Phillips wrote:
>>
>>>On February 20, 2002 at 12:48:06, Steve Maughan wrote:
>>>
>>>>Thanks for the help everyone!
>>>>
>>>>I've implemented the idea I outlined and this has fixed the problem.  However
>>>>effectively I ignore possition where I cannot add a hash entry without
>>>>overwriting another.  This means that there is currently the possibility of a
>>>>draw not being detected.  I'll probably test a rehashing mechanism.
>>>>
>>>>Regards,
>>>>
>>>>Steve
>>>
>>>Just stick the entry in the next available slot (that has a hash signature of
>>>zero).  The debug tests I did never showed more than a few re-hashes - once it
>>>was working properly.
>>>
>>>I changed to this method from a simple array list following Bruce's description,
>>>because it seemed so elegant with the possibility of speeding up detection in
>>>the endgame - when the list approach might have many entries to check.
>>>
>>>After falling for the obvious trap of not always removing an entry when exiting
>>>ABsearch() early, it seems to work fine.
>>>
>>>I noticed no significant speed loss (or speed up) in the short middle game test
>>>I use.
>>>
>>>Frank
>>
>>You measured pretty bad then depending upon hashtable size. An array
>>that gets read within 1 cache line and is already within L1 or L2
>>is kicking the hell out of this hashtable approach.
>
>Depends on the exact design. If the hash table is small enough then
>it will tend to be in L2 most of the time.  A 400 entry hash table
>is quite large enough to handle triple rep detection.
>Also, how are you fitting your array into a single cache line
>when you are searching 10+ ply deep?  It seems to me that
>you have to be storing at least 10, 8 byte hash entries in
>that array by the time you reach a leaf node.
>
>Angrim


The hash table trick does work well...  and it is particularly favorable when
you are in positions where you play a lot of moves with no pawn pushes or
captures so that the repetition list becomes lengthy.  The repetition detection
code is O(N) complexity, while the hash table detection is O(1).  If N is very
small, as it is in many positions, then the two are pretty equal in performance,
the O(1) of hashing is offset by 4 consecutive repetition signatures in a single
cache line.  But if N is large, then hashing is clearly faster.

I used this for a while and found that it worked just fine.  There is a cost,
in that when you enter a node, you have to store the hash signature, and when
you exit a node you have to remove or inactivate it.  So a little more work
on the back-side to clean it up as you back out of the search, less work on
the front as you don't have to search a long list for a match.  But for SMP
searching, I went back to the repetition list as each thread needs its own
unique repetition facility and copying a reasonable sized repetition table
is more expensive than just copying the appropriate part of the repetition
list.

If it weren't for the parallel search, I would probably have stuck with the
hashing approach.  I believe Bruce used that at one point in time in Ferret.
I don't know whether he still does or not, however...

It isn't unreasonable.  It isn't really significant in a chess engine at all,
it is "just another way" to accomplish a common task...



This page took 0.04 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.