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

1、人人 工工 智智 能能Artificial Artificial Intelligence (AI)Intelligence (AI)曲维光曲维光南京师范大学计算机学院南京师范大学计算机学院2.4 博弈问题的搜索技术博弈问题的搜索技术 2.4.1 博弈问题的表达博弈问题的表达 2.4.2 极大极小搜索过程极大极小搜索过程 2.4.3 - 剪枝法剪枝法2.4.1 博弈问题的表达博弈问题的表达 博弈是一类具有竞争性的智能活动博弈是一类具有竞争性的智能活动双人博弈：即两位选手对垒，轮番依双人博弈：即两位选手对垒，轮番依次走步，其中任何一方都完全知道对次走步，其中任何一方都完全

2、知道对方过去曾经走过的棋步和今后能够的方过去曾经走过的棋步和今后能够的走步，其结果是一方赢走步，其结果是一方赢( (而另一方那而另一方那么输么输) )，或双方和局，或双方和局博弈的例子：博弈的例子：一字棋一字棋跳棋跳棋中国象棋中国象棋围棋围棋五子棋五子棋双方的智能活动，任何一方都不能单独控制双方的智能活动，任何一方都不能单独控制博弈过程，而是由双方轮番实施其控制对策博弈过程，而是由双方轮番实施其控制对策的过程的过程博弈的特点：博弈的特点：如何根据当前的棋局，选择对本人最有利的如何根据当前的棋局，选择对本人最有利的一步棋一步棋 ？！？！人工智能中研讨的博弈问题：人工智能中研讨的博弈问题：用博弈树

3、来表示，它是一种特殊的与或图。节点用博弈树来表示，它是一种特殊的与或图。节点代表博弈的格局即棋局，相当于形状空间中代表博弈的格局即棋局，相当于形状空间中的形状，反映了博弈的信息。的形状，反映了博弈的信息。 与节点、或节点与节点、或节点隔层交替出现隔层交替出现博弈问题的表示：博弈问题的表示：假设博弈双方为：假设博弈双方为：MAX和和MIN在博弈过程中，规那么是双方轮番走步。在博在博弈过程中，规那么是双方轮番走步。在博弈树中，相当于博弈双方轮番扩展其所属节点弈树中，相当于博弈双方轮番扩展其所属节点为什么与节点、或节点隔层交替出现？为什么与节点、或节点隔层交替出现？从从MAXMAX方的角度来看：方的

4、角度来看： 一切一切MINMIN方节点都是与节点方节点都是与节点理由：理由：由于由于MINMIN方必定选择最不利于方必定选择最不利于MAXMAX方的方式方的方式来扩展节点，只需来扩展节点，只需MINMIN方节点的子节点中方节点的子节点中有一个对有一个对MAXMAX方不利，那么该节点就对方不利，那么该节点就对MAXMAX方不利，故为方不利，故为“与节点与节点MIN好招好招从从MAXMAX方的角度来看：方的角度来看： 一切属于一切属于MAXMAX方的节点都是方的节点都是“或节或节点点理由：理由：由于扩展由于扩展MAXMAX方节点时，方节点时，MAXMAX方可选择扩展方可选择扩展最有利于本人的节点，

5、只需可扩展的子节最有利于本人的节点，只需可扩展的子节点中有一个对已有利，点中有一个对已有利， 那么该节点就对那么该节点就对已有利已有利MAX好招好招总之总之从从MAXMAX方来说，与节点、或节点交替出现；反之，方来说，与节点、或节点交替出现；反之，从从MINMIN方的角度来看，情况正好相反方的角度来看，情况正好相反在博弈树中，先行一方的初始形状对应着树的根在博弈树中，先行一方的初始形状对应着树的根节点，而任何一方获胜的最终格局为目的形状，节点，而任何一方获胜的最终格局为目的形状，对应于树的终叶节点可解节点或本原问题对应于树的终叶节点可解节点或本原问题但是，从但是，从MAXMAX的角度出发，一切

6、使的角度出发，一切使MAXMAX获胜的形状获胜的形状格局都是本原问题，是可解节点，而使格局都是本原问题，是可解节点，而使MINMIN获胜的获胜的形状格局是不可解节点形状格局是不可解节点例例 Grundy博弈：分配物品的问题博弈：分配物品的问题假设有一堆数目为假设有一堆数目为N的钱币，由两位选手轮的钱币，由两位选手轮番进展分配，要求每个选手每次把其中某番进展分配，要求每个选手每次把其中某一堆分成数目不等的两小堆，直至有一选一堆分成数目不等的两小堆，直至有一选手不能将钱币分成不等的两堆为止，那么手不能将钱币分成不等的两堆为止，那么断定这位选手为输家断定这位选手为输家用数字序列加上一个阐明来表示一个

