《极小极大分析法》PPT课件

1,4.5极小极大分析法,在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动。,2,4.5.1静态估值根据问题的特性信息定义一个估价函数，用来估算当前博弈树节点的得分。此时估算出来的得分称为静态估值。,3,例1：一字棋游戏。设有如图所求的九个空格，由A，B二个对弈，轮到谁走棋就往空格上放一只自己的棋子，谁先使自已的棋子构成“三子成一线”谁就取得了胜利。,设A的棋子用,来表示，B的棋子用,来表示。,根据问题的特性信息定义一个估价函数，用来估算当前博弈树节点的得分_-静态估值(decidewhichoneisbetter),4,估价函数定义：,设棋局为P，估价函数为e(P).若P是胜负未定的棋局，则e(P)=e(+P)-e(-P)其中e(+P)表示棋局P上有可能使,成为三子一线的数目。,e(-P)表示棋局P上有可能使,成为三子一线的数目。,5,e(P)=64=2,e(-P)表示棋局P上有可能使,成为三子一线的数目。,6,根据问题的特性信息定义一个估价函数，用来估算当前博弈树节点的得分_-静态估值(decidewherenextblackonewillgo),例2：5chesspiecegame,4.5.2极小极大分析法基本思想站在X方设博弈的双方中一方为X，另一方为Y，站在X方立场上为其寻找一个最优行动方案。(2)向前搜索若干步为了找到当前的最优行动方案，需对各个可能的方案所产生的后果进行比较。考虑每一方案实施后对方可能采取的所有行动，并计算每一方案可能的得分。为比较不同方案的优劣，需向前搜索若干步。,8,Example3,2,7,4,-1,1,4,根据估价函数，估算当前博弈树节点的得分。7分是最好的格局。在众多的可能格局中，如何达到最好的?,9,(3)倒推值-极小极大分析法当端节点的估值计算出来后，再推算出父节点的得分，这样计算出的父节点的得分称为倒推值。,对“或”节点，选其子节点中一个最大的得分作为父节点的得分；,对“与”节点，选其子节点中一个最小的得分作为父节点的得分;,10,3,2,2,7,4,-1,-1,1,1,4,-2,-2,6,4,3,5,3,2,Example4,11,极小极大分析法-当前最好的行动方案,对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；,对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。估价函数是站在X方立场上估计分数,当格局对对方有利时,估价函数给出的估计分值小(对X方而言).,如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。,12,3,2,2,7,4,-1,-1,1,1,4,-2,-2,6,4,3,5,3,2,Example5,当前最好的行动方案分别是？,13,所有可能的格局,Example6站在X方方向前搜索,根据估价函数，估算当前博弈树节点的得分。,当前最好的行动方案是？,14,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,Example6,当前最好的行动方案是？,15,例7：一字棋游戏。设有如图所求的九个空格，由A，B二个对弈，轮到谁走棋就往空格上放一只自己的棋子，谁先使自已的棋子构成“三子成一线”谁就取得了胜利。,设A的棋子用,来表示，B的棋子用,来表示。,16,估价函数定义：,设棋局为P，估价函数为e(P).若P是A必胜的棋局，则e(P)=+.若P是B必胜的棋局，则e(P)=.若P是胜负未定的棋局，则e(P)=e(+P)-e(-P)其中e(+P)表示棋局P上有可能使,成为三子一线的数目。,e(-P)表示棋局P上有可能使,成为三子一线的数目。,17,e(P)=64=2,e(-P)表示棋局P上有可能使,成为三子一线的数目。,18,假定：A先走棋，站在A的立场上。博弈树每次仅扩展两层具有对称性的两个棋局算作一个棋局。,图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出，对于A来说最好的一步棋是S3,因为S3比S1和S2有较大的倒推值。在A走S3这一步棋后，B的最优选择是S4,因为这一步棋的静态估值较小，对A不利。不管B选择S4或S5，A都要再次运用极小极大分析法产生深度为2的博弈树，以决定下一步应该如何走棋，其过程与上面类似。图如下页,19,一字棋极小极大搜索,S0,S1,S2,S3,S4,S5,20,双方博弈4步后的当前格局,Summary双方博弈过程中出现过的格局,初始格局,Max-Minhelponesidetototakeaction.,21,2,2,3,2,2,7,4,-1,-1,2,2,4,-2,-2,6,4,3,5,3,4,4,6,-5,6,-5,4,3,Example8,当前最好的