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

第六讲博弈与启发式及极大极小思想
博弈:
诸如下棋、打牌、战争等一类竞争性的智能活动。
其中最简单的一种称为双方完备博弈
博弈是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。如下图 MIN 7表示只有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
MIN
MAX
由于上图所示位置具有最大的倒推值,它应当选取为MAX的第一步(正好是MAX的最好的优先走步)
算法分析②
现在图中MAX有两个可能“最好的”优先走步,假设MAX走了图上指明的那一步
MAX
MIN