人工智能的计算机模拟课件.pptx

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