对抗性搜索与游戏理论

1. 相关概念

在传统搜索问题中，智能体可以使用搜索算法确定最佳计划并直接执行以达到目标。但在对抗性环境中，智能体面临一个或多个试图阻止其达成目标的对手。由于无法确定性地预知对手的策略和反应，传统搜索算法不再适用，我们需要新的算法类别来解决对抗性搜索问题，也就是游戏。

2. 确定性零和游戏

$a.$ 相关概念

确定性零和游戏具有以下特点：

• 确定性：动作的结果是确定的，没有随机性
• 零和：一方的收益直接等于对方的损失，反之亦然
• 可以用单一变量值来定义，一方试图最大化此值，另一方试图最小化此值

3. 策略 vs 计划

对抗性搜索返回的不是计划（plan），而是策略（strategy）或政策（policy）。策略会根据智能体和对手的当前配置推荐最佳可能的移动。

这种算法具有通过计算产生行为的特性：相对简单且广泛可推广的计算，能够内在地产生同队智能体间的合作以及对对抗智能体的"智胜"。

4. 标准游戏形式化

标准游戏由以下要素定义：

• 初始状态：$s_0$
• 参与者：$Players(s)$ 表示轮到谁行动
• 动作：$Actions(s)$ 当前玩家的可用动作
• 转移模型：$Result(s,a)$ 执行动作后的结果状态
• 终止测试：$Terminal\text{-}test(s)$ 判断游戏是否结束
• 终止值：$Utility(s,player)$ 每个玩家在终止状态下的效用值