人工智能(极大极小算法)课件.ppt

该【人工智能(极大极小算法)课件 】是由【yzhluyin9】上传分享，文档一共【12】页，该文档可以免费在线阅读，需要了解更多关于【人工智能(极大极小算法)课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第六讲博弈与启发式及极大极小思想
博弈:
诸如下棋、打牌、战争等一类竞争性的智能活动。
其中最简单的一种称为双方完备博弈
博弈是AI研究的起源和动力之一,是启发式算法所针对的一个重要领域
1、提供了可构造的任务领域,能明确判断成功或失败
2、博弈问题是对AI研究提出了严峻的挑战。
如何表示博弈问题的状态、博弈的过程和博弈的知识?
博弈是二人博弈、全信息、非偶然博弈、博弈双方利益完全对立,过程:
(1)对垒双方MAX和MIN轮流采取行动。结果:MAX胜、MIN败;MAX败,MIN胜;和局。
(2)对垒过程中,任何一方都了解当前的格局和过去的历史
(3)任何一方在采取行动前都要根据当前实际情况,进行得失分析,选自对己最有利而对对方最不利的对策,不存在碰运气成分。


博弈树
当某一方当前有多个行动方案可供选择时,他总是选择对自己最为有利而对对方最为不利的那个行动方案。
当轮到A方走棋时,则可供A方选择的若干个行动方案之间是“或”的关系。轮到B方走棋时,B方也有若干个可供选择的行动方案,但此时这些行动方案对A方来说它们之间是“与”的关系。
使用与或图(与或树)来表示博弈过程,叫做博弈树。

例子:假设有7枚硬币,任一选手只能将已分好的1堆钱币分成两堆
个数不等的钱币,2位选搜轮流进行,直到每一堆都只有1枚或2枚钱币,
不能再分为止,哪个选手遇到不能再分的情况,则为输。

,标上MAX/MIN。如下图MIN7表示只有1个7枚钱币的堆,由MIN来选择划分。每个叶子节点有一个1或0的值,代表MAX获胜还是MIN获胜
(1)如果父状态是MAX节点,将孩子中最大的值赋给它
(2)如果父状态是MIN节点,将孩子中最小的值赋给它
MIN
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,1,1,1,1,1
2,2,1,1,1
1
1
1
1
0
1
1
1
1
0
0
0
0
MAX
MIN
MAX
MIN
MAX
0

1、极大极小策略
是考虑双方对弈若干步之后,从可能的步中选一步相对好的步法来走,即在有限的搜索深度范围内进行求解
定义一个静态估价函数f,以便对棋局的态势作出优劣评估
规定:
MAX和MIN代表对弈双方
P代表一个棋局(即一个状态)
有利于MAX的态势,f(p)取正值
有利于MIN的态势,f(p)取负值
态势均衡,f(p)取零值
2、MINMAX的基本思想:
(1)当轮到MIN走步时,MAX应该考虑最坏的情况(即f(p)取极小值)
(2)当轮到MAX走步时,MAX应该考虑最好的情况(即f(p)取极大值)
(3)评价往回倒推时,相应于两位棋手的对抗策略,交替使用(1)和(2)两种方法传递倒推值。

例子:一字棋(或井字棋)算法分析
设棋局为P,估价函数为e(P)。
规定:
(1)若P对任何一方来说都不是获胜的位置,则e(P)=e(所有空格都放上MAX的棋子后三字成一线的总数)-e(所有空格都放上MIN的棋子后三字成一线的总数)
(2)若P是MAX必胜的棋局,则e(P)=+∞。
(3)若P是MIN必胜的棋局,则e(P)=-∞。比如P如右图示,则e(P)=6-4=2
叉代表MAX方,圆圈代表MIN方
向上值的传播规则:
若父状态在MIN层,那么孩子中最小值被传递上去
若父状态在MAX层,那么孩子中最大值被传递上去
②
现在图中MAX有两个可能“最好的”优先走步,假设MAX走了图上指明的那一步
MAX
MIN

不足:
1、地平线效应:即由于被搜索有限层深度时所发现特别好的状态引诱而遭到沉重打击
它有限搜索状态空间中搜索,具体数字是由可用的时间和空间资源来决定的。我们称这种策略为N-层预判。其中n是要搜索的层数。由于这个子图的叶子节点不是博弈的最终状态,所以按照胜利或失败来为这些状态赋值是不可能的。相反需要根据某个启发评估函数给每个节点赋一个值。这个向上传播的值并不表示最佳状态的启发值,它只代表从当前节点通过N次移动可以达到的最佳状态的启发值。
也是最重要的一点,在固定层深情况下作出的评估可能完全是误导性的。因为当把一个启发用于有限深度预判时,在这个预判深度内无法探测出一个有希望的路径是否会在以后的博弈中产生坏的结果。
2、其次空间中非常深层的状态评估时,评估结果可能由于发生过大的深度而存在偏差,过犹不及。(pearl1984)