F-对抗搜索-人工智能(AI).ppt

对抗搜索和博弈Adversarial Search and Game Playing (要做出好的决策，就必须尊重你的对手)  RN: Chap. 6  博弈（如国际象棋、围棋）由于敌我双方交替行棋的相互影响，使得问题本身具有了不确定性 很多世纪以来，人类用博弈来挑战人的智能极限 近来，出现了许多成功的博弈程序，能够与人对弈 一些特别的设定 双人游戏，交替走棋，确定的环境，完全可观察，零和，时间限制 State space Initial state Successor function: 对于每一个状态能够执行哪些动作及相应得到的状态 默认情况下， 假设MAX和MIN交替走棋，且设定MAX先走第一步，也即初始状态 Terminal test: 分辨是否最终状态，如果是，那么MAX赢、输还是和？ 所有的状态都是完全可观察的 对手的变数 由于对手(MIN)的动作带来了问题的不确定性，这是我方(MAX) 做决策时需要考虑的问题 博弈 由于对手(MIN)的动作带来了问题的不确定性，这是我方(MAX) 做决策时需要考虑的问题 MIN 希望 MAX 失利 (反之亦然) 如果无视MIN的应对，那么MAX没有任何希望能够胜出 (对于 MIN亦然) 每一个回合，必须在有限的时间内做出行动决策 状态空间非常大：在有限的时间内只能对空间的一小块进行探索 博弈树Game Tree 博弈树Game Tree 选择一步走棋: 基本思想 将当前状态作为初始状态，建立一个深度为h的搜索树， h（horizon，称为视野）是在有限时间内能够考虑到的最大深度 对所有叶节点状态进行评价 由叶节点回推至根节点，选择其中最好的一个动作决策（假设对手MIN的应对总是给MAX带来最坏的结果） ? 极大极小算法 Minimax algorithm 评价函数Evaluation Function 函数 e: 状态 s ? 数值 e(s) e(s) 即为估计状态s对于MAX来说“好”的程度的启发式信息 e(s) 0 意味着状态s对于MAX来说是有利的(数值越大越有利) e(s) 0意味着状态s对于MIN 来说是有利的 e(s) = 0 意味着状态 s 是中立的 例子: Tic-tac-Toe 评价函数的构造 通常采用“特征”的加权和构造评价函数: 特征可能是 每种类型棋子的数量 可能的走棋数量 …… p133 值的回推 为什么使用回推值? 在每一个非叶节点N，回推值就是MAX到达深度时能够获得的最大值（总是认为对手MIN的应对是最好的） e(STATE(N))可以对节点N的状态”好”的程度进行估计，而回推值则是一个更好的估计 极大极小算法Minimax Algorithm 从当前状态（MAX走棋）开始，扩展博弈树到深度h 对博弈树的每一个叶节点计算评价函数值 由叶节点开始至根节点计算回推值: MAX节点取得其后继的最大评价值 MIN节点取得其后继的最小评价值 选择能够得到最大回推值的走棋 博弈过程 (MAX) 到达最终状态前重复以下步骤 采用极大极小方法选择一步走棋 按1的决策走棋 观察MIN的应对走棋 还能做得更好吗？ 是的 ! 能够做得更好 ! Example Example Example Example Example Example a - b 剪枝Alpha-Beta Pruning 采用深度优先方法探索博弈树 只要有可能就回推 a 和 b 的值 把那些不会改变最终决策的分支剪去 a - b 算法 当节点N以下的搜索完成（或剪枝中止）时，更新N的父节点的a或b值 当一个MAX节点N的a 值? N 的MIN祖先节点的b值，则节点 N 以下的搜索中止 当一个MIN节点N的b值? N 的MAX祖先节点的a 值，则节点 N 以下的搜索中止 Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example Example 剪枝让我们得了多少好处？ 考虑以下两种情况: 剪枝让我们得了多少好处？ 假设博弈树有着均一的分支因子b 极大极小检查O(bh) 个节点，这也是a－b的最坏情况 a－b 带来的好处最大，当: MAX节点的MIN子节点按照回推值递减顺序排列 MIN 节点的MAX子节点按照回推值递增顺序排列 a－b 检查O(bh/2) 个节点 [Knuth and Moor