0

我正在使用带有alpha-beta pruning的Negamax在搜索功能中实现搜索算法。但是，它经常错过强制将死。 （注意： “X 中的伴侣”计算整个回合，而“深度”和“移动”依赖于半个移动。）

例子

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

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

可能的原因

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

简化代码

我已经使代码的某些部分更易于阅读。（例如 remove 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;
}
4

1 回答 1

0

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

于 2021-06-22T08:48:38.837 回答