5.5__极小极大分析法.ppt

1、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 ) 静态估值

2、,例如，当格局对对方(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) = 6 4 = 2,例1 棋局 P 站在X方,7,e(P) = 5 4 = 1,例2 棋局 P 站在X方,8,一字棋极小极大搜索,S0,S1,S2,S3,S4,S5,思考: 12个棋局, 静态估值如下,

3、如果站在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一方当前有多个行动方案可供

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

5、较。-计算每一方案（从当前节点走到某一可能后果的走法）的得分。,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,当前最好的行动方案是？-计算倒推值,Example 3 站在A方 方向前搜索,16,可解棋局P,不可解棋局P,e(P)= ,e(P)= -,思考,1. 向前推4步S0的行动方案?/倒推值? 2. 部分向前推6步(见下图)S0的行动方案?/