何时使用alpha-beta修剪和换位表终止迭代深化？

Question

如何知道何时可以停止增加使用negamax alpha beta修剪和换位表的迭代深化算法的深度？以下伪代码取自wiki页面：

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)
}

当然，当我知道游戏中的总移动次数时，我可以使用深度

Answer 1

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

在这里，我假设您的评估函数是合理的（给出了位置的良好近似值）。

将迭代深化与alpha beta相结合的主要思想如下：让我们假设您有15秒的时间来想出最佳移动。你能搜索多远？我不知道，也没有人知道。您可以尝试搜索到深度=8才发现搜索在1秒内完成（因此您放弃了可用的14秒时间）。通过反复试验，您发现深度=10在13秒内为您提供结果。所以您决定一直使用它。但是现在出了大问题（你的阿尔法贝塔修剪得不够好，有些位置需要太多时间来评估），你的结果在15秒内还没有准备好。所以你要么随机移动，要么输掉了比赛。

因此，这种情况永远不会发生，最好准备好一个好的结果。所以您执行以下操作。获取深度=1的最佳结果并将其存储。找到深度=2的最佳结果，并覆盖它。依此类推。不时检查还剩多少时间，如果它真的接近时间限制-返回您的最佳动作。

现在，您无需担心时间，您的方法将给出迄今为止您发现的最佳结果。通过对不同子树的所有这些重新计算，您只会浪费一半的资源（如果您检查整个树，但在alpha-beta中，您很可能不会）。另一个优点是，现在您可以在每个深度迭代中将移动从最好的位置重新排序到最差的位置，从而使修剪更具攻击性。