artificial-intelligence - 在国际象棋的 Alpha-Beta 搜索中实现 killer 启发式

Question

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

Answer 1

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

killerMoves[ply][slot]

哪里 ply是与根的距离(不是搜索深度)和 slot是你想要的杀手级 Action 的数量。这确保首先尝试同级节点，因为同级节点位于同一层。

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

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 是常态)以及它们相对于其他好的移动(例如捕获)的顺序。