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