minimax函数中的Python深度复制

Question

我正在通过使用带有alpha-beta修剪的minimax算法在Python中创建国际象棋引擎。但是，此刻此刻非常慢，我发现在minimax中进行每次深度复制都和我所有其他函数的组合一样慢。

有什么方法可以绕过深度复制，或使其更快？下面是我今天的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()方法是如何实现的，并假定它不进行任何排序。最好为minimax算法订购移动，以便从最佳到最坏的顺序循环移动（在这种情况下，您可能会修剪更多节点并加快程序速度）。

3] child循环中的for child in children变量是一个二维矩阵。我还猜想board也是一个多维数组。多维数组由于其内存布局而可能比一维数组慢（例如，如果您逐列遍历它们）。尽可能使用一维数组（例如，您可以将二维数组表示为一维数组的“串联”）。

4）使用生成器进行延迟评估。例如，您可以将get_all_possible_moves()转换为生成器并对其进行迭代，而无需创建列表和使用额外的内存。如果alpha / beta修剪条件触发得较早，则无需扩展该位置的所有子级列表。

5）通过进行和取消当前移动来避免对电路板进行深度复制。在这种情况下，您无需创建板的副本，而是重复使用可能更快的原始板：

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）添加更多经典的优化象棋引擎功能，例如迭代加深，主变量搜索，换位表，位板等。>>