笔记人工智能：第5章《对抗搜索》

【笔记】人工智能 一种现代方法 人工智能 一种现代方法 第5章 对抗搜索

5.1博弈

对抗搜索：在竞争性环境下，各智能体之间存在的目标冲突特性使其演变为一种博弈形式。

博弈：指具有完备信息、确定性规则、轮流进行操作且由两名参与者构成的零和游戏。

剪枝：在构建搜索树的过程中，剔除那些对最终决策结果无实质影响的分支结构。

启发式评估函数：在未完成全面搜索的前提下，用于估算特定状态实际效用值的一种策略性函数。

5.2博弈中的优化决策

最佳解决方案：实现目标状态所需的一系列操作步骤

终止状态：某一方取得胜利

极大极小值：可视为存在两个参与者MAX与MIN，其中MAX倾向于选择具有最大值的路径，而MIN则偏好于选择最小值的路径，最终状态通过效用函数进行评估。MAX会选择具有最高极大极小值的终止状态。假设对手所做出的每一个决策均为最优选择。

5.2.1极小极大算法

递归算法按照自顶向下的方式持续深入，直至抵达树结构的末端节点，随后通过回溯机制在搜索树中将极小极大值逐层传递回初始位置。

理解：在每一步操作中，均以最小化对手所能获得的最大利益为决策依据。

5.2.2多人博弈时的最优决策

在多人博弈场景中，MINIMAX算法的应用存在局限性，因其最初设计用于两人博弈，此时一方的得分可直接反映另一方的得分，因此仅需采用单一数值