alpha-beta修剪算法中的alpha值如何使用和更新？ [英] How is the alpha value in alpha-beta pruning algorithm used and updated?

问题描述

我正在查看帖子在实现alpha-beta修剪算法时函数中的奇怪行为和可接受的答案，其中指出：您的 rootAlphaBeta 不会更新alpha值。我想知道代码中需要添加什么。

I was looking at the post Strange behaviour in a function while implementing the alpha-beta pruning algorithm and the accepted answer, where it is stated: "Your rootAlphaBeta doesn't update the alpha value". I was wondering what the necessary addition to the code was.

推荐答案

要使alpha-beta修剪起作用，alpha值需要传播到深度优先搜索的顶层。这可以通过以下方式实现：初始化一个变量以将alpha存储在潜在移动的循环外，将调用结果存储在 alphaBeta（）中，然后使用它作为 alphaBeta（）的参数。在如下代码中：

For alpha-beta pruning to work, the alpha value needs to get propagated up to the top level of the depth first search. This can be achieved by initializing a variable to store alpha outside of the loop over the potential moves, storing the result of the call to alphaBeta() in it, and then using it as an argument to alphaBeta(). In code that will look like:

def rootAlphaBeta(self, board, rules, ply, player):
    """ Makes a call to the alphaBeta function. Returns the optimal move for a player at given ply. """
    best_move = None
    max_eval = float('-infinity')

    move_list = board.generateMoves(rules, player)
    alpha = float('infinity')
    for move in move_list:
        board.makeMove(move, player)
        alpha = -self.alphaBeta(board, rules, float('-infinity'), alpha, ply - 1, board.getOtherPlayer(player))
        board.unmakeMove(move, player)

        if alpha > max_eval:
            max_eval = alpha
            best_move = move

    return best_move

这篇关于alpha-beta修剪算法中的alpha值如何使用和更新？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！