（国际象棋）negamax 搜索缺少将死的问题

Question

我正在使用 Negamax 和 alpha-beta 修剪 在搜索函数中实施搜索算法。然而，它经常会错过被逼的将死。
（注意：“X 交配”计算整圈，而“深度”和“移动”依赖于半移动。）

例子

具有以下 FEN 的位置：1k1r4/pp1b1R2/3q2pp/4p3/2B5/4Q3/PPP2B2/2K5 b - - 0 1 有一个 Mate in 3（算法深度为 5）。它是 Qd1+、Kxd1、Bg4+、Kc1/Ke1（无关紧要）、Rd1#。

它可以从 1 步远的距离发现将死，但在更高的深度失败。

可能的原因

这可能是打字错误、误用 type，甚至是对方法的完全误解，因为所有这些都发生在以前。

简化代码

我已经使代码的某些部分更易于阅读。（例如，删除 std::，将多行变成函数）。
不过不应更改功能。

根调用

pieceMove searchBestMove (gameState currentState, int depth) {
//Calls the Negamax search
    pieceColor sideToMove = whoseTurnIsIt();
    
    vector<pieceMove> moveList = generateLegalMoves(currentState, sideToMove);
    
    pieceMove bestMove;
    signed int bestEval = numeric_limits<signed int>::max();
    
    for (const auto move : moveList) {
        signed int evaluation = negaMax(applyMove(currentState, move), numeric_limits<signed int>::min(), numeric_limits<signed int>::max(), depth - 1, 1);
        if (evaluation < bestEval) {
            bestMove = move;
            bestEval = evaluation;
        }
    }
    
    return bestMove;
}

搜索功能

signed int negaMax (gameState currentState, signed int alpha, signed int beta, int depth, int rootDepth) {
//Main Negamax search
    //Terminal node
    if (depth == 0) {
        return evaluates(currentState); //Replace this line with the one below to enable the extended search
        //return quiescenceSearch(currentState, alpha, beta); 
    }
    
    //Mate distance pruning
    signed int mateDistScore = numeric_limits<signed int>::max() - rootDepth;
    alpha = max(alpha, -mateDistScore);
    beta = min(beta, mateDistScore - 1);
    if (alpha >= beta) return alpha;
    
    vector<pieceMove> moveList = generateLegalMoves(currentState);

    //If no moves are allowed, then it's either checkmate or stalemate
    if (moveList.size() == 0) return evaluates(currentState)
     
    orderMoves(currentState, moveList);


    for (const auto move : moveList) {
        signed int score = -negaMax(applyMove(currentState, move), -beta, -alpha, depth - 1, rootDepth + 1);
        if (score >= beta) return beta; //Bata cutoff
        alpha = max(score, alpha);
    }
    
    return alpha;
}

扩展搜索

signed int quiescenceSearch (gameState currentState, signed int alpha, signed int beta) {
//Searches only captures
    //Terminal node
    int evaluation = evaluates(currentState);
    if (evaluation >= beta) return beta;
    alpha = max(alpha, evaluation);
    
    vector<pieceMove> moveList = generateCaptureMoves(currentState);

    //If no moves are allowed, then it's either checkmate or stalemate
    if (moveList.size() == 0) return evaluates(currentState);
    
    orderMoves(currentState, moveList);

    for (const auto move : moveList) {
        signed int score = -quiescenceSearch(applyMove(currentState, move), -beta, -alpha);
        if (score >= beta) return beta; //Bata cutoff
        alpha = max(score, alpha);
    }
    
    return alpha;
}

Answer 1

我认为你需要在“negaMax”中当深度为0时调用函数“quiescenceSearch”。您还需要在“quiescenceSearch”中检查“检查”以及捕获，因为它们不是安静的移动。此外，Matedistance 修剪仅在位置被正确评分时才起作用（https://www.chessprogramming.org/Mate_Distance_Pruning#Mating_Value）。可能正在检查您的评估函数是否正确评估也可能有所帮助。

（国际象棋）negamax 搜索缺少将死的问题

(Chess) Problem with negamax search missing checkmate

c++

chess

minimax

negamax

例子

可能的原因

简化代码

根调用

搜索功能

扩展搜索