带有alhpa-β剪枝的国际象棋迷你最大

Question

我正在创建一个国际象棋AI使用极小极大方法与α-β剪枝。我正试图理解α-β剪枝是如何工作的，但当涉及到国际象棋时，我无法理解它，在国际象棋中，你设定了一定的搜索深度。

如何使用alpha-beta解决最大的问题，为了优势牺牲一片，2-3步前进？难道只看祭祀处的位置，马上就把那支树枝丢弃坏了，就错过了好的“牺牲”吗？

感谢您对改进的任何澄清或建议。到目前为止，我的代码如下：

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)
            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)
            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

为了让你明白这一点，我想解释一下极小极大搜索树。

在minimax搜索树中，引擎假设在一定的深度下，两个玩家都会在分支的末尾(在移动3次之后)最大限度地最大化板的价值(来自evaluate())。如果移动序列在3次移动中牺牲皇后为零，则此分支被认为是糟糕的。但是如果它在两个动作中为一个不可避免的死刑犯牺牲了一个女王，这被认为是好的。

顺便说一句，Alpha-Beta剪枝是对minimax的优化，这有助于获得与minimax相同的结果，但速度更快。有关更多信息，您可能希望查看维基百科中的α-beta剪枝。

一个简单的方法让你的引擎寻找更长期的优势是增加搜索深度，但由于它通常伴随着时间成本成倍增长，这是不完全可行的。以下是一些让你的引擎更快的建议。

• 使用Python国际象棋库。我不确定您是否已经从您显示的代码中使用了它，但如果没有，我建议您使用这个库。该库提供了像样的棋盘计算性能，方便的棋盘表示，打印到分弦或PGN字符串，等等。
• 使用移动排序。这通常可以帮助您更快地找到好的移动，并且可以将移动生成和排序算法转化为一个函数，并使用functools.lru_cache()进一步提高搜索速度。请注意，lru_cache()使用哈希表来存储以前的执行，但默认情况下，chess.Board并不是可选的，因此您需要在导入之后将其放入缓存才能工作：chess.Board.__hash__ = chess.polyglot.zobrist_hash。有关更多信息，请访问移动排序。
• 使用打开数据和打开搜索器。您可以使用数据这里使您的引擎使用空缺，这不需要时间计算，同时也为早期游戏提供了更好的结果。