人工智能第二章与或图搜索问题68

1、目标目标目标目标初始节点初始节点sabc1.K个个2.i个个nn1n2ni3目标目标目标目标初始节点初始节点 解图：解图：456ns7目标目标目标目标初始节点初始节点abc89其中：其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0设：设：K连接符连接符的耗散值为的耗散值为K目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n810目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8初始节点初始节点n0n1(2)n4(1)n5(1)红色：红色：4黄色：黄色：311初

2、始节点初始节点n0n4(1)n5(1)红色：红色：4黄色：黄色：6n1n2(4)n3(4)5目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n812红色：红色：5黄色：黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n813红色：红色：5黄色：黄色：621初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n814博弈博弈 是一类具有竞争性的智能活动是

3、一类具有竞争性的智能活动双人博弈双人博弈：即两位选手对垒，轮流依次走步，：即两位选手对垒，轮流依次走步，其中任何一方都完全知道对方过去已经走过的其中任何一方都完全知道对方过去已经走过的棋步和今后可能的走步，其结果是一方赢棋步和今后可能的走步，其结果是一方赢(而另而另一方则输一方则输)，或双方和局，或双方和局15博弈的例子博弈的例子： 一字棋一字棋 跳棋跳棋 中国象棋中国象棋 围棋围棋 五子棋五子棋1617双方的智能活动，任何一方都不能单独控制双方的智能活动，任何一方都不能单独控制博弈过程，而是由双方轮流实施其控制对策博弈过程，而是由双方轮流实施其控制对策的过程。的过程。博弈的特点：博弈的特点：

4、18如何根据当前的棋局，选择对自己最有利的如何根据当前的棋局，选择对自己最有利的一步棋一步棋 ？人工智能中研究的博弈问题人工智能中研究的博弈问题：中国象棋中国象棋19用博弈树来表示，它是一种特殊的用博弈树来表示，它是一种特殊的与或树与或树。节点。节点代表博弈的格局（即棋局），相当于状态空间中代表博弈的格局（即棋局），相当于状态空间中的状态，反映了博弈的信息，的状态，反映了博弈的信息， 并且与节点、或并且与节点、或节点隔层交替出现。节点隔层交替出现。博弈问题（求解过程）的表示博弈问题（求解过程）的表示：20假设博弈双方为：假设博弈双方为：MAX和和MIN在博弈过程中，规则是双方轮流走步。在博弈在

5、博弈过程中，规则是双方轮流走步。在博弈树中，相当于博弈双方轮流扩展其所属节点。树中，相当于博弈双方轮流扩展其所属节点。为什么与节点、或节点隔层交替出现为什么与节点、或节点隔层交替出现？21从从MAX方的角度来看方的角度来看： 所有所有MIN方节点都是方节点都是与节点与节点理由理由：因为因为MIN方必定选择最不利于方必定选择最不利于MAX方的方式来方的方式来扩展节点，只要扩展节点，只要MIN方节点的子节点（下出棋方节点的子节点（下出棋局）中有一个对局）中有一个对MAX方不利，则该节点就对方不利，则该节点就对MAX方不利，故为方不利，故为“与节点与节点”。MIN好招好招22从从MAX方的角度来看方

6、的角度来看： 所有属于所有属于MAX方的节点都是方的节点都是或节点或节点理由理由：因为扩展因为扩展MAX方节点时，方节点时，MAX方可选择扩展最方可选择扩展最有利于自己的节点，只要可扩展的子节点中有有利于自己的节点，只要可扩展的子节点中有一个对已有利，一个对已有利， 则该节点就对已有利。则该节点就对已有利。MAX好招好招23总之：总之：从从MAX方来说，与节点、或节点交替出现；反之，方来说，与节点、或节点交替出现；反之，从从MIN方的角度来看，情况正好相反。方的角度来看，情况正好相反。24在博弈树中，先行一方的初始状态对应着树的在博弈树中，先行一方的初始状态对应着树的根根节点节点，而任何一方获

7、胜的最终格局为目标状态，而任何一方获胜的最终格局为目标状态，对应于树的对应于树的终叶节点终叶节点（可解节点或本原问题）。（可解节点或本原问题）。但是，从但是，从MAX的角度出发，所有使的角度出发，所有使MAX获胜的获胜的状态格局都是本原问题，是状态格局都是本原问题，是可解节点可解节点，而使，而使MIN获胜的状态格局是获胜的状态格局是不可解节点不可解节点。2526例例 Grundy博弈：分配物品的问题博弈：分配物品的问题如果有一堆数目为如果有一堆数目为N的钱币，由两位选手轮流进的钱币，由两位选手轮流进行分配，要求每个选手每次把其中某一堆分成数行分配，要求每个选手每次把其中某一堆分成数目目不等不等

