Author: Robert Hyatt
Date: 21:06:00 08/14/01
Go up one level in this thread
On August 14, 2001 at 21:51:49, Dieter Buerssner wrote: >On August 14, 2001 at 00:37:15, Robert Hyatt wrote: > >>On August 13, 2001 at 14:07:43, Dieter Buerssner wrote: >> >>>On August 13, 2001 at 00:01:35, Robert Hyatt wrote: >>> >>>>On August 12, 2001 at 23:49:35, Pham Minh Tri wrote: >>>> >>>>>How about the UPPER? Should we choose the move has score nearest alpha (the >>>>>highest score or the first of highest ones)? Perhaps store something is better >>>>>than nothing. >>>>> >>>> >>>>Nope. Something is not better than nothing here. In a LOWER position, every >>>>move was refuted by the next ply. > >Much snipped, but I will come back to this later. > >>Note that I use fail-soft as well. > >Then, I must totally misread your source. You don't keep track of the best >score, when it is lower alpha. You allways return alpha, in the case of an upper >bound node. This will move earlier be beta. So, this looks essentially as fail >hard to me. > If a call to search returns a value < alpha, I return that value to the previous ply, not the original alpha. But if you search each move at a ply, and you get a score <= alpha for each, you can _not_ reasonably expect those scores to reflect anything about which move is better. It just doesn't work like that. At the next ply you fail high as soon as you find a score >= beta. Not necessarily on the _best_ move, just on _any_ move that will produce a score >= beta. And since you don't search all moves to find the largest fail-high, how can you use tht result at the previous ply to find the worst move? Answer is, you can't, reliably. >> But the bounds you get back, while they >>can be below alpha, are _still_ useless to choose which of the moves is the >>best one. They _might_ give you a better idea of what to do about changing >>the lower bound on the re-search, but not to choose the best of the worst... > >I am very well aware of the fact, that the scores you get back outside of the >window, are not trustable at all. Still, I have mentioned the case, of all >scores beeing losing mate scores, but one is not. This move will be good to try >first. I have seen this, by investigating multi MB large tree dumps, so it is >not only there in theory. Often, even with fail soft, I of course will also get >multiple moves with the same score (alpha). But then one can see the "best" move >as an additional killer move. It was most probably the killer move anyway, when >this position was visited the last time. I cannot see a reason, why trying such >a move early could hurt. And I do see reductions of tree sizes. I don't try >upper-bound moves first. I try them (more or less) after the good captures, and >together with the killer moves, but before history moves. > Even if all are losing mate scores but one, that only means that one move was refuted by a move that didn't lead to mate. It doesn't mean that _other_ moves won't lead to a mate for that move as well. Move ordering is critical. Using such moves for ordering is worse than taking a random move. And the winning-captures and killer moves are _far_ better than a random move, as this is easy to prove. > >>The terminology is a bit unclear, but I am using the words UPPER and LOWER the >>same way most others do. >> >>A position marked "UPPER" means that all moves failed low, and the bound we >>store is the _upper_ bound for that position, because we know all scores are >><= that bound. We don't know how bad the score is however. Nor do we know >>which move was best as all are simply known to be <= some value. >> >>A position marked "LOWER" means that the move played there failed high, but >>all we know is that the score is >= some value. IE "some value" is the >>lower bound for this position but the real score could be much higher. Hence >>the name "lower". And here we _do_ have a best move, the one that failed >>high. >> >>It seems backward, but LOWER means a fail high node, while UPPER means a >>fail low node. If you use that terminology everybody will understand what >>you are saying. If you use the obvious terminology, you will be using the >>opposite of everybody else and that will cause some interesting miscues. :) > >I believe, I am using the terminology, you are describing here. But to me it >seems, that in the sentance I cited at the start of my post, you don't use this >terminology. Sure, sometimes I may have a big problem in reading comprehension. >But I tried, to rearead again and again. What you named "LOWER" above, seems to >be upper to me. In an upper bound position, every move gets refuted at the next >ply. In an lower bound position, you find a move, that cannot get refuted at >all. > >Regards, >Dieter I'm not quite sure our definitions match or don't, after reading the above. LOWER means that at the current ply, a move failed high with a score >= X, where we call X the "lower bound on the score for this position" even though it is actually beta in the current search context. Because we just proved that the score is >= X, but we have no idea how much better it will be than X if we search all moves. So even though X is beta in the current instantiation of search, it is a LOWER bound on the score for the position. The inverse is true for fail lows, which then produce an UPPER hash entry because we know that the scores are all <= X, so X is an UPPER bound on the score. We have no idea how low the scores will be, as we only proved that each move produces a score <= X... (alpha).
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.