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