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 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.