我为班级的比赛实现了一个四子棋AI。我实现了带有alpha-beta剪枝的深度限制的Minimax算法。我们可以为比赛提供一个深度参数。我的程序会走一步，然后另一位学生会走一步，这样持续下去直到决出胜者。这是一个修改过的四子棋，6×7的棋盘上所有42个位置都被填满，每次连成4个即得一分，得分最多者获胜。

我的问题是关于alpha-beta剪枝。我们的每步操作必须在“大约1秒”内完成，所以2秒以内都是可以接受的。在没有alpha-beta剪枝的情况下，我的程序在深度6时每步操作大约需要1.3秒或更少。深度7是不可接受的。现在，使用alpha-beta剪枝，我能保证可以增加深度吗？我知道平均情况下它会让我搜索得更深，但我认为在最坏情况下没有任何剪枝，我会超过时间限制。这是正确的吗？

回答：

这是正确的：在最坏情况下，alpha-beta剪枝的速度和Minimax一样慢。

但这种情况发生的几率非常小。为了优化alpha-beta并防止这种问题发生，请在谷歌上搜索“move ordering alpha beta”。

如果你必须在时间限制内完成，我建议使用迭代加深（以深度1, 2, …, x进行搜索）。由于指数级的增长，这应该不是问题。如果你的程序超时了，就使用之前搜索深度确定的走法。