实现带Alpha/Beta置换表的Negamax：超时后如何处理部分搜索结果？

首先明确结论：绝对不能直接返回null，也不能完全丢弃已完成的工作。正确的做法是终止当前深度的着法循环，保留并利用已完成搜索的着法结果，同时更新置换表中已完成的节点数据，最后返回当前能找到的最佳合法着法。

为什么不能直接退出且不更新置换表？ #

置换表的核心价值是缓存已搜索节点的估值、深度和剪枝类型（EXACT/LOWER/UPPER），这些数据是后续搜索（哪怕是同一对局的下一次思考）的宝贵算力节省资源。如果因为时间耗尽就丢弃已完成的计算，不仅浪费了之前的努力，还会导致后续重复计算相同节点，大幅降低搜索效率。哪怕只完成了部分着法的搜索，这些节点的有效信息也必须存入置换表。

为什么要终止循环而非继续？ #

既然时间已经耗尽，继续处理剩余着法只会导致超时，违反时间控制要求。此时必须立刻停止当前深度的剩余搜索，避免无意义的算力消耗。

具体处理步骤 #

1. 中断循环：当检测到时间耗尽时，立即跳出当前的着法遍历循环，不再处理未搜索的着法。
2. 更新置换表：确保所有已经完成搜索的节点（包括当前深度下已处理的着法对应的子节点，以及Negamax递归过程中已经遍历的节点）都正确写入置换表。注意：置换表的更新应该在Negamax函数内部完成——每次完成一个节点的搜索（无论是否触发剪枝），就将该节点的信息存入表中，这样即使中途中断循环，已完成的节点数据也已经被保存。
3. 确定最佳着法：从已完成搜索的着法中，选出当前深度下估值最优的着法（符合Negamax的估值逻辑：对当前玩家而言，估值越高的着法越好）。
4. 返回合法着法：返回这个最优着法；如果极端情况下当前深度没有完成任何着法的搜索，就返回一个默认的合法着法（比如第一个生成的合法着法），绝对不能返回null——返回null会导致程序无法走棋甚至崩溃。

额外提示：迭代加深的回退逻辑 #

如果是在迭代加深的过程中触发超时，优先使用当前深度已完成部分的结果（因为更深的搜索估值通常更准确）；只有当当前深度完全没有完成任何搜索时，才回退到上一个完整深度搜索得到的最佳着法。

代码示例片段 #

def iterative_deepening_negamax(position, time_limit):
    best_move = None
    best_overall_value = -float('inf')
    current_depth = 1
    start_timestamp = time.time()

    while time.time() - start_timestamp < time_limit:
        current_best_move = None
        current_best_value = -float('inf')
        legal_moves = generate_legal_moves(position)

        for move in legal_moves:
            # 2a位置：检测时间是否耗尽
            if time.time() - start_timestamp >= time_limit:
                break  # 终止着法循环，不再处理剩余着法

            # 执行着法并调用Negamax
            new_pos = apply_move(position, move)
            move_value = -negamax(new_pos, current_depth - 1, -float('inf'), float('inf'), transposition_table)

            # 更新当前深度的最佳着法
            if move_value > current_best_value:
                current_best_value = move_value
                current_best_move = move

        # 更新全局最佳着法（如果当前深度有有效结果）
        if current_best_move is not None:
            best_move = current_best_move
            best_overall_value = current_best_value

        current_depth += 1

    # 确保返回合法着法，兜底处理极端情况
    return best_move if best_move is not None else legal_moves[0] if legal_moves else None

（注：negamax函数内部需实现置换表的写入逻辑，每次完成节点搜索后就将节点信息存入表中）

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