Author: Robert Hyatt
Date: 17:20:18 01/16/06
Go up one level in this thread
On January 16, 2006 at 17:49:10, Harald Lüßen 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. > >I did some 'homework'. I found that in my engine I used the hash move >always. Now I tested to restrict it as you recommended. > >// ... There was no hash entry or not deep enough or no cutoff ... >// We really have to search moves in this position. >// The move order can be improved with the hashed move when it was >// exact (it simply seems to be the best move) >// or a fail high (it seems to be the best of the first tested moves >// and we will problably sort the moves to the same order here). >// In case of fail low moves all moves were tested, had beta cut scores >// on the next ply and their values are not really comparable. >// The 'best' is random. >// Probably it should not be stored in the hash table then, >// but I fear problems with my PV. >// ... and then I take an existing hash move in the first two cases ... > >There was no overall improvement. I have no statistics but I had >just a quick look and a fast tournament. > >Is the logic correct for fail soft programs? I do not return beta >when score >= beta but I return score. And I try to keep any score >as long as possible uninfluenced from alpha and beta. The scores >from beta cuts are certainly not exact because later moves may have >a better score but they are not _that_ bad and they may give hints >when they are used one ply above and fail low. Doesn't matter and here's why. Even with fail-soft, where you can return values >beta and <alpha, the problem is that this is still a "refutation" search. And the move that produces the score >beta that you return is not necessarily the "best move". Because all you need is any move that produces a score >= beta to get a beta cutoff. So no matter what happens, moves at a ply that produces a score <= alpha are never going to be accurately ordered. Or at least not accurately enough to trust as +the+ first move you search at such a ply....
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.