<分区>
我想用深度优先搜索来解决极小极大问题;然而,为了让我的算法能够完成并始终有一个解决方案,我使用迭代 DFS(所以找到一层深的所有节点,然后是两层,然后是三层)。我希望能够在经过一定时间后中断搜索,但是,除了将我的递归算法转换为带有堆栈的迭代算法并每次检查时间之外,我似乎找不到其他好方法循环(这似乎效率低下)或将结束时间传递给所有递归调用并在每次调用开始时检查(这似乎比迭代更低效,甚至更复杂)。
除了 Java 8 源代码之外,我不希望使用任何其他库。
伪代码:
function negamax(node, depth, α, β, color)
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
return bestValue
function search()
depth := 0
bestValue := null
while (++depth > 0) // runs forever until interrupted
bestValue := negamax( rootNode, depth, -∞, +∞, 1)
return bestValue
function main()
search();