我的 Negamax 实施有问题吗？

Question

我正在尝试用 Rust 为我的国际象棋引擎编写一个简单的 negamax 算法。我有一个非常简单的评估函数：

pub fn evaluate(&self) -> i32 {
    let mut eval: i32 = 0;

    for piece_type in PType::PIECE_TYPES {
        eval += (
            self.bitboards[piece_type, Col::White].count_ones() as i32 - 
            self.bitboards[piece_type, Col::Black].count_ones() as i32
        ) * piece_type.value();
    }

    eval
}

这是我的 negamax 实现：

fn negamax(pos: &mut Position, depth: u32, piece_colour: Col) -> i32 {
    let mult = match piece_colour {
        Col::Black => -1,
        Col::White => 1
    };

    if depth == 0 {
        return pos.evaluate() * mult
    }

    let mut best_so_far = -9999;

    let legal_moves = movegen::legal_moves(pos, piece_colour);

    for child in legal_moves {
        pos.make_move(child);
        best_so_far = std::cmp::max(best_so_far, negamax(pos, depth - 1, piece_colour.inverse()));
        pos.unmake_move(child);
    }

    -best_so_far
}

其中很多内容来自 Negamax 算法的维基百科伪代码。然而，在深度 5 的下一个位置，为白方生成的最佳着法是 Nxd3，而应该是 Nb7 来分出皇后和国王，然后在下一步中捕获皇后（是的，我的着法生成器确实考虑了分叉）。

我感觉我的 Negamax 实现有问题，但我不知道是哪里。

Answer 1

您遵循的 Wikipedia article 中给出的伪代码是错误的：depth == 0 和 depth > 0 之间存在差异。在depth == 0的情况下，return是从当前玩家的角度进行的评价。但是对于depth > 0，由于最后的否定，所以return是从对方玩家的角度来评价的。当从深度 1 到 0 时，这会导致不正确的结果。

要解决这个问题，否定应该在递归调用之后立即完成，而不是在 returning 时完成。请注意，这是它在 alpha-beta 修剪变体的伪代码中完成的方式，这似乎是正确的。

您的代码中还有一些其他问题：

你没有发现僵局。当前，当没有合法的移动时，您 return -9999（假设您先进行上述修复），这可能表明当前玩家已死。但另一种可能性是僵局，其得分应为 0。
所有“N 位交配”的分数都为 9999，这意味着 AI 不会急于交配，可能只会重复动作。解决这个问题的一种方法是给“mate in N”打分 9999-N。

我的 Negamax 实施有问题吗？

Is there a problem with my Negamax implementation?

chess

rust

negamax