主页 / 问题 / 1425587
Accepted
Максим Фисман
Asked:2022-08-31 03:16:28 +0000 UTC2022-08-31 03:16:28 +0000 UTC

Minimax 与迭代深化：如何使用以前的计算？

  • 772

我正在使用AI minimax算法来玩跳棋。
为了获得最佳性能，我使用 alpha-beta 剪辑。

由于在检查器中很难预测在特定位置需要什么深度的搜索，我想使用迭代加深：搜索首先发生在深度 1，然后是 2、3，依此类推。

据我了解，迭代加深的意思是，当计算到n的深度时，我们使用之前执行的计算到n-1的深度，其结果存储（在哈希表/文件中...... )

但是，我并不完全清楚我需要在这个哈希表中存储什么？我应该保存在 minimax 过程中出现的所有位置还是只保存起始深度的位置？

现在我的程序只是按顺序遍历所有深度，而不以任何方式使用先前较不深度计算的结果。

class AI:
    def get_best_move (self, board, time_limit):
        self.analysed_positions = 0
        self.best_move = None
        self.calculation_process = True

        calculation_process = threading.Thread(target=self.iterative_deepening_minimax, args=(board, ))
        calculation_process.start()
        calculation_process.join(time_limit)
        self.calculation_process = False

        return self.best_move


    def iterative_deepening_minimax (self, board):
        for depth in range(2, 30):
            if self.calculation_process:
                # Начинаем поиск на глубине depth, который возвращает лучший ход в этой позиции
                self.best_move = self.minimax(board, depth, -INFINITY, INFINITY, board.whitesMove)[1]
            else:
                break


    def minimax (self, board, depth, alpha, beta, maximizingPlayer):
        if self.calculation_process == False:
            return (0, None)

        board.find_all_moves()

        game_state = board.get_game_state()
        if game_state != STATE_OK:
            self.analysed_positions += 1
            return (INFINITY + depth, None) if game_state == WHITE_WIN else (-INFINITY - depth, None)
        if depth == 0:
            self.analysed_positions += 1
            eval = self.evaluate(board)
            return (eval, None)

        bestMove = None
        if maximizingPlayer:
            maxEval = -INFINITY
            for move in board.moves:
                next_pos = Board(board, search_all_moves=False)
                next_pos.make_move(move)
                next_pos.change_turn()

                eval = self.minimax(next_pos, depth - 1, alpha, beta, False)[0]
                if eval > maxEval:
                    maxEval = eval
                    bestMove = move
                # Pruning
                alpha = max(alpha, eval)
                if beta <= alpha:
                    break
            return (maxEval, bestMove)

        else:
            minEval = INFINITY
            for move in board.moves:
                next_pos = Board(board, search_all_moves=False)
                next_pos.make_move(move)
                next_pos.change_turn()

                eval = self.minimax(next_pos, depth-1, alpha, beta, True)[0]
                if eval < minEval:
                    minEval = eval
                    bestMove = move
                # Pruning
                beta = min(beta, eval)
                if beta <= alpha:
                    break

            return (minEval, bestMove)

    # Возвращает статическую оценку позиции
    def evaluate():
        ...
python искусственный-интеллект

1 个回答

  1. Best Answer

    简而言之：正确的解决方案是记住在极小极大过程中遇到的所有位置。这称为转置表。

    当某个深度的极小极大得出关于某个位置的最佳移动的结论时（在代码中，这发生在行return (maxEval, bestMove)和中return (minEval, bestMove)），您需要记住以下特征：

    • 位置本身（考虑转牌顺序）
    • 职位评估
    • 在这个位置进行深度搜索
    • 在这个深度的这个位置找到的最好的移动
    class Transposition:
    def __init__ (self, pos, eval, depth, best_move):
        self.pos = pos
        self.eval = eval
        self.depth = depth
        self.best_move = best_move

    每次我们要求 minimax 确定给定位置的最佳移动时，我们都会查看该位置是否在转置表中。如果没有，像往常一样继续 minimax。如果有，那么我们需要检查深度：如果转置表中记录的这个位置的深度大于或等于我们正在寻找的深度，那么我们可以使用转置表中记录的最佳移动对于这个职位。

    如果位置记录在表中较浅的深度，那么，唉，这对我们没有帮助，因为我们需要更深入地查看。但是，我们仍然可以使用最佳走法：如果在深度 N 处找到最佳走法，那么在大于 D 的深度处，同样的走法很有可能是最佳走法。

        def minimax (self, board, depth, alpha, beta, maximizingPlayer):
        # ...
     
        # Ищем позицию
        position_index = board.convert_to_number()
        transposition = next((tr for tr in self.transpositions if tr.pos == position_index), None)
        # Если позиция уже встречалась
        if transposition != None:
            # Если глубина нам подходит
            if transposition.depth >= depth:
                # Используем ранее найденный результат
                return (transposition.eval, transposition.best_move)

    几点评论：

    1. 当我们向表中添加位置时，我们需要确保在较浅的深度没有相同的位置。
    2. 一个有用的解决方案是向转置添加一个属性，以isOnly确定找到的移动是否是唯一的移动。如果该位置只有一招，那么在什么深度找到它并不重要，无论深度如何，我们都可以使用它。

    一个类似的解决方案（可能看起来像拐杖）：如果一个位置只有一个移动，则将该位置记录在换位表中，用 depth 解析БЕСКОНЕЧНОСТЬ。

    • 1

相关问题