Chapter 6 Adversarial Search¶
- 对应于 "Artificial Intelligence - A Modern Approach (3rd Edition)" 中的 Chapter 5
- ADVERSARIAL SEARCH: GAME PLAYING (5.1~5.9)
博弈类型¶
博弈的形式化¶
- 多Agent环境: 每个Agent需要考虑 其它Agent的行动 及其对自身的影响
- 竞争环境: 每个Agent的 目标之间是有冲突 的
- 对抗搜索(博弈)同时考虑多Agent和竞争环境
- 人工智能中的“博弈”: 通常专指博弈论专家们称为有完整信息的、确定性的、轮流行动的、两个游戏者的 零和游戏
-
零和游戏: 参与博弈的各方，在严格竞争下，一方的收益 必然 意味着另一方的损失，博弈各方的 收益和损失相加总和永远为“零”(常量) ，双方不存在合作的可能
-
两人参与的游戏: MAX和MIN。MAX先行，轮流出招，直到游戏结束。结束时优胜者加分，失败者罚分
- 𝑆0: 初始状态，规范游戏开始时的情况
- PLAYER(𝑠): 处于状态𝑠的游戏者，定义 此时该谁行动
- ACTIONS(𝑠): 返回状态𝑠下的合法移动集合
- RESULT(𝑠, 𝑎): 转移模型，返回 状态𝑠下行动𝑎的结果 状态
- TERMINAL − TEST(𝑠): TRUE/FALSE，终止测试，游戏结束返回TRUE，否则返回FALSE。游戏结束的状态称为终止状态
- UTILITY(𝑠, 𝑝): 效用函数(目标函数或收益函数)，定义 游戏者𝑝在终止状态𝑠下的数值
- UTILITY(𝑠) 适用于两人游戏、零和博弈。因为: UTILITY(𝑠, 𝑝1) = −UTILITY(𝑠, 𝑝2)
博弈树¶
博弈树: 由初始状态、ACTIONS函数 和 RESULT函数 定义，其中结点是状态，边是移动
博弈中的优化决策¶
极小极大算法¶
思想: 给定一棵博弈树，最优策略可以通过检查每个结点的极小极大值(Minmax)来决定
- 终止结点 的极小极大值就是它自身的效用值
- 对于给定的选择，MAX喜欢移动到有极大值的状态，而 MIN喜欢移动到有极小值的状态
- 感觉像是分层的贪心，MIN-layer与MAX-layer交替
- 模拟运行过程：递归算法自上而下前进到树的结点，然后随着递归回溯通过搜索树把极小极大值 回传 （字底向上）
\(\alpha - \beta\) 剪枝¶
- 极小极大值搜索存在的问题: 必须检查的游戏状态的数量随着博弈进行呈指数级增长
- 𝛼-𝛽剪枝的思想: 尽可能消除部分搜索树——会剪掉不影响决策的分支，仍然返回和极小极大算法相同的结果
- 是深度优先的，所以任何时候只需要考虑树上某条单一路径上的结点
讲解链接见原书P142，我觉得讲解的非常清晰！
不完美的实时决策¶
添加 启发式评估函数 用于搜索中的状态，把非终止结点转变为终止结点。也就是按两种方式对极大极小算法或者 𝛼-𝛽算法进行修改
- 用估计棋局效用值的启发式评估函数EVAL取代效用函数UTILITY
- 用决策何时运用EVAL的截断测试 (CUTOFF-TEST) 取代终止测试
感觉类似于“截断搜索”
线性加权函数: EVAL 𝑠 = ∑l 𝑤i*𝑓i(𝑠)，𝑤i是权值，𝑓i(𝑠) 是状态𝑠的某个特征
随机博弈¶
期望极小极大¶
- 机会结点: 圆圈
- 每个分支标记骰子数及其出现概率
- 没有明确的极小极大值，只能计算棋局的期望极小极大值: 机会结点的所有可能结果的平均值
把 确定性博弈中的极小极大值 一般化为包含 机会结点的博弈的期望极小极大值 ，其中MAX和MIN结点的使用和以前完全一样
机会博弈中的评估函数¶
和极大极小值一样，期望极大极小值的近似估计可以通过在某结点截断搜索并对每个叶节点计算其评估函数来进行
- 𝛼 − 𝛽 剪枝不适用于期望极小极大值的 MAX/MIN 结点
- 𝛼 − 𝛽 剪枝仍然适用于机会结点