函数的 C++ 时间限制

Question

我正在尝试为我的 negamax alpha beta 算法实现时间限制，但我似乎无法弄清楚。我想要实现的是:开始计算着法，如果计算没有在 5 秒内完成，则返回此时的最佳着法。

我该怎么做？ negamax 甚至有可能吗？

negamax 的伪代码:

01 function negamax(node, depth, α, β, color)
02     if depth = 0 or node is a terminal node
03         return color * the heuristic value of node

04     childNodes := GenerateMoves(node)
05     childNodes := OrderMoves(childNodes)
06     bestValue := −∞
07     foreach child in childNodes
08         v := −negamax(child, depth − 1, −β, −α, −color)
09         bestValue := max( bestValue, v )
10         α := max( α, v )
11         if α ≥ β
12             break
13     return bestValue

如果需要，我可以添加我的 negamax 算法的 C++ 实现

Answer 1

我能看到的唯一困难是递归，但这不是真正的问题，只需使用当前时间调用它并在每次调用开始时检查耗时是否大于 5 秒:

01 function negamax(node, depth, α, β, color, startTime)
02     if (currentTime - startTime > 5sec) or depth = 0 or node is a terminal node
03         return color * the heuristic value of node

为方便起见，您可以使用包装器:

function negamaxWrap(node, depth, α, β, color)
    return negamax(node, depth, α, β, color, currentTime)

如何确保您获得最佳值(value)？当堆栈展开时，返回值仍将通过测试:

bestValue := max( bestValue, v )

因此您将获得目前找到的值的最大值。