人工智能-博弈树的搜索.ppt

2 3博弈树搜索 20世纪60年代 研制出的西洋跳棋和国际象棋的博弈程序达到了大师级的水平 1958约翰 麦卡锡提出博弈树搜索算法1997年 IBM公司研制的 深蓝 国际象棋程序 采用博弈树搜索算法 该程序战胜了国际象棋世界冠军卡斯帕罗夫 1 概述 正在与深蓝下棋的卡斯帕罗夫 博弈问题特点 双人对弈 轮流走步 信息完备 双方所得到的信息是一样的 零和 即对一方有利的棋 对另一方肯定是不利的 不存在对双方均有利或无利的棋 1 概述 博弈的特性两个棋手交替地走棋 比赛的最终结果 是赢 输和平局中的一种 可用图搜索技术进行 但效率很低 博弈的过程 是寻找置对手于必败态的过程 双方都无法干预对方的选择 1 概述 2 Grundy博弈 下棋的双方是对立的 命名博弈的双方 一方为 正方 这类节点称为 MAX 节点 另一方为 反方 这类节点称为 MIN 节点 正方和反方是交替走步的 因此MAX节点和MIN节点会交替出现 2 Grundy博弈 Grundy博弈是一个分钱币的游戏 有一堆数目为N的钱币 由两位选手轮流进行分堆 要求每个选手每次只把其中某一堆分成数目不等的两小堆 例如 选手甲把N分成两堆后 轮到选手乙就可以挑其中一堆来分 如此进行下去 直到有一位选手先无法把钱币再分成不相等的两堆时就得认输 2 Grundy博弈 设初始状态为 7 MIN 建立问题的状态空间图 图中所有终结点均表示该选手必输的情况 取胜方的目标是设法使棋局发展为结束在对方走步时的终结点上 MIN先走 MAX必胜 2 Grundy博弈 结点A是MAX的搜索目标 而结点B C则为MIN的搜索目标 2 Grundy博弈 搜索策略要考虑的问题是 对MIN走步后的每一个MAX结点 必须证明MAX对MIN可能走的每一个棋局对弈后能获胜 即MAX必须考虑应付MIN的所有招法 这是一个与的含意 因此含有MAX符号的结点可看成与结点 2 Grundy博弈 对MAX走步后的每一个MIN结点 只须证明MAX有一步能走赢就可以 即MAX只要考虑能走出一步棋使MIN无法招架就成 因此含有MIN符号的结点可看成或结点 2 Grundy博弈 对弈过程的搜索图呈现出与或图表示的形式 实现一种取胜的策略就是搜索一个解图的问题 解图就代表一种完整的博弈策略 2 Grundy博弈 中国象棋 一盘棋平均走50步 总状态数约为10的161次方 假设1毫微秒走一步 约需10的145次方年 结论 不可能穷举 3 极小极大搜索过程 对各个局面进行评估评估的目的 对后面的状态提前进行考虑 并且以各种状态的评估值为基础作出最好的走棋选择 评估的方法 用评价函数对棋局进行评估 赢的评估值设为 输的评估值设为 平局的评估值设为0 评估的标准 由于下棋的双方是对立的 只能选择其中一方为评估的标准方 3 极小极大搜索过程 MAX节点和MIN节点 命名博弈的双方 一方为 正方 对每个状态的评估都是对应于该方的输赢的 例如 赢2个 输1个等 都是指正方的 正方每走一步 都在选择使自己赢得更多的节点 因此这类节点称为 MAX 节点 3 极小极大搜索过程 另一方为 反方 对每个状态的评估都是对应于对手的输赢的 例如 赢2个 输一个 其实是指自己输2个 赢1个的 反方每走一步 都在选择使对手输得更多的节点 因此这类节点称为 MIN 节点 3 极小极大搜索过程 由于正方和反方是交替走步的 因此MAX节点和MIN节点会交替出现 3 极小极大搜索过程 正方 MAX节点 从所有子节点中 选取具有最大评估值的节点 反方 MIN节点 从其所有子节点中 选取具有最小评估值的节点 反复进行这种选取 就可以得到双方各个节点的评估值 这种确定棋步的方法 称为极小极大搜索法 3 极小极大搜索过程 3 极小极大搜索过程 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 MIN MAX 0 MAX MIN 3 极小极大搜索过程 0 1 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 0 3 3 3 3 2 1 3 6 3 0 3 1 6 0 1 MAX MIN MAX MIN 3 极小极大搜索过程 在九宫格棋盘上 两位选手轮流在棋盘上摆各自的棋子 每次一枚 谁先取得三线的结果就取胜 设程序方MAX的棋子用 表示 MAX先走 对手MIN的棋子用 o 表示 例如 3 极小极大搜索过程 MIN取胜 估计函数f p 所有空格都放上MAX的棋子之后 MAX的三子成线数 所有空格都放上MIN的棋子之后 MIN的三子成线的总数 若P是MAX获胜的格局 则f p 若P是MIN获胜的格局 则f p 3 极小极大搜索过程 3 极小极大搜索过程 估计函数值f p 6 4 2 估计函数f p 所有空格都放上MAX的棋子之后 MAX的三子成线 行 列 对角 数 所有空格都放上MIN的棋子之后 MIN的三子成线 行 列 对角 的总数 当前棋局f p 2 3 极小极大搜索过程 一字棋第一阶段搜索树 3 极小极大搜索过程 一字棋第二阶段搜索树 3 极小极大搜索过程 一字棋第三阶段搜索树 设有一个摆放三个子的棋盘残局 如下图所示 和 在结束前有三步棋可以走 而且设走第一步的是 这时存在着三个空格A B C 用博弈树搜索算法判断应该把棋子放到哪一格内 棋盘残局举例 3 极小极大搜索过程 0 1 0 1 0 0 MAX节点 MIN节点 终端节点 3 极小极大搜索过程 对于棋盘残局中的 来说 最好的选择 是将 放在C的位置上 这时可以导致平局局面 3 极小极大搜索过程 剪支法的引入在极小极大法中 必须求出所有终端节点的评估值 当预先考虑的棋步比较多时 计算量会大大增加 为了提高搜索的效率 引入了通过对评估值的上下限进行估计 从而减少需进行评估的节点范围的 剪支法 4 搜索过程 作为正方出现的MAX节点 假设它的MIN子节点有N个 那么当它的第一个MIN子节点的评估值为 时 则对于其它的子节点 如果有高过 的 就取那最高的值作为该MAX节点的评估值 如果没有 则该MAX节点的评估值为 总之 该MAX节点的评估值不会低于 这个 就称为该MAX节点的评估下限值 4 搜索过程 MAX节点的评估下限值 MIN节点的评估上限值 作为反方出现的MIN节点 假设它的MAX子节点有N个 那么当它的第一个MAX子节点的评估值为 时 则对于其它子节点 如果有低于 的 就取那个低于 的值作为该MIN节点的评估值 如果没有 则该MIN节点的评估值取 总之 该MIN节点的评估值不会高过 这个 就称为该MIN节点的评估上限值 4 搜索过程 剪支法 MAX节点 MIN节点 剪支 A B C D 4 搜索过程 设MAX节点的下限为 则其所有的MIN子节点中 其评估值的 上限小于等于 的节点 其以下部分的搜索都可以停止了 即对这部分节点进行了 剪支 设MIN节点的上限为 则其所有的MAX子节点中 其评估值的 下限大于等于 的节点 其以下部分的搜索都可以停止了 即对这部分节点进行了 剪支 MAX节点 MIN节点 剪支 A B C D 4 搜索过程 剪支法 A B C D E F G H I J K L N O M 4 搜索过程 MAX节点 MAX节点 MIN节点 终端节点 3 5 6 5 2 1 6 4 MAX节点 5 3 5 6 5 2 1 6 4 6 2 5 2 5 MIN节点 终端节点 剪支 剪支 A B C D E F G H I J K L N O M MAX节点 4 搜索过程 一字棋第一阶段 剪支方法 4 搜索过程 4 搜索过程 极大节点的下界为 极小节点的上界为 剪支的条件 后辈节点的 值 祖先节点的 值时 剪支后辈节点的 值 祖先节点的 值时 剪支简记为 极小 极大 剪支极大 极小 剪支 4 搜索过程 8 6 3 1 4 5 3 3 5 0 3 3 0 2 2 3 0 2 3 0 9 3 0 0 3 0 3 3 0 5 4 1 1 3 1 6 6 1 a b c d e f g h i j k m n MAX MIN MAX MIN 改进方法使用 剪支技术 当不满足剪支条件 即 时或 值比 值大不了多少或极相近时 这时也可以进行剪支 以便有条件把搜索集中到会带来更大效果的其他路径上 这就是中止对效益不大的一些子树的搜索 以提高搜索效率 4 搜索过程 不严格限制搜索的深度 当到达深度限制时 如出现博弈格局有可能发生较大变化时 则应多搜索几层 使格局进入较稳定状态后再中止 这样可使倒推值计算的结果比较合理 避免考虑不充分产生的影响 这是等候状态平稳后中止搜