|
|
An enhancement to alpha-betaPrincipal Variation Search (PVS) is a means of getting a small performance improvement out of the alpha-beta algorithm. Any node in an alpha-beta search belongs to one of three types:
Sometimes you can figure out what kind of node you are dealing with early on. If the first move you search fails high (returns a score greater than or equal to beta), you've clearly got a beta node. If the first move fails low (returns a score less than or equal to alpha), assuming that your move ordering is pretty good, you probably have an alpha node. If the first move returns a score between alpha and beta, you probably have a PV node. Of course, you could be wrong in two of the cases. Once you fail high, you return beta, so you can't make a mistake about that, but if the first move fails low or is a PV move, it's still possible that a later move will come back with a higher value. Principal Variation Search makes the assumption that if you find a PV move when you are searching a node, you have a PV node. It assumes that your move ordering will be good enough that you won't find a better PV move, or a fail-high move (which would cause this to become a beta node), amongst the other moves. Once you've found a move with a score that is between alpha and beta, the rest of the moves are searched with the goal of proving that they are all bad. It's possible to do this a bit faster than a search that worries that one of the remaining moves might be good. If the algorithm finds out that it was wrong, and that one of the subsequent moves was better than the first PV move, it has to search again, in the normal alpha-beta manner. This happens sometimes, and it's a waste of time, but generally not often enough to counteract the savings gained from doing the "bad move proof" search referred to earlier. Here is the algorithm, overlaid on alpha-beta, with changes highlighted: int AlphaBeta(int depth, int alpha, int beta) { BOOL fFoundPv = FALSE;
if (depth == 0) return Evaluate(); GenerateLegalMoves(); while (MovesLeft()) { MakeNextMove();
if (fFoundPv) { if ((val > alpha) && (val < beta)) // Check for failure. val = -AlphaBeta(depth - 1, -beta, -alpha); } else val = -AlphaBeta(depth - 1, -beta, -alpha); UnmakeMove(); if (val >= beta) return beta; if (val > alpha) { alpha = val; fFoundPv = TRUE; } } return alpha; } The algorithm is all about the highlighted if-block in the middle of the function. If no PV move has been found, "AlphaBeta()" is recursed normally. If one has been found, everything changes. Rather than searching with a normal (alpha, beta) window, we search with (alpha, alpha + 1). The premise is that all of the searches are going to come back with a score less than or equal to alpha, and if this is going to happen, the elimination of the top end of the window results in more cutoffs. Of course, if the premise is wrong, the score comes back at alpha + 1 or higher, and the search must be re-done with the wider window. The performance improvement for PVS has been claimed to be 10%. I haven't tried to figure out exactly how much improvement I get if I use PVS in my program, but I do get some improvement, so I use it. Search instability issuesIf you search with an (alpha, alpha + 1) window, and the score comes back above the window (but doesn't exceed beta), you have to re-search. You'd think the re-search must come back with a score between alpha and beta, but this is not necessarily so. It might not be so because of search instability, which is something that I will discuss at various points. The routine as written above defends against this situation, and handles it properly if it happens. If you are going to write this routine and change things around, be very careful that you don't assume that your search will always be stable. You have to not crash and burn if you get a value back that you supposedly just proved you can't get. |
Send mail to
brucemo@seanet.com with
questions or comments about this web site.
|