博弈搜索-copy_北航6系人工智能课件ppt课件
32页1、北京航空航天大学软件开发环境国家重点实验室 Slide 1问题求解基本原理博 弈:被认为高智能行为游戏; 不断为AI研究提出新课题,推动AI研究的发展。搜 索 技 术 ( 三 )博 弈 搜 索北京航空航天大学软件开发环境国家重点实验室 Slide 2基于博弈搜索的搜索策略n 博弈问题及博弈树概念n 博弈搜索控制策略n 博弈搜索算法及其应用实例n 博弈树的 - 剪枝 北京航空航天大学软件开发环境国家重点实验室 Slide 3博弈问题及博弈树概念n 博弈问题:对抗的双方参加博弈,取胜的因素不仅取决于一方的如意 算盘,还需充分考虑对方的应付策略,(一字棋、国际象 棋、打扑克、中国象棋、围棋)。 双人完备信息:对垒的双方轮流走步,对弈的条件和走步规则完全相同。每 一方不仅知道对方已走过的所有棋步,而且还能估计出对方 未来可能走的棋步。北京航空航天大学软件开发环境国家重点实验室 Slide 4博弈问题及博弈树概念n 博弈问题描述:w 棋局描述;w 棋局走步规则。 博弈搜索过程:搜索棋局走步规则,隐含生成一棵特殊的与或树博弈问题求解:北京航空航天大学软件开发环境国家重点实验室 Slide 5博弈问
2、题及博弈树概念与或节点分层交替出现的与或树从甲的立场出发或节点与节点或节点完全取胜解 图甲走步北京航空航天大学软件开发环境国家重点实验室 Slide 6博弈问题及博弈树概念n判断走步的极小-极大原则:v 考虑对方走步时(与节点):假定对手不会犯错 误,他总是选择对自己最有利,对我方最不利的 棋步走。因此,我方不能采取任何冒险行动,视对 手将走出的棋局为极小值;v 考虑我方走步时(或节点):应在对方造成的 最坏的局势中尽可能地选择最好的棋着走,视自己 可能走出的棋局为极大值。北京航空航天大学软件开发环境国家重点实验室 Slide 7基于博弈搜索的搜索策略n 博弈问题及博弈树n 博弈搜索控制策略n 博弈搜索算法及其应用实例n 博弈树的 - 剪枝 w 完整的博弈搜索策略(盲目搜索策略)w 有界深度博弈搜索策略北京航空航天大学软件开发环境国家重点实验室 Slide 8完整的博弈搜索策略n核心思想:从博弈的初始格局开始,轮番考虑自己与对方可能的所有走步,生成出棋局的各个格局,直到达到分出胜负输赢的终止格局为止,此搜索过程产生的一棵完整的博弈树。北京航空航天大学软件开发环境国家重点实验室 Slid
3、e 9完整的博弈搜索策略n博弈问题实例:有一堆数目为N的钱币,甲、乙二人轮流分堆。要求每人每次挑 选其中某一堆钱币,将其分成数目不等的两小堆。分堆过程持 续,直至其中一人无法再将任一堆钱币分成数目不等的两堆时 ,则认输。 博弈问题描述:分堆格局(状态): (x1,x2,xn,M), 其中,xi: 第 i 堆钱币的个数;M: 当前走步人编号 -(MAX, MIN)走步规则:IF (x1,x2,xn,M) (xi = Y+Z) (Y Z)THEN (x1,x2,xi-1, Y, Z, xi+1, , xn, M)北京航空航天大学软件开发环境国家重点实验室 Slide 10完整的博弈搜索策略站在MAX立场与节点或节点 与节点完全取胜的完 备策略北京航空航天大学软件开发环境国家重点实验室 Slide 11n特点: w 搜索策略简单,易于控制,可用于简单的博弈或一个复 杂博弈的残局;完整的博弈搜索策略w不适合复杂的博弈问题搜索 - 指数爆炸。例,中国象棋:设每种格局有40种走法,一盘棋双方平均走50步,完整的博弈搜索-搜索节点数(402)50 10160,搜索深度达100层。 有必要引入有界深度
4、博弈搜索策略。北京航空航天大学软件开发环境国家重点实验室 Slide 12基于博弈搜索的搜索策略n 博弈问题及博弈树n 博弈搜索控制策略w 完整的博弈搜索策略(盲目搜索策略)w 有界深度博弈搜索策略(启发式搜索策略)北京航空航天大学软件开发环境国家重点实验室 Slide 13有界深度搜索策略n 核心思想:根据对方已走出的棋步,构造出具有一定深度的博 弈树,并从此局部博弈树中选择相对好的棋着走。 需解决的关键问题:定义估计终结棋局优劣的评价函数;给出棋局优劣性传递的计算方法。北京航空航天大学软件开发环境国家重点实验室 Slide 14定义棋局的评价函数设 P 为有界博弈树中棋局;(P): 棋局优劣的评价函数。 例1:从当前棋局到离我方最后取胜的差距:胜利在望 (P)值较大,败局显露 (P)值较小; 例2:从当前棋局到到某个明显有利于我方棋局的差距:吃掉对方一子, 或者 “叫吃”。v (P)MAX赢 = (P)MIN输 = + v (P)MAX输 = (P)MIN赢 = - v (P)平 = 0v (P) 任一终叶棋局优劣的评价函数的定义原则:北京航空航天大学软件开发环境国家重点实验室 S
《博弈搜索-copy_北航6系人工智能课件ppt课件》由会员ZJ****4分享,可在线阅读,更多相关《博弈搜索-copy_北航6系人工智能课件ppt课件》请在金锄头文库上搜索。
精编小学英语语法(0002)
如何使SEO在企业品牌营销和渠道拓展中发挥最大价值ppt课件
活动提案企划书撰写
人教版新课标小学数学三年级下册《求平均数》课件
北师大版小学一年级数学上册加与减一《练习二PPT课件》
如何选择服务器ppt课件
人教版新课标小学语文一年级下册_柳树醒了ppt
小学四年级上册语文第十五课猫PPT课件2
小学五年级下学期语文《西门豹治邺》PPT课件
精编小学英语新课标(0002)
根据业务类型选择服务器平台ppt课件
信息系统、组织、管理和战略ppt课件
VC0039网络即时通信的原理和实现答辩材料ppt课件
服务器RAID卡及操作ppt课件
精编小学语文《雪儿》
法学专业毕业论文写作指导
精编小学数学六年级《百分数应用题》复习课课件[1]
工商管理学(本科)毕业(学位)论文写作指导
精编小学英语教学法1
设备施工图及装饰施工图
2023-12-22 55页
2023-12-22 50页
2023-12-22 50页
2023-12-22 64页
2023-12-22 50页
2023-12-22 55页
2023-12-22 51页
2023-12-22 50页
2023-12-22 50页
2023-12-19 24页