极大极小值算法改进

theme: fancy

原文链接 Minimax Improvements -- 作者 Ofek Gila

在上一篇文章中，我们讨论了在 AI 游戏（主要是五子棋）中，应用 Minimax 算法。在本文中，我们将对该算法进行些改造。虽然它并不适用所有的游戏，但是它可能适用于一般的零和游戏，比如国际象棋，四子棋，跳棋等等...请注意，这些改进中的大部分都是针对特定的游戏。

无关移动

一些零和游戏中，在极大极小值搜索算法应用过程中，有些移动是可以跳过的。比如，在五棋子或者 othello 游戏中，在棋盘上不靠近其他棋子的方格中下子将是糟糕的举动，因此会被跳过，而不会导致搜索结果失败。

限制检查的移动次数

因为极大极小值算法的复杂度取决于分支因素 -- 即任何节点的子节点数量 -- 限制检查的移次数可以很有效地提升你的搜索效率。通常的做法是基于深度为 1 的评估函数得到的优化后的移动位置，进行所有可能移动的排序（评估函数主要是对移动前和移动后位置进行比较）。所以只是搜索前 n 个深度的最佳移动，而不是所有可能的移动。

检测强制移动

在大多数游戏中，存在强制移动的场景。强制移动情况可以分为两类，我将会拿国际象棋和五子棋来举例：

1. 强制防御

• 在国际象棋中，当国王 King 遇险时，玩家被迫以某种方式保卫国王。
• 在五子棋中，当一个玩家有四子相连并且只有一个开端，那么另一个玩家就要强迫关闭此开端。

2. 争取胜利

这个很简单 -- 当能争取到胜利，那就下该步。

• 在国际象棋中，轮到你时，如果你能威胁到对方的国王，那就抓住机会。
• 在五子棋中，轮到你时，如果你有四子相连并有一个开端，那么你就应该下子在开端并取得胜利。

在你的 minimax 函数执行这些动作之一后，你都可以简单结束游戏并返回游戏结果。不需要在该分支进一步搜索，因为游戏已经结束了。

争取胜利总是优先于防守。如果没有获胜的可能，并且你已经检测到强制防御动作，那么你只需要搜索强制移动就行 -- 不需要考虑其他步骤。

Alpha-Beta 剪枝

很经典，且很出名的优化极大极小值算法的是 alpha-beta 剪枝 算法。该算法允许你在运行极大极小值算法时跳过分支，该算法和原本极大极小值算法一样 -- 在同个深度找到相同的结果。该方法的本质是当它发现该分支比之前检查过的分支更糟糕的时候，就会退出该分支。

我强烈推荐你看看 Wikipedia page -- 这比我的解释好得多了。

游戏特定算法

在很多游戏中，minmax 在不单独使用时是最好的。强大的五子棋程序使用 Threat-Space Search 结合极大极小值算法实现。强大的国际象棋使用 alpha-beta 剪枝算法结合上述两种类型算法实现。简而言之 -- 考量下你的游戏并对你的游戏采用更有意义的方式进行搜索。这是我目前做的最复杂的改进。

复查你的代码

这看起来不应该在本文出现，但是你可以在你的函数方法中进行改进。在极大极小值算法中，评估函数总是被调用。如果有任何东西 -- 无论多么微不足道 -- 如果有任何提高它的效率，这是值得的。

如果你将上述步骤的内容应用到你的游戏中，你就创建了一个很强大的程序，它有可能打败人类。当然，如果你是编写 围棋(https://en.wikipedia.org/wiki/Go_(game%29) 游戏。那么，你应该考虑 Monte Carlo tree search 算法。我会在后面的文章中提到。谢谢你的阅读！

本文正在参加「金石计划 . 瓜分6万现金大奖」