《博弈与搜索》ppt课件

《《博弈与搜索》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章博弈与搜索5.1博弈与对策博弈一向被认为是富有挑战性的智力的游戏，有着难以言语的魅力。博弈问题常与对策问题联系在一起。对策论（GameTheory）用数字方法研究对策问题。一般将对策问题分为零和对策和非零和对策。最典型的零和对策问题是我国古代齐王与田忌赛马的问题。该问题是齐王与田忌都有可分为上、中、下三匹马。齐王的上马、中马、下马都比田忌相应的上马、中马、下马好，但田忌的上马比齐王的中马好，田忌的中马比齐王的下马好，聪明的田忌采取了下述对策后一举取胜：5.1博弈与对策非零和对策的例子有：囚犯难题（Theprisonerdilemma）。该问题是有

2、两个嫌疑犯A和B，暂时还没有获得他们犯罪的确定的证据。现对他们判刑的规则是：博弈虽然自古就是人与人的对弈，但自从有了计算机以后，人们开始就有用计算机下棋的想法，早在60年代就已经出现若干博弈程序，并达到较高的水平，现已出现计算机博弈程序能够与人类博弈大师抗衡的局面。举世瞻目的人机对弈是1997年IBM公司编制的深蓝（deepblue）计算机与国际象棋大师卡斯帕罗夫对弈，取得了三胜二和一负的好成绩。博弈的研究不断为人工智能提出新的课题，可以说博弈是人工智能研究的起源和动力之一。博弈问题对人的深层次的知识研究提出了严峻的挑战。如何表示博弈问题的状态，博弈过

3、程和博弈取胜的知识，这是目前人类仍在探讨之中的问题。要提高博弈问题求解程序的效率，应作到如下两点：改进生成过程，使之只生成好的走步，如按棋谱的方法生成下一步；改进测试过程，使最好的步骤能够及时被确认。要达到上述目的有效途径是使用启发式方法引导搜索过程，使其只生成可能赢的走步。而这样的博弈程序应具备：一个好的（即只产生可能赢棋步骤的）生成过程。一个好的静态估计函数。下面介绍博弈中两种最基本的搜索方法。5.2极小极大搜索过程5.2.1．极小极大搜索的思想极小极大搜索策略是考虑双方对弈若干步之后，从可能的步中选一步相对好的走法来走，即在有限的搜索深度范围内进

4、行求解。为此要定义一个静态估计函数f，以便对棋局的势态作出优劣估计。这个函数可根据棋局优劣势态的特征来定义。这里规定：MAX代表程序方MIN代表对手方P代表一个棋局（即一个状态）f（P）的大小由棋局势态的优劣来决定:有利于MAX的势态，f（P）取正值有利于MIN的势态，f（P）取负值势态均衡，f（P）取零使用静态函数进行估计必须以下述两个条件为前提：（１）双方都知道各自走到什么程度、下一步可能做什么。（２）不考虑偶然因数影响。在这个前提下，博弈双方必须考虑：（１）如何产生一个最好的走步。（２）如何改进测试方法，能尽快搜索到最好的走步。MINMAX的基本

5、思想是：（１）当轮到MIN走步的结点时，MAX应考虑最坏的情况（因此，f(p)取极小值）。（２）当轮到MAX走步的结点时，MAX应考虑最好的情况（因此，f(p)取极大值）。（３）当评价往回倒推时，相应于两位棋手的对抗策略，不同层上交替的使用（１）、（２）两种方法向上传递倒推值。5.2.2极小极大搜索算法极小极大过程的算法如下：1.T:=(s,MAX),OPEN:=(s),CLOSED:=();{开始时树由初始结点构成，OPEN表只含有s.}2.LOOP1:IFOPEN=()THENGOLOOP2;3.ｎ:＝FIRST(OPEN),REMOVE(n,OP

6、EN),ADD_TO_LAST(n,CLOSED);//约定加到尾部4.IFn可直接判定为赢、输或平局THENf(n):=∞∨-∞∨0,GOLOOP1ELSEEXPAND(n)→ni,ADD({ni},T)IFd({ni})

7、）THENf(np):=MAX{f(nci)},REMOVE(np,CLOSED);{若MAX所有子节点均有值，则该MAX取其极大值。}IF(np∈MIN)∧(f(nci∈MAX)有值）THENf(np):=MIN{f(nci)},REMOVE(np,CLOSED);{若MIN所有子节点均有值，则该MIN取其极小值。}7.GOLOOP2;8.LOOP3:IFf(s)=NILTHENEXIT(END∨Mark(Move,T));{s有值，或结束或标记走步}其中ADD_TO_LAST约定加入节点到表的尾部，END表示失败或成功或平局退出，MARK标记一个走

8、步。5.2.3算法分析与举例该算法分三个阶段进行。第一阶段为步骤2－4，使用宽度优先法生成规定