Author: Harald Lüßen
Date: 14:49:10 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. 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.
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.