在国际象棋的 Alpha-Beta 搜索中实现杀手启发式

Question

我理解杀手启发式背后的想法以及它为什么有帮助。我正在努力解决的是如何在 Alpha-Beta 搜索例程中实现它。特别是如何保证只先尝试兄弟节点的杀手级动作？伪代码会有很大帮助。

Answer 1

我将解决实施问题。要获得兄弟节点的杀手级移动，请使用这样的方案

killerMoves[ply][slot]

哪里ply是与根的距离（不是搜索深度），slot是您想要的杀手级移动次数。这确保首先尝试同级节点，因为同级节点位于同一层。

要在获得 beta 截止时插入杀手级移动，您可以将给定层的移动向右移动，可能会丢弃旧移动，然后插入新移动。通常，您不会将捕获或散列移动存储为杀手级移动，因为它们是通过其他机制排序的。

for (int i = killerMoves[ply].Length - 2; i >= 0; i--) 
    killerMoves[ply][i + 1] = killerMoves[ply][i];
killerMoves[ply][0] = move;

现在，当您执行移动排序时（在遍历移动列表之前），您可以确定移动是否是杀手级移动：

for (int slot = 0; slot < killerMoves[ply].Length; slot++) {
    int killerMove = killerMoves[ply][slot];

    for (int i = 0; i < movesCount; i++)
        if (moves[i] == killerMove) {
            // moves[i] is a killer move so move it up the list
            break;
    }
}

您不需要清除层或类似物的杀手级移动，因为杀手级移动很可能是在同一层出现的一系列相似位置上的良好移动。

由于另一个答案提出了它，您可能不需要执行严格的测试，因为杀手启发式在理论上是合理的。您可以试验您使用的杀手级移动的数量（2 或 3 是常态）以及它们相对于其他好的移动（例如捕获）的顺序。

Answer 2

在搜索树的许多部分，杀手棋可能是一个很好的反驳棋。因此，尝试其他职位的杀手锏可能是个好主意。

你可能为每个层有不同的杀手动作数组，并在进入（层）时清除（层+1）的数组，这将为你提供“仅限兄弟姐妹”的杀手。我想说，“+1”偏移量就像一个需要调整的参数：尝试清除 (ply+N) 的数组，看看哪里的性能最好（我猜增加 N 会改善情况）。

顺便说一句，评估引擎的性能是一项不同的、相当消耗资源的任务：通常一个引擎尝试解决一个测试套件，或者两个具有不同参数的引擎正在相互进行比赛（比赛应该足够长，例如100场比赛）以确定哪个更好。