我的Negamax实现有问题吗？

Question

我试图写一个简单的否定算法在锈蚀我的象棋引擎。我有一个非常简单的评估功能：

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
}

下面是我的否定实现：

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

您所遵循的维基百科文章中给出的伪代码是错误的：depth == 0和depth > 0之间存在差异。在depth == 0的情况下，它从当前玩家的角度返回评估。但是对于depth > 0，由于最后的否定，它会从其他玩家的角度返回评估结果。这将导致从深度1到0的不正确结果。

要解决这个问题，应该在递归调用之后立即执行否定操作，而不是返回时。请注意，这是为alpha-beta剪枝变量的伪代码所做的，这似乎是正确的。

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

• 你不会发现僵局的。当前，当没有合法的动作时，您返回-9999 (假设您首先进行了修复)，这可以指示当前的播放器已被选中。但另一种可能是僵局，它应该有0的分数。
• 所有“N”位置的“配偶”都有9999的相同分数，这意味着AI不会急于交配，可能只会重复移动。解决这一问题的一种方法是给"mate in N“一个9999-N的分数。