0

我正在根据此处的伪代码使用 alpha/beta 转置表实现 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. 在移动循环的开始）时，正确的做法是什么？我是立即放弃（不更新换位表）还是只是打破循环（保存我所做的任何部分工作）？

目前，我在该点返回 null，表示搜索在“完成”该节点之前被取消（无论是通过尝试每一步还是通过 alpha/beta 切割）。null 被向上传播并向上传播，并且向上传播的每个节点都通过返回来保释，因此第 3 步永远不会运行。

本质上，我只在节点“完成”时将值存储在 TT 中。随着迭代深化，我不断看到的场景：

  1. 我很快就通过了 1-5 的深度，所以 TT 的深度 = 5，类型 = 精确条目。
  2. depth = 6 搜索需要很长时间，所以我放弃了。

我最终返回转置表中的最佳移动，这是我在深度 = 5 搜索期间找到的移动。问题是，如果我开始一个新的 depth = 6 搜索，感觉就像我从头开始一样。但是，如果我保存我发现的任何部分结果，我担心我会损坏我的 TT，可能是通过用不完整的深度 = 6 条目覆盖完成的深度 = 5 条目。

4

1 回答 1

2

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

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

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

于 2018-02-11T13:29:26.977 回答