实现alpha-beta修剪算法时函数中的奇怪行为 [英] Strange behaviour in a function while implementing the alpha-beta pruning algorithm

问题描述

我已经实现了带有alpha-beta修剪功能的minimax算法.为了获得最佳效果，我使用rootAlphaBeta函数调用alpha-beta算法.但是，在rootAlphaBeta函数中，我发现了一些非常奇怪的行为.当我用ply为4调用rootAlphaBeta函数时，它将进行约20000次调用，但是当我直接调用alphaBeta函数时，它将仅进行2000次调用.我似乎找不到问题所在，因为通话次数应该相同.

I've implemented a minimax algorithm with alpha-beta pruning. In order to get the best move, I call the alpha-beta algorithm with the rootAlphaBeta function. However, in the rootAlphaBeta function, I spotted some very strange behaviour. When I call the rootAlphaBeta function with a ply of 4, it makes about 20 000 calls, but when I call the alphaBeta function directly, it makes only about 2000 calls. I can't seem to find what's the problem, as the number of calls should be the same.

两种算法最终找到的动作应该相同，对吗?我认为是这样，至少此举的分数是相同的，当我不使用rootAlphaBeta直接调用它时，我无法知道alphaBeta选择的举动.

The move that both algorithms eventually find should be the same, right? I think so, at least the score of the move is the same, I have no way of knowing the move the alphaBeta chooses when I call it directly without rootAlphaBeta.

def alphaBeta(self, board, rules, alpha, beta, ply, player):
    """Implements a minimax algorithm with alpha-beta pruning."""
    if ply == 0:
        return self.positionEvaluation(board, rules, player)

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

        if current_eval >= beta:
            return beta

        if current_eval > alpha:
            alpha = current_eval

    return alpha


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)
    for move in move_list:
        board.makeMove(move, player)
        current_eval = -self.alphaBeta(board, rules, float('-infinity'),
                                       float('infinity'), ply - 1,
                                       board.getOtherPlayer(player))
        board.unmakeMove(move, player)

        if current_eval > max_eval:
            max_eval = current_eval
            best_move = move

    return best_move

推荐答案

您的rootAlphaBeta不会更新alpha值.当它可以缩小除第一个节点以外的所有子节点的范围时，它将使用其全部范围(-inf，inf)调用其所有子节点.这样可以防止某些分支的修剪对最终分数没有影响，并增加节点数.

Your rootAlphaBeta doesn't update the alpha value. It calls all its child nodes with the full range of (-inf, inf), when it could have narrowed down the range for all child nodes except the first. This will prevent pruning of some branches which will have no effect on the final score, and increase the node count.

这篇关于实现alpha-beta修剪算法时函数中的奇怪行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！