何时终止使用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)
}

当然,当我知道游戏中的移动总数时,我可以将其depth < numberOfMovesLeft用作上限.但是,如果没有给出这些信息,我什么时候才能知道另一次使用negamax的调用没有比之前的运行更好？我需要在算法中做些什么改变？

Answer 1

简短的回答是:当你的时间用完时(换位表与答案/问题无关)

在这里,我假设您的评估函数是合理的(给出了良好的位置近似值).

将迭代加深与alpha beta相结合的主要想法如下:让我们假设您有15秒的时间来提出最佳动作.你能搜索多远？我不知道,也没有人知道.您可以尝试搜索,直到depth = 8找出搜索在1秒内完成(因此您可以使用14秒的时间).通过反复试验,您发现可以depth = 10在13秒内获得结果.所以你决定一直使用它.但是现在出现了一些非常糟糕的错误(你的alpha版本修剪不够好,有些位置需要花费太多时间来评估)并且你的结果在15秒内没有准备好.所以你要么随机移动,要么输掉游戏.

所以这永远不会发生,好好准备一个好的结果.所以你做了以下几点.获得最佳结果depth=1并存储它.找到最佳结果depth=2,并覆盖它.等等.不时检查剩余的时间,如果它真的接近时间限制 - 返回你最好的举动.

现在你不需要担心时间,你的方法将给你到目前为止找到的最好的结果.通过所有这些不同子树的重新计算,您只会浪费一半的资源(如果您检查整个树,但在alpha-beta中,您很可能不会).另外一个优点是,现在您可以在每次深度迭代中对从最佳到最差的移动进行重新排序,从而使修剪更具攻击性.