Author: Stuart Cracraft
Date: 10:06:17 01/16/06
Go up one level in this thread
On January 15, 2006 at 11:52:04, Robert Hyatt wrote:
>On January 14, 2006 at 04:50:05, Harald Lüßen wrote:
>
>>On January 14, 2006 at 00:15:25, Robert Hyatt wrote:
>>
>>>On January 13, 2006 at 18:38:35, Branislav Bezak wrote:
>>>
>>>>
>>>>I struggle to prevent my opponent to draw by repetition when I’m using best move
>>>>stored in entry in transposition table.
>>>>
>>>>At the beginning of AB function, I check the table, find a nice fat score and
>>>>make the best move stored. My opponent makes his move and it's a draw by
>>>>repetition. So, I added a code to check all opponent’s possible responses to my
>>>>stored best move to see if they are not draw. In that case, I don't use the best
>>>>move from hash table but force the full search to pick some other move that will
>>>>not allow the opponent to draw. But there are cases where I still cannot prevent
>>>>the draw because it is already too late and no matter what I do, my opponent’s
>>>>next move is a draw.
>>>>
>>>>What's the best way how to deal with this situation?
>>>>
>>>>Thanks
>>>
>>>
>>>I don't understand the question. You just use the "best move" as the first move
>>>to search, but you _still_ search it. And you should pick up the repetition at
>>>the next ply easily enough... You don't just take the best move and say "i'll
>>>play that and not search any deeper"...
>>
>>I believe I do this right in my engine but I may have introduced
>>a new similar bug in the last few weeks. Consider this situation:
>>
>>alpha = -20, beta = 20, depth = 10, Hash: value = 100, depth = 12, move = ...
>>
>>May I return from this position because hash value > beta?
>>The hash move and the opponent's response may lead to an immediate
>>repetition draw. I play this line hopefully winning a pawn and game over.
>>Do I have to forbid hash value cutoffs?
>>Do I have to restrict hash value cutoffs to deeper plies?
>>Do I have to restrict hash value cutoffs to beta < value < 0?
>>Do I have to check my move and its pv through the hash table and look for
>>repetition draws (as Branislav does)?
>>Does this depend on the recognized number of repetitions (2nd or 3rd)
>>in the search?
>>Do I have to store a repetition flag in the hash entry? When?
>>How does that help in this situation? There could be another path to
>>the current position, or not? How to react to such a flag?
>>
>>Harald
>
>
>Here is the easy, non-mind-numbing way of thinking about this:
>
>When you do a search, you can only get three possible results. (1) EXACT
>(score>alpha and score<beta); (2) LOWER (score>=beta or fail-high); (3) UPPER
>(score<=alpha or fail-low).
>
>When you get a signature match in the hash probe code, your goal is to re-use
>the above results and search no further at all. The usual test is "if draft >=
>depth" (is the depth of the stored search at least as deep as the search depth
>we have remaining when we do the probe?). If the depth is sufficient, we are
>not going to search any further. You simply repeat the result you did for the
>previous search, assuming that the value in the table is useful.
>
>If the table entry is EXACT, you just return the score and you are done.
>
>If the table entry is LOWER, meaning the score we have is a lower bound but the
>true score could be higher, then we simply test the stored bound against the
>current beta value. If the stored lower bound is >= beta, then we can once
>again say "this is a fail-high" and search no more.
>
>If the table entry is UPPER, meaning the score we have is an upper bound but the
>true score could be lower still, we compare this stored bound against alpha, and
>if the stored value is <= alpha, then we fail low here with no further
>searching.
>
>Note that if either of the two bounds tests above fails, we are going to have to
>search. If the draft test fails, we are going to have to search. Now we can
>check to see if this is a LOWER or EXACT entry, and if so, search the "best move
>from the table" first. Otherwise (UPPER positoin) we just resort to our normal
>move ordering.
>
>This isn't complicated when you sit down and study what you are trying to
>accomplish, namely avoiding searching the same subtree more than once, and that
>the only results you can get from the search is one of the three given above.
Bob - in light of the above, does this code look approximately right?
(This is my hash table probe from my main pvs search() routine.)
I get about 30%-35% for hash table matches / hash table probes and
about 96% for pawn hash table matches / pawn hash table probes.
--Stuart
search(alpha,beta,depth,etc.)
#ifdef TT
// Probe hash table. If seen before with equal or greater draft, return.
// Otherwise, set alpha and beta bounds if available.
// Last, if alpha exceeds or equals beta, return.
// sdepth is the unmodified depth passed to search()
if (retrieve(&length, &score, &flag, &hashmv, &threat)) {
if (MATESCORE(score))
if (score > 0) score+=ply; else score-=ply;
// if (flag == UBOUND && depth-R <= length && score < beta) donull = 0;
if (length >= sdepth) {
if (flag == VALID) {
savemove(&npv[ply][ply],hashmv);
for (j=ply+1;j<npvl[ply+1];++j) savemove(&npv[ply][j],npv[ply+1][j]);
npvl[ply]=npvl[ply+1];
return(score);
}
if (flag == LBOUND) alpha = MAX(alpha, score);
if (flag == UBOUND) beta = MIN(beta, score);
if (alpha >= beta) return(score);
if (legalmove2(bd,hashmv)) hashed = 1;
}
}
#endif
:
:
rest of search
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.