人工智能知识表示与推理博弈树搜索.ppt

2020 3 23 人工智能ArtificialIntelligence AI 2020 3 23 2 4博弈问题的搜索技术2 4 1博弈问题的表达2 4 2极大极小搜索过程2 4 3 剪枝法 2020 3 23 2 4 1博弈问题的表达 博弈是一类具有竞争性的智能活动双人博弈 即两位选手对垒 轮流依次走步 其中任何一方都完全知道对方过去已经走过的棋步和今后可能的走步 其结果是一方赢 而另一方则输 或双方和局 2020 3 23 博弈的例子 一字棋跳棋中国象棋围棋五子棋 2020 3 23 双方的智能活动 任何一方都不能单独控制博弈过程 而是由双方轮流实施其控制对策的过程 博弈的特点 2020 3 23 如何根据当前的棋局 选择对自己最有利的一步棋 人工智能中研究的博弈问题 2020 3 23 用博弈树来表示 它是一种特殊的与或图 节点代表博弈的格局 即棋局 相当于状态空间中的状态 反映了博弈的信息 与节点 或节点隔层交替出现 博弈问题的表示 2020 3 23 假设博弈双方为 MAX和MIN在博弈过程中 规则是双方轮流走步 在博弈树中 相当于博弈双方轮流扩展其所属节点 为什么与节点 或节点隔层交替出现 2020 3 23 从MAX方的角度来看 所有MIN方节点都是与节点理由 因为MIN方必定选择最不利于MAX方的方式来扩展节点 只要MIN方节点的子节点中有一个对MAX方不利 则该节点就对MAX方不利 故为 与节点 2020 3 23 从MAX方的角度来看 所有属于MAX方的节点都是 或节点 理由 因为扩展MAX方节点时 MAX方可选择扩展最有利于自己的节点 只要可扩展的子节点中有一个对已有利 则该节点就对已有利 MAX 好招 2020 3 23 总之从MAX方来说 与节点 或节点交替出现 反之 从MIN方的角度来看 情况正好相反 2020 3 23 在博弈树中 先行一方的初始状态对应着树的根节点 而任何一方获胜的最终格局为目标状态 对应于树的终叶节点 可解节点或本原问题 但是 从MAX的角度出发 所有使MAX获胜的状态格局都是本原问题 是可解节点 而使MIN获胜的状态格局是不可解节点 2020 3 23 例Grundy博弈 分配物品的问题如果有一堆数目为N的钱币 由两位选手轮流进行分配 要求每个选手每次把其中某一堆分成数目不等的两小堆 直至有一选手不能将钱币分成不等的两堆为止 则判定这位选手为输家 2020 3 23 用数字序列加上一个说明来表示一个状态 3 2 1 1 MAX 数字序列 表示不同堆中钱币的个数说明 表示下一步由谁来分 即取MAX或MIN 2020 3 23 现在取N 7的简单情况 并由MIN先分 注 如果MAX走红箭头的分法 必定获胜 所有可能的分法 7 MIN 6 1 MAX 5 2 MAX 4 3 MAX 5 1 1 MIN 4 2 1 MIN 3 2 2 MIN 3 3 1 MIN 4 1 1 1 MAX 3 2 1 1 MAX 2 2 2 1 MAX 2 2 1 1 1 MIN 3 1 1 1 1 MIN 2 1 1 1 1 1 MAX 2020 3 23 对于比较复杂的博弈问题 只能模拟人的思维 向前看几步 然后作出决策 选择最有利自己的一步 即只能给出几层走法 然后按照一定的估算办法 决定走一好招 2020 3 23 2 4 2极大极小过程 对于复杂的博弈问题 要规定搜索深度与时间 以便于博弈搜索能顺利进行 假设由MAX来选择走一步棋 问题是 MAX如何来选择一步好棋 2020 3 23 对于每一格局 棋局 给出 定义或者倒推 一个静态估价函数值 值越大对MAX越有利 反之越不利 极大极小过程的基本思路 2020 3 23 对于给定的格局 MAX给出可能的走法 然后MIN对应地给出相应的走法 这样重复若干次 得到一组端节点 必须由MIN走后得到的 由MAX下的棋局 这一过程相当于节点扩展注 博弈树深度或层数一定是偶数 2020 3 23 对于每一个端节点 计算出它们的静态估价函数 然后自下而上地逐层计算倒推值 直到MAX开始的格局 在MIN下的格局中取估值的最小值 在MAX下格局中取估值的最大值 取估值最大的格局作为MAX要走的一招棋 2020 3 23 例 向前看一步的两层博弈树 2020 3 23 定义静态函数e P 的一般原则 2020 3 23 OPEN 存放待扩展的节点 此时为队列 即以宽度优先的策略扩展节点CLOSED 存放已扩展的节点 此时为堆栈 即后扩展的节点先计算静态估价函数值 符号 2020 3 23 1 将初始节点S放入OPEN表中 开始时搜索树T由初始节点S构成2 若OPEN表为空 则转53 将OPEN表中第一个节点n移出放入CLOSED表的前端 极大极小搜索过程为 2020 3 23 4 若n可直接判定为赢 输 或平局 则令对应的e n 或0 并转2 否则扩展n 产生n的后继节点集 ni 将 ni 放入搜索树T中 2020 3 23 此时 若搜索深度d ni 小于预先设定的深度k 则将 ni 放入OPEN表的末端 转2 否则 ni达到深度k 计算e ni 并转2 续 2020 3 23 5 若CLOSED表为空 则转8 否则取出CLOSED表中的第一个节点 记为np Open为空 即已经扩展完节点 步2 2020 3 23 6 若np属于MAX层 且对于它的属于MIN层的子节点nci的e nci 有值 则 e np max nci 某一个节点属于MAX的含义是该节点等待MAX来扩展 2020 3 23 续 若np属于MIN层 且对于它的属于MAX层的子节点nci的e nci 有值 则 e np min nci 2020 3 23 7 转58 根据e S 的值 标记走步或者结束 或0 2020 3 23 第一阶段为1 2 3 4步 用宽度优先算法生成规定深度k的全部博弈树 然后对其所有端节点计算e P 第二阶段为5 6 7 8步 是自下而上逐级求节点的倒推估价值 直至求出初始节点的e S 为止 再由e S 选得相对较好的走法 过程结束 算法分成两个阶段 2020 3 23 等对手走出相应的棋 再以当前的格局作为初始节点 重复此过程 选择对自己有利的走法 2020 3 23 2020 3 23 例 一字棋的极大极小搜索过程 约定 每一方只向前看一步 扩展出二层 记MAX的棋子为 MIN的棋子为 O 规定MAX先手 2020 3 23 若格局P对任何一方都不能获胜 则e P 所有空格上都放上MAX的棋子后 MAX的三个棋子所组成的行 列及对角线的总数 所有空格上都放上MIN的棋子后 MIN的三个棋子所组成的行 列及对角线的总数 静态估计函数e P 定义为 2020 3 23 若P是MAX获胜 则e P 若P是MIN获胜 则e P 2020 3 23 例 计算下列棋局的静态估价函数值 e P 6 4 2 棋局 行 2列 2对角 2 行 2列 2对角 0 2020 3 23 利用棋盘的对称性 有些棋局是等价的 2020 3 23 1 0 1 0 1 1 0 1 0 2 1 2 1 2 1 1 MAX MIN MAX MAX的走步 2020 3 23 第二步 2 1 3 2 1 1 1 0 2 0 1 1 0 2 2 3 1 2 2 1 1 1 0 0 1 3 MIN 2020 3 23 第三步 0 2 1 1 2 2 1 0 1 1 1 1 1 1 1 2 1 1 2020 3 23 MAX MIN 2020 3 23 MAX MIN O O 2020 3 23 上机实验作业 用C C 语言编写 一字棋 的游戏程序 基本要求 必须实现极大极小过程能够进行 人 机 对垒 机 机 对垒简单地显示对垒过程实验形式 两人或者一人一组 2020 3 23 实验报告格式 一字棋 游戏的计算机程序学号 姓名 专业 摘要1一字棋游戏的文字描述2一字棋对垒过程的计算机描述和实现3实例 人机对垒的过程 机机对垒的过程 4体会5参考文献附录 程序使用的简单说明 2020 3 23 提交的材料 1 文字报告 2 程序原代码提交的方式 以学号姓名为压缩文件名 发送到wgqu 提交的时间 11月21日口头报告 介绍报告的主要内容和演示程序 特别是自己觉得有特色的地方 初步时间是12月初 2020 3 23 2 4 3 剪枝法 极大极小搜索过程由两个完全分离的两个步骤组成 1 用宽度优先算法生成一棵博弈搜索树 2 估计值的倒推计算 缺点 这种分离使得搜索的效率比较低 2020 3 23 改进 在博弈树生成过程中同时计算端节点的估计值及倒推值 以减少搜索的次数 这就是 过程的思想 也称为 剪枝法 其中 表示MAX节点的估值的下界 已经搜索到的MAX节点的最小值 表示MIN节点的估值的上界 已经搜索到的MIN节点的最大值 2020 3 23 极大极小过程 采用宽度优先的方式来扩展节点 剪枝法 改用深度优先的策略来扩展节 2020 3 23 一字棋的左边部分 MAX MIN 现扩展B得到C 其值为 1 则B的倒推值小于等于 1 即 1 再扩展B的子节点 B的值也不会大于 1 结果是B比A差 不用再扩展B的其他子节点了 此处 MIN节点B的 值小于等于其先辈MAX节点S的 值 停止扩展 C 扩展S生成A B 扩展A生成5个子节点 倒推得到A的值为 1 可以得到S的值大于等于 1 即 1 2020 3 23 更一般的情况 MIN节点的 不大于其先辈MAX节点的 值 则可以中止扩展 MAX节点的 不小于其先辈MIN节点的 值 则可以中止扩展 2020 3 23 一般而言 当某一个节点的后继节点倒推值已经给定时 则倒推值的上下界可以被修正 注意 MAX节点的 值非减 MIN节点的 值非增 2020 3 23 值的计算方法 第一 一个MAX节点的 值等于其后继节点当前最大的最终倒推值 第二 一个MIN节点的 值等于其后继节点当前最小的最终倒推值 2020 3 23 剪枝的规则为 1 若任何MIN结点的 值小于或等于任何它的先辈MAX结点的 值 则可中止该MIN结点以下的搜索 此时这个MIN结点的最终倒推值就是已得到的 值 该值与真正的极大极小的搜索结果的倒推值可能不相同 但是对起始结点而言 倒推值是相同的 使用它选择的走步也是相同的 2020 3 23 2 若任何MAX结点的 值大于或等于它的MIN先辈结点的 值 则可以中止该MAX结点以下的搜索 此时这个MAX结点处的倒推值就是已得到的 值 2020 3 23 当搜索用规则1终止时 我们称进行了 剪枝 而当搜索用规则2终止时 我们称进行了 剪枝 在搜索过程中 保存 和 值 如果出现满足使用两条规则的条件 我们就中止某一些搜索 这一过程称为 剪枝 过程 2020 3 23 过程的主要思想 步骤 1 采用有界的深度优先搜索算法 2 立即计算端节点的估值 3 剪枝4 剪枝5 当初始节点的所有后继节点的最终倒推值全部给出后 搜索过程结束 2020 3 23 例