已阅读5页,还剩17页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1,4.5 极小极大分析法,在博弈过程中,任何一方都希望自己取得胜利。因此,当某一方当前有多个行动方案可供选择时,他总是挑选对自己最为有利而对对方最为不利的那个行动。,2,4.5.1 静态估值 根据问题的特性信息定义一个估价函数,用来估算当前博弈树节点的得分。 此时估算出来的得分称为静态估值。,3,例1:一字棋游戏。 设有如图所求的九个空格,由A,B二个对弈,轮到谁走棋就往空格上放一只自己的棋子,谁先使自已的棋子构成“三子成一线”谁就取得了胜利 。,设A的棋子用,来表示,B的棋子用,来表示。,根据问题的特性信息定义一个估价函数,用来估算当前博弈树节点的得分_-静态估值(decide which one is better),4,估价函数定义:,设棋局为P,估价函数为e(P). 若P是胜负未定的棋局,则e(P)= e(+P)- e(-P) 其中 e(+P)表示棋局P上有可能使,成为三子一线的数目。,e(-P) 表示棋局P上有可能使,成为三子一线的数目。,5,e(P) = 6 4 = 2,e(-P) 表示棋局P上有可能使,成为三子一线的数目。,6,根据问题的特性信息定义一个估价函数,用来估算当前博弈树节点的得分_-静态估值(decide where next black one will go),例2:5 chesspiece game,4.5.2 极小极大分析法基本思想 站在X方 设博弈的双方中一方为X,另一方为Y,站在X方立场上为其寻找一个最优行动方案。 (2)向前搜索若干步 为了找到当前的最优行动方案,需对各个可能的方案所产生的后果进行比较。 考虑每一方案实施后对方可能采取的所有行动,并计算每一方案可能的得分。为比较不同方案的优劣,需向前搜索若干步。,8,Example 3,2,7,4,-1,1,4,根据估价函数,估算当前博弈树节点的得分。7分是最好的格局。在众多的可能格局中,如何达到最好的?,9,(3)倒推值-极小极大分析法 当端节点的估值计算出来后,再推算出父节点的得分,这样计算出的父节点的得分称为倒推值 。,对“或”节点,选其子节点中一个最大的得分作为父节点的得分;,对“与”节点,选其子节点中一个最小的得分作为父节点的得分;,10,3,2,2,7,4,-1,-1,1,1,4,-2,-2,6,4,3,5,3,2,Example 4,11,极小极大分析法-当前最好的行动方案,对“或”节点,选其子节点中一个最大的得分作为父节点的得分,这是为了使自己在可供选择的方案中选一个对自己最有利的方案;,对“与”节点,选其子节点中一个最小的得分作为父节点的得分,这是为了立足于最坏的情况。 估价函数是站在X方立场上估计分数, 当格局对对方有利时,估价函数给出的估计分值 小(对X方而言).,如果一个行动方案能获得较大的倒推值,则它就是当前最好的行动方案。,12,3,2,2,7,4,-1,-1,1,1,4,-2,-2,6,4,3,5,3,2,Example 5,当前最好的行动方案分别是?,13,所有可能的格局,Example 6 站在X方 方向前搜索,根据估价函数,估算当前博弈树节点的得分。,当前最好的行动方案是?,14,2,3,2,3,2,2,7,4,-1,-1,2,2,4,-2,-2,6,4,3,5,3,4,4,6,-5,6,-5,1,8,6,3,2,6,8,2,1,3,3,4,3,Example 6,当前最好的行动方案是?,15,例7:一字棋游戏。 设有如图所求的九个空格,由A,B二个对弈,轮到谁走棋就往空格上放一只自己的棋子,谁先使自已的棋子构成“三子成一线”谁就取得了胜利 。,设A的棋子用,来表示,B的棋子用,来表示。,16,估价函数定义:,设棋局为P,估价函数为e(P). 若P是A必胜的棋局,则e(P)=+. 若P是B必胜的棋局,则e(P)= . 若P是胜负未定的棋局,则e(P)= e(+P)- e(-P) 其中 e(+P)表示棋局P上有可能使,成为三子一线的数目。,e(-P) 表示棋局P上有可能使,成为三子一线的数目。,17,e(P) = 6 4 = 2,e(-P) 表示棋局P上有可能使,成为三子一线的数目。,18,假定: A先走棋,站在A的立场上。 博弈树每次仅扩展两层 具有对称性的两个棋局算作一个棋局。,图中节点旁的数字分别表示相应节点的静态估值或倒推值。 由图可以看出,对于A来说最好的一步棋是S3,因为 S3比S1和S2有较大的倒推值。 在A走S3这一步棋后,B的最优选择是S4,因为这一步棋的静态估值较小,对A不利。 不管B选择S4 或S5,A都要再次运用极小极大分析法产生深度为2的博弈树,以决定下一步应该如何走棋,其过程与上面类似。 图如下页,19,一字棋极小极大搜索,S0,S1,S2,S3,S4,S5,20,双方博弈4步后的当前格局,Summary 双方博弈过程中出现过的格局,初始格局,Max-Min help one side to to take action.,21,2,2,3,2,2,7,4,-1,-1,2,2,4,-2,-2,6,4,3,5,3,4,4,6,-5,6,-5,4,3,Example 8,当前最好的行动方
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 著作权版权权利归属与使用声明
- 林权转让协议书
- 红薯种植收购合同农作物资料
- 全新业务承包合同范本
- 个体店面转让协议书范本
- 公益性岗位用工协议
- 手房中介与银行合作协议范本版
- 幼儿园施工安全协议书
- 车位租赁简单的协议书范本
- 盐城租赁合同合同变更
- 2024年浙江金义融资租赁有限公司招聘笔试参考题库含答案解析
- 主题班会社会主义核心价值观主题班会课件
- 肾结石护理查房课件演示
- 2022-2023学年北京市昌平区七年级(下)期末英语试卷
- 【公开课】超越与延异教案-西方现代艺术高中美术人美版(2019)必修美术鉴赏
- 广东省深圳市龙华区2024届中考数学模拟精编试卷含解析
- 长春市中考:《道德法治》2023年考试真题与参考答案
- 校园商业街建筑设计方案
- 《固体废弃物处理与处置》期末考试试卷附答案
- 太原铁路局招聘2023届高校毕业生880人笔试参考题库(共500题)答案详解版
- 减压井 施工方案
评论
0/150
提交评论