Author: Severi Salminen
Date: 02:10:40 10/06/00
Go up one level in this thread
>First your example: When 0 is returned , the value is less the A = 900. I'm not >sure about the exact vocabulary but I assume you can say that this particular >move failed low. So actually every fail-high results a fail-low when we return to parent node? If result>=Beta then -result<=-Beta and -Beta=A(of parent node). >0 is a lower bound of the position which arises after e6 has been played, >and that is from black's perspective. Who knows, he might even have captured >a bishop and evaluated the position as +3000 and the returnvalue at the root >would had been -3000 (but that move wasn't searched since we got a beta-cutoff) Yes, this is very clear. >Now, if you back down to the root, the same information can be expressed >from white's point of view: "After e6 I can't get better score than 0. But >this isn't *exactly* what is meant by the "upper bound after fail-low". >Or at least not what I think the passage you referred to originally >was saying. > >OK: one single move at the root fails low (if that is what >one says) and indeed it is an upper bound of the position which occurs >after this particular >move, but now from white's perspective. But this is not the whole story. >What can we say about *this* position (the root) ? This is indeed pretty confusing, as there is no particular case "fail_low" in chess programs. At least we don't do anything if score<=alpha. >So this is my personal terminology: > >All moves tried in a node returns scores >less than (or equal to) alpha. The highest of these values is an upper bound >of the value for this position. I have failed low at this position. > >One move (at least, but I don't search any more after that) returns a score >higher than (or equal to) beta. This gives me a lower bound for the >position. I failed high. > >The following is how I think about alpha and beta. It might help you but make >sure that you form your own understanding of the problem. You might find >a better way of thinking: > >I enter a search node with values of alpha and beta. Alpha is a score that >the side to move is guaranteed to get based on the search in earlier parts of >the tree. He can always find a move that will give him a score of alpha. >Beta expresses the same guarantee that the opponent have. > >If we now find a move that returns a score higher than beta, we know that >the opponent can refuse to enter this position, since it would (from his >perspective) result in a worse score than he already is guaranteed. Likewise, >if all moves searched gives scores less than alpha, the side to move has >no reason to get to this position since it is worse than what he already >has found elsewhere. In both these cases the position can't be in >the principal variation. > >The third alternative is that the score of the best move is between alpha and >beta. This is a potential PV. If this happens all the way back to the root >this will indeed be part of a PV. This was interesting. So I can make use of this to store the PV and search those moves first at the next iteration. So actually we _need_ fail-low situation in storing PV. We store the PV if and only if we can got a<result<b case the whole way from top to root? Can Alpha equal result or should result be bigger? >Btw, when we start a search in the root, alpha = -Infinity >and beta = +Infinity since everything can happen :) Yes. I actually have programmed an alpha-beta engine, so I understand the basics. Just couldn't understand what was MR. Heinz talking about... > >Hopes this helps, Ralf Thanks for this detailed explanation/commentation! It surely crystalized my mind:) Severi
This page took 0.01 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.