Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Alpha-Beta explanation on Heinz's book?

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.