Author: Ralf Elvsén
Date: 17:15:59 10/05/00
Go up one level in this thread
On October 05, 2000 at 15:48:01, Severi Salminen wrote: > >I understant the fail-high case. But maybe I don't know what is a fail-low: > >Could you check the next example, did I understand? > >In this exaple we make a 2 ply search and assume that black is in totally lost >position. In root node we have two moves for white: exf6 and e6. Let's say that >exf6 is the first move searched and after searching it we have A=900 (we >captured a queen) and B=Inf. Then we search e6. After making that move we have >A=-Inf and b=-900. Probably at first black responce we get a fail-high. So we >return a 0 (material is even). And at root node we have a fail-low situation, >right (A=900 and the score returned was 0)? So, this 0 should be an upper bound >for e6 situation. Did I understand?? > >Severi "I was so clear" Salminen I think the confusion originated from what alpha and beta are bounds for. Bounds for the position at the root or at the node in the search tree? Or maybe you understood/understand it ? :) 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. 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). 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) ? I *personally* say that I fail low in a position (as opposed to a single move) when *all* moves tried there returns a score <= alpha. Say alpha is -200 and the best value was -300. In that case you know that -300 is an upper bound on the score of this position from the-side-to-moves perspective. Remember that since alpha was -200 when we entered this node, beta had a value of +200 in all positions seached after making moves. In all these subpositions we must have had fail-highs (scores higher then 200 since they were transformed to scores lower than -200 with a minus sign when they were returned). Since they were lower bounds then , they are now upper bounds after applying the minus sign. So we know that we can't get a score better than the value of the highest upper bound (which was -300) and thus -300 is an upper bound for the whole position. 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. Btw, when we start a search in the root, alpha = -Infinity and beta = +Infinity since everything can happen :) I apologize to all experts if I have misused any terms. This way of thinking works for me, at least as far as I know. Hopes this helps, Ralf
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.