Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Basic questions about alpha beta

Author: Bruce Moreland

Date: 16:52:01 09/28/98

Go up one level in this thread


Rather than address your points I would like to do a general discussion of a few
aspects of alpha-beta, in the hopes that you might have an "aha!" experience.

"Search" is a recursive routine.  Each call to Search is designed to return the
score of the current position, given a particular search depth.

Two values are passed in to Search.  These values are alpha and beta, and they
represent a lower- and an upper-bound on the value of the position.  Alpha is
always less than beta.

To expand a node in the search, you generate all of the legal moves and try them
out one by one.  You recursively call Search and each of the resulting
positions.

If one of these positions scores >= beta, you immedately return beta.  This is
called a fail-high.  A fail-high happens when you find a move that is better
than you will allow.  If you get one, you know that the opponent has some
strategy that will prevent you from achieving the position you are searching,
and that they will want to do this, because the position is great from your
point of view.

If one of these positions scores <= alpha, you completely ignore it.  These are
positions that aren't good from  your point of view.  You have to continue
searching in order to try to find a position that is good for you.  If you don't
find one, you know that your opponent can force you to reach this node or a node
that is equivalent or worse.  Searching through every legal move, and finding no
moves that result in a score that is > alpha is called a fail-low.  This
represents a case where you might have problems.

If a position returns a value that is > alpha and < beta, this is called a PV
(principle variation) node.  It represents a node that is no worse than any node
that will be reached if both sides play optimally.  It represents you best guess
about what might happen in the position.  If you find one of these, you have to
contine searching moves, in case you fail high, but you can no longer fail low.

When you try a move,  you recursively call Search.  In order to take into
account the fact that the goal of the game is different, since the other side is
triyng to find the best move from its point of view, the current alpha and beta
bounds are swapped, and the result of Search is negated.  So you get something
like this:

  val = -Search(-beta, -alpha);

What this also means is that if you fail low in a node, you'll return "alpha",
which gets flipped around and becomes beta from the point of view of the caller
of this instance of Search.  So if you fail low, the instance of Search that
called you will fail high.  Likewise if you fail high, your caller will have to
ignore this move and continue searching.

I explained how this all works, but I didn't explain what it does.  What it does
is eliminate positions, before all legal moves are searched from that position,
if one of the moves searched from that position is found to lead to a situation
that is so good that your opponent can't afford to allow you to reach it.

For instance, say that material is even, and you find one move that keeps
material even.  Let's say you check the next possible move, and you find that if
you make that move, there is a strategy that lets your opponent win a piece.
You don't need to continue seeing what else they can do to you, because losing a
piece is bad enough.  You know that you at least lose a piece, there is no way
to avoid this, so you don't have to worry about whether they can also mate you
from that position.  You know that given your choice, you will always choose the
position that keeps the material level, rather than the one where you lose a
piece at least.  If you think about this, humans do this to an extent when they
play, but it is not a rigidly structured as the way a chess program does it.

bruce





This page took 0.03 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.