极小最大α-β剪枝深度

Question

我已经实现了一个连接4人工智能发挥在比赛为我的班级。我已经实现了一个深度有限的minimax与α-β剪枝。我们被允许给出一个深度作为比赛的论据。我的项目将采取行动，然后另一个学生将采取行动，这将继续，直到有一个赢家。这也是一个改进的连接4，6×7棋盘上的全部42个点位都被填满，每排4分都是一分，最多的就是胜利。

我的问题是关于α-β修剪。我们的动作需要“大约1秒”，所以任何低于2秒的动作都应该可以。运行我的程序，没有α-beta剪枝允许移动约1.3秒或更短的深度6。深度7是不可接受的。现在，随着α-β修剪，我能保证我可以改变我的深度去更深吗？我知道这会让我走得更深，但我相信在最坏的情况下，什么都不会被剪掉，而且我会超过时限。这是正确的吗？

Answer 1

这是正确的:在最坏的情况下，alpha-beta和minimax一样慢。

比特，发生这种情况的可能性很小。为了优化alphabeta并防止这个问题，在google上搜索“移动订购alpha beta”。

如果您必须停留在一个时限内，我建议使用迭代深化(搜索深度为1，2，…，x)。这不应该是一个问题，因为指数爆炸。如果你的程序没有时间了，只需按照你之前的搜索深度去做。