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

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