慢棋机器人，需要走得更快

Question

我使用 minimax 和 alpha beta 修剪创建了一个国际象棋机器人，同时我还创建了一个 GUI。但是我的机器人在变得非常慢之前不能走得很深。在深度 4 中，可能需要 40-50 秒才能找到着手点。

算法如下所示：

def minimax(depth,board, alpha, beta, is_max):
    if depth == 0:
        return evaluation(board)
    leg_moves = board.legal_moves
    if is_max:
        value = -9999
        for i_move in leg_moves:
            move = chess.Move.from_uci(str(i_move))
            board.push(move)
            value = max(value, minimax(depth - 1, board, alpha, beta, False))
            board.pop()
            alpha = max(alpha, value)
            if beta <= alpha:
                return value
        return value
    else:
        value = 9999
        for i_move in leg_moves:
            move = chess.Move.from_uci(str(i_move))
            board.push(move)
            value = min(value, minimax(depth - 1, board, alpha, beta, True))
            board.pop()
            beta = min(beta, value)
            if(beta <= alpha):
                return value
        return value

总而言之，如何让它更快？

Answer 1

有很多因素可以使算法快速添加更多国际象棋程序的标准功能。但是只有 4 步和这么多时间对于您的源代码来说是不正常的。你如何产生动作？你不应该通过 UCI 协议询问它们，而是尝试非常快速地生成它们。特别是不要搜索板上的数字，而是将这些位置组织在列表中，如果它们是从板上取下来的，add/remove。

可能是你的求值函数慢了。如果你只关心棋子的值，那么有一个变量来保存颜色的差异，并且只有在棋子被拿走或恢复时才更新它。所以评估几乎不需要时间了。

在一个 java 程序中，我在不使用哈希表等方法的情况下实现了这些细节，在 4 秒内达到了 7 的深度。

Answer 2

实现一个 Negamax 函数而不是 Minimax 将使未来的效率实现更容易作为一个开始，它也会使代码看起来更清晰：

def negamax(depth, board, alpha, beta, color):
    if depth == 0:
        return evaluation(board)
    leg_moves = board.legal_moves
    for i_move in leg_moves:
        move = chess.Move.from_uci(str(i_move))
        board.push(move)
        value = -negamax(depth - 1, board, -beta, -alpha, -color)
        board.pop()
        alpha = max(alpha, value)
        if beta <= alpha:
            return value
     return value

那么您可能想要研究一些概念，例如在进入递归函数之前对移动进行排序，因为这样您将更快地获得 beta 截止值，而不必查看那么多移动。然后您还可以实现例如换位 table（迭代加深）、空移动和后期移动减少。

你可能还想看看你的移动生成，看看你是否可以让它更快。例如，您使用什么样的董事会代表？

我在 Python 中制作了一个国际象棋引擎，它根本不是一流的。它在大约 15 秒内到达深度 6，您可以在此处找到代码以获取灵感：Affinity Chess。它使用一维板表示，但位板表示会更快。

我也强烈建议查看 www.chessprogramming.org，那里有很多非常好的信息。

慢棋机器人，需要走得更快

Slow chess bot, need to go faster

python

algorithm

chess

minimax

alpha-beta-pruning