Author: Robert Hyatt
Date: 17:33:35 01/16/06
Go up one level in this thread
On January 16, 2006 at 13:06:17, Stuart Cracraft wrote:
>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;
I don't do any of those. I just return a value back to search that says "the
table value says fail high here", "the table value says fail low here", "the
table value is EXACT here", or "the table value is useless here". I then do the
usual test against the bound to see if the table value will cause a cutoff or
whatever...
> }
> }
>#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.