人工智能知识表示与推理博弈树搜索精品PPT课件.pptx

2024/3/262.4博弈问题的搜索技术2.4.1博弈问题的表达2.4.2极大极小搜索过程2.4.3?-?剪枝法

2024/3/262.4.1博弈问题的表达博弈是一类具有竞争性的智能活动双人博弈：即两位选手对垒，轮流依次走步，其中任何一方都完全知道对方过去已经走过的棋步和今后可能的走步，其结果是一方赢(而另一方则输)，或双方和局

2024/3/26博弈的例子：一字棋跳棋中国象棋围棋五子棋

2024/3/26双方的智能活动，任何一方都不能单独控制博弈过程，而是由双方轮流实施其控制对策的过程博弈的特点：

2024/3/26如何根据当前的棋局，选择对自己最有利的一步棋？！人工智能中研究的博弈问题：

2024/3/26用博弈树来表示，它是一种特殊的与或图。节点代表博弈的格局（即棋局），相当于状态空间中的状态，反映了博弈的信息。与节点、或节点隔层交替出现博弈问题的表示：

2024/3/26假设博弈双方为：MAX和MIN在博弈过程中，规则是双方轮流走步。在博弈树中，相当于博弈双方轮流扩展其所属节点为什么与节点、或节点隔层交替出现？

2024/3/26从MAX方的角度来看：所有MIN方节点都是与节点理由：因为MIN方必定选择最不利于MAX方的方式来扩展节点，只要MIN方节点的子节点中有一个对MAX方不利，则该节点就对MAX方不利，故为“与节点”MIN好招

2024/3/26从MAX方的角度来看：所有属于MAX方的节点都是“或节点”理由：因为扩展MAX方节点时，MAX方可选择扩展最有利于自己的节点，只要可扩展的子节点中有一个对已有利，则该节点就对已有利MAX好招

2024/3/26总之从MAX方来说，与节点、或节点交替出现；反之，从MIN方的角度来看，情况正好相反

2024/3/26在博弈树中，先行一方的初始状态对应着树的根节点，而任何一方获胜的最终格局为目标状态，对应于树的终叶节点（可解节点或本原问题）但是，从MAX的角度出发，所有使MAX获胜的状态格局都是本原问题，是可解节点，而使MIN获胜的状态格局是不可解节点

2024/3/26例Grundy博弈：分配物品的问题如果有一堆数目为N的钱币，由两位选手轮流进行分配，要求每个选手每次把其中某一堆分成数目不等的两小堆，直至有一选手不能将钱币分成不等的两堆为止，则判定这位选手为输家

2024/3/26用数字序列加上一个说明来表示一个状态：(3,2,1,1,MAX)数字序列：表示不同堆中钱币的个数说明：表示下一步由谁来分，即取MAX或MIN

2024/3/26现在取N＝7的简单情况，并由MIN先分注：如果MAX走红箭头的分法，必定获胜所有可能的分法(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(2,2,1,1,1,MIN)(3,1,1,1,1,MIN)(2,1,1,1,1,1,MAX)

2024/3/26对于比较复杂的博弈问题，只能模拟人的思维“向前看几步”，然后作出决策，选择最有利自己的一步。即只能给出几层走法，然后按照一定的估算办法，决定走一好招

2024/3/262.4.2极大极小过程对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺利进行假设由MAX来选择走一步棋，问题是：MAX如何来选择一步好棋？

2024/3/26①对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数值。值越大对MAX越有利，反之越不利极大极小过程的基本思路：

2024/3/26②对于给定的格局，MAX给出可能的走法，然后MIN对应地给出相应的走法，这样重复若干次，得到一组端节点（必须由MIN走后得到的，由MAX下的棋局）。这一过程相当于节点扩展注：博弈树深度或层数一定是偶数

2024/3/26③对于每一个端节点，计算出它们的静态估价函数，然后自下而上地逐层计算倒推值，直到MAX开始的格局。在MIN下的格局中取估值的最小值，在MAX下格局中取估值的最大值④取估值最大的格局作为MAX要走的一招棋

2024/3/26例：向前看一步的两层博弈树

2024/3/26定义静态函数e(P)的一般原则：

2024/3/26OPEN：存放待扩展的节点，此时为队列，即以宽度优先的策略扩展节点CLOSED：存放已扩展的节点，此时为堆栈，即后扩展的节点先计算静态估价函数值符号：

2024/3/261、将初始节点S放入OPEN表中，开始时搜索树T由初始节点S构成2、若OPEN表为空，则转53、将OPEN表中