0

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

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 算法的 Wikipedia 伪代码。然而，在深度 5 的以下位置中，为白色生成的最佳着法是 Nxd3，此时应该是 Nb7 来分叉皇后和国王，然后在下一步行动中捕获皇后（是的，我的移动生成器确实考虑了叉子）。

有问题的立场

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

4

1 回答 1

2

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

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

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

  • 你没有发现僵局。当前，当没有合法移动时，您返回 -9999（假设您首先进行了上述修复），这可能表明当前玩家已被将死。但另一种可能性是僵局，它的得分应该是 0。
  • 所有“N 位交配”的分数都相同，都是 9999，这意味着 AI 不会急于交配，可能只是重复动作。解决此问题的一种方法是给“N 中的伴侣”评分 9999-N。
于 2021-10-07T23:35:43.407 回答