7、形状：用数字序列加上一个阐明来表示一个形状： (3, 2, 1, 1, MAX) (3, 2, 1, 1, MAX)数字序列：表示不同堆中钱币的个数数字序列：表示不同堆中钱币的个数阐明：表示下一步由谁来分，即取阐明：表示下一步由谁来分，即取MAXMAX或或MINMIN如今取如今取N N7 7的简单情况，并由的简单情况，并由MINMIN先分先分 注：假设注：假设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)

8、(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)对于比较复杂的博弈问题，只能模拟人的思想对于比较复杂的博弈问题，只能模拟人的思想“向前看几步，然后作出决策，选择最有利本向前看几步，然后作出决策，选择最有利本人的一步。即只能给出几层走法，然后按照一定人的一步。即只能给出几层走法，然后按照一定的估算方法，决议走一好招的估算方法，决议走一好招2.4.2 极大极小过程极大极小过程 对于复杂的博弈问题，要规定搜索深度与时间，对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能

9、顺利进展以便于博弈搜索能顺利进展假设由假设由MAXMAX来选择走一步棋，问题是：来选择走一步棋，问题是：MAXMAX如何来选择一步好棋？如何来选择一步好棋？ 对于每一格局棋局给出定义或者倒推对于每一格局棋局给出定义或者倒推一个静态估价函数值。值越大对一个静态估价函数值。值越大对MAX越有利，反越有利，反之越不利之越不利极大极小过程的根本思绪：极大极小过程的根本思绪： 对于给定的格局，对于给定的格局，MAX给出能够的走法，然给出能够的走法，然后后MIN对应地给出相应的走法，这样反复假设干对应地给出相应的走法，这样反复假设干次，得到一组端节点必需由次，得到一组端节点必需由MIN走后得到的，走后得到

10、的，由由MAX下的棋局。这一过程相当于节点扩展下的棋局。这一过程相当于节点扩展注：博弈树深度或层数一定是偶数注：博弈树深度或层数一定是偶数 对于每一个端节点，计算出它们的静态估价函对于每一个端节点，计算出它们的静态估价函数，然后自下而上地逐层计算倒推值，直到数，然后自下而上地逐层计算倒推值，直到MAX开场的格局。在开场的格局。在MIN下的格局中取估值的最小值，下的格局中取估值的最小值，在在MAX下格局中取估值的最大值下格局中取估值的最大值 取估值最大的格局作为取估值最大的格局作为MAX要走的一招棋要走的一招棋例：向前看一步的两层博弈树例：向前看一步的两层博弈树 定义静态函数定义静态函数e(P)

11、的普通原那么：的普通原那么：0MAXMIN( )0 0MAX MINe P 占优，不利势均力敌不利，占优 OPEN：存放待扩展的节点，此时为队列，：存放待扩展的节点，此时为队列，即以宽度优先的战略扩展节点即以宽度优先的战略扩展节点 CLOSED：存放已扩展的节点，此时为堆栈，：存放已扩展的节点，此时为堆栈，即后扩展的节点先计算静态估价函数值即后扩展的节点先计算静态估价函数值 符号：符号：1、将初始节点、将初始节点 S 放入放入 OPEN 表中，开场时表中，开场时搜索树搜索树 T 由初始节点由初始节点 S 构成构成2、假设、假设 OPEN 表为空，那么转表为空，那么转53、将、将 OPEN 表中

12、第一个节点表中第一个节点 n 移出放入移出放入CLOSED 表的前端表的前端极大极小搜索过程为：极大极小搜索过程为：4、假设、假设 n 可直接断定为赢、输、或平局，可直接断定为赢、输、或平局，那么令对应的那么令对应的 e(n)=，-或或 0，并转，并转2；否那么扩展否那么扩展 n，产生，产生 n 的后继节点集的后继节点集 ni ，将，将 ni 放入搜索树放入搜索树 T 中中此时，假设搜索深度此时，假设搜索深度d ni 小于预先设定的深度小于预先设定的深度 k，那么将，那么将 ni 放入放入OPEN表的末端，转表的末端，转2；否；否那么，那么，ni 到达深度到达深度k，计算，计算e ( ni )

