问题求解基本原理.ppt
《问题求解基本原理.ppt》由会员分享,可在线阅读,更多相关《问题求解基本原理.ppt(32页珍藏版)》请在三一办公上搜索。
1、问题求解基本原理,博 弈:被认为高智能行为游戏;,不断为AI研究提出新课题,推动AI研究的发展。,搜 索 技 术(三)博 弈 搜 索,基于博弈搜索的搜索策略,博弈问题及博弈树概念 博弈搜索控制策略 博弈搜索算法及其应用实例 博弈树的-剪枝,博弈问题及博弈树概念,博弈问题:对抗的双方参加博弈,取胜的因素不仅取决于一方的如意算盘,还需充分考虑对方的应付策略,(一字棋、国际象棋、打扑克、中国象棋、围棋)。,双人完备信息:对垒的双方轮流走步,对弈的条件和走步规则完全相同。每一方不仅知道对方已走过的所有棋步,而且还能估计出对方未来可能走的棋步。,博弈问题及博弈树概念,博弈问题描述:棋局描述;棋局走步规则
2、。,博弈搜索过程:搜索棋局走步规则,隐含生成一棵特殊的与或树,博弈问题求解:,博弈问题及博弈树概念,与或节点分层交替出现的与或树,从甲的立场出发,或节点,与节点,或节点,博弈问题及博弈树概念,判断走步的极小-极大原则:,考虑对方走步时(与节点):假定对手不会犯错误,他总是选择对自己最有利,对我方最不利的棋步走。因此,我方不能采取任何冒险行动,视对手将走出的棋局为极小值;,考虑我方走步时(或节点):应在对方造成的最坏的局势中尽可能地选择最好的棋着走,视自己可能走出的棋局为极大值。,基于博弈搜索的搜索策略,博弈问题及博弈树 博弈搜索控制策略 博弈搜索算法及其应用实例 博弈树的-剪枝,完整的博弈搜索
3、策略(盲目搜索策略)有界深度博弈搜索策略,完整的博弈搜索策略,核心思想:从博弈的初始格局开始,轮番考虑自己与对方可能的所有走步,生成出棋局的各个格局,直到达到分出胜负输赢的终止格局为止,此搜索过程产生的一棵完整的博弈树。,完整的博弈搜索策略,博弈问题实例:有一堆数目为N的钱币,甲、乙二人轮流分堆。要求每人每次挑选其中某一堆钱币,将其分成数目不等的两小堆。分堆过程持续,直至其中一人无法再将任一堆钱币分成数目不等的两堆时,则认输。,博弈问题描述:分堆格局(状态):(x1,x2,xn,M),其中,xi:第 i 堆钱币的个数;M:当前走步人编号-(MAX,MIN),走步规则:IF(x1,x2,xn,M
4、)(xi=Y+Z)(Y Z)THEN(x1,x2,xi-1,Y,Z,xi+1,xn,M),完整的博弈搜索策略,站在MAX立场,与节点,或节点,与节点,特点:搜索策略简单,易于控制,可用于简单的博弈或一个复杂博弈的残局;,完整的博弈搜索策略,不适合复杂的博弈问题搜索-指数爆炸。例,中国象棋:设每种格局有40种走法,一盘棋双方平均走50步,完整的博弈搜索-搜索节点数(402)50 10160,搜索深度达100层。,有必要引入有界深度博弈搜索策略。,基于博弈搜索的搜索策略,博弈问题及博弈树 博弈搜索控制策略,完整的博弈搜索策略(盲目搜索策略)有界深度博弈搜索策略(启发式搜索策略),有界深度搜索策略,
5、核心思想:根据对方已走出的棋步,构造出具有一定深度的博弈树,并从此局部博弈树中选择相对好的棋着走。,需解决的关键问题:,定义估计终结棋局优劣的评价函数;,给出棋局优劣性传递的计算方法。,定义棋局的评价函数,设 P 为有界博弈树中棋局;(P):棋局优劣的评价函数。,例1:从当前棋局到离我方最后取胜的差距:胜利在望(P)值较大,败局显露(P)值较小;例2:从当前棋局到到某个明显有利于我方棋局的差距:吃掉对方一子,或者“叫吃”。,(P)MAX赢=(P)MIN输=+(P)MAX输=(P)MIN赢=-(P)平=0,(P)任一终叶棋局优劣的评价函数的定义原则:,计算棋局的评价函数,有界博弈树中任一棋局(节
![问题求解基本原理.ppt_第1页](https://www.31ppt.com/fileroot1/2023-5/18/a2b63042-dafe-473f-a8f2-8e39d09ef4cb/a2b63042-dafe-473f-a8f2-8e39d09ef4cb1.gif)
![问题求解基本原理.ppt_第2页](https://www.31ppt.com/fileroot1/2023-5/18/a2b63042-dafe-473f-a8f2-8e39d09ef4cb/a2b63042-dafe-473f-a8f2-8e39d09ef4cb2.gif)
![问题求解基本原理.ppt_第3页](https://www.31ppt.com/fileroot1/2023-5/18/a2b63042-dafe-473f-a8f2-8e39d09ef4cb/a2b63042-dafe-473f-a8f2-8e39d09ef4cb3.gif)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 问题 求解 基本原理
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5472699.html