Author: Roberto Waldteufel
Date: 18:10:49 09/28/98
Go up one level in this thread
On September 28, 1998 at 19:52:01, Bruce Moreland wrote: >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 When you fail high, you can return the value of the fail-high move, which might be even greater than beta, and, if you use "fail-soft" alpha beta, you can also return the value of the fail-low move, which might be even less than beta. By returning slightly tighter bounds, you allow for possible extra beta cut-offs later in the search. It is not important for traditional alpha-beta, where you call search on the root position with alpha=-infinity and beta=+infinity, but it can improve efficiency if you use a narrow aspiration window, or even more so if you do a lot of null width searches as in PVS or MTDF for example. Best wishes, Roberto
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.