- 《对弈程序基本技术》专题
-
- 主要变例搜索
-
- 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://www.seanet.com/~brucemo/topics/pvs.htm
- 译者：象棋百科全书网 (webmaster@xqbase.com)
- 类型：全译
上一篇 高级搜索方法——期望窗口
下一篇 高级搜索方法——搜索的不稳定性
返 回 象棋百科全书——电脑象棋
