击败minimax对手
我必须创建一个人工智能，它必须与其他人工智能竞争。
两个人工智能将在相同的硬件上运行，具有相同的处理时间和内存量。我知道对手AI将使用带有alpha beta剪枝的极大极小算法。
现在我的问题是--有什么方法可以击败这样的对手？如果我自己使用minimax -那么两个AI都能完美地预测对方的走法，游戏会根据游戏的固有属性(第一步获胜等)来解决问题。
显而易见的解决方案是以某种方式提前看到可能的移动，这将允许更好的评估-因为处理器时间是相同的，我不能评估到更深的深度(假设相反的AI代码同样优化)。我可以使用预计算树来获得额外的优势，但如果没有超级计算机，我肯定无法“解决”任何重要的游戏。
有意识地选择一个非最优节点是否有一定的价值？这可能会导致对手的CPU时间惩罚，因为他们必须返回并重新评估树。这会给我带来惩罚，因为我必须评估极小极大树+ alpha beta，以查看alpha beta将修剪哪些节点，而不会获得任何直接好处。
针对这样的对手进行优化的其他策略是什么？
回答 2
Stack Overflow用户
发布于 2013-03-30 02:04:34
首先，选择非最佳路线没有任何价值。假设你的对手会打得最好(这是极小极大搜索的一个基本假设)，你的对手会利用这个错误采取行动。一个好的游戏引擎将有一个散列的反驳表项，其中包含了你的错误的反击，所以你不会因为做出一个疯狂的举动而赢得时间。做出不好的动作可以让电脑对手更快地找到好的动作。
要认识到像奥赛罗这样的游戏的关键是，直到游戏后期你才能确定最优的走法是什么。这是因为搜索树几乎总是太大，无法详尽地搜索所有赢或输的位置，因此极小极大无法确定哪一步会导致胜利或失败。你只能启发式地决定在哪里停止搜索，任意地将这些节点称为“终端”，然后运行一个评估函数来猜测头寸的输赢潜力。
评估函数的工作是评估职位的价值，通常使用静态指标，无需进一步搜索博弈树即可计算。棋子数量，位置特征，终局桌面库，甚至对手心理都可以在这里发挥作用。通常，你在评估函数中投入的智能越多，你的引擎就会发挥得越好。但静态评估的重点是替换代价太高的搜索。如果您的评估函数做得太多或效率太低，它可能会变得比获取相同信息所需的博弈树搜索更慢。知道在评估函数中放入什么，以及何时使用静态评估而不是搜索，是编写一个好的游戏引擎的艺术的一大部分。
Stack Overflow用户
发布于 2013-03-30 12:33:13
有很多方法可以通过AB剪枝来提高标准的极大极小值。例如，杀手启发式尝试改善移动的顺序，因为AB的效率与有序的移动更好。
在chessprogramming.wikispaces.com上可以找到许多关于AB的不同搜索增强和变体的信息。
https://stackoverflow.com/questions/15697479
复制相似问题
腾讯云开发者
