4

アルファ ベータ プルーニングを使用したミニマックス アルゴリズムを実装しました。最良の動きを得るために、関数でアルファ ベータ アルゴリズムを呼び出しrootAlphaBetaます。しかし、rootAlphaBeta関数内で、非常に奇妙な動作を見つけました。rootAlphaBeta4 の関数を呼び出すと、ply約 20 000 回の呼び出しが行われますが、alphaBeta関数を直接呼び出すと、約 2000 回の呼び出ししか行われません。呼び出しの数は同じでなければならないので、何が問題なのかわかりません。

両方のアルゴリズムが最終的に見つける動きは同じはずですよね? alphaBeta私はそう思います、少なくとも移動のスコアは同じ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
4

1 に答える 1

4

あなたは値rootAlphaBetaを更新しませんalpha。最初のノードを除くすべての子ノードの範囲を絞り込むことができた場合、(-inf, inf) の全範囲ですべての子ノードを呼び出します。これにより、最終的なスコアに影響を与えない一部のブランチの剪定が防止され、ノード数が増加します。

于 2012-09-24T17:04:33.073 に答える