如果对手在 minimax 中没有最佳发挥会发生什么?

人工智能 强化学习 极小极大
2021-11-17 22:06:26

我刚刚读了一篇关于极小极大算法的文章。当你设计算法时,你假设你的对手是一个完美的玩家,即他打得最好。

让我们考虑一下国际象棋游戏。如果对手打得非理性或次优怎么办?你还有保证会赢吗?

1个回答

如果对手打得非理性或次优怎么办?你还有保证会赢吗?

如果您的搜索深度足以保证在所有情况下都能获得最佳发挥,那么可以。最佳比赛是对手的决定对您的代理人造成的影响最小。事实上,如果对手犯了错误,通常可以使搜索更容易/更快,并且代理会更令人信服地获胜。

这可能意味着您可能采取的优化措施——例如,修剪导致任一玩家做出非最佳决策的游戏树段——可能没有那么有用。如果您在移动之间保留一些部分游戏树或缓存分支评估以帮助加快代理速度,这可能会影响决策时间。

像国际象棋这样复杂的游戏的实际最优代理是不可能的。在这些游戏中,您不会有一个真正最优的代理,而是近似最优的。当极小极大搜索不能强制最终游戏获胜时,您将依靠一些启发式方法来指导极小极大搜索。如果对手设法将游戏控制到启发式不准确的状态,他们可能会导致极小极大搜索失败并误导您的代理犯错误。

如果您实施了树缓存机制以提高性能并通过限制计划时间使系统可玩,那么效果的组合也是可能的 - 例如,您将计算机搜索时间限制为最多 3 秒 - 非理性的对手可能会导致您的代理的性能下降到它也开始犯错误的地方。这是否足以让聪明的对手利用它并击败能够以其他方式玩“完美”游戏的智能体取决于游戏的细节,以及智能体对“完美”的衡量范围有多窄。

一个极端的情况可能是一个智能体已经记住了一个完美的游戏(通过两个玩家预先计算的完美动作的游戏中的任何状态在单个目标上的任何状态得分高启发式),否则启发式很差 - 一次状态偏离了它可以直接评估的状态,智能体将受到其搜索已完成游戏胜利的能力的限制,并且可以很容易地被更聪明的对手操纵到超出其搜索深度的失败位置。

在实践中,编码良好的代理不会受到这种影响的太大影响。如果你犯了一个错误,或者在与 Stockfish 比赛时尝试随机可能是错误的举动以试图混淆代理,你失败。