egamax国际象棋算法：如何使用最终返回？

Question

我为象棋游戏做了一个负极算法，我想知道如何使用最终的棋盘值结果。我知道负极算法的最终回报代表了玩家采取最佳策略后的棋盘值，但这并不完全是有用的信息。我需要知道那一步是什么，而不是它的价值。

代码如下：

public int negamax(Match match, int depth, int alpha, int beta, int color) {
    if(depth == 0) {
        return color*stateScore(match);
    }

    ArrayList<Match> matches = getChildren(match, color);

    if(matches.size() == 0) {
        return color*stateScore(match);
    }

    int bestValue = Integer.MIN_VALUE;

    for(int i = 0; i != matches.size(); i++) {
        int value = -negamax(matches.get(i), depth-1, -beta, -alpha, -color);

        if(value > bestValue) {
            bestValue = value;
        }

        if(value > alpha) {
            alpha = value;
        }

        if(alpha >= beta) {
            break;
        }
    }

    return bestValue;
}

public void getBestMove(Match match, int color) {

    int bestValue = negamax(match, 4, Integer.MIN_VALUE, Integer.MAX_VALUE, color);

    // What to do with bestValue???

}

在确定bestValue后，我考虑重新评估当前匹配状态的子项。然后我遍历它们，找出其中哪个孩子的statecore等于bestValue。但这是行不通的，因为不管怎样，他们中的很多人都会有相同的状态分数，这是他们可以导致的结果。。。

Answer 1

我看得出你在做qsearch和alpha beta。您的算法是众所周知的，但缺少一个关键部分。

让我来概述一下国际象棋搜索的基本算法，它甚至适用于Stockfish（世界上最强的引擎）。

search(Position p) {

    if (leaf node)
        qsearch(p)

    if (need to do move reduction)
        do_move_reduction_and_cut_off(p)

    moves = generate_moves(p)

    for_each(move in moves) {            
        p.move(move)
        v = -search(p, -beta, -alpha)
        p.undo(move)

        store the score and move into a hash table

        if (v > beta)
           cutoff break;           
    }

这只是一个非常简短的草图，但所有国际象棋算法都遵循它。将您的版本与之进行比较，是否注意到您尚未执行p.move（移动）和p.undo（移动）？

基本上，传统的方法为给定的位置生成一个移动列表。循环遍历移动，播放并撤消它并搜索它。如果你这样做，你就确切地知道哪个移动会产生哪个分数。

还要注意将移动和得分存储到哈希表中的行。如果您这样做，您可以轻松地从根节点重建整个主要变体。

我不知道你的Java类Match里面到底有什么，但无论如何，你的尝试很接近，但不完全是经典的搜索方式。记住，你需要在搜索算法中给出一个位置对象，但你给了它一个匹配对象，这是错误的。