8、的两小堆，直至有一选手不能将钱币分成的两小堆，直至有一选手不能将钱币分成不等的两堆为止，则判定这位选手为输家。不等的两堆为止，则判定这位选手为输家。27用数字序列加上一个说明来表示一个状态：用数字序列加上一个说明来表示一个状态： ( (3, 2, 1, 1, MAX) )数字序列数字序列：表示不同堆中钱币的个数：表示不同堆中钱币的个数说明说明：表示下一步由谁来分，即取：表示下一步由谁来分，即取MAX或或MIN28现在取现在取 N7 的简单情况的简单情况，并由，并由MIN先分先分 注注：如果如果MAX走红箭头的分法，必定获胜。走红箭头的分法，必定获胜。所有可能的分法所有可能的分法(7,MIN)(

9、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)29（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走对方先走我方必胜我方必胜30对于比较复杂的博弈问题，只能模拟

10、人的思维对于比较复杂的博弈问题，只能模拟人的思维“向前看几步向前看几步”，然后作出决策，选择最有利自，然后作出决策，选择最有利自己的一步。即己的一步。即只能给出几层走法，然后按照一定只能给出几层走法，然后按照一定的估算办法，的估算办法，决定走一好招。决定走一好招。313233对于复杂的博弈问题，要规定搜索深度与时间，对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺利进行。以便于博弈搜索能顺利进行。假设由假设由MAX来选择走一步棋，问题是：来选择走一步棋，问题是：MAX如何来选择一步好棋如何来选择一步好棋？ 3435 对于每一格局（棋局）给出（定义或者倒推）对于每一格局（棋局）给出（

11、定义或者倒推）一个静态估价函数值。值越大对一个静态估价函数值。值越大对MAX越有利，反越有利，反之越不利；之越不利；极大极小过程的基本思路极大极小过程的基本思路：36 对于给定的格局，对于给定的格局，MAX给出可能的走法，然后给出可能的走法，然后MIN对应地给出相应的走法，这样重复若干次，对应地给出相应的走法，这样重复若干次，得到一组端节点（必须由得到一组端节点（必须由MIN走后得到的，等待走后得到的，等待MAX下的棋局）。这一过程相当于节点扩展；下的棋局）。这一过程相当于节点扩展；注注：博弈树深度或层数一定是偶数。：博弈树深度或层数一定是偶数。37 对于每一个端节点，计算出它们的静态估价函对

12、于每一个端节点，计算出它们的静态估价函数，然后自下而上地逐层计算倒推值，直到数，然后自下而上地逐层计算倒推值，直到MAX开始的格局。在开始的格局。在MIN下的格局中取估值的最小值，下的格局中取估值的最小值，在在MAX下格局中取估值的最大值；下格局中取估值的最大值； 取估值最大的格局作为取估值最大的格局作为MAX要走的一招棋。要走的一招棋。38例例：向前看一步的两层博弈树向前看一步的两层博弈树 39定义静态函数定义静态函数e(P)的一般原则的一般原则：0MAXMIN( )0 0MAX MINe P 占优，不利势均力敌不利，占优40OPEN：存放待扩展的节点，此时为队列，即以存放待扩展的节点，此时

13、为队列，即以宽度优先的策略扩展节点。宽度优先的策略扩展节点。CLOSED：存放已扩展的节点，此时为堆栈，存放已扩展的节点，此时为堆栈，即后扩展的节点先计算。即后扩展的节点先计算。 符号符号：41421、将初始节点、将初始节点 S 放入放入 OPEN 表中，开始时搜索表中，开始时搜索树树 T 由初始节点由初始节点 S 构成；构成；2、若、若 OPEN 表为空（表为空（节点扩展结束节点扩展结束），则转），则转5；3、将、将 OPEN 表中第一个节点表中第一个节点 n 移出放移出放入入CLOSED 表的前端；表的前端；极大极小搜索过程极大极小搜索过程为为：434、若、若 n 可直接判定为赢、输、或平

14、局，则令对应的可直接判定为赢、输、或平局，则令对应的 e(n)=，-或或 0，并转，并转2；否则扩展；否则扩展 n，产生产生 n 的的后继节点集后继节点集 ni ，将将 ni 放入搜索树放入搜索树 T 中。此时，中。此时，若搜索深度若搜索深度d ni 小于预先设定的深度小于预先设定的深度 k，则将则将 ni 放入放入OPEN表的末端，转表的末端，转2；否则，；否则，ni 达到深达到深度度k，计算计算e ( ni )，并转并转2；445、若、若CLOSED表为空，则转表为空，则转8；否则取出；否则取出CLOSED表中的第一个节点，记为表中的第一个节点，记为 np；Open为空，即已经扩展完节点为

