击败一个极小极大的对手
我必须创建一个AI，它必须与其他AI进行竞争。
两个AI将在相同的硬件上运行，具有相同数量的处理时间和内存。 我知道对手AI将使用alpha beta修剪的minimax算法。
现在我的问题是 - 击败这样的对手有哪些方法？ 如果我自己使用minimax - 那么AI就完全预测对方的动作，并根据游戏的固有属性（首先移动胜利等）来解决游戏。
明显的解决方案是以某种方式进一步提前考虑可能的更好的评估方法 - 因为处理器时间是相同的，我无法以更高的深度评估（假设相反的AI代码被同等优化）。 我可以使用预先计算的树来获得额外的优势，但是如果没有超级计算机，我当然无法“解决”任何不平凡的游戏。
在故意挑选一个非最佳节点（如alpha beta将会修剪的节点）方面是否有一些价值？ 这可能会对对手造成CPU时间损失，因为他们必须返回并重新评估该树。 它会对我造成惩罚，以及我不得不评估最小最大树+ alpha测试版，以查看哪些节点alpha beta会修剪而不会获得任何直接益处。
针对这种对手进行优化的其他策略是什么？
首先，在选择非最佳游戏方面没有任何价值。 假设你的对手将会打出最佳状态（这是超级极小号搜索的一个基本假设），那么你的对手将会采取一种行动来利用这个错误。 一个好的游戏引擎会有一个散列反驳表条目，其中包含对你的错误的反制动作，所以你可以通过疯狂的举动来获得时间。 做出不好的动作可以让电脑对手更快地找到好动作。
用奥赛罗这样的游戏来实现的关键是，直到游戏后期你才能确定最佳的举措。 这是因为搜索树几乎总是太大而无法全面搜索所有赢得的或失去的位置，因此极小极小组无法确切地告诉您哪些移动会导致胜利或失败。 您只能启发式地决定停止搜索的位置，随意调用这些节点的“终端”，然后运行一个评估函数来猜测某个头寸的赢/输潜力。
评估职能的工作是评估一个职位的价值，通常使用静态指标，可以在没有进一步搜索游戏树的情况下进行计算。 棋子数量，位置特征，残局桌球基础，甚至是对手心理都可以在这里发挥作用。 您对评估功能的智能越强，通常发动机的性能越好。 但静态评估的重点在于取代那些成本太高的搜索。 如果你的评估函数做得太多或者效率太低，它可能会比获得相同信息所需的游戏树搜索慢。 知道在评估函数中放什么以及何时使用静态评估而不是搜索是编写好游戏引擎的很大一部分。
有很多方法可以通过AB修剪来提高标准极小极大值。 例如，杀手启发式试图改善秩序的动作，因为AB的效率在有序移动的情况下更好。
在chessprogramming.wikispaces.com上可以找到关于AB上不同搜索增强和变体的大量信息。
链接地址: http://www.djcxy.com/p/56325.html上一篇: Beating a minimax opponent
下一篇: Concurrently search a game tree using minimax and AB pruning. Is that possible?