问题
我正试图使用negamax算法和阿尔法-贝塔修剪来解决一个性能信息零和游戏(如tick-tack-toe或国际象棋(。我们的目标是证明一名球员是否能取得胜利或平局。这意味着没有深度限制，但算法总是评估配子树，直到出现胜利/平局。
我花了好几个星期的时间来优化我的代码以适应我的特定游戏，并把它降到了几天的运行时间。但问题在于：
由于阿尔法-贝塔修剪，极大极小算法的运行时间是高度不可预测的。在我真正模拟它之前，我不知道它是在接下来的5分钟内完成还是再运行5周。我希望能够预测剩余的运行时间，而不会偏离几个数量级。
到目前为止我尝试了什么
我正在记录所有子和包含分支到5*子分支是假设同一级别的职位需要同样的时间来评估并到此为止。这些预测有时会偏离因子10或更大。
我还查看了记录的数据，看看我的假设是否成立。评估5*分支所需的时间在0.01s和180s之间变化。这就是为什么我的预测失败的原因。谁会相信呢。
我的问题
正如我所想象的，这将适用于minimax的所有实现：
-
是否有更复杂的算法可以准确预测具有α-β修剪的极小极大算法的剩余运行时间？或者，极小值只是设计上的不可预测
-
如果是，它们是如何工作的
我花了很多时间研究Negamax算法，我强烈建议您切换到该算法。它将给出与Minimax相同的结果，但更容易进一步调试和优化，因为它只是代码的一半。
我对你试图解决的游戏一无所知，但如果它是最复杂的，我想如果没有超级计算机，这是不可能的。不过，要回答您的问题：
-
具有alpha-beta修剪的Minimax在很大程度上取决于你尝试移动的顺序(使用棋盘游戏术语(。你想先尝试最好的招式，这在国际象棋中是通过对可能的招式功能进行排序来完成的，例如，捕捉比投掷更高的招式。
根据您试图解决的问题，您还可以使用不同的技术对算法进行更多的优化。例如，如果相同的位置可以出现在另一个分支中，则换位表。
-
我们需要更多地了解你试图解决的游戏，才能知道什么算法最有效。
最后一句话：如果你想知道解决问题需要多长时间，以及一段时间后你已经走了多远，我建议你使用迭代深度。这也会加快你的搜索速度，因为你可以先尝试前几次迭代中的最佳猜测，从而在下一次迭代中获得更快的测试截止时间：
for depth in range(1, inf):
score = minimax(alpha, beta, depth....)
time = elapsed_time()
现在，您可以打印每个深度的经过时间，并查看在特定时间段内经过的时间。如果您的优化产生了任何结果，这也很好地衡量了一下。由于Minimax树在每个深度上都呈指数级增长，你可以知道下一个深度需要多少时间。
因此，如果你知道一场胜利/平局/失利需要多少步，你就可以很容易地通过这项技术来估计这是否可能。
希望我能说清楚，英语不是我的母语：(如果有什么不清楚的地方，可以在评论中提问。