Negamax：取消搜索后如何处理 "partial" 结果？

Question

我正在基于伪代码 here 实现带 alpha/beta 转置 table 的 negamax，算法大致如下：

NegaMax():
1. Transposition Table lookup
2. Loop through moves
  2a. **Bail if I'm out of time**
  2b. Make move, call -NegaMax, undo move
  2c. Update bestvalue, alpha/beta but if appropriate
3. Transposition table store/update
4. Return bestvalue

我也在使用迭代加深，用逐渐增加的深度调用 NegaMax。

我的问题是：当我确定我运行超时时（2a。在移动循环的开头），正确的做法是什么？我是立即放弃（不更新换位 table）还是只是打破循环（保存我所做的任何部分工作）？

目前，我 return 在那一点上为空，表示搜索在 "completing" 该节点之前被取消（无论是尝试每一步还是 alpha/beta 切割）。 null 在堆栈中向上和向上传播，向上传播的每个节点都被 return 保释，因此第 3 步永远不会运行s.

本质上，如果节点 "completed"，我只将值存储在 TT 中。随着迭代的深入，我不断看到的场景：

我很快就通过了深度 1-5，所以 TT 的深度 = 5，类型 = 精确输入。
depth = 6 搜索耗时较长，所以放弃。

我最终return换位table中的最佳着法，这是我在depth = 5搜索时找到的着法。问题是，如果我开始新的 depth = 6 搜索，感觉就像是从头开始。但是，如果我保存找到的任何部分结果，我担心我会破坏我的 TT，可能是通过用不完整的 depth = 6 条目覆盖已完成的 depth = 5 条目。

Answer 1

如果搜索未完成，则分数不准确，可能不应添加到 TT。如果你有一个最好的棋步和它仍然是最好的并且分数没有显着下降，你可以玩那个。

另一方面，如果在深度 6 时你发现对手有 3 个队友（哎呀！）或者可以赢得你的皇后，你可能需要花费更多时间来尝试解决这个问题。

这会让你剩下的时间更少（如果有的话......），但时间稍微短一点可能比在剩余时间充足的情况下交配更好。 :-)

Negamax：取消搜索后如何处理 "partial" 结果？

Negamax: what to do with "partial" results after canceling a search?

chess

negamax