文章/答案/技术大牛

发布

社区首页 >问答首页 >将Minimax修改为Alpha-Beta剪枝伪代码

问将Minimax修改为Alpha-Beta剪枝伪代码
EN

Stack Overflow用户

提问于 2016-12-16 10:20:14

回答 1查看 1.1K关注 0票数 0

我正在学习Alpha-Beta伪代码，我想为Alpha剪枝编写一个最简单的伪代码。

我已经为Minimax编写了伪代码。

function minimax(node, depth)
     if node is a terminal node or depth ==0
          return the heuristic value of node
     else 
          best = -99999
     for child in node
          best = max(best, -minimax(child, depth-1))
     return best

但是，我不知道如何将其修改为α-beta剪枝。有人能帮忙吗？

minimax

algorithm

artificial-intelligence

pseudocode

chess

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-12-19 16:12:28

在阿尔法-贝塔，你跟踪你的保证分数为一个位置。如果你发现一个比对手在前一个位置上已经保证的得分更好的移动，你可以立即停止。

从技术上讲，每一方都能跟踪自己的下限得分(alpha)，并且你可以访问对手的下限分数(beta)。

下面的伪代码没有经过测试，但是下面是这样的想法：

function alphabeta(node, depth, alpha, beta)
     if node is a terminal node or depth ==0
          return the heuristic value of node
     else 
          best = -99999
     for child in node
          best = max(best, -alphabeta(child, depth-1, -beta, -alpha))
          if best >= beta
                return best
          if best > alpha
                alpha = best
     return best

在搜索开始时，可以将alpha设置为-INFINITY，将beta设置为+无穷大。严格地说，草图的算法不是alpha-beta，而是尼加马克斯。两者是相同的，所以这只是一个实现细节。

注意，在Alpha-Beta中，移动顺序是至关重要的。如果在大多数情况下，从最好的一步开始，或者至少是非常好的一步，你应该会看到比Minimax有很大的进步。

一个附加的优化，从受限的alpha beta窗口开始(不是-INFINITY和+无穷大)。但是，如果你的假设是错误的，你必须用一个更开放的搜索窗口重新启动搜索。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/41182117

复制

相似问题

问将Minimax修改为Alpha-Beta剪枝伪代码
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问将Minimax修改为Alpha-Beta剪枝伪代码EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问将Minimax修改为Alpha-Beta剪枝伪代码
EN