如何判断在使用negamax alpha-beta剪枝和置换表的迭代加深算法中何时可以停止增加深度？以下是从维基页面获取的伪代码：

function negamax(node, depth, α, β, color) alphaOrig := α // Transposition Table Lookup; node is the lookup key for ttEntry ttEntry := TranspositionTableLookup( node ) if ttEntry is valid and ttEntry.depth ≥ depth     if ttEntry.Flag = EXACT         return ttEntry.Value     else if ttEntry.Flag = LOWERBOUND         α := max( α, ttEntry.Value)     else if ttEntry.Flag = UPPERBOUND         β := min( β, ttEntry.Value)     endif     if α ≥ β         return ttEntry.Value endif if depth = 0 or node is a terminal node     return color * the heuristic value of node bestValue := -∞ childNodes := GenerateMoves(node) childNodes := OrderMoves(childNodes) foreach child in childNodes     val := -negamax(child, depth - 1, -β, -α, -color)     bestValue := max( bestValue, val )     α := max( α, val )     if α ≥ β         break // Transposition Table Store; node is the lookup key for ttEntry ttEntry.Value := bestValue if bestValue ≤ alphaOrig     ttEntry.Flag := UPPERBOUND else if bestValue ≥ β     ttEntry.Flag := LOWERBOUND else     ttEntry.Flag := EXACT endif ttEntry.depth := depth  TranspositionTableStore( node, ttEntry ) return bestValue

这是迭代加深的调用代码：

while(depth < ?){    depth++;    rootNegamaxValue := negamax( rootNode, depth, -∞, +∞, 1)}

当然，如果我知道游戏中总共有多少步，我可以使用depth < numberOfMovesLeft作为上限。但如果没有提供这个信息，我如何知道再次调用negamax不会比之前的运行结果更好？我需要在算法中做哪些更改？

回答：

简短的回答是：当你用完时间（置换表与答案/问题无关）

这里我假设你的评估函数是合理的（能很好地近似位置）。

将迭代加深与alpha-beta结合的主要思想如下：假设你有15秒的时间来找到最佳的移动。你能搜索多深？我不知道，其他人也不知道。你可以尝试搜索到depth = 8，结果发现搜索只用了1秒（所以你浪费了可用的14秒）。通过反复试验，你发现depth = 10可以在13秒内给出结果。所以你决定一直使用它。但现在出了大问题（你的alpha-beta剪枝不够好，有些位置的评估花费了太多时间），结果在15秒内没有准备好。所以你要么随机移动，要么输掉比赛。

为了避免这种情况发生，最好有一个好的结果准备好。你可以这样做。获取depth=1的最佳结果并存储它。找到depth=2的最佳结果，并覆盖它。以此类推。时不时检查剩余时间，如果真的接近时间限制 – 返回你找到的最佳移动。

现在你不需要担心时间，你的方法会给出你迄今为止找到的最佳结果。通过重新计算不同的子树，你只浪费了一半的资源（如果你检查整个树，但在alpha-beta中你很可能不会这样做）。额外的优势是，现在你可以从最佳到最差重新排序每个深度迭代的移动，从而使剪枝更加激进。