python - 极小极大函数内国际象棋移动生成的转置表

Question

背景

我正在尝试优化我的国际象棋极小极大算法，并且到目前为止使用了 alpha-beta 剪枝。我还实现了迭代加深，以便以后使用换位表进行优化。到目前为止，我得到的基本上是一些 python 代码中的内容:

# Original call
def ai_make_move(gamestate):
    for depth in range(1, max_depth):
        move, evaluation = minimax(gamestate, depth, -math.inf, math.inf, maximizing_player)

# Minimax
def minimax(gamestate, depth, -math.inf, math.inf, 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 = children[0]

    if maximizing_player:
        max_eval = -math.inf
        for child in children:
            board.make_move(child)
            current_eval = minimax(board, depth - 1, alpha, beta, False)[1]
            board.unmake_move()

            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.make_move(child)
            current_eval = minimax(board, depth - 1, alpha, beta, True)[1]
            board.unmake_move()

            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

问题

因为我进行了迭代加深，所以我认为我可以利用之前计算的来自之前深度的 valid_moves(位置的子级)。因此，当计算深度 1 的位置时，它会计算该位置黑色的所有有效移动。当在深度 2 处计算时，它将再次开始计算相同位置的黑色有效移动，这似乎是一个不必要的操作，因为我已经在上一个循环中这样做了。所以我应该能够从表中保存的 valid_moves 中检索它。

我已经使用 zobrist 散列法为每个位置获得一个几乎唯一的数字，并尝试在我的 minimax 函数中这样使用它:

# Minimax
def minimax(gamestate, depth, -math.inf, math.inf, maximizing_player):

    if gamestate.zobrist_key in gamestate.transposition_table:
        children = gamestate.transposition_table[gamestate.zobrist_key]
    else:
        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)

   ......

由于某种原因，引擎做出了完全不合理的举动，在当前位置上是不合法的，而且似乎不起作用。

我尝试过的

我检查过:

• 我的 Zobrist 计算正确。
• make_move 和 unmake_move 函数正常工作(在人机对战时)。
• 在没有换位表概念的情况下，AI 似乎可以正常工作并下出正确有效的 Action 。

问题

我不知道出了什么问题，也不知道这是否是正确的处理方式。非常感谢任何指导!

Answer 1

您不能假设引擎在较浅深度下所做的评估是准确的，因为位置可能会改变下一步行动，例如简单捕获您的女王。这就是为什么不是完全不计算先前搜索的移动，而是可以进行移动排序并首先从表中计算之前迭代中最有希望的移动，而且通常情况下，alpha-beta 修剪将使这比仅从固定深度。