Python minimax函数中的深度复制

Question

我正在 Python 中使用带有 alpha-beta 剪枝的极小极大算法创建一个国际象棋引擎。然而，目前速度非常慢，而且我发现在 minimax 中进行每次迭代的深度复制与我所有其他函数的总和一样慢。

有什么办法可以绕过深度复制，或者让它更快吗？以下是我今天的极小极大函数。它只能向前思考 3-4 步左右，这并不是一个很好的引擎...非常感谢任何有关加快算法速度的建议。

def minimax(board, depth, alpha, beta, maximizing_player):

    board.is_human_turn = not maximizing_player 

    children = board.get_all_possible_moves()

    if depth == 0 or board.is_draw or board.is_check_mate:
        return None, evaluate(board)

    best_move = random.choice(children)

    if maximizing_player:
        max_eval = -math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child[0][0], child[0][1], child[1][0], child[1][1])
            current_eval = minimax(board_copy, depth - 1, alpha, beta, False)[1]
            if current_eval > max_eval:
                max_eval = current_eval
                best_move = child
            alpha = max(alpha, current_eval)
            if beta <= alpha:
                break
        return best_move, max_eval

    else:
        min_eval = math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child[0][0], child[0][1], child[1][0], child[1][1])
            current_eval = minimax(board_copy, depth - 1, alpha, beta, True)[1]
            if current_eval < min_eval:
                min_eval = current_eval
                best_move = child
            beta = min(beta, current_eval)
            if beta <= alpha:
                break
        return best_move, min_eval

Answer 1

关于如何优化程序的一些想法(排名不分先后):

1) 进行检查 if depth == 0 or board.is_draw or board.is_check_mate您在 minimax 中做的第一件事功能。现在您调用board.get_all_possible_moves()这可能是多余的(例如在 depth == 0 的情况下)。

2) 我不明白get_all_possible_moves()方法已实现并假设它不进行任何类型的排序。为极小极大算法排序移动是一种很好的做法，这样您就可以从最好的到最差的进行循环(在这种情况下，您可能会修剪更多节点并加快程序速度)。

3) child for child in children 中的变量循环是一个二维矩阵。我也猜想board也是一个多维数组。由于其内存布局，多维数组可能比一维数组慢(例如，如果按列迭代它们)。如果可能，请使用一维数组(例如，您可以将二维数组表示为一维数组的“串联”)。

4) 使用生成器进行惰性求值。例如，您可以将您的 get_all_possible_moves()进入生成器并迭代它，而不创建列表并消耗额外的内存。如果 alpha/beta 修剪条件提前触发，您将不​​需要展开该位置的整个子级列表。

5) 通过做出和取消当前的 Action 来避免对棋盘进行深度复制。在这种情况下，您不会创建板的副本，而是重用原始板，这可能会更快:

current_move_info = ... # collect and store info necessary to make/unmake the current move

board.move(current_move_info)

current_eval = minimax(board, ...)[1]

board.unmake_move(current_move_info) # restore the board position by undoing the last move

6) 添加更多经典的优化国际象棋引擎功能，如迭代深化、主变搜索、换位表、位板等。