《人工智能的计算机模拟课件33441.pptx》由会员分享，可在线阅读，更多相关《人工智能的计算机模拟课件33441.pptx（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人类智能的计算机模拟人类智能的计算机模拟一、人工智能简介一、人工智能简介二、人工智能的发展二、人工智能的发展三、博弈树搜索三、博弈树搜索3.1博弈概述博弈概述3.2极小极大分析法极小极大分析法3.3-剪枝技术剪枝技术1.1人工智能的定义v从1956年正式提出人工智能学科算起，40多年来，取得长足的发展，成为一门广泛的交叉和前沿科学。总的说来，人工智能的目的就是让计算机这台机器能够象人一样思考。科学家已经作出了汽车，火车，飞机，收音机等等，它们模仿我们身体器官的功能，但是能不能模仿人类大脑的功能呢？1.1人工智能的定义v定义定义1智能机器智能机器(intelligentmachine)能够在各类
2、环境中自主地或交互地执行各种拟能够在各类环境中自主地或交互地执行各种拟人任务人任务(anthropomorphictasks)的机器。的机器。例子1：能够模拟人的思维，进行博弈的计算机。1997年5月11日，一个名为深蓝(DeepBlue)的计算机系统战胜当时的国际象棋世界冠军盖利.卡斯帕罗夫（GarryKasparov）。例子2：能够进行深海探测的潜水机器人。例子3：在星际探险中的移动机器人，如美国研制的火星探测车。1.1人工智能的定义v定义定义2人工智能人工智能(AI)AI(artificalintelligence)斯坦福大学的斯坦福大学的Nilsson提出人工智能是关于知识的科学提出人
3、工智能是关于知识的科学（知识的表示、知识的获取以及知识的运用）（知识的表示、知识的获取以及知识的运用）,从学科的界定来定义：从学科的界定来定义：人工智能（学科）是计算机科学中涉及研究、设计和人工智能（学科）是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期主要目标在于研究用机应用智能机器的一个分支。它的近期主要目标在于研究用机器来模仿和执行人脑的某些智能功能，并开发相关理论和技器来模仿和执行人脑的某些智能功能，并开发相关理论和技术。术。从人工智能所实现的功能来定义从人工智能所实现的功能来定义：人工智能（能力）是智能机器所执行的通常与人类智人工智能（能力）是智能机器所执行的通常与人类
4、智能有关的功能，如判断、推理、证明、识别、感知、理解、能有关的功能，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。设计、思考、规划、学习和问题求解等思维活动。1.2人工智能的发展v1.2.1人工智能的起源与发展人工智能的起源与发展人工智能的发展是以硬件与软件为基础。它的发展经历了漫长的发展历程。人们从很早就已开始研究自身的思维形成，早在亚里士多德(公元前384-322年)在着手解释和编注他称之为三段论的演绎推理时就迈出了向人工智能发展的早期步伐，可以看作为原始的知识表达规范。1.2人工智能的发展v什么是三段论？三段论是以真言判断为其前提的一种演绎推理，它借助
5、于一个共同项，把两个直言判断联系起来，从而得出结论。例如：一切金属都是能够熔解的；铁是金属；所以，铁是能够熔解的。v知识表示、知识利用和知识获取是人工智能系统的三个基本问题。1.3人类智能与人工智能人类智能与人工智能v人的心理活动具有不同的层次，它可以与计算机的层次相比较，见图1.1。图1.1人类任知活动与计算机的比较1.3人类智能与人工智能人类智能与人工智能v心理活动的最高层级是思维策略，中间一层是初级信息处理，最低层级是生理过程，即中枢神经系统、神经元和大脑的活动，与此相应的是计算机程序、语言和硬件。研究认知过程的主要任务是探求高层次思维决策与初级信息处理的关系，并用计算机程序来模拟人的思
6、维策略水平，而用计算机语言模拟人的初级信息处理过程。1.3.1智能信息处理系统的假设智能信息处理系统的假设v推论一:既然人具有智能，那么他(她)就一定是个物理符号系统。v推论二:既然计算机是一个物理符号系统，它就一定能够表现出智能。v推论三:既然人是一个物理符号系统，计算机也是一个物理符号系统，那么我们就能够用计算机来模拟人的活动。1.3.1智能信息处理系统的假设智能信息处理系统的假设v1940年，维纳开始考虑计算机如何能像大脑一样工作。他发现了二者的相似性。维纳认为计算机是一个进行信息处理和信息转换的系统，只要这个系统能得到数据，机器本身就应该能做几乎任何事情。而且计算机本身并不一定要用齿轮
7、，导线，轴，电机等部件制成。麻省理工学院的一位教授为了证实维纳的这个观点，甚至用石块和卫生纸卷制造过一台简单的能运行的计算机。维纳系统地创建了控制论，根据这一理论，一个机械系统完全能进行运算和记忆。1.3.2人类智能的计算机模拟人类智能的计算机模拟v著名的英国科学家图灵被称为人工智能之父,图灵不仅创造了一个简单的通用的非数字计算模型，而且直接证明了计算机可能以某种被理解为智能的方法工作。1950年，图灵发表了题为计算机能思考吗？的论文，给人工智能下了一个定义，而且论证了人工智能的可能性。定义智慧时，如果一台机器能够通过称之为图灵实验的实验，那它就是智慧的。图灵实验的本质就是让人在不看外型的情况
8、下不能区别是机器的行为还是人的行为时，这个机器就是智慧的1.3.2人类智能的计算机模拟人类智能的计算机模拟v图灵测试游戏由一男(A)、一女(B)和一名询问者(C)进行；C与A、B被隔离，通过电传打字机与A、B对话。询问者只知道二人的称呼是X，Y，通过提问以及回答来判断，最终作出X是A，Y是B或者X是B，Y是A的结论。游戏中，A必须尽力使C判断错误，而B的任务是帮助C。当一个机器代替了游戏中的A，并且机器将试图使得C相信它是一个人。如果机器通过了图灵测试，就认为它是智慧的。1.3.2人类智能的计算机模拟人类智能的计算机模拟v物理符号系统假设的推论一也告诉我们，人有智能，所以他是一个物理符号系统；
9、推论三指出，可以编写出计算机程序去模拟人类的思维活动。这就是说，人和计算机这两个物理符号系统所使用的物理符号是相同的，因而计算机可以模拟人类的智能活动过程。1.4人工智能的研究和应用领域人工智能的研究和应用领域v在大多数学科中存在着几个不同的研究领域，每个领域都有其特有的感兴趣的研究课题、研究技术和术语。在人工智能中，这样的领域包括语言处理、自动定理证明、智能数据检索系统、视觉系统、问题求解、人工智能方法和程序语言以及自动程序设计等。在过去30多年中，已经建立了一些具有人工智能的计算机系统；例如，能够求解微分方程的，下棋的，设计分析集成电路的，合成人类自然语言的，检索情报的，诊断疾病以及控制太
10、空飞行器和水下机器人的具有不同程度人工智能的计算机系统。1.4.1问题求解问题求解v人工智能的第一个大成就是发展了能够求解难题的下棋(如国际象棋)程序。在下棋程序中应用的某些技术，如向前看几步，并把困难的问题分成一些比较容易的子问题，发展成为搜索和问题归约这样的人工智能基本技术。今天的计算机程序能够下锦标赛水平的各种方盘棋、十五子棋和国际象棋。另一种问题求解程序把各种数学公式符号汇编在一起，其性能达到很高的水平，并正在为许多科学家和工程师所应用。有些程序甚至还能够用经验来改善其性能。1.4.2逻辑推理与定理证明逻辑推理与定理证明v逻辑推理是人工智能研究中最持久的子领域之一。其中特别重要的是要找
11、到一些方法，只把注意力集中在一个大型数据库中的有关事实上，留意可信的证明，并在出现新信息时适时修正这些证明。对数学中臆测的定理寻找一个证明或反证，确实称得上是一项智能任务。为此不仅需要有根据假设进行演绎的能力，而且需要某些直觉技巧。1976年7月，美国的阿佩尔(K.Appel)等人合作解决了长达124年之久的难题-四色定理。他们用三台大型计算机，花去1200小时CPU时间，并对中间结果进行人为反复修改500多处。四色定理的成功证明曾轰动计算机界。1.4.3自然语言理解自然语言理解vNLP(NaturalLanguageProcessing)自然语言处理也是人工智能的早期研究领域之一，已经编写出
12、能够从内部数据库回答用英语提出的问题的程序，这些程序通过阅读文本材料和建立内部数据库，能够把句子从一种语言翻译为另一种语言，执行用英语给出的指令和获取知识等。有些程序甚至能够在一定程度上翻译从话筒输入的口头指令(而不是从键盘打入计算机的指令)。目前语言处理研究的主要课题是：在翻译句子时，以主题和对话情况为基础，注意大量的一般常识-世界知识和期望作用的重要性。人工智能在语言翻译与语音理解程序方面已经取得的成就，发展为人类自然语言处理的新概念。1.4.4自动程序设计自动程序设计v也许程序设计并不是人类知识的一个十分重要的方面，但是它本身却是人工智能的一个重要研究领域。这个领域的工作叫做自动程序设计
13、。已经研制出能够以各种不同的目的描述(例如输入/输出对，高级语言描述，甚至英语描述算法)来编写计算机程序。这方面的进展局限于少数几个完全现成的例子。对自动程序设计的研究不仅可以促进半自动软件开发系统的发展，而且也使通过修正自身数码进行学习(即修正它们的性能)的人工智能系统得到发展。自动编制一份程序来获得某种指定结果的任务同证明一份给定程序将获得某种指定结果的任务是紧密相关的。后者叫做程序验证。许多自动程序设计系统将产生一份输出程序的验证作为额外收获。1.4.5专家系统专家系统v一般地说，专家系统是一个智能计算机程序系统，其内部具有大量专家水平的某个领域知识与经验，能够利用人类专家的知识和解决问
14、题的方法来解决该领域的问题。也就是说，专家系统是一个具有大量专门知识与经验的程序系统，它应用人工智能技术，根据某个领域一个或多个人类专家提供的知识和经验进行推理和判断，模拟人类专家的决策过程，以解决那些需要专家决定的复杂问题。当前的研究涉及有关专家系统设计的各种问题。这些系统是在某个领域的专家(他可能无法明确表达他的全部知识)与系统设计者之间经过艰苦的反复交换意见之后建立起来的。在已经建立的专家咨询系统中，有能够诊断疾病的(包括中医诊断智能机)，估计潜在石油等矿藏的，研究复杂有机化合物结构的以及提供使用其它计算机系统的参考意见等。发展专家系统的关键是表达和运用专家知识，1.4.5专家系统专家系
15、统v即来自人类专家的并已被证明对解决有关领域内的典型问题是有用的事实和过程。专家系统和传统的计算机程序最本质的不同之处在于专家系统所要解决的问题一般没有算法解，并且经常要在不完全、不精确或不确定的信息基础上作出结论。专家系统可以解决的问题一般包括解释、预测、诊断、设计、规划、监视、修理、指导和控制等。高性能的专家系统也已经从学术研究开始进入实际应用研究。随着人工智能整体水平的提高，专家系统也获得发展。正在开发的新一代专家系统有分布式专家系统和协同式专家系统等。在新一代专家系统中，不但采用基于规则的方法，而且采用基于模型的原理。1.4.6机器学习v学习能力无疑是人工智能研究上最突出和最重要的一个
16、方面。人工智能在这方面的研究近年来取得了一些进展。学习是人类智能的主要标志和获得知识的基本手段。机器学习(自动获取新的事实及新的推理算法)是使计算机具有智能的根本途径。正如香克(R.Shank)所说：一台计算机若不会学习，就不能一台计算机若不会学习，就不能称为具有智能的。称为具有智能的。此外，机器学习还有助于发现人类学习的机理和揭示人脑的奥秘。所以这是一个始终得到重视，理论正在创立，方法日臻完善，但远未达到理想境地的研究领域。1.5人工智能对人类的影响人工智能对人类的影响v1.5.1人工智能对经济的影响人工智能对经济的影响人工智能系统的开发和应用，已为人类创造出可观的经济效益，专家系统就是一个
17、例子。随着计算机系统价格的继续下降，人工智能技术必将得到更大的推广，产生更大的经济效益。下面略举二例说明。1.5.1人工智能对经济的影响人工智能对经济的影响v1.专家系统的效益专家系统的效益成功的专家系统能为它的建造者、拥有者和用户带来明显的经济效益。用比较经济的方法执行任务而不需要有经验的专家，可以极大地减少劳务开支和培养费用。由于软件易于复制，所以专家系统能够广泛传播专家知识和经验，推广应用数量有限的和昂贵的专业人员及其知识。如果保护得当，软件能被长期地和完整地保存。领域专业人员(如医生)难以同时保持最新的实际建议(如治疗方案和方法)，而专家系统却能迅速地更新和保存这类建议，使终端用户(如
18、病人)从中受益。1.5.1人工智能对经济的影响人工智能对经济的影响v2.人工智能推动计算机技术发展人工智能推动计算机技术发展人工智能研究已经对计算机技术的各个方面产生并将继续产生较大影响。人工智能应用要求繁重的计算，促进了并行处理和专用集成片的开发。算法发生器和灵巧的数据结构获得应用，自动程序设计技术将开始对软件开发产生积极影响。所有这些在研究人工智能时开发出来的新技术，推动了计算机技术的发展，进而使计算机为人类创造更大的经济实惠。1.5.2人工智能对社会的影响人工智能对社会的影响v人工智能在给它的创造者、销售者和用户带来经济利益的同时，就象任何新技术一样，它的发展也引起或即将出现许多问题，并
19、使一些人感到担心或懊恼。1.5.2人工智能对社会的影响人工智能对社会的影响v。1.劳务就业问题劳务就业问题由于人工智能能够代替人类进行各种脑力劳动，将会使一部分人不得不改变他们的工种，甚至造成失业。人工智能在科技和工程中的应用，会使一些人失去介入信息处理活动(如规划、诊断、理解和决策等)的机会，甚至不得不改变自己的工作方式。1.5.2人工智能对社会的影响人工智能对社会的影响v2.社会结构变化社会结构变化人们一方面希望人工智能和智能机器能够代替人类从事各种劳动，另一方面又担心它们的发展会引起新的社会问题。实际上，近十多年来，社会结构正在发生一种静悄悄的变化。人-机器的社会结构，终将为人-智能机器
20、-机器的社会结构所取代。智能机器人就是智能机器之一。现在和将来的很多本来是由人承担的工作将由机器人来担任，因此，人们将不得不学会与有智能的机器相处，并适应这种变化了的社会结构。1.5.2人工智能对社会的影响人工智能对社会的影响v3.思维方式与观念的变化思维方式与观念的变化人工智能的发展与推广应用，将影响到人类的思维方式和传统观念，并使它们发生改变。例如，传统知识一般印在书本报刊或杂志上，因而是固定不变的，而人工智能系统的知识库的知识却是可以不断修改、扩充和更新的。又如，一旦专家系统的用户开始相信系统(智能机器)的判断和决定，那么他们就可能不愿多动脑筋，变得懒惰，并失去对许多问题及其求解任务的责
21、任感和敏感性。那些过分依赖计算器的学生，他们的主动思维能力和计算能力也会明显下降。过分地依赖计算机的建议而不加分析地接受，将会使智能机器用户的认知能力下降，并增加误解。在设计和研制智能系统时，应考虑到上述问题，尽量鼓励用户在问题求解中的主动性，让他们的智力积极参与问题求解过程。1.5.2人工智能对社会的影响人工智能对社会的影响v4.心理上的威胁心理上的威胁人工智能还使一部分社会成员感到心理上的威胁，或叫人工智能还使一部分社会成员感到心理上的威胁，或叫做精神威胁。人们一般认为，只有人类才具有感知精神，而做精神威胁。人们一般认为，只有人类才具有感知精神，而且以此与机器相别。如果有一天，这些人开始相
22、信机器也能且以此与机器相别。如果有一天，这些人开始相信机器也能够思维和创作，那么他们可能会感到失望，甚至感到威胁。够思维和创作，那么他们可能会感到失望，甚至感到威胁。他们担心：有朝一日，智能机器的人工智能会超过人类的自他们担心：有朝一日，智能机器的人工智能会超过人类的自然智能，使人类沦为智能机器和智能系统的奴隶。对于人的然智能，使人类沦为智能机器和智能系统的奴隶。对于人的观念观念(更具体地指人的精神更具体地指人的精神)和机器的观念和机器的观念(更具体地指人工智更具体地指人工智能能)之间的关系问题，哲学家、神学家和其它人们之间一直之间的关系问题，哲学家、神学家和其它人们之间一直存在着争论。按照人
23、工智能的观点，人类有可能用机器来规存在着争论。按照人工智能的观点，人类有可能用机器来规划自己的未来，甚至可以把这个规划问题想象为一类状态空划自己的未来，甚至可以把这个规划问题想象为一类状态空间搜索。当社会上一部分人欢迎这种新观念时，另一部分人间搜索。当社会上一部分人欢迎这种新观念时，另一部分人则发现这些新观念是惹人烦恼的和无法接受的，尤其是当这则发现这些新观念是惹人烦恼的和无法接受的，尤其是当这些观念与他们钟爱的信仰和观念背道而驰时。些观念与他们钟爱的信仰和观念背道而驰时。1.5.2人工智能对社会的影响人工智能对社会的影响v5.技术失控的危险任何新技术最大危险莫过于人类对它失去了控制，或者是它
24、落入那些企图利用新技术反对人类的人手中。有人担心机器人和人工智能的其它制品威胁人类的安全。为此，著名的美国科幻作家阿西莫夫(I.Asimov)提出了“机器人三守则”：(1)机器人必须不危害人类，也不允许它眼看人类受害而袖手旁观。(2)机器人必须绝对服从人类，除非这种服从有害于人类。(3)机器人必须保护自身不受伤害，除非为了保护人类或者是人类命令它作出牺牲。我们认为，如果把这个“机器人三守则”推广到整个智能机器，成为“智能机器三守则”，那么，人类社会就会更容易接受智能机器和人工智能。人工智能技术是一种信息技术，能够极快地传递。我们必须保持高度警惕,防止人工智能技术被用于反对人类和危害社会的犯罪(
25、有的人称之为“智能犯罪”)。同时，人类有足够的智慧和信心，能够研制出防范、检测和侦破各种智能犯罪活动的智能手段。1.5.2人工智能对社会的影响人工智能对社会的影响v6.引起的法律问题引起的法律问题人工智能的应用技术不仅代替了人的一些体力劳动，也代替了人的某些脑力劳动，有时甚至行使着本应由人担任的职能，免不了引起法律纠纷。比如医疗诊断专家系统万一出现失误，导致医疗事故，怎么样来处理，开发专家系统者是否要负责任，使用专家系统者应负什么责任，等等。人工智能的应用将会越来越普及，正在逐步进入家庭，使用机顶盒技术的智能化电器已问世。可以预料，将会出现更多的与人工智能的应用有关的法律问题，需要社会在实践的
26、基础上从法律角度作出对这些问题的解决方案。要通过法律手段，对利用人工智能技术来反对人类和危害社会的犯罪行为进行惩罚，使人工智能技术为人类的利益作贡献。1.5.3人工智能对文化的影响人工智能对文化的影响v1.改善人类知识改善人类知识在重新阐述我们的历史知识的过程中，哲学家、科学家和人工智能学家有机会努力解决知识的模糊性以及消除知识的不一致性。这种努力的结果，可能导致知识的某些改善，以便能够比较容易地推断出令人感兴趣的新的真理。1.5.3人工智能对文化的影响人工智能对文化的影响2.改善人类语言改善人类语言根据语言学的观点，语言是思维的表现和工具，思维规律可用语言学方法加以研究，但人的下意识和潜意识
27、往往只能意会，不可言传。由于采用人工智能技术，综合应用语法、语义和形式知识表示方法，我们有可能在改善知识的自然语言表示的同时，把知识阐述为适用的人工智能形式。随着人工智能原理日益广泛传播，人们可能应用人工智能概念来描述他们生活中的日常状态和求解各种问题的过程。人工智能能够扩大人们交流知识的概念集合，为我们提供一定状况下可供选择的概念，描述我们所见所闻的方法以及描述我们的信念的新方法。1.5.3人工智能对文化的影响人工智能对文化的影响v3.改善文化生活改善文化生活人工智能技术为人类文化生活打开了许多新的窗口。比如图像处理技术必将对图形艺术、广告和社会教育部门产生深远的影响。比如现有的智力游戏机将
28、发展为具有更高智能的文化娱乐手段。综上分析我们知道，人工智能技术对人类的社会进步、经济发展和文化提高都有巨大的影响。随着时间的推进和技术的进步，这种影响将越来越明显地表现出来。还有一些影响，可能是我们现在难以预测的。可以肯定，人工智能将对人类的物质文明和精神文明产生越来越大的影响。三、博弈树搜索三、博弈树搜索v3.1博弈概述博弈概述诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的二人零和、全信息、非偶然博弈，其特征如下：(1)对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。(2)在对垒过程
29、中，任何一方都了解当前的格局及过去的历史。(3)任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的碰运气因素。即双方都是很理智地决定自己的行动。三、博弈树搜索三、博弈树搜索v在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在MAX方的立场上，则可供MAX方选择的若干行动方案之间是或关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，
30、MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是与关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。三、博弈树搜索三、博弈树搜索v这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博弈过程用图表示出来，则得到的是一棵与或树。描述博弈过程的与或树称为博弈树，它有如下特点：三、博弈树搜索三、博弈树搜索v(1)博弈的初始格局是初始节点。(2)在博弈树中，或节点和与节点是逐层交替出现的。自己一方扩展的节点之间是或关系，对方扩展的节点之间是与关系。双方轮流地扩展节点。(3)所有自己一方获
31、胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。我们假定MAX先走，处于奇数深度级的节点都对应下一步由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。3.2极小极大分析法极小极大分析法v在二人博弈问题中，为了从众多可供选择的行动方案中选出一个对自己最为有利的行动方案，就需要对当前的情况以及将要发生的情况进行分析，通过某搜索算法从中选出最优的走步。在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树，如果试图通过直到终局的与或树搜索而得到最好的一步棋是不可能的，比如曾有人估计，西洋跳棋完整的博弈树约有1040个节点。最常使
32、用的分析方法是极小极大分析法。其基本思想或算法是：3.2极小极大分析法极小极大分析法v(1)设博弈的双方中一方为MAX，另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。(2)为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。(3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。3.2极小极大分析法极小极大分析法v(4)当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大
33、的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。(5)如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。3.2极小极大分析法极小极大分析法v在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树。试图利用完整的博弈树来进行极小极大分析是困难的。可行的办法是只生成一定深度的博弈树，然后进行极小极大分析,找出当前最好的行动方案。在此之后，再在已选定的分支上扩展一定深度，再选最好的行动方案。如此进行下去，直到取
34、得胜败的结果为止，至于每次生成博弈树的深度，当然是越大越好，但由于受到计算机存储空间的限制，只好根据实际情况而定。一字棋游戏极小极大分析法一字棋游戏极小极大分析法v设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。一字棋游戏极小极大分析法一字棋游戏极小极大分析法v用叉号表示MAX，用圆圈代表MIN。比如下图中就是MIN取胜的棋局。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：v设棋局为P，估价函数为e(P)。一字棋游戏极小极大分析法一字棋游戏极小极大分析法v
35、(1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)v(2)若P是MAX必胜的棋局，则e(P)+。v(3)若P是B必胜的棋局，则e(P)-。如右图示,则e(P)=6-4=2一字棋游戏极小极大分析法一字棋游戏极小极大分析法v要注意利用棋盘位置的对称性,在生成后继节点的位置时，下列博弈结局一字棋游戏极小极大分析法一字棋游戏极小极大分析法v都是相同的棋局(在博弈中，一宇棋的分枝系数比较小起初是由于对称性，而后是由于棋盘上未布子的空格减少所致)。图3.15画出了经过两层搜索生成的博弈树，静态估值
36、记在端节点下面，倒推值记在圆圈内。图3.15应用于一字棋的极小极大搜索过程(第一阶段)一字棋游戏极小极大分析法一字棋游戏极小极大分析法v由于右图所示位置具有最大的倒推值，它应当选取为MAX的第一步（正好是MAX的最好的优先走步）。一字棋游戏极小极大分析法一字棋游戏极小极大分析法v现在我们假设MAX走了这一步，而MIN的回步是直接在X上方的空格里放上一个圆圈(对MAX来说这是一步坏棋，他一定没有采用好的搜索策略)。下一步，MAX又在新的格局下搜索两层，产生如图3.16所示的搜索图。图3.16应用于一字棋的极小极大搜索过程(第二阶段)一字棋游戏极小极大分析法一字棋游戏极小极大分析法v现在图中MAX
37、有两个可能“最好的”优先走步，假设MAX走了图上指明的那一步。而MIN为了避免立即败北被迫走了另一步，从而产生如下棋局：MAX再次搜索，产生如图3.17所示的树。图3.17应用于一字棋的极小极大搜索过程(第三阶段)一字棋游戏极小极大分析法一字棋游戏极小极大分析法v在这棵树中某些端节点(例如其中一个标记着A)代表MIN获胜，因此它们的估值为。当这些估值被倒推回去时，可看到MAX的最好的也是唯一能使他避免立即失败的一个走步。现在，MIN可以看出MAX必然在他的下一走步中获胜，因此，MIN只好认输。3.3-剪枝技术剪枝技术v首先分析极小极大分析法效率，上述的极小极大分析法，实际是先生成一棵博弈树，然
38、后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了-剪枝技术。-剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：3.3-剪枝技术剪枝技术v(1)对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为剪枝。(2)对于
39、一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为剪枝。3.3-剪枝技术剪枝技术v从算法中看到：(1)MAX节点(包括起始节点)的值永不减少；(2)MIN节点(包括起始节点)的值永不增加。v在搜索期间，和值的计算如下：(1)一个MAX节点的值等于其后继节点当前最大的最终倒推值。(2)一个MIN节点的值等于其后继节点当前最小的最终倒推值。图318一步棋第一阶段部分搜索树3.3-剪枝技术剪枝技术v画出根节点、节点A及5个
40、儿子，计算并标上这些节点的静态估值，A的5个儿子节点的静态估值的最小值是-1，因此节点A的倒推值为-1，从而起始节点的倒推值的下界定为-1，当然有可能比-1更小，因为它有其他的儿子节点。画出节点B及它的第一个儿子节点C，算出节点C的静态值为-1，于是节点B的倒推值不会比-1大，又注意到节点B的最终倒推值不会小于起始节点的值，由此可肯定最终倒推值=-1。由于值不比值小，故可以终止节点B的搜索。3.3-剪枝技术剪枝技术v例：-剪枝技术的例子，如下图所示。图中所生成的搜索树共有六层(我们规定首先生成最左面的节点。MAX节点用方块表示，MIN节点用圆圈表示)。图中还给出了端节点的静态估值。现在假设我们
41、采用-剪枝技术来引导深度优先搜索。由-剪枝技术生成的子树在图中用粗树枝表示。发生修剪的那些节点用“”表示。说明-剪枝技术的例题v我们注意到原先41个端节点只有18个必须估值，可见说明-方法能够有效地提高效率。下面让我们对-剪枝技术的搜索效率再作一些分析。要进行-修剪，必须至少使某一部分的搜索树生长到最大深度，因为和值必须以端节点的静态估值为依据。因此采用-剪枝技术通常都要使用某种深度优先的搜索方法。而且在一次搜索期间修剪的枝数取决于早期的、值与最终倒推值之间的近似程度。起始节点的最终倒推值等于某个端节点的静态估值。如果在深度优先搜索过程中第一次就遇到这个端节点，则修剪枝数最大。当前修剪枝数最大时，需要生成和估计的端节点数就最少。