Author: Robert Hyatt
Date: 13:05:18 12/20/03
Go up one level in this thread
On December 20, 2003 at 00:41:52, Uri Blass wrote:
>On December 19, 2003 at 23:36:48, Robert Hyatt wrote:
>
>>On December 19, 2003 at 18:12:09, Uri Blass wrote:
>>
>>>I try to understand hash.c of Crafty so I see that HashProbe is called mainly
>>>from search.c and
>>>I see that it has
>>>case EXACT:
>>>if (alpha<beta) savePV(tree,ply,alpha,1);
>>>return alpha;
>>>
>>>some questions
>>>1)what is the job of the third parameter in savePV
>>
>>Do you mean the third or fourth? third = alpha, which is the best
>>score so far at this ply. fourth is a flag that says "this PV was
>>truncated by a hash table hit." That is how I produce PVs that
>>look like this: e4 e5 Nf3 <HT>
>>
>>
>>
>>
>>>
>>>the definition in chess.h is
>>>
>>>#define SavePV(tree,ply,value,ph) do { \
>>> tree->pv[ply-1].path[ply-1]=tree->current_move[ply-1]; \
>>> tree->pv[ply-1].pathl=ply-1; \
>>> tree->pv[ply-1].pathh=ph; \
>>> tree->pv[ply-1].pathd=iteration_depth;} while(0)
>>>
>>>value is not used in savePV.
>>
>>Correct. I am not sure why it is there in fact, and I will remove it.
>>It was probably used years ago as the way of backing up the PV and value
>>to the previous ply, but it was changed for some reason.
>>
>>
>>
>>>
>>>2)In the comments to search.c I see
>>>
>>>"1. HashProbe() returned "EXACT" if this score is greater than beta, return
>>>beta."
>>>
>>>The problem is that later I see only return alpha in search.c
>>>
>>>case EXACT:
>>> if(alpha < beta) SavePV(tree,ply,alpha,1);
>>> return(alpha);
>>>
>>>I understand that HashProbe already changes alpha but the question is if it
>>>changes it to be beta in case that the score is greater than beta.
>>
>>No. this is an _exact_ score, so I just return it, whatever it is. You
>>could limit it to be not greater than beta, but at one time I used a full
>>fail-soft implementation and this is necessary for fail-soft.
>>
>>>
>>>I guess that the answer is dependent on a part of hash.c that I need to
>>>understand and I am talking about calculating type and val in the following part
>>>of hashprobe and the question is if val can get value that is bigger than beta
>>>when type get EXACT.
>>>
>>>htable=trans_ref+((int) temp_hashkey&hash_mask);
>>> word1=htable->prefer.word1;
>>> word2=word1^htable->prefer.word2;
>>> if (word2 == temp_hashkey) do {
>>>#if !defined(FAST)
>>> local_hits++;
>>>#endif
>>> word1l=word1>>32;
>>> word1r=word1;
>>> val=(word1r & 0377777)-65536;
>>> draft=word1r>>17;
>>> tree->hash_move[ply]=word1l & 07777777;
>>> *threat=(word1l>>26) & 01;
>>> type=(word1l>>27) & 03;
>>> if ((type & UPPER) &&
>>> depth-null_depth <= draft &&
>>> val < *beta) avoid_null=AVOID_NULL_MOVE;
>>> if (depth > draft) break;
>>> if (abs(val) > MATE-300) {
>>> if (val > 0) val-=(ply-1);
>>> else val+=(ply-1);
>>> }
>>>
>>>
>>
>>>Uri
>>
>>
>>The types are pretty obvious.
>>
>>0=worthless
>>1=lower
>>2=upper
>>3=exact
>>
>>If you want to ask about specific parts of the above, feel free and I
>>can give details...
>
>I understand now the code better after looking at it again
>but I still have some questions.
>
>1)I see that the key is not stored directly in htable->prefer.word2 but you need
>to do xor of it with htable->prefer.word1 that include information evaluation
>and move.
>
>Is there a special reason not to have the key directly in the 64 bits?
Yes. It has to do with parallel programming. If you are an ICCA member,
look at the article "A lockless transposition table" (not exact title)
written by myself and Tim Mann. If you are not going to do a parallel
search, the xor is not needed.
>
>2)I understand that you have
>
>typedef struct {
> TABLE_ENTRY prefer;
> TABLE_ENTRY always[2];
>} HASH_ENTRY;
>
>What is the reason to have 2 table entries in always when I see that in the code
>you use only one that is htable->always[hwhich] and what is the meaning of
>hwhich?
If you remember the "Belle" algorithm, it uses one table "depth preferred"
and another table 2x bigger "always store". I combined these into one
"block" of memory so that they often fit into the same cache line, which
improves performance _very_ slightly. "prefer" is the one entry that
corresponds to the old "depth-preferred" table. "always" is two entries
and corresponds to the two entries in the "always store" table. The "hwhich"
variable is simply the next consecutive bit in the hash signature, above the
N bits use to select this entry, which chooses which of the two "always" entries
to use. This _exactly_ matches the belle 2-table idea, but is more cache-
friendly.
>
>Uri
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.