13、，并转，并转2续续5、假设、假设CLOSED表为空，那么转表为空，那么转8；否；否那么取出那么取出CLOSED表中的第一个节点，表中的第一个节点，记为记为 npOpen为空，即曾经扩展完节点为空，即曾经扩展完节点步步26、假设、假设 np 属于属于MAX层，且对于它的属层，且对于它的属于于MIN层的子节点层的子节点 nci 的的 e ( nci )有值，那有值，那么：么： e ( np ) =max nci 某一个节点属于某一个节点属于MAX的含义的含义是该节点等待是该节点等待MAX来扩展来扩展续续假设假设 np 属于属于MIN层，且对于它的属于层，且对于它的属于MAX层层的子节点的子节点 n

14、ci 的的 e ( nci )有值，那么：有值，那么： e ( np )=min nci 7、转、转58、根据、根据 e (S) 的值，标志走步或者终了的值，标志走步或者终了-，或或 0第一阶段为第一阶段为1、2、3、4步，用宽度优先算法生成步，用宽度优先算法生成规定深度规定深度 k 的全部博弈树，然后对其一切端节点的全部博弈树，然后对其一切端节点计算计算 e(P)第二阶段为第二阶段为5、6、7、8步，是自下而上逐级求节步，是自下而上逐级求节点的倒推估价值，直至求出初始节点的点的倒推估价值，直至求出初始节点的 e(S) 为止，为止，再由再由 e(S) 选得相对较好的走法，过程终了选得相对较好的

15、走法，过程终了算法分成两个阶段：算法分成两个阶段：等对手走出相应的棋，再以当前的格局等对手走出相应的棋，再以当前的格局作为初始节点，反复此过程，选择对本作为初始节点，反复此过程，选择对本人有利的走法人有利的走法例：例： 一字棋的极大极小搜索过程一字棋的极大极小搜索过程 商定：商定：每一方只向前看一步每一方只向前看一步 扩展出二层扩展出二层记记MAXMAX的棋子为的棋子为“，MINMIN的棋子为的棋子为“O O规定规定MAXMAX先手先手 假设格局假设格局 P 对任何一方都不能获胜，那么对任何一方都不能获胜，那么e(P) =一切空格上都放上一切空格上都放上MAX的棋子后，的棋子后，MAX的三个棋

16、子所组成的行、列及对角线的总数的三个棋子所组成的行、列及对角线的总数-一切空格上都放上一切空格上都放上MIN的棋子后，的棋子后，MIN的三个的三个棋子所组成的行、列及对角线的总数棋子所组成的行、列及对角线的总数静态估计函数静态估计函数e(P)定义为：定义为： 假设假设P是是MAX获胜，那么获胜，那么 e(P)=+ 假设假设P是是MIN获胜，那么获胜，那么 e(P)=例：计算以下棋局的静态估价函数值例：计算以下棋局的静态估价函数值 e(P)=6-4=2 棋局棋局O O OOOO OOOO行行=2列列=2对角对角=2行行=2列列=2对角对角=0利用棋盘的对称性，有些棋局是等价的利用棋盘的对称性，有

17、些棋局是等价的 OOOOOOOOOOO OOOO O1010-1-10-10-2121-2-11MAXMIN MAXMAX的走步的走步第二步第二步OXXOXOXXOXXOXXXOOXXOOXXOXOXOXOXOXO213211OOXXOXXOOXXOOXXOOXXO10201OOXX10OOXXOOXXOOXXOXOXOXXOOXXO2231221OOXXOXOXOOXX11001XOXO3MIN第三步第三步OOXXXOOXXOOXXXOOXXXOOXXXOOXXXXOOOXXXOOXXOXOOXXOXOOXOXOOOXXXOOOXXXOOXXXOOOXXXOOOOXXXOOXXXOOOXXX

18、OOOXXOXOOOXXXOOOXXXOOXXOXOOXOXXOOOXXXOOOXXXOOXXXOOOXOXX- 021- - - 122101- - - 1111112- 11OOMAXMINMAXMINOO上机实验作业：上机实验作业：用用C/C+言语编写言语编写“一字棋的游戏程序，根本要一字棋的游戏程序，根本要求：求：必需实现极大极小过程必需实现极大极小过程可以进展可以进展“人人-机对垒、机对垒、“机机-机对垒机对垒简单地显示对垒过程简单地显示对垒过程实验方式：两人或者一人一组实验方式：两人或者一人一组实验报告格式：实验报告格式：“一字棋游戏的计算机程序一字棋游戏的计算机程序学号：学号：

19、姓名：姓名： 专业：专业：摘要摘要1 一字棋游戏的文字描画一字棋游戏的文字描画2 一字棋对垒过程的计算机描画和实现一字棋对垒过程的计算机描画和实现3 实例人机对垒的过程、机机对垒的过程实例人机对垒的过程、机机对垒的过程4 领会领会5 参考文献参考文献附录：程序运用的简单阐明附录：程序运用的简单阐明提交的资料：提交的资料：1、文字报告；、文字报告；2、程序原代码、程序原代码提交的方式：以学号姓名为紧缩文件名发送到提交的方式：以学号姓名为紧缩文件名发送到 提交的时间：提交的时间：11月月21日日口头报告：引见报告的主要内容和演示程序，特别口头报告：引见报告的主要内容和演示程

