Author: Robert Hyatt
Date: 08:52:04 01/15/06
Go up one level in this thread
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.
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.