《极小极大分析法》PPT课件.ppt
《《极小极大分析法》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《极小极大分析法》PPT课件.ppt(19页珍藏版)》请在装配图网上搜索。
1,5.5极小极大分析法,2,例1:一字棋游戏。设有如图所求的九个空格,由A,B二个对弈,轮到谁走棋就往空格上放一只自己的棋子,谁先使自已的棋子构成“三子成一线”谁就取得了胜利。,设A的棋子用,来表示,B的棋子用,来表示。,3,S0,S1,S2,S3,S4,S5,思考:如果X行动,走S1,S2,S3?如果O分别应对S1,S2,S3,应下哪些位置?,4,如何估计节点/格局的好坏?定义估价函数根据问题的特性信息定义一个估价函数,用来估算当前博弈树节点的得分。估价函数是站在A方立场上估计分数。静态估值站在某一方(如A方),估算当前博弈树节点的得分。,1)静态估值,例如,当格局对对方(B方)有利时,估价函数给出的估计分值小.,5,估价函数定义(站在A方):,设棋局为P,估价函数为e(P).若P是A必胜的棋局,则e(P)=+.若P是B必胜的棋局,则e(P)=.若P是胜负未定的棋局,则e(P)=e(+P)-e(-P)其中e(+P)表示棋局P上有可能使成为三子一线的数目。e(-P)表示棋局P上有可能使成为三子一线的数目。,6,e(P)=64=2,例1棋局P站在X方,7,e(P)=54=1,例2棋局P站在X方,8,一字棋极小极大搜索,S0,S1,S2,S3,S4,S5,思考:12个棋局,静态估值如下,如果站在X方,最希望的是哪个棋局?如果站在O方,最希望的是哪个棋局?,9,假定:A先走棋,站在A的立场上。博弈树每次仅扩展两层(A、B各走一步)具有对称性的两个棋局算作一个棋局。,图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出,对于A来说最好的一步棋是S3,因为S3比S1和S2有较大的倒推值。在A走S3这一步棋后,B的最优选择是S4,因为这一步棋的静态估值较小,对A不利。不管B选择S4或S5,A都要再次运用极小极大分析法产生深度为2的博弈树,以决定下一步应该如何走棋,其过程与上面类似。图如下页,10,2)极小极大分析法,当A一方当前有多个行动方案可供选择时,A总是挑选对自己最为有利而对对方最为不利的那个行动。-getthebest当B方行动时,A要充分估计到对方采取对自己最为不利的那个行动。-avoidtheworst,站在A方搏弈树,AAct,BAct,11,倒推值-极小极大分析法当端节点的静态估值计算出来后,再推算出父节点的得分,这样计算出的父节点的得分称为倒推值。,对“或”节点,选其子节点中一个最大的得分作为父节点的得分;,对“与”节点,选其子节点中一个最小的得分作为父节点的得分;,12,极小极大分析法-当前最好的行动方案,如果一个行动方案能获得较大的倒推值,则它就是当前最好的行动方案。,对各个可能的后果进行比较。-计算每一方案(从当前节点走到某一可能后果的走法)的得分。,13,一字棋极小极大搜索,S0,S1,S2,S3,S4,S5,思考:12个棋局,静态估值如下,如果站在X方,最希望的是哪个棋局?如果站在O方,最希望的是哪个棋局?,14,-2,6,4,3,5,例2:可能的行动方案倒推值分别是?,15,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,当前最好的行动方案是?-计算倒推值,Example3站在A方方向前搜索,16,可解棋局P,不可解棋局P,e(P)=,e(P)=-,思考,1.向前推4步S0的行动方案?/倒推值?2.部分向前推6步(见下图)S0的行动方案?/倒推值?,18,S0,S3,S2,S1,19,0,当前格局S0格局S1S5是A方5种选择,B分别应对格局S1S5,S4倒推值最大A方最佳方案S4,思考,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 极小极大分析法 极小 极大 分析 PPT 课件
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文