Author: Robert Hyatt
Date: 08:36:18 01/17/06
Go up one level in this thread
On January 17, 2006 at 00:38:30, J. Wesley Cleveland wrote: >On January 16, 2006 at 20:20:18, Robert Hyatt wrote: > >>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.... > >I tried an experiment using the same method that crafty uses at the root, >counting the number nodes each move searched and using that to pick the move to >search first. I ran some statistics and got some analomous results. All these >numbers refer to the case where the hash table returned a fail low and the >search then failed high. > > standard ordered by > move order most nodes >failhigh >first move 48% 45% > >average number >of moves searched >until a failhigh 5.8 4.8 > >total number of >nodes searched 1289827142 1362753147 or 5.6% more > >Note that the average number of moves searched is significantly lower, but the >total number of nodes searched is somewhat higher. This suggests to me that >using the number of nodes has value, but not as the first move searched. More >tests need to be done. The reason I do this is based on "history". Say you are destined to "fail high" on a move that is down in the ply-1 move list, at maybe depth=14. What you will see is every iteration, that particular move takes longer and longer with respect to the time for the other ply-1 moves (not counting the first which is generally going to always be the biggest search tree). And each iteration this disparity grows, until "bang" you get a fail high. Unless you run out of time before you start searching that move. The Crafty approach simply moves this "suspicious move" up to near the top of the move list, so that it will be gotten to quickly on the next search, which might be the last iteration we attempt. This way I am certain to search the move, since once Crafty starts a ply-1 move search, it won't abandon it until it has been completed... Whether that is a good idea or not is a guess, but I believe it works better in games than in test sets for sure...
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.