Minimax alpha-beta 剪枝深度
Minimax alpha-beta pruning depth
我已经实现了一个 connect 4 AI 来为我的 class 参加锦标赛。我已经通过 alpha-beta 修剪实现了深度受限的 minimax。我们被允许给出一个深度作为比赛的论据。我的程序会走一步，然后另一个学生会走一步，这样一直持续到有赢家为止。也是修改后的连4，将6×7棋盘上的42个点全部填满，每4个连成一个点，点数多者为胜。
我的问题是关于 alpha-beta 修剪。我们的动作必须花费 "about 1 second"，所以任何低于 2 秒的时间都应该没问题。 运行 我的程序没有 alpha-beta 修剪允许在深度 6 移动大约 1.3 秒或更少。深度 7 是不可接受的。现在，有了 alpha-beta 修剪，我能保证我可以改变我的深度来更深吗？我平均知道它会让我更深入，但我相信在最坏的情况下，什么都不会被修剪，我会超过时间限制。这是正确的吗？
这是正确的：在最坏的情况下，alpha-beta 和 minimax 一样慢。
但这种情况发生的可能性很小。要优化 alphabeta 并防止出现该问题，请在 google 上搜索 "move ordering alpha beta"。
如果你必须在时间限制内停留，我建议使用迭代加深（搜索深度 1, 2, ..., x）。由于指数爆炸，这应该不是问题。如果您的程序用完了时间，只需播放您用之前的搜索深度计算出的着法。
我已经实现了一个 connect 4 AI 来为我的 class 参加锦标赛。我已经通过 alpha-beta 修剪实现了深度受限的 minimax。我们被允许给出一个深度作为比赛的论据。我的程序会走一步，然后另一个学生会走一步，这样一直持续到有赢家为止。也是修改后的连4，将6×7棋盘上的42个点全部填满，每4个连成一个点，点数多者为胜。
我的问题是关于 alpha-beta 修剪。我们的动作必须花费 "about 1 second"，所以任何低于 2 秒的时间都应该没问题。 运行 我的程序没有 alpha-beta 修剪允许在深度 6 移动大约 1.3 秒或更少。深度 7 是不可接受的。现在，有了 alpha-beta 修剪，我能保证我可以改变我的深度来更深吗？我平均知道它会让我更深入，但我相信在最坏的情况下，什么都不会被修剪，我会超过时间限制。这是正确的吗？
这是正确的：在最坏的情况下，alpha-beta 和 minimax 一样慢。
但这种情况发生的可能性很小。要优化 alphabeta 并防止出现该问题，请在 google 上搜索 "move ordering alpha beta"。
如果你必须在时间限制内停留，我建议使用迭代加深（搜索深度 1, 2, ..., x）。由于指数爆炸，这应该不是问题。如果您的程序用完了时间，只需播放您用之前的搜索深度计算出的着法。