45极小极大分析法

1、14.5 极小极大分析法 在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动。24.5.1 静态估值静态估值 根据问题的特性信息定义一个估价函数估价函数，用来估算当前博弈树节点的得分。 此时估算出来的得分称为静态估值静态估值。3例例1：一字棋游戏。：一字棋游戏。 设有如图所求的九个空格，由a，b二个对弈，轮到谁走棋就往空格上放一只自己的棋子，谁先使自已的棋子构成“三子成一线”谁就取得了胜利 。设a的棋子用来表示，b的棋子用来表示。 根据问题的特性信息定义一个估价函数估价函数，用来估算当前博弈树节点的得分_-静

2、态估值静态估值(decide which one is better)4估价函数定义：设棋局为p，估价函数为e(p).若p是胜负未定的棋局，则e(p)= e(+p)- e(-p) 其中 e(+p)表示棋局p上有可能使成为三子一线的数目。e(-p) 表示棋局p上有可能使成为三子一线的数目。5e(p) = 6 4 = 2e(-p) 表示棋局p上有可能使成为三子一线的数目。6 根据问题的特性信息定义一个估价函数估价函数，用来估算当前博弈树节点的得分_-静态估值静态估值(decide where next black one will go)例例2：5 chesspiece game 4.5.2 极小

3、极大分析法基本思想极小极大分析法基本思想(1)站在站在x方方 设博弈的双方中一方为x，另一方为y，站在站在x方方立场上为其寻找一个最优行动方案。(2)向前搜索向前搜索若干步 为了找到当前的最优行动方案，需对各个可能的方案所产生的后果进行比较。 考虑每一方案实施后对方可能采取的所有行动，并计算计算每一方案每一方案可能的得可能的得分分。为比较不同方案的优劣比较不同方案的优劣，需向前搜索向前搜索若干步。8example 3274-114 根据估价函数估价函数，估算当前博弈树节点的得分。7分是最好的格局。在众多的可能格局中，如何达到最好的?9 (3)倒推值倒推值-极小极大分析法极小极大分析法 当端节点

4、的估值计算出来后，再推算出父节推算出父节点的得分点的得分，这样计算出的父节点的得分称为倒推倒推值值 。对对“或或”节点节点，选其子节点中一个最大最大的得分作为父节点的得分；对对“与与”节点节点，选其子节点中一个最小最小的得分作为父节点的得分;1032274-1-1114-2-2643532example 411极小极大分析法-当前最好的行动行动方案对对“或或”节点节点，选其子节点中一个最大最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对对“与与”节点节点，选其子节点中一个最小最小的得分作为父节点的得分，这是为了立足于最坏的情况。 估价函数是估价函数是站在

5、站在x方方立场上估计分数, 当格局对对方有利时,估价估价函数给出的函数给出的估计分值分值 小小(对对x方方而言而言). 如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动行动方案。1232274-1-1114-2-2643532example 5当前最好的行动行动方案分别是？13所有可能的格局example 6站在x方方向前搜索 根据估价函数估价函数，估算当前博弈树节点的得分。当前最好的行动行动方案是？1423232274-1-1224-2-264353446-56-51863268213343example 6当前最好的行动行动方案是？15例例7：一字棋游戏。：一字棋游戏。 设有如图

6、所求的九个空格，由a，b二个对弈，轮到谁走棋就往空格上放一只自己的棋子，谁先使自已的棋子构成“三子成一线”谁就取得了胜利 。设a的棋子用来表示，b的棋子用来表示。16估价函数定义：设棋局为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上有可能使成为三子一线的数目。17e(p) = 6 4 = 2e(-p) 表示棋局p上有可能使成为三子一线的数目。18 假定：1. a先走棋，站在a的

7、立场上。2. 博弈树每次仅扩展两层3. 具有对称性的两个棋局算作一个棋局。 图中节点旁的数字分别表示相应节点的静态估值或倒推值。 由图可以看出，对于a来说最好的一步棋是s3,因为 s3比s1和s2有较大的倒推值。 在a走s3这一步棋后，b的最优选择是s4,因为这一步棋的静态估值较小，对a不利。 不管b选择s4 或s5，a都要再次运用极小极大分析法产生深度为2的博弈树，以决定下一步应该如何走棋，其过程与上面类似。 图如下页19一字棋极小极大搜索s0s1s2s3s4s520双方博弈4步后的当前格局summary 双方博弈过程中出现过的格局 初始格局max-min help one side to to take action.212232274-1-1224-2-264353446-56-543example 8当前最好的行动