`

alpha-beta算法的诸多变种

阅读更多
原文:http://www.elephantbase.net/computer/advanced_intro2.htm
Alpha-Beta搜索的诸多变种 
David Eppstein */文
* 加州爱尔文大学(UC Irvine)信息与计算机科学系

 
  尽管我们已经讨论过Alpha-Beta搜索简单有效,还是有很多方法试图更有效地对博弈树进行搜索。它们中的大部分思想就是,如果认为介于Alpha和Beta间的评价是感兴趣的,而其他评价都是不感兴趣的,那么对不感兴趣的评价作截断会让Alpha-Beta更有效。如果我们把Alpha和Beta的间距缩小,那么感兴趣的评价会更少,截断会更多。
  首先让我们回顾一下原始的Alpha-Beta搜索,忽略散列表和“用当前层数调整胜利值”的细节。
 
// 基本的Alpha-Beta搜索
int alphabeta(int depth, int alpha, int beta) {
 move bestmove;
 if (棋局结束 || depth <= 0) {
  return eval();
 }
 for (每个合理着法 m) {
  执行着法 m;
  score = -alphabeta(depth - 1, -beta, -alpha);
  if (score >= alpha) {
   alpha = score;
   bestmove = m;
  }
  撤消着法 m;
  if (alpha >= beta) {
   break;
  }
 }
 return alpha;
}
 
超出边界(Fail-Soft)的Alpha-Beta
 
  以上代码总是返回Alpha、Beta或在Alpha和Beta之间的数。换句话说,当某个值不感兴趣时,从返回值无法得到任何信息。原因就是当前值被变量Alpha所保存,它从感兴趣的值的窗口下沿开始一直增长的,没有可能返回比Alpha更小的值。一个对Alpha-Beta的简单改进就是把当前评价和Alpha分开保存。下面的伪代码用常数“WIN”表示最大评价,它可以在Alpha-Beta搜索中返回任何评价。
 
// 超出边界的Alpha-Beta搜索
int alphabeta(int depth, int alpha, int beta) {
 move bestmove;
 int current = -WIN;
 if (棋局结束 || depth <= 0) {
  return eval();
 }
 for (每个可能的着法 m) {
  执行着法 m;
  score = -alphabeta(depth - 1, -beta, -alpha);
  撤消着法 m;
  if (score >= current) {
   current = score;
   bestmove = m;
   if (score >= alpha) {
    alpha = score;
   }
   if (score >= beta) {
    break; // 【译注:这里可以直接返回score、current或alpha,如果返回beta,则是不会高出边界的Alpha-Beta搜索。】
   }
  }
 }
 return current;
}

 
  这样改动以后,就可以知道比以前稍多一点的信息。如果返回值x等于或小于Alpha,我们仍然不知道局面的确切值(因为我们可能在搜索中裁剪了一些线路),但是我们知道确切值最多是x。类似地,如果x大于或等于Beta,我们就知道搜索值至少是x。这些微小的上界和下界变化不会影响搜索本身,但是它们能导致散列表命中率的提高。超出边界的Alpha-Beta搜索对下面要介绍的MTD(f)算法有重要作用。
 
期望搜索
 
  这个方法不是代替Alpha-Beta的,只是从外部改边一个途径来调用搜索过程。通常用Alpha-Beta找最好路线时,可以调用:
 
alphabeta(depth, -WIN, WIN)
 
  这里 -WIN 和 WIN 之间的范围很大,表明我们不知道搜索值是多少,因此任何可能的值都必须考虑。随后,要走的那步保存在搜索函数外部的变量中。
  期望搜索的不同之处在于,我们可以人为地指定一个狭窄窗口(用前一个搜索值为中心),对搜索通常是有帮助的。如果你搜索失败,必须加宽窗口重新搜索:
 
// 期望搜索
int alpha = previous - WINDOW;
int beta = previous + WINDOW;
for ( ; ; ) {
 score = alphabeta(depth, alpha, beta);
 if (score <= alpha) {
  alpha = -WIN;
 } else if (score >= beta) {
  beta = WIN;
 } else {
  break;
 }
}

 
  权衡狭窄搜索所节约的时间,和因为失败而重新搜索的时间,可以决定常数 WINDOW 的大小。在国际象棋中,典型的值也许是半个兵。期望搜索的变体有,搜索失败时适当增加窗口宽度,或者用初始窗口而没必要以前一次搜索结果为中心,等等。
 
MTD(f)
 
  这个技术跟期望搜索一样,只是在调用Alpha-Beta时对初始值进行调整。搜索窗口越窄搜索就越快,这个技术的思想就是让搜索窗口尽可能的窄:始终用“beta = alpha + 1”来调用Alpha-Beta。用这样一个“零宽度”搜索的作用是用Alpha和确切值作比较:如果搜索的返回值最多是Alpha,那么确切值本身最多是Alpha,相反确切值大于Alpha。
  我们可以用这个思想对确切值作二分搜索:
 
int alpha = -WIN;
int beta = +WIN;
while (beta > alpha + 1) {
 int test = (alpha + beta) / 2;
 if (alphabeta(depth, test, test + 1) <= test) {
  beta = test;
 } else {
  alpha = test + 1;
 }
}

 
  但是,这样会导致大规模的搜索(即 WIN 和 -WIN 的差的对数)。而MTD(f)的思想则是用超出边界的Alpha-Beta对搜索进行控制:每次调用超出边界的Alpha-Beta就会返回一个值更接近于最终值,如果用这个搜索值作为下次测试的开始,我们最终会达到收敛。
 
// MTD(f)
int test = 0;
for ( ; ; ) {
 score = alphabeta(depth, test, test + 1);
 if (test == score) {
  break;
 }
 test = score;
}

 
  不幸的是,它和散列表之间的复杂作用会导致这个过程陷入无限循环,所以必须加上额外的代码,如果迭代次数太多而没有收敛,就必须中止搜索。
  MTD(f)的一个大的优势在于我们可以简化Alpha-Beta搜索,因为它只需要两个参数(深度和Alpha)而不是三个。【据说这样做可以提高并行计算的效率,遗憾的是译者对并行计算一窍不通。】
  【为了对MTD(f)有更详细的了解,译者查阅了该算法的发明者Plaat的网站,他提供的MTD(f)代码中用了两个边界,可以防止迭代过程中出现振荡而不收敛的情况,代码如下(原来是Pascal语言,现被译者转写为C语言):
 
int MTDF(int test, int depth) {
 int score, beta, upperbound, lowerbound;
 score = test;
 upperbound = +INFINITY;
 lowerbound = -INFINITY;
 do {
  beta = (score == lowerbound ? score + 1 : score);
  score = alphabeta(depth, beta - 1, beta);
  (score < beta ? upperbound : lowerbound) = score;
 } while (lowerbound < upperbound);
 return score;
}

 
  而关于MTD(f)的使用另有以下几点技巧:
  (1) 通常试探值并不一定设成零,而是用迭代加深的形式由浅一层的MTD(f)搜索给出;
  (2) 局面评价得越粗糙,MTD(f)的效率越高,例如国际象棋中可使一个兵的价值由100降低为10,其他子力也相应比例降低,以提高MTD(f)的效率(但粗糙的局面评价函数却不利于迭代加深启发,因此需要寻求一个均衡点);
  (3) 零宽度窗口的搜索需要置换表的有力支持,因此称为“用存储器增强的试探驱动器”(Memory-enhanced Test Driver,即MTD),它只需要传递两个参数(深度n和试探值f),故得名为MTD(n,f),缩写为MTD(f)。】
 
PVS
 
  或许最好的Alpha-Beta变体,要算是这些名称了:负值侦察(NegaScout)和主要变例搜索(Principal Variation Search,简称PVS)。这个思想就是当第一次迭代搜索时找到最好的值,那么Alpha-Beta搜索的效率最高。对着法列表进行排序,或者把最好的着法保存到散列表中,这些技术可能让第一个着法成为最佳着法。如果真是如此,我们就可以假设其他着法不可能是好的着法,从而对它们快速地搜索过去。
  因此PVS对第一个搜索使用正常的窗口,而后续搜索使用零宽度的窗口,来对每个后续着法和第一个着法作比较。只有当零窗口搜索失败后才去做正常的搜索。
 
// 主要变例搜索(超出边界的版本)
int alphabeta(int depth, int alpha, int beta) {
 move bestmove, current;
 if (棋局结束 || depth <= 0) {
  return eval();
 }
 move m = 第一个着法;
 执行着法 m;
 current = -alphabeta(depth - 1, -beta, -alpha);
 撤消着法 m;
 for (其余的每个着法 m) {
  执行着法 m;
  score = -alphabeta(depth - 1, -alpha - 1, -alpha);
  if (score > alpha && score < beta) {
   score = -alphabeta(depth - 1, -beta, -alpha);
  }
  撤消着法 m;
  if (score >= current) {
   current = score;
   bestmove = m;
   if (score >= alpha) {
    alpha = score;
   }
   if (score >= beta) {
    break;
   }
  }
 }
 return current;
}

 
  这个算法跟MTD(f)有个同样的优势,即搜索树的大多数结点都以零宽度的窗口搜索,可以用双参数的Alpha-Beta。由于“Beta > Alpha + 1”的调用非常少,因此不必担心额外的工作(例如保存最佳着法以供将来使用)会占用很多时间。【原作者的意思是,调用零宽度窗口的搜索时,可以免去保存最佳着法等操作,因此可以省下不少时间。】
 
推荐
 
  我自己的程序结合了期望搜索(用在整个搜索过程以外)和PVS(用在搜索过程内部)。但是不同的棋类游戏不一样,由于这些搜索不难实现,所以要在这些方法中进行选择或调节参数,就必须对它们逐一实现并做一些试验。它们都必须返回同样的搜索值(如果受散列表影响,那么至少是相近的值【例如常规的Alpha-Beta搜索和超出边界的Alpha-Beta搜索,在使用散列表时可能会返回不同的值】),但搜索的结点数会不同。在你的棋类的典型局面中,能使搜索树最小的方法则被采纳。
 
  原文:http://www.ics.uci.edu/~eppstein/180a/990202b.html
  译者:黄晨 ()
  类型:全译加译注
分享到:
评论
1 楼 metaphy 2009-12-26  
好!http://www.elephantbase.net 这个网站上的文章是你翻译的吗?

相关推荐

    alpha-beta算法 一字棋

    《深入理解Alpha-Beta剪枝:以一字棋为例》 Alpha-Beta算法是搜索树策略中的一种优化...在更复杂的棋类游戏中,如国际象棋和围棋,Alpha-Beta算法的优化和变种(如PVS和iterative deepening)在AI领域有着广泛的应用。

    Alpha_Beta算法实现人工智能作业

    Alpha_Beta算法是人工智能领域中一种经典的搜索策略,主要用于优化棋类游戏的决策过程,比如国际象棋、围棋等。...在实践中,Alpha_Beta算法及其变种至今仍在许多棋类游戏中发挥着重要作用,它的应用价值不言而喻。

    Yamaxun.zip_Alpha_yamaxun.com_亚马逊棋

    Alpha-Beta算法是蒙特卡洛树搜索(MCTS)的一种优化,特别适用于棋类游戏,因为它能有效地减少搜索空间,提高决策效率。 Alpha-Beta剪枝是A*搜索算法的一个变种,用于在博弈树中进行深度优先搜索。它的目标是在两个...

    alphabeta剪枝算法的C++实现下棋程序

    阿尔法贝塔(Alpha-Beta)剪枝算法是基于搜索树的优化策略,主要用于解决两个玩家的零和博弈问题,例如国际象棋、围棋等棋类游戏。这种算法是A*搜索算法的一个变种,它在寻找最优解的过程中通过剪枝来减少不必要的...

    tic_tac_toe程序

    alpha-beta剪枝是A*搜索算法的一个变种,主要用于解决两个玩家的零和博弈问题,如井字游戏。它在搜索游戏树的过程中,通过比较alpha(代表当前已知的最佳结果)和beta(代表对手可以达到的最差结果)来提前舍弃无效...

    人工智能与信息社会考试答案参考.pdf

    总结来说,"Alpha剪枝"可能是指在决策树学习中的某种特定剪枝方法,但更常见的是在博弈论的Alpha-Beta搜索算法中,它通过设置Alpha和Beta值来减少搜索空间,提高搜索效率。在给定的考试答案中,这可能是考察学生对这...

    ch -killer.rar

    首先,Alpha-Beta剪枝是A*搜索算法的一个变种,专为两人零和博弈设计。在象棋游戏中,它通过在搜索树中提前剪掉无法影响最优解的分支,极大地减少了搜索空间,提高了搜索效率。具体来说,Alpha代表当前已知的最佳...

    cpp-带图形界面的黑白棋程序有保存悔棋联机对战与电脑对战等功能

    alpha-beta剪枝是A*搜索算法的一个变种,用于在树状结构(如游戏树)中寻找最佳路径。它通过设置alpha(代表当前最优解的下界)和beta(代表当前最优解的上界),在搜索过程中剔除无法改进当前最优解的分支,以减少...

    五子棋源碼支援人機對戰

    Alpha-Beta剪枝是A*搜索算法的一个变种,用于减少在游戏树中搜索的最佳路径时的冗余计算,提高了在有限时间内找到最优解的效率。 4. **Piskvork(PVS,Principal Variation Search)**:`piskcomp.cpp`、`pisqpipe....

    Gobang.rar

    A-B剪枝算法是Alpha-Beta剪枝的变种,由Alpha(α)和Beta(β)两个参数定义。在五子棋的上下文中,Alpha表示当前节点所有可能的最佳结果的下界,而Beta则表示所有可能的最差结果的上界。当搜索过程中发现某个分支...

    最优化算法

    Fletcher-Reeves 方法是共轭梯度法的一种变种,它通过更新搜索方向的方式加快了收敛速度。与标准的共轭梯度法不同的是,Fletcher-Reeves 方法在每次迭代时都会根据当前的梯度来调整搜索方向。 #### 2.2 算法流程 ...

    整站源代码~~一个用c#开发的游戏---支持单人--和双人

    Alpha-beta搜索是一种优化的博弈树搜索算法,用于在有限步数内预测最优走法,它是A*搜索算法的一个变种,广泛应用于棋类游戏的人工智能中,以提高决策效率并避免不必要的计算。 结合以上信息,我们可以推测这个项目...

    C++实现五子棋小游戏的准备策略

    五子棋属于零和博弈,传统的解决方法是使用博弈树搜索算法,如极小化极大算法(Minimax)或其变种,如Alpha-Beta 剪枝算法。 在人机对战算法中,开发者需要考虑以下几个方面: * 博弈树搜索:开发者需要使用博弈树...

    电脑象棋循序渐进中象棋小巫师的源代码(VC++)

    "象棋小巫师"可能采用了变种或改进版的Alpha-Beta算法,比如PVS(Principal Variation Search)或者iterative deepening,以提高搜索效率并减少计算量。 4. **Zobrist校验码技术**:这是一种高效且独特的位置编码...

    reversi:使用 Alpha Beta 剪枝的黑白棋游戏代理

    Alpha Beta剪枝是A*搜索算法的变种,用于减少在决策树中无用的分支搜索。在黑白棋游戏中,这个算法可以快速评估当前棋局的潜在价值,预测对手的下一步,并选择最优的棋步。Alpha代表当前已知的最佳结果(对己方有利...

    chiness_chess_jieqi-master_揭棋_

    4. 算法与数据处理:掌握minmax算法和Alpha-Beta剪枝,理解它们如何帮助机器人做出决策。 5. 游戏AI设计:了解如何设计一个基本的AI玩家,以及如何优化其性能。 6. 控制台交互:学习如何通过命令行接口实现用户与...

    negamax

    Negamax算法基于Alpha-Beta剪枝的变种,目的是在有限的深度内尽可能高效地探索游戏树。它的工作流程如下: 1. **游戏状态评估**: Negamax算法首先需要一个评估函数来衡量当前游戏状态的好坏。这个函数通常根据棋盘...

    中国象棋(c#源码)

    在象棋程序中,常见的是Minimax算法或其变种Alpha-Beta剪枝。Minimax是一种深度优先搜索策略,通过递归地模拟所有可能的走法来预测对手的反应,直到达到结束条件(如达到预设的搜索深度或出现胜负状态),然后回溯并...

    井字棋游戏-易语言

    3. **Alpha-Beta剪枝算法**:在“井字棋(AlphaBeta).e”文件中,可能包含的是一个优化过的搜索算法。Alpha-Beta剪枝是A*搜索算法的一个变种,用于减少在决策树中搜索的最佳走法的时间。在井字棋这样的游戏中,由于...

Global site tag (gtag.js) - Google Analytics