基础Alpha Beta剪枝算法评估结果异常问题求助

我正在用Python优化国际象棋引擎，在深度为4的条件下测试某局面（引擎执黑），发现当白兵从e6移动到e7、黑后从h1移动到h6时，局面被评估为黑方得69.5分——这显然错误，白方可在下一步升变，此局面应为白方大优。

深度1测试时评估函数表现正常，走子排序无误且能正确找到所有合法走法；移除剪枝后程序运行正常，确定问题出在剪枝逻辑。我已将Alpha Beta函数重写为国际象棋编程维基上的基础形式，但问题仍存在，求助排查原因。

我的Alpha-Beta实现 #

def search(self, depth: int, whiteTurn: bool, alpha: int, beta: int, baseDepth: int) -> float:
        if depth == 0:
            return self.evaluate(whiteTurn)
        moves = []
        squares = list(self.board.keys())
        # finding legal moves this turn
        if whiteTurn:
            for square in squares:
                # check for a piece
                if self.board[square] != '0' and self.board[square].isupper():
                    squareMoves = self.orderMoves(findLegalMoves(self.pythonBoard.legal_moves, square), square)
                    for move, score in squareMoves:
                        moves.append([ch.Move.from_uci(square + move), score])
            moves = [move[0] for move in sorted(moves, key=lambda x: x[1], reverse=True)]

        else:
            for square in squares:
                if self.board[square] != '0' and self.board[square].islower():
                    squareMoves = self.orderMoves(findLegalMoves(self.pythonBoard.legal_moves, square), square)
                    for move, score in squareMoves:
                        moves.append([ch.Move.from_uci(square + move), score])
            moves = [move[0] for move in sorted(moves, key=lambda x: x[1], reverse=True)]
        for move in moves:
            self.pythonBoard.push(move)
            fenboard = self.pythonBoard.board_fen()
            self.board = fenConverter(fenboard)
            evaluation = -self.search(depth - 1, not whiteTurn, -beta, -alpha, baseDepth)
            if depth == DEPTH:
                print(evaluation, '\n', self.pythonBoard)
            self.pythonBoard.pop()
            self.board = fenConverter(self.pythonBoard.board_fen())
            if evaluation >= beta:
                return beta
            if evaluation > alpha:
                if depth == DEPTH:
                    self.move = move
                    self.materialValue = evaluation
                alpha = evaluation
        return alpha

国际象棋编程维基的Alpha-Beta伪代码 #

int alphaBeta( int alpha, int beta, int depthleft ) {
   if( depthleft == 0 ) return quiesce( alpha, beta );
   bestValue = -infinity;
   for ( all moves)  {
      score = -alphaBeta( -beta, -alpha, depthleft - 1 );
      if( score > bestValue )
      {
         bestValue = score;
         if( score > alpha )
            alpha = score; // alpha acts like max in MiniMax
      }
      if( score >= beta )
         return bestValue;   //  fail soft beta-cutoff, existing the loop here is also fine
   }
   return bestValue;
}

评估函数实现 #

def evaluate(self, isWhite: bool) -> float:
        """
        evaluate evaluates the position
        """
        materialValue = 0
        squares = list(self.board.keys())
        if self.pythonBoard.is_stalemate():
            return 0
        if self.pythonBoard.outcome() != None:
            if self.pythonBoard.is_checkmate():
                return float('-inf')

        for square in squares:
            # if there's a piece on the square
            if self.board[square] != '0':
                name = self.board[square]
                color = findColor(name)
                moves = set()
                piece = Piece(name, color, 0, moves)
                if color == 'black':
                    if name == 'p':
                        vMap = pawnMap(square)
                    elif name == 'n':
                        vMap = knightMap(square)
                    elif name == 'b':
                        vMap = bishopMap(square)
                    elif name == 'q':
                        vMap = queenMap(square)
                    elif name == 'k':
                        if ((self.whitePieceCount['Q'] == 0 and self.whitePieceCount['R'] <= 1 and self.whitePieceCount['B'] + self.whitePieceCount['N'] <= 2) or
                            (self.whitePieceCount['B'] + self.whitePieceCount['N'] + self.whitePieceCount['R'] <= 2 and self.whitePieceCount['R'] <= 1)):
                            vMap = lateKingMap(square)
                        else:
                            vMap = earlyKingMap(square)
                    else:
                        vMap = rookMap(square)
                    materialValue += vMap.mapValue()
                if color == 'white':
                    row = int(square[1])
                    newRow = str(9 - row)
                    square = square[0] + newRow
                    if name == 'P':
                        vMap = pawnMap(square)
                    elif name == 'N':
                        vMap = knightMap(square)
                    elif name == 'B':
                        vMap = bishopMap(square)
                    elif name == 'Q':
                        vMap = queenMap(square)
                    elif name == 'K':
                        if ((self.blackPieceCount['q'] == 0 and self.blackPieceCount['r'] <= 1 and self.blackPieceCount['b'] + self.blackPieceCount['n'] <= 2) or
                            (self.blackPieceCount['b'] + self.blackPieceCount['n'] + self.blackPieceCount['r'] <= 2 and self.blackPieceCount['r'] <= 1)):
                            vMap = lateKingMap(square)
                        else:
                            vMap = earlyKingMap(square)
                    else:
                        vMap = rookMap(square)
                    materialValue += -vMap.mapValue()
                materialValue += piece.value * 10
        if isWhite:
            # materialValue += self.endGameEval(self.blackPieces, isWhite)
            return materialValue
        else:
            # materialValue -= self.endGameEval(self.whitePieces, isWhite)
            return -materialValue

关键背景说明 #

黑方棋子值为负，白方为正，因此黑方评估时返回-materialValue。

排查方向 #

1. 缺少宁静搜索（Quiescence Search）
   维基伪代码在深度为0时调用quiesce(alpha, beta)，而你的实现直接返回评估值。当局面存在吃子、升变等关键战术动作时，普通评估函数无法捕捉后续变化，会导致剪枝时错误截断搜索树——比如白兵e7升变是关键战术，深度4刚好在黑方走后结束搜索，没有继续搜索白方升变的后续，导致评估错误。

2. 剪枝返回值逻辑不一致
   维基伪代码中，beta截断时返回bestValue（当前找到的最优值），而你的代码直接返回beta。这属于fail-soft vs fail-hard的差异：

   • 维基是fail-soft：返回实际找到的最佳值（可能>=beta）
   • 你的实现是fail-hard：直接返回beta
     这种差异可能导致上层搜索收到错误的评估值，进而影响剪枝判断。

3. 评估函数的胜负判断错误
   评估函数中，当局面是将死时返回float('-inf')，但未区分胜负方：如果白方被将死，黑方应返回float('inf')，反之亦然。当前逻辑无论谁被将死都返回负无穷，会导致搜索时对胜负局面的评估完全错误，尤其是在剪枝时会错误地截断或保留分支。

4. 递归时的alpha/beta传递是否正确
   检查递归调用-self.search(depth - 1, not whiteTurn, -beta, -alpha, baseDepth)时，是否始终保持alpha和beta的对称性反转。另外，确认初始调用时的alpha/beta值是否正确（比如初始alpha=-inf，beta=inf）。

5. 走子生成的合法性验证
   虽然深度1测试正常，但在剪枝场景下，是否存在某些合法走法未被生成？比如白兵e7升变的所有可能（升变为后、车等）是否都被包含在合法走法列表中？如果升变走法未被生成，搜索时就不会考虑这个关键变化。

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