20、序，特别是本人觉得有特征的地方。初步时间是是本人觉得有特征的地方。初步时间是12月初。月初。2.4.3 -剪枝法剪枝法 极大极小搜索过程由两个完全分别的两个步骤极大极小搜索过程由两个完全分别的两个步骤组成：组成：1、用宽度优先算法生成一棵博弈搜索树。、用宽度优先算法生成一棵博弈搜索树。2、估计值的倒推计算。、估计值的倒推计算。缺陷：这种分别使得搜索的效率比较低。缺陷：这种分别使得搜索的效率比较低。改良：在博弈树生成过程中同时计改良：在博弈树生成过程中同时计算端节点的估计值及倒推值，以减算端节点的估计值及倒推值，以减少搜索的次数，这就是少搜索的次数，这就是-过程的思过程的思想，也称为想，也称为-

21、剪枝法。剪枝法。其中，其中，表示表示MAX节点的估值的下节点的估值的下界曾经搜索到的界曾经搜索到的MAX节点的最小节点的最小值。值。 表示表示MIN节点的估值的上界节点的估值的上界曾经搜索到的曾经搜索到的MIN节点的最大节点的最大值值 。 极大极小过程：极大极小过程： 采用宽度优先的方式来扩展节点采用宽度优先的方式来扩展节点-剪枝法：剪枝法： 改用深度优先的战略来扩展节改用深度优先的战略来扩展节一字棋的左边部分一字棋的左边部分 MAXMIN现扩展现扩展B得到得到C，其值为，其值为-1，那么，那么B的倒推值小于的倒推值小于等于等于-1，即，即-1。再扩展。再扩展B的子节点，的子节点，B的值也不的

22、值也不会大于会大于-1。结果是。结果是B比比A差，不用再扩展差，不用再扩展B的其他的其他子节点了。此处，子节点了。此处，MIN节点节点B的的值小于等于其先值小于等于其先辈辈MAX节点节点S的的值，停顿扩展。值，停顿扩展。C扩展扩展S生成生成A, B,.。扩。扩展展A生成生成5个子节点，倒个子节点，倒推得到推得到A的值为的值为-1。可。可以得到以得到 S 的值大于等于的值大于等于 -1，即，即 -1。更普通的情况更普通的情况MIN节节点的点的不大于不大于其先辈其先辈MAX节节点的点的值，那值，那么可以么可以中止扩中止扩展展MAX节节点的点的 不小于不小于其先辈其先辈MIN节节点的点的值，那值，那

23、么可以么可以中止扩中止扩展展普通而言，当某一个节点的后继节点倒推值曾普通而言，当某一个节点的后继节点倒推值曾经给定时，那么倒推值的上下界可以被修正。经给定时，那么倒推值的上下界可以被修正。留意：留意：MAXMAX节点的节点的值非减，值非减，MINMIN节点的节点的值非增。值非增。 、值的计算方法：值的计算方法：第一、一个第一、一个MAXMAX节点的节点的值等于其后继节点当前值等于其后继节点当前最大的最终倒推值。最大的最终倒推值。第二、一个第二、一个MINMIN节点的节点的值等于其后继节点当前值等于其后继节点当前最小的最终倒推值。最小的最终倒推值。 -剪枝的规那么为：剪枝的规那么为：1 1、假设

24、任何、假设任何MINMIN结点的结点的值小于或等于任何它的值小于或等于任何它的先辈先辈MAXMAX结点的结点的值，那么可中止该值，那么可中止该MINMIN结点以下结点以下的搜索，此时这个的搜索，此时这个MINMIN结点的最终倒推值就是已结点的最终倒推值就是已得到的得到的值。该值与真正的极大极小的搜索结果值。该值与真正的极大极小的搜索结果的倒推值能够不一样，但是对起始结点而言，倒的倒推值能够不一样，但是对起始结点而言，倒推值是一样的，运用它选择的走步也是一样的。推值是一样的，运用它选择的走步也是一样的。 2、假设任何、假设任何MAX结点的结点的值大于或等于值大于或等于它的它的MIN先辈结点的先辈结点的值，那么可以中止值，那么可以中止该该MAX结点以下的搜索，此时这个结点以下的搜索，此时这个MAX结点处的倒推值就是已得到的结点处的倒