修复国际象棋Negamax算法中的Alpha-Beta剪枝错误

问题核心 #

在FEN局面1R6/Pn6/K6p/7P/8/4NNp1/6P1/7k w - - 0 1、搜索深度7时，引擎误判多个走法为强制将杀（仅a7a8N是有效将杀）。移除Alpha-Beta剪枝的if alpha >= beta: break可修复，但性能暴跌（单次搜索超10分钟），需保留剪枝并修正错误。

错误原因分析 #

1. 置换表（TT）未前置查询：代码仅在退出negamax时存储局面信息，未在进入时查询复用，导致重复计算且错误结果无法被修正。
2. 走法排序效率低下：仅简单将升变、吃子走法优先，未使用杀手走法、MVV-LVA等启发式排序，导致逃脱将杀的走法被排在后面，Alpha-Beta剪枝可能过早截断正确走法的搜索。
3. 将杀得分与剪枝的交互问题：将杀得分依赖搜索层数（ply），但剪枝时未考虑该差异，可能错误将非将杀局面的得分判定为将杀。

修复步骤 #

1. 前置查询置换表 #

在negamax函数开头添加TT查询逻辑，复用已计算的局面结果，避免重复计算和错误传播：

def negamax(self, board: Board, depth: int, alpha: float, beta: float, ply: int = 0) -> float:
    # 优先查询置换表
    tt_entry = self.tt.get(board.zobrist)
    if tt_entry and tt_entry["depth"] >= depth:
        return tt_entry["value"]
    
    # 原生成走法、排序逻辑...

2. 改进走法排序逻辑 #

加入杀手走法（记录非吃子的高价值走法）和MVV-LVA（吃子价值排序），让更可能逃脱将杀的走法优先被搜索，提升Alpha-Beta剪枝的准确性：

class Engine:
    def __init__(self):
        self.tt = {}
        self.killers = [[None, None] for _ in range(64)]  # 每层存储2个杀手走法

    def move_value(self, move: Move, board: Board, ply: int) -> int:
        # 杀手走法优先级最高
        if move == self.killers[ply][0]:
            return 0
        if move == self.killers[ply][1]:
            return 0
        # 升变走法次之
        if move.prom:
            return 1
        # 吃子走法用MVV-LVA排序
        elif move.capture:
            victim_vals = {"p":1, "n":3, "b":3, "r":5, "q":9, "k":0}
            attacker_vals = {"p":1, "n":3, "b":3, "r":5, "q":9, "k":0}
            victim_val = victim_vals[board.board[move.to].lower()]
            attacker_val = attacker_vals[board.board[move.fr].lower()]
            return 100 + victim_val - attacker_val
        # 普通走法优先级最低
        return 2

    def negamax(self, board: Board, depth: int, alpha: float, beta: float, ply: int = 0) -> float:
        # ... 前置TT查询 ...
        
        moves = move_gen(board)
        # 传入board和ply进行排序
        moves = sorted(moves, key=lambda x: self.move_value(x, board, ply))
        
        # ... 后续逻辑 ...
        
        for move in moves:
            # ... 走法生成、递归搜索 ...
            
            if value >= best_value:
                # 更新杀手走法（仅非吃子、非升变走法）
                if not move.capture and not move.prom:
                    if move != self.killers[ply][0]:
                        self.killers[ply][1] = self.killers[ply][0]
                        self.killers[ply][0] = move
                best_value = value
                best_move = move
            
            # ... 剪枝逻辑 ...

3. 验证局面状态正确性 #

确保board.make(move)和board.unmake(move)完全正确更新局面，包括zobrist哈希值、棋子位置、将军状态等。错误的局面状态会导致TT存储错误信息，进而传播误判。

4. 修正将杀得分的边界处理 #

确保将杀得分与正常评估值拉开足够差距（比如MATE_SCORE设为100000，远高于最大评估值~2000），避免剪枝时混淆将杀得分和正常评估值：

# constants.py中定义
MATE_SCORE = 100000

修复效果验证 #

应用上述修改后，引擎会优先搜索逃脱将杀的走法，Alpha-Beta剪枝不会过早截断正确路径，同时借助置换表提升搜索效率。在目标局面下，引擎仅会判定a7a8N为有效将杀走法，且搜索耗时保持在可接受范围。

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