击败最小最大对手

Question

我必须创建一个与其他人工智能竞争的人工智能。

两种人工智能将运行在相同的硬件上，具有相同的处理时间和内存。我知道对手AI会用alpha beta剪枝的minimax算法。

现在我的问题是——有什么方法可以击败这样的对手？如果我自己使用极大极小——那么两个人工智能都可以完美地预测对方的移动，游戏会根据游戏的固有属性来决定(先移动者获胜等)。

显而易见的解决方案是，以某种方式进一步展望可能的举措，以便进行更好的评估——因为处理器时间是相同的，我无法进行更深层次的评估（假设相反的人工智能代码同样优化）。我可以使用预先计算的树来获得额外的优势，但如果没有超级计算机，我肯定无法“解决”任何重要的游戏。

故意选择一个非最佳节点是否有一些价值，例如 alpha beta 会修剪的节点？这可能会对对手造成 CPU 时间损失，因为他们必须返回并重新评估树。这会给我带来惩罚，而且我必须评估最小最大树 alpha beta，看看哪些节点 alpha beta 会在没有获得任何直接好处的情况下修剪。

针对这样的对手，还有哪些其他优化策略？

Answer 1

有很多方法可以通过 AB 修剪提高标准最小值。例如，研究了改进顺序移动的杀手启发式尝试，因为有序移动时 AB 的效率更高。

在chessprogramming.wikispaces.com可以找到很多关于AB的不同搜索增强和变化的信息。

Answer 2

首先，选择非最优的游戏路线没有任何价值。假设你的对手会以最佳方式玩游戏（这是极大极小搜索的基本假设），你的对手会利用这个错误采取行动。一个好的游戏引擎会有一个散列反驳表条目，其中包含对你错误的反击，所以你做一个疯狂的举动不会赢得任何时间。做不好的动作可以让电脑对手更快地找到好的动作。

像《奥赛罗》这样的游戏要意识到的关键是，你要到游戏后期才能确定最佳的移动方式。这是因为搜索树几乎总是太大，无法彻底搜索所有赢或输的位置，因此minimax无法确定哪些移动将导致胜利或失败。你只能试探性地决定在哪里停止搜索，任意地将这些节点称为“终端”，然后运行一个评估函数来猜测位置的输赢潜力。

评估功能的工作是评估一个位置的价值，通常使用静态指标，无需进一步搜索游戏树即可计算。计分、位置特征、比赛结束时的桌面，甚至对手心理都会在这里发挥作用。您在评估功能中投入的智能越多，通常您的引擎将发挥得越好。但静态评估的重点是替换搜索，这太贵了。如果您的评估功能做得太多或效率太低，它可能会比获得相同信息所需的游戏树搜索慢。在编写一个好的游戏引擎的艺术中，知道应该在评估函数中放入什么，以及何时使用静态评估而不是搜索是一个很大的部分。