5

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

4

2 回答 2

7

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

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 个）以及它们相对于其他好动作（例如捕获）的顺序。

于 2013-07-17T17:15:44.990 回答
0

在搜索树的许多部分中，杀手级的举动可能是一个很好的反驳举动。所以尝试其他位置的杀手锏可能是个好主意。

您可能对每个层有不同的杀手动作数组，并在进入 (ply) 时清除 (ply+1) 的数组，这将为您提供“仅限兄弟姐妹”的杀手。我会说“+1”偏移量类似于要调整的参数：尝试清除 (ply+N) 的数组，然后查看性能最佳的位置（我猜增加 N 会改善情况）。

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

于 2013-07-17T07:22:07.823 回答