1

问题

我正在尝试使用带有alpha-beta-pruning的negamax算法来解决完美信息零和游戏（如滴答声或国际象棋） 。目标是证明一名球员是否可以强制获胜或平局。这意味着没有深度限制，但算法总是评估游戏树，直到有赢/平局。

我花了数周时间优化我的代码以适应我的特定游戏，并将其缩短为几天的运行时间。但问题就在这里：

由于 alpha-beta 修剪，极小极大算法的运行时间是高度不可预测的。我不知道它会在接下来的 5 分钟内完成还是再运行 5 周，直到我真正模拟它为止。我希望能够预测剩余的运行时间，而不是偏离几个数量级。

到目前为止我尝试了什么

我正在记录所有子和子子分支的结果，最多5*子分支，以及我的机器模拟它们所花费的时间。然后我只是假设同一级别的职位需要相同的时间来评估并收工。这些预测有时会偏离10 倍或更多。

我还查看了记录的数据，看看我的假设是否成立。评估5* 子分支0.01s所需的时间在180s. 这就是为什么我的预测不正确的原因。谁会猜到。

我的问题

正如我想象的那样，这将适用于 minimax 的所有实现：

  1. 是否有更复杂的算法可以准确预测带有 alpha-beta-pruning 的 minimax-algorithm 的剩余运行时间？还是极小极大只是设计不可预测的？

  2. 如果是这样，它们是如何工作的？

4

1 回答 1

1

我花了很多时间研究 Negamax算法，我强烈建议您切换到这些算法。它将给出与 Minimax 相同的结果，但更容易调试和进一步优化，因为它只是代码的一半。

我对您要解决的游戏一无所知，但即使是最复杂的游戏，我认为如果没有超级计算机也无法实现。不过，要回答您的问题：

  1. 带有 alpha-beta 修剪的 Minimax 高度依赖于您尝试移动的顺序（使用棋盘游戏术语）。您想首先尝试最好的移动，这在国际象棋中通过排序可能的移动功能来完成，例如捕获移动高于易位。

    您还可以根据您要解决的问题使用不同的技术进一步优化算法。例如，如果同一位置可以出现在另一个分支中，则换位表。

  2. 我们需要更多地了解您尝试解决的游戏，以了解哪种算法最有效。

最后的话：如果你想知道需要多长时间才能解决以及一段时间后你已经走了多远，我建议你使用迭代深化。这也将加快您的搜索速度，因为您可以先尝试先前迭代中的最佳猜测，从而在下一次迭代中获得更快的 beta 截止：

for depth in range(1, inf):
    score = minimax(alpha, beta, depth....)
    time = elapsed_time()

现在您可以打印每个深度的经过时间，并查看它在特定时间段内的距离。如果您的优化产生任何结果，这也很好测量。由于 Minimax 树对于每个深度都呈指数增长，因此您可以了解下一个深度需要多长时间。

因此，如果您知道赢/平/输需要多少步，您可以很容易地估计通过这种技术是否有可能。

希望我说清楚，英语不是我的母语 :) 如果有不清楚的地方，请随时在评论中提问。

于 2021-01-05T12:15:07.343 回答