问题求解与博弈.ppt

问题求解与博弈,主要内容,状态空间搜索技术机器博弈,一些例子,搭积木智力游戏：有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到右岸，但受下列条件限制：船太小，农夫每次只能带一样东西过河没有农夫看管，则狼要吃羊，羊要吃菜请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）,状态空间表示法,人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个“问题求解”过程问题求解过程实际上就是一个搜索过程为了进行搜索，首先必须用某种形式把问题表示出来状态空间表示法就是用来表示问题及其搜索过程的一种方法,状态空间表示法,状态空间表示法是用“状态”和“算子”来表示问题的一种方法状态：用来描述问题求解过程中不同时刻的状况算子：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解,状态空间表示法,状态状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示SK(SK0,SK1,)当给每一分量以确定的值时，就得到一个具体的状态算子引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子状态空间由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用三元组表示:(S,F,G)S:所有初始状态构成的集合F:算子的集合G:目标状态的集合,例子:Hanoi Tower,二阶hanoi towerSK=(SK0,SK1)表示问题的状态，SK0 表示盘片A所在的柱号，SK1 表示盘片B所在的柱号全部可能的状态:S0=(1,1),S1=(1,2),S2=(1,3),S3=(2,1),S4=(2,2),S5=(2,3),S6=(3,1),S7=(3,2),S8=(3,3).问题的初始状态集合S=S0,目标集合为G=S4,S8算子分别用A(i,j),B(i,j)表示A(i,j):盘片A从柱i移到柱jB(i,j):盘片B从柱i移到柱j全部可能的算子：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2),B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2),状态空间表示法,首先必须定义状态的描述形式，通过使用这种描述可把问题的一切状态都表示出来。其实还要定义一组算子，通过使用算子可把问题由一种状态转变为另一种状态问题的求解过程就是一个不断把算子作用于状态的过程算子的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算子序列都可使问题从初始状态变到目标状态，这就得到了多个解，我们把使用算子最少的解称为最优解对于任何一种状态，可使用的算子可能不止一个，这样由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算子生成更进一步状态时，首先应对哪一状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的。,搜索技术,搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。例如，A.Newell(艾伦纽厄尔)和HASimon(西蒙)等人编写的LT(Logic Theorist)程序,J.Slagle写的符号积分程序SAINT,ANewell和HASimon写的GPS(General Problem Solver)程序,HGelernter(格伦特尔)写的Geometry theorem-proving machine程序,R.Fikes(菲克斯)和N.Nilsson(尼尔逊)写的STRIPS(Stanford Research Institute Problem Solver)程序以及A.Samuel(塞缪尔)写的Chechers程序等,都使用了各种搜索技术。现在,搜索技术渗透在各种人工智能系统中,可以说没有哪一种人工智能的应用不用搜索方法,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈都广泛使用搜技术。,搜索技术,搜索问题是AI核心理论问题之一一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：(1)搜索空间小;(2)解最佳。,搜索技术,搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。当所给定的问题用状态空间表示时,则求解过程可归结为对状态空间的搜索。当问题有解时,使用不同的搜索策略,找到解的搜索空间范围是有区别的。一般来说,对大空间问题,搜索策略是要解决组合爆炸的问题,搜索策略,通常搜索策略的主要任务是确定如何选取规则的方式。有两种基本方式:一种是不考虑给定问题所具有的特定知识,系统根据事先确定好的某种固定排序,依次调用规则或随机调用规则,这实际上是盲目搜索的方法,一般统称为无信息引导的搜索策略。另一种是考虑问题领域可应用的知识,动态地确定规则的排序,优先调用较合适的规则使用,这就是通常称为启发式搜索策略或有信息引导的搜索策略。,AI领域的搜索方法,(1)求任一解路的搜索策略回溯法(Backtracking)爬山法(Hill Climbing)宽度优先法(Breadth-first)深度优先法(Depth-first)限定范围搜索法(Beam Search)最佳优先法(Best-first)(2)求最佳解路的搜索策略大英博物馆法(British Museum)分枝界限法(Branch and Bound)动态规划法(Dynamic Programming)最佳图搜索法(A*),AI领域的搜索方法,(3)求与或关系解图的搜索法一般与或图搜索法(AO*)极小极大法(Minimax)剪枝法(Alpha-beta Pruning)启发式剪枝法(Heuristic Pruning),搜索策略分类,盲目搜索方法,盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索。典型的盲目搜索方法是深度优先搜索和宽度优先搜索(亦称广度优先搜索),这是两处基本搜索方法,回溯策略,例：皇后问题 在一个44的国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获,(),(),Q,(1,1),(),Q,Q,(1,1),(1,1)(2,3),(),Q,(1,1),(1,1)(2,3),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),Q,(1,1)(2,4)(3.2),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),Q,(1,2)(2,4)(3,1)(4,3),递归的思想,Fibonacci数列,1202年，意大利家斐波那契在提出了一个关于兔子繁殖的问题：如果一对兔子每月能生一对小兔（一雄一雌），而每对小兔在它出生後的第三个月里，又能开始生一对小兔，假定在不发生死亡的情況下，由一对出生的小兔开始，50個月后会有多少对兔子？,當n1時，Fn+2=Fn+1+Fn，而 F0=F1=1。,递归的思想（续）,当前状态,目标状态g,回溯搜索算法,BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。,回溯搜索算法,递归过程BACKTRACK(DATA)1,IF TERM(DATA)RETURN NIL;2,IF DEADEND(DATA)RETURN FAIL;3,RULES:=APPRULES(DATA);4,LOOP:IF NULL(RULES)RETURN FAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);,存在问题及解决办法,问题：深度问题死循环问题解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径,回溯搜索算法1,BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。,回溯搜索算法1,1,DATA:=FIRST(DATALIST)2,IF MENBER(DATA,TAIL(DATALIST)RETURN FAIL;3,IF TERM(DATA)RETURN NIL;4,IF DEADEND(DATA)RETURN FAIL;5,IF LENGTH(DATALIST)BOUND RETURN FAIL;6,RULES:=APPRULES(DATA);7,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);,回溯搜索算法1（续）,9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);,一些深入的问题,失败原因分析、多步回溯,一些深入问题（续）,回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。,图搜索策略,问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。,一些基本概念,节点深度：根节点深度=0其它节点深度=父节点深度+1,0,1,2,3,一些基本概念（续1）,路径设一节点序列为(n0,n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。,一些基本概念（续1）,扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,图搜索的一般过程,(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中（简称OPEN表）。(2)建立一个叫做CLOSED的已扩展节点表（简称CLOSED表），其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，它是CLOSED表中节点的编号。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。,(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GO LOOP。,OPEN表节点父节点CLOSED表标号节点父节点,例子,例子：从某王姓家族的四代中找王A的后代且其寿命为X的人。王A：寿命47，有儿子王B1、王B3、王B2王B1：寿命77，有儿子王C1、王C2王B3：寿命52，有儿子王D1王B2：寿命65，有儿子王E1、王E2王F1：寿命32王G1：寿命96王C2：寿命87，有儿子王F1王D1：寿命77，没有儿子王E1：寿命57，有儿子王G1王E2：寿命92，有儿子王H1 王C1：寿命27，没有儿子王H1：寿命51若X=57，如何寻找？,无信息图搜索过程,深度优先搜索(1)把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。(2)如果OPEN为一空表，则失败退出。(3)把第一个节点(节点n)从OPEN表移到CLOSED表。(4)如果节点n的深度等于最大深度，则转向(2)。(5)扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。(6)如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。,无信息图搜索过程,宽度优先搜索(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步,2 31 8 47 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,深度优先搜索的性质,一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法,2 31 8 47 6 5,1,2,5,6,7,3,目标,8,4,宽度优先搜索的性质,当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法,非启发式搜索,按照事先规定的路线进行搜索广度优先搜索是按“层”进行搜索的，先进入OPEN 表的节点先被考察深度优先搜索是沿着纵深方向进行搜索的，后进入OPEN表的节点先被考察按已经付出的代价决定下一步要搜索的节点代价树的广度优先代价树的深度优先,启发式图搜索,利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发性信息用于指导搜索过程，且与具体问题求解有关的控制性信息称为启发性信息启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解,希望：,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,基本思想,定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,1，启发式搜索算法A（A算法）,评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数g(n):实际已经付出的代价函数h(n)：启发函数,符号的意义,g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值,一个A算法的例子,定义评价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数,2 8 31 6 47 5,1 2 38 47 6 5,h计算举例,h(n)=4,2 8 31 6 47 5,1 2 3,45,7 6,8,2 8 31 6 47 5,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,6,最佳图搜索算法A*（A*算法）,在A算法中，如果满足条件：h(n)h*(n)则A算法称为A*算法。,A*条件举例,8数码问题h(n)=“不在位”的将牌数h(n)=将牌“不在位”的距离和,A*算法的性质,定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。,问题,图搜索是针对什么知识表示方法的问题求解方法？什么是图搜索?其中，重排OPEN表意味着什么，重排的原则是什么?宽度优先搜索方法中OPEN表需要按什么方式进行操作A先进后出 B先进先出有界深度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径吗？试比较各种盲目搜索搜索方法的效率，找出影响算法效率的原因试比较宽度优先搜索、有界深度优先搜索及有序搜索的搜索效率，并以实例数据加以说明,启发式搜索的必要性,现实的困难迫使人们转而求援于启发式算法。这种算法的本质是部分地放弃算法“一般化,通用化”的概念,把所要解的问题的具体领域 的知识加进算法中去,以提高算法的效率。如,广度优先法几乎可以用于解一切搜索问题：九宫图(八数码难题),hanoi塔(焚塔问题),旅行推销员,华容道,以至魔方等等。但实际使用时,效率也许低得惊人,甚至根本解不出来(例如魔方问题)。如果我们为每类问题找出一些特殊规则,和广度优先法配合起来使用,那结果就可能完全不一样了。,启发式搜索的必要性,根据启发信息,在生成各种搜索树时可以考虑种种可能的选择,如:1.下一步展开哪个节点?2.是部分展开还是完全展开?3.使用哪个规则(或算子)?4.怎样决定舍弃还是保留新生成的节点?5.怎样决定舍弃还是保留一棵子树?6.怎样决定停止或继续搜索?7.如何定义启发函数(评价函数)?8.如何决定搜索方向?由于这些选择的不同,就得到了不同的启发式算法,*解路径如粗线所标左、上、右、下*S、A、B、L、M等为状态空间图中各个节点名,其后的小括号中数字表示该节点的评价函数f(n)的估计值,例如S(4)、L(5)等。*图中标记节点为被扩的节点,标记的节点为生成的节点。,九宫重排问题,搜索效率比较,启发式搜索策略,人工智能问题求解者在两种基本情况下运用启发式策略:一个问题由于在问题陈述和数据获取方面固有的模糊性可能使它没有一个确定的解。医疗诊断即是一例。所给出的一系列症状可能有多个原因,医生运用启发式搜索来选择最有可能的论断并依此产生治疗计划。一个问题可能有确定解,但是求解过程中的计算机代价令人难以接受。在很多问题(如国际象棋)中,状态空间的增长特别快,可能的状态数随着搜索的深度呈指数级增长、分解。在这种情况下,穷尽式搜索策略诸如深度优先或广度优先搜索,在一个给定的较实际的时空内很可能得不到最终的解和发明创造的所有规则一样,启发式策略也是极易出错的,图搜索策略,图搜索策略的定义图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤。图搜索算法中的几个重要名词术语（1）OPEN表与CLOSE表（2）搜索图与搜索树,你可曾听说过“深蓝”？,1997年5月11日，IBM开发的“深蓝”击败了国际象棋冠军卡斯帕罗夫。,1980年他获得世界少年组冠军 1982年他并列夺得苏联冠军 1985年22岁的卡斯帕罗夫成为历史上最年轻的国 际象棋冠军积分是2849，这一分数是有史以来最高分。远远领先于第二位的克拉姆尼克的2770,卡氏何许人也？,电脑棋手：永不停歇的挑战！,1988年“深思”击败了丹麦特级大师拉森。1993年“深思”第二代击败了丹麦世界优秀女棋手小波尔加。,电脑棋手：永不停歇的挑战！,2001年“更弗里茨”击败了除了克拉姆尼克之外的所有排名世界前十位的棋手。2002年10月“更弗里茨”与世界棋王克拉姆尼克在巴林交手，双方以4比4战平。2003年1至2月“更年少者”与卡斯帕罗夫在纽约较量，3比3战平。,许多人在努力,机器博弈,20世纪50年代，有人设想利用机器智能来实现机器与人的对弈。1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，惊动了世界。加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳棋程序Chinook也相继成为确定的、二人、零和、完备信息游戏世界冠军西洋双陆棋这样的存在非确定因素的棋类也有了美国卡内基梅隆大学的西洋双陆琪程序BKG这样的世界冠军。对围棋、中国象棋、桥牌、扑克等许多种其它种类游戏博弈的研究也正在进行中。,机器博弈的基本思想,机器博弈的核心思想就是对博弈树节点的估值过程和对博弈树搜索过程的结合,博弈树,在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局。,机器博弈系统的构成,知识表示规则集，产生机制，构建博弈树搜索技术估值技术,博弈搜索,博弈搜索的基本思想已经提出半个多世纪，目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。没有随机因素的博弈在两个人之间进行，在任何一个时刻，一方失去的利益即为另一方得到的利益，不会出现“双赢”的局面，而且在任何时刻，博弈的双方都明确的知道每一个棋子是否存在和存在于哪里。二人、零和、完备信息的博弈搜索理论已经很系统。极大极小算法是所有搜索算法的基础。一类是作为主流的深度优先的alpha-beta搜索及其系列增强算法另一类是最佳优先的系列算法。,解谜：电脑是怎样下棋的 人机博弈程序的一般设计方法,以中国 棋为例,（1）第一步该做什么？,数据结构的选取,棋盘表示,占用空间-少操作速度-快是否方便-方便,在机器中表示棋局，让程序知道博弈状态。,九列十行,十四种不同的棋子,三十二个棋子,几种棋盘表示的方式,二维数组直观,紧凑的数据结构省空间，不直 观，速度?,比特棋盘用于8*8棋盘（国际象 棋），64位主机,（2）接下来怎么办？,产生合法走步的规则，使博弈能公正的进行，并且能够判断对手是否乱走。依赖于具体棋类特征。是一段将局面所有可能的正确走法罗列出来的程序。称之为走法产生。,几种走法产生的实现方式,一般做法,建立小型数据库,位运算,位运算走法产生之例,寻找象的可走步,位运算走法产生之要求,一个基于比特棋盘的完善的数据库该数据库应位于内存中,（3）终于到核心了,从所有的走法中找出最佳的走法，也就是,搜索,博弈概述,诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的二人零和、全信息、非偶然博弈，其特征如下：(1)对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。(2)在对垒过程中，任何一方都了解当前的格局及过去的历史。(3)任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的碰运气因素。即双方都是很理智地决定自己的行动。,博弈概述,在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是或关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是与关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。,博弈概述,这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵与或树。描述博弈过程的与或树称为博弈树，它有如下特点：(1)博弈的初始格局是初始节点。(2)在博弈树中，或节点和与节点是逐层交替出现的。自己一方扩展的节点之间是或关系，对方扩展的节点之间是与关系。双方轮流地扩展节点。(3)所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。我们假定MAX先走，处于奇数深度级的节点都对应下一步由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。,搜索算法,极大极小值算法 负极大值搜索深度优先的 alpha-beta搜索渴望搜索（Aspiration Search）极小窗口搜索（Minimal Window Search）遍历深化（Iterative Deepening）历史启发搜索（History Heuristic）杀手启发搜索(Killer Heuristic)MTD(f)算法（Memory enhanced Test Driver with f and n）,极大极小法,基本思想或算法是：(1)设博弈的双方中一方为MAX，另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。(2)为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。(3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。,极大极小法（续）,(4)当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。(5)如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。,一字棋游戏极小极大分析法,设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。用叉号表示MAX，用圆圈代表MIN。,一字棋游戏极小极大分析法,为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下设棋局为P，估价函数为e(P)(1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)(2)若P是MAX必胜的棋局，则e(P)+。(3)若P是B必胜的棋局，则e(P)-。,一字棋极大极小法的第一阶段,一字棋极大极小法的第二阶段,一字棋极大极小法的第三阶段,Alpha-Beta剪枝技术,基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。,Alpha-Beta剪枝技术,(1)对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为剪枝。,搜索算法,最佳优先算法 SSS*和DUAL*算法B*和PB*算法,Alpha-Beta剪枝,Alpha-Beta搜索,和极大极小搜索结合在奇数层进行Alpha剪枝，偶数层Beta剪枝。,和负极大值搜索结合在每一层都进行Beta剪枝。,（4）最后,评估局面优劣，配合搜索技术做出智能的选择估值技术,棋子价值评估 SideValue=Sum(piecenumber*piecevalue)棋子灵活性 Mobility=Sum(movenumber*movevalue)棋盘控制棋子关系的评估（威胁、保护、形、定势。并且要考虑到谁走棋）,估值的几种形式,终点估值 思路清晰，容易设计，模块独立性高，同搜索算法耦合程度低 速度慢,棋子价值表 TpieceTypeboardWidthboardHeight,二者结合,动态棋子价值表,估值函数的内容及其调试,Score=aX+bY+cZ+dK+X=车+马+炮+,参数确定的方法,手工调整爬山法蒙特卡罗模拟退火遗传算法,爬山法的缺陷初值依赖,蒙特卡罗,使用多种初始参数，从不同的地方开始多次爬山有足够多次的爬山，出现频率最高的结果是最优解的概率就会足够大不同初值的大量采样，使运算效率低,模拟退火,MetroPolis重要性采样的基本思想：在寻优的开始使用较高的概率进行随机突跳，随着寻优过程的深入逐步降低这一接受不佳参数概率。并且随着搜索的深入，可接受的参数的不佳程度也越来越小。,模拟退火,一次对参数改变一点，测试。提高，保留不提高，在一定概率上继续由粗到细，逼近最优参数,遗传算法,随机产生一组初始个体构成初始种群，并评价每一个体的适配值。判断算法收敛准则是否满足，若满足则输出搜索结果，否则执行以下步骤。根据适配值大小以一定方式执行复制操作。按交叉概率pc之行交叉操作。按变异概率pm执行变异操作。返回上面第二步骤。,遗传算法,适配值：对个体进行评价的指标，算法优化的主要信息，与个体的目标值对应复制：复制概率正比于适配值交叉：交换父代个体中的部分信息产生后代，继承变异：随机改变个体中的某些信息产生新个体，增加种群多样性,标准遗传算法优化框图,Genetic Algorithms 优越性,全空间并行搜索，重点集中在高性能部分，防止陷入局部最优,孰优孰劣？,名局测试和其他博弈程序对弈选不同的参数，自相对弈同向下几层的搜索结果比较,启发式搜索的一个例子,井字博弈中，博弈者在3X3数组中轮流标记，一个标记X，一个标记O,先用标记填满一行、一列或一条对角线者便赢得博弈。初始状态为空棋盘，从起点到终点的路径表明了赢棋的走法。,启发式搜索的一个例子,一个简单的启发式策略几乎可以整个地消除复杂的搜索过程。假设我方为“X”,首先,将棋子走到棋盘上有最多的赢线的点,启发式搜索的一个例子,启发信息：将棋子走到棋盘上有最多的赢线的点,衡量一个搜索策略性能的准则,完备性只要问题有解，在搜索策略的控制下就一定能找到这个（些）解尽量避免无用搜索增强搜索的目的性，尽量避免产生及考察那些无用的节点控制开销小要求搜索策略实现简单，选择及调度可用知识的开销尽可能小,问题,什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？广度优先搜索和深度优先搜索有和区别？在何种情况下广度优先搜索优于深度优先搜索？在何种情况下深度优先搜索优于广度优先搜索？试谈机器博弈的基本思想。,