tic-tac-toe - 是否可以使用 4 * 4 板井字游戏应用 Minimax 或需要 Alpha-Beta 修剪？

Question

我在 java 中实现了一个 3 * 3 Tic Tac Toe 游戏，仅应用 Minimax 算法。但是，当我将板尺寸更改为 4 * 4 时，程序似乎挂起。我想问我是否应该应用带有 alpha-beta 修剪的 Minimax 来解决这个问题，或者 Minimax 本身可以吗？

Answer 1

如果您尝试进行全深度搜索，则需要使用 alpha-beta。一个朴素的 4 x 4 搜索树有 16 个！或大约 21 万亿个节点。许多这些节点不需要搜索，因为另一方通过在下一步中获胜或创建一个迫使稍后获胜 2 层的位置来反驳祖先位置。Alpha-beta 将让您在不遍历它们的情况下切掉其中一些搜索空间。