迭代深化和移动排序

Question

据我了解，在实施迭代深化时，应该使用一个深度的最佳移动来对更高深度的移动进行排序。我对此有一个问题：假设我在深度 n 得到的移动 m 作为我的最佳移动，那么当在深度 n + 1 搜索时，移动排序者是否应该只优先考虑 [=13] =] 在搜索的最高级别或在移动 m 合法的每个级别？

我目前实现的迭代深化：

搜索：

pvLine = None
for depth in range(1, self.maxDepth):
    self.auxSearch(board, depth, initalHash)
    
    # find the principal variation from the TT
    pvLine = self.getPVLine(board, initalHash)

    bestMove = pvLine[0][0] 
    bestValue = pvLine[0][1]

    self.ordering.setBestMove(bestMove, depth + 1)
    print(f'{depth=} | {bestValue=} | {bestMove=} | {pvLine=}')

return pvLine

移动顺序：

if((move, depth) == self.bestMove):
    priority += self.BESTMOVE_BONUS

setBestMove函数：

def setBestMove(self, move: chess.Move, depth: int) -> None:
    self.bestMove = (move, depth)

self.BESTMOVE_BONUS是一个非常大的数字，所以这一步棋的优先级最高。

目前，我正在确保移动排序器仅优先考虑当前搜索的最高级别的先前较浅搜索的最佳移动。不知道我的做法对不对？

Answer 1

移动排序将为您提供比没有排序更快的算法，并且相当容易实现。您可以在这里阅读更多相关信息：https://www.chessprogramming.org/Move_Ordering.

我建议你从现在开始做，把上一次迭代中最好的一步放在第一位。最佳着法（或最佳着法顺序，“主要变化”）始终是从先前深度开始的着法。因此，如果您从深度 3 获得一系列移动 a1、b1 和 c1，那么在深度 4，您将首先尝试深度 1 的 a1、深度 2 的 b1 和深度 3 的 c1。

其次，您应该尝试使用 MVV-LVA 经常发现的良好的捕捉动作。用兵俘虏皇后通常是好棋，但如果兵受到保护，反之则可能很糟糕。

其他容易实施的技术是杀手招式和历史招式，也可以在上面的 link 中找到。

迭代深化和移动排序

Iterative deepening and move ordering

python

chess

artificial-intelligence

iterative-deepening