主要变例搜索
发布时间：2008-11-20
点击：
来源：本站原创
录入者：Bruce Moreland
对Alpha-Beta的改进
主要变例搜索(PVS, Principal Variation Search)是提高“Alpha-Beta”算法效率的一种方法。
在Alpha-Beta搜索中，任何结点都属于以下三种类型：
1. Alpha结点。每个搜索都会得到一个小于或等于Alpha的值，这就意味着这里没有一个着法是好的，可能是因为这个局面对于要走的一方太坏了。
2. Beta结点。至少一个着法会返回大于或等于Beta的值。
3. 主要变例(PV)结点。有一个或多个着法会返回大于或等于Alpha的值(即PV着法)，但是没有着法会返回大于或等于Beta的值。
有些时候你可以很早地判断出你要处理的是哪类结点。如果你搜索的第一个着法高出边界(返回一个大于或等于Beta的值)，那么很明显你得到Beta结点。如果低出边界(返回一个小于或等于Alpha的值)，假设你的着法顺序非常好，那么你有可能得到Alpha结点。如果返回值在Alpha和Beta之间，你可能得到PV结点。
当然，有两种情况你可能会判断错误。当你高出边界时，你返回Beta，因此你不会犯错误，但是如果第一个着法低出边界或者是PV着法时，仍然有可能在下一个着法得到更高的值。
主要变例搜索作了假设，如果你在搜索一个结点时找到一个PV着法，那么你就得到PV结点。也就是说假设你的着法排序已经足够好了，使得你不必在其余的着法中找更好的PV着法或者高出边界的着法(这就会使结点变成Beta结点)。
你找到一个着法其值在Alpha和Beta之间，那么对其余的着法，搜索的目标就是证明他们都是坏的。跟要搜索出更好的着法相比，这种搜索也许要快一些。
如果这个算法发现判断是错的，即其中一个后续着法比第一个PV着法好，那么它会被再一次搜索，这次使用正常的Alpha-Beta搜索方法。这种情况有时会发生，这样就浪费时间了，但是这些时间通常不会超过面所说的“证明是坏着法”所节约下来的时间。
算法如下，是从Alpha-Beta算法改过来的，改过的地方用醒目的字标出：
int AlphaBeta(int depth, int alpha, int beta) {
BOOL fFoundPv = FALSE;
if (depth == 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
if (fFoundPv) {
val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);
if ((val > alpha) && (val < beta)) { // 检查失败
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;
}
算法的核心部分就是函数中间醒目的“if”块中的内容。如果没有找到PV结点，“AlphaBeta()”函数就正常调用，如果找到了一个，那么情况就变了。不是用常规的窗口(Alpha, Beta)，而是用(Alpha, Alpha + 1)来搜索。这样做的前提是，搜索必须返回小于或等于Alpha的值，如果确实这样，那么把窗口的上面部分去掉就会导致更多的截断。当然，如果前提是错的，返回值是Alpha + 1或更高，那么搜索必须用宽的窗口重做。
据报道PVS可以提高10%的效率。我没有试图检测PVS用在我的程序里到底提高了多少，但是确实提高了，所以我用了这个算法。
搜索不稳定性的问题
如果你用(Alpha, Alpha + 1)这个窗口去做搜索，返回值超过了窗口(但是没有超过Beta)，你就必须重新搜索。你认为重新搜索的值必定在Alpha和Beta之间，但是恐怕不一定是。这很有可能是由“搜索的不稳定性”引起的，我会在别的章节中讨论这个问题。
上面写的那个程序对这个情况作了防御，并对这种情况的发生作了正确的处理。如果你要使用这个程序并且作一些改动，就要特别当心你的搜索是否总是稳定的。如果你得到不期望得到的返回值，就必须采取措施避免让程序陷入故障。
原文：http://{域名已经过期}/~brucemo/topics/pvs.htm
译者：黄晨 (webmaster@{域名已经过期})
类型：全译
 关闭窗口  打印文档 |
账号登录