如何在任意时刻中断Python国际象棋实现中的Minimax算法？

我用Python实现了国际象棋的数字复刻版本，并为对战玩家加入了Minimax算法。为了在不过度耗时的前提下搜索最大深度，我设置了时间限制，在超时前不断加深搜索，超时则使用最后完成的搜索结果。

以下是算法核心代码（已移除非关键部分）：

def play(self, current_game, depth, maxi, alpha, beta, white, limit):
        if depth <= 0 or Game.instance.isCheckmate(True) or Game.instance.isCheckmate(False) or not Game.instance.isAdequate() or Game.instance.isStalemate(True) or Game.instance.isStalemate(False):
            v = self.evaluate(current_game.board)
            return [v, None]

        board = current_game.board
        current_game.generateAllMoves(white)
        all_moves = current_game.getAllMoves()
    
        if maxi:
            best_score = float('-inf')
        else:
            best_score = float('inf')
        best_move = None

        if time.time() > limit:
            return [0, None]
            
        for move in all_moves:            
            board.makeMove(move)
            curr_score = self.play(current_game, depth - 1, not maxi, alpha, beta, not white, limit)[0]
            
            if maxi:
                if curr_score >= best_score:
                    best_score = curr_score
                    best_move = move
                alpha = max(alpha, curr_score)
            else:
                if curr_score <= best_score:
                    best_score = curr_score
                    best_move = move
                beta = min(beta, curr_score)

            board.undoMove()
            
            if beta <= alpha:
                break

        return [best_score, best_move]

目前我通过简单的时间检查判断超时，返回[0, None]，但这会破坏算法——因为算法并不期望返回None。请问有什么更好的实现方式？如何在达到时间限制时正确停止算法？

解决方案 #

1. 自定义异常终止搜索（推荐） #

通过抛出自定义异常中断递归链，不在递归过程中返回无效值，而是在迭代加深的顶层捕获异常，直接使用之前已完成深度的最佳走法。

步骤如下：

• 定义超时异常类：

class TimeOutException(Exception):
    pass

• 修改play函数的超时检查逻辑：

def play(self, current_game, depth, maxi, alpha, beta, white, limit):
        # 终止条件不变
        if depth <= 0 or Game.instance.isCheckmate(True) or Game.instance.isCheckmate(False) or not Game.instance.isAdequate() or Game.instance.isStalemate(True) or Game.instance.isStalemate(False):
            v = self.evaluate(current_game.board)
            return [v, None]

        board = current_game.board
        current_game.generateAllMoves(white)
        all_moves = current_game.getAllMoves()
    
        if maxi:
            best_score = float('-inf')
        else:
            best_score = float('inf')
        best_move = None

        # 超时则抛出异常，而非返回无效值
        if time.time() > limit:
            raise TimeOutException()
            
        for move in all_moves:            
            board.makeMove(move)
            try:
                curr_score = self.play(current_game, depth - 1, not maxi, alpha, beta, not white, limit)[0]
            except TimeOutException:
                # 捕获下层抛出的异常，向上传递
                board.undoMove()
                raise
            
            if maxi:
                if curr_score >= best_score:
                    best_score = curr_score
                    best_move = move
                alpha = max(alpha, curr_score)
            else:
                if curr_score <= best_score:
                    best_score = curr_score
                    best_move = move
                beta = min(beta, curr_score)

            board.undoMove()
            
            if beta <= alpha:
                break

        return [best_score, best_move]

• 在迭代加深的主循环中捕获异常：

# 假设TIME_ALLOWED是你设置的单次搜索时间上限
TIME_ALLOWED = 5  # 示例：5秒
best_move = None
current_depth = 0

while True:
    try:
        # 计算当前深度的超时时间
        time_limit = time.time() + TIME_ALLOWED
        # 执行当前深度的搜索
        score, move = ai.play(game, current_depth + 1, True, float('-inf'), float('inf'), True, time_limit)
        # 搜索完成，保存最佳走法并加深深度
        best_move = move
        current_depth += 1
    except TimeOutException:
        # 超时，终止循环，使用最后保存的最佳走法
        break

# 使用best_move执行AI走法

2. 共享超时标志传递状态 #

使用可变对象（如自定义类实例）传递超时状态，递归过程中检查该标志，一旦触发则返回当前层已找到的最佳结果，而非无效值。

步骤如下：

• 定义超时标志类：

class TimeoutFlag:
    def __init__(self):
        self.timed_out = False

• 修改play函数，加入标志参数：

def play(self, current_game, depth, maxi, alpha, beta, white, limit, timeout_flag):
        # 先检查是否已超时，若超时则返回当前层已有的最佳结果
        if timeout_flag.timed_out:
            return [best_score, best_move]
            
        # 终止条件不变
        if depth <= 0 or Game.instance.isCheckmate(True) or Game.instance.isCheckmate(False) or not Game.instance.isAdequate() or Game.instance.isStalemate(True) or Game.instance.isStalemate(False):
            v = self.evaluate(current_game.board)
            return [v, None]

        board = current_game.board
        current_game.generateAllMoves(white)
        all_moves = current_game.getAllMoves()
    
        if maxi:
            best_score = float('-inf')
        else:
            best_score = float('inf')
        best_move = None

        # 检查超时，设置标志
        if time.time() > limit:
            timeout_flag.timed_out = True
            return [best_score, best_move]
            
        for move in all_moves:            
            board.makeMove(move)
            curr_score = self.play(current_game, depth - 1, not maxi, alpha, beta, not white, limit, timeout_flag)[0]
            
            # 若已超时，提前终止循环
            if timeout_flag.timed_out:
                board.undoMove()
                break
            
            if maxi:
                if curr_score >= best_score:
                    best_score = curr_score
                    best_move = move
                alpha = max(alpha, curr_score)
            else:
                if curr_score <= best_score:
                    best_score = curr_score
                    best_move = move
                beta = min(beta, curr_score)

            board.undoMove()
            
            if beta <= alpha:
                break

        return [best_score, best_move]

• 主循环中使用标志控制搜索：

TIME_ALLOWED = 5
best_move = None
current_depth = 0

while True:
    timeout_flag = TimeoutFlag()
    time_limit = time.time() + TIME_ALLOWED
    score, move = ai.play(game, current_depth + 1, True, float('-inf'), float('inf'), True, time_limit, timeout_flag)
    
    if timeout_flag.timed_out:
        # 超时，终止循环
        break
    else:
        # 搜索完成，更新最佳走法
        best_move = move
        current_depth += 1

# 使用best_move执行AI走法

关键注意点 #

• 迭代加深的核心是保存每次完整深度搜索后的最佳走法，超时后直接使用上一次完成的深度结果，而非中断当前深度的不完整搜索结果。
• 避免在递归过程中返回[0, None]这类无效值，会破坏Minimax的评分传递逻辑，导致上层搜索得到错误的评分，进而选择错误的走法。

内容的提问来源于stack exchange，提问作者Tim_M