15、空，即已经扩展完节点步步2456、若若 np 属于属于MAX层，且对于它的属于层，且对于它的属于MIN层层的子节点的子节点 nci 的的 e ( nci )有值，则：有值，则： e ( np ) =max nci 46（续）（续）若若 np 属于属于MIN层，且对于它的属于层，且对于它的属于MAX层的子层的子节点节点 nci 的的 e ( nci )有值，则：有值，则： e ( np )=min nci 477、转、转5；8、根据、根据 e (S) 的值，标记走步或者结束（的值，标记走步或者结束（-，或或 0）。）。48第一阶段第一阶段为为1、2、3、4步，用宽度优先算法生成步，用宽度优先算法

16、生成规定深度规定深度 k 的全部博弈树，然后对其所有端节点的全部博弈树，然后对其所有端节点计算计算 e(P)；第二阶段第二阶段为为5、6、7、8步，是自下而上逐级求节步，是自下而上逐级求节点的倒推估价值，直至求出初始节点的点的倒推估价值，直至求出初始节点的 e(S) 为止，为止，再由再由 e(S) 选得相对较好的走法，过程结束。选得相对较好的走法，过程结束。算法分成两个阶段算法分成两个阶段：49等对手走出相应的棋，再以当前的格局等对手走出相应的棋，再以当前的格局作为初始节点，重复此过程，选择对自作为初始节点，重复此过程，选择对自己有利的走法。己有利的走法。50极大极小过程极大极小过程51例例：

17、 一字棋的极大极小搜索过程一字棋的极大极小搜索过程 约定约定： 每一方只向前看一步每一方只向前看一步 （扩展出二层）（扩展出二层） 记记MAX的棋子为的棋子为“”，MIN的棋子为的棋子为“O” 规定规定MAX先手先手52 若格局若格局 P 对任何一方都不能获胜，则对任何一方都不能获胜，则e(P) =（所有空格上都放上所有空格上都放上MAX的棋子后，的棋子后，MAX的三个棋子所组成的行、列及对角线的总数的三个棋子所组成的行、列及对角线的总数）-（所有空格上都放上所有空格上都放上MIN的棋子后，的棋子后，MIN的三个的三个棋子所组成的行、列及对角线的总数棋子所组成的行、列及对角线的总数）静态估计函

18、数静态估计函数e(P)定义为定义为：53 若若 P 是是MAX获胜，则获胜，则 e(P)=+ 若若 P 是是MIN获胜，则获胜，则 e(P)=54例：例：计算下列棋局的静态估价函数值计算下列棋局的静态估价函数值 e(P)=6-4=2 棋局棋局行行=2列列=2对角对角=2行行=2列列=2对角对角=055利用棋盘的对称性，有些棋局是等价的利用棋盘的对称性，有些棋局是等价的 561010-1-10-10-2121-2-11MAXMIN MAXMAX的走步的走步57第二步第二步213211102011022312211100158第三步第三步- 021- - - 122101- - - 1111112

19、- 1159MAXMIN60MAXMINOO61极大极小搜索过程由两个完全分离的两个步骤极大极小搜索过程由两个完全分离的两个步骤组成：组成：第一第一、用宽度优先算法生成一棵博弈搜索树、用宽度优先算法生成一棵博弈搜索树第二第二、估计值的倒推计算、估计值的倒推计算缺点缺点：这种分离使得搜索的效率比较低：这种分离使得搜索的效率比较低6205-333-3022-30-23541-30689-30-33-3-3-21-360316011极大极大极小极小ab注：用表示注：用表示MAXMAX，用表示，用表示MINMIN，端节点上的数字表示它对应，端节点上的数字表示它对应的估价函数的值。的估价函数的值。极大极

20、大极小极小63极大极小过程是先生成与极大极小过程是先生成与/或树，然后再计算各节或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点，因此索方式，需要生成规定深度内的所有节点，因此搜索效率较低。搜索效率较低。改进改进：在博弈树生成过程中同时计算端节点的估在博弈树生成过程中同时计算端节点的估计值及倒推值，以减少搜索的次数，这就是计值及倒推值，以减少搜索的次数，这就是-过过程的思想，也称为程的思想，也称为-剪枝法。剪枝法。剪枝的概念剪枝的概念 : 如果能边生成节点边对节点估值，并剪去一些没如果能边生成节点边对节点估值，并剪去一些没用的分枝，这种技术被称为用的分枝，这种技术被称为-剪枝。剪枝。6465 一个一个-剪枝的具体例子，如下图所示。其中最下面一层端节剪枝的具体例子，如下图所示。其中最下面一层端节点旁边的数字是假设的估值。点旁边的数字是假设的估值。 在该图中，在该图中，L、M、N的估值推出节点的估值推出节点F的倒推值为的倒推值为4，即，即F的的值为值为4，由此可推出节点，由此可推出节点C的倒推值的倒推值4。 记记C的倒推值的下