java - Negamax国际象棋算法: How to use final return?

Question

我已经为类似国际象棋的游戏制作了一个 negamax 算法，我想知道如何使用最终的棋盘值结果。我知道 negamax 算法的最终返回代表了玩家采取最佳行动后棋盘的值(value)，但这并不是有用的信息。我需要知道该移动是什么，而不是它的值(value)。

代码如下:

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后重新评估当前match状态的children。然后我遍历它们并找出其中哪些 child 的 stateScore 等于 bestValue。但那是行不通的，因为它们中的很多人无论如何都会有相同的 stateScore，这就是它们可以导致哪些重要......

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(move) 和 p.undo(move)？

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

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

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