5.5极小极大分析法.ppt

《5.5极小极大分析法.ppt》由会员分享，可在线阅读，更多相关《5.5极小极大分析法.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、15.5 极小极大分析法2例例1：一字棋游戏。：一字棋游戏。设有如图所求的九个空格，由A，B二个对弈，轮到谁走棋就往空格上放一只自己的棋子，谁先使自已的棋子构成“三子成一线”谁就取得了胜利。设A的棋子用来表示，B的棋子用来表示。3S0S1S2S3S4S5思考:如果X行动,走 S1,S2,S3?如果O分别应对S1,S2,S3,应下哪些位置?4 如何估计 节点/格局 的好坏?定义估价函数估价函数 根据问题的特性信息定义一个估价函数估价函数，用来估算当前博弈树节点的得分。估价函数是估价函数是站在站在A方方立场上估计分数。静态估值静态估值 站在某一方(如A方)，估算当前博弈树节点的得分。1)静态估值静

2、态估值例如，当格局对对方(B方方)有利时,估价函数给出的估价函数给出的估计分值分值 小小.5估价函数定义估价函数定义(站在站在A方方)：设棋局为P，估价函数为e(P).(1)若P是A必胜的棋局，则e(P)=+.(2)若P是B必胜的棋局，则e(P)=.(3)若P是胜负未定的棋局，则e(P)=e(+P)-e(-P)其中 e(+P)表示棋局P上有可能使成为三子一线的数目。e(-P)表示棋局P上有可能使成为三子一线的数目。6e(P)=6 4=2例1 棋局 P 站在X方7e(P)=5 4=1例2 棋局 P 站在X方8一字棋极小极大搜索S0S1S2S3S4S5思考:12个棋局,静态估值静态估值如下,如果站

3、在X方,最希望的是哪个棋局?如果站在O方,最希望的是哪个棋局?9 假定：1.A先走棋，站在A的立场上。2.博弈树每次仅扩展两层(A、B各走一步)3.具有对称性的两个棋局算作一个棋局。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出，对于A来说最好的一步棋是S3,因为 S3比S1和S2有较大的倒推值。在A走S3这一步棋后，B的最优选择是S4,因为这一步棋的静态估值较小，对A不利。不管B选择S4 或S5，A都要再次运用极小极大分析法产生深度为2的博弈树，以决定下一步应该如何走棋，其过程与上面类似。图如下页10 2)极小极大分析法 当A一方当前有多个行动方案可供选择时，A总是挑选对自

4、己最为有利而对对方最为不利的那个行动。-get the best 当B方行动时,A要充分估计到对方采取对自己最为不利的那个行动。-avoid the worst 站在A方搏弈树AAActActB BActAct11倒推值倒推值-极小极大分析法极小极大分析法 当端节点的静态估值静态估值计算出来后，再推算出父节点推算出父节点的得分的得分，这样计算出的父节点的得分称为倒推值倒推值。对对“或或”节点节点，选其子节点中一个最大最大的得分作为父节点的得分；对对“与与”节点节点，选其子节点中一个最小最小的得分作为父节点的得分;12极小极大分析法-当前最好的行动行动方案 如果一个行动方案能获得较大的倒推值，则

5、它就是当前最好的行动行动方案。对各个可能的后果进行比较。-计算每一方案（每一方案（从从当前节点走到某一当前节点走到某一可能后果的走法）的得分。13一字棋极小极大搜索S0S1S2S3S4S5思考:12个棋局,静态估值静态估值如下,如果站在X方,最希望的是哪个棋局?如果站在O方,最希望的是哪个棋局?1523232274-1-1224-2-264353446-56-51863268213343当前最好的行动行动方案是？-计算计算倒推值Example 3站在A方方向前搜索16可解棋局P不可解棋局P e(P)=e(P)=-思考1.向前推4步S0的行动方案?/倒推值?2.部分向前推6步(见下图)S0的行动方案?/倒推值?18S0S3S2S119 0S01345211 21 11 211当前格局S0格局S1S5是A方5种选择B分别应对格局S1S5S4 倒推值最大A方最佳方案S4思考