45极小极大分析法.ppt

,任何一方都希望自己取得胜利。因此,当某一方当前有多个行动方案可供选择时,他总是挑选对自己最为有利而对对方最为不利的那个行动。,用来估算当前博弈树节点的得分。此时估算出来的得分称为静态估值。2例1:一字棋游戏。设有如图所求的九个空格,由A,B二个对弈,轮到谁走棋就往空格上放一只自己的棋子,谁先使自已的棋子构成“三子成一线”谁就取得了胜利。设A的棋子用来表示,B的棋子用来表示。根据问题的特性信息定义一个估价函数,用来估算当前博弈树节点的得分__-----静态估值(decidewhichoneisbetter)3估价函数定义:设棋局为P,估价函数为e(P).若P是胜负未定的棋局,则e(P)=e(+P)-e(-P)其中e(+P)表示棋局P上有可能使成为三子一线的数目。e(-P)表示棋局P上有可能使成为三子一线的数目。4e(P)=6–4=2e(-P)表示棋局P上有可能使成为三子一线的数目。5根据问题的特性信息定义一个估价函数,用来估算当前博弈树节点的得分__-----静态估值(decidewherenextblackonewillgo)例2:,另一方为Y,站在X方立场上为其寻找一个最优行动方案。(2)向前搜索若干步为了找到当前的最优行动方案,需对各个可能的方案所产生的后果进行比较。——考虑每一方案实施后对方可能采取的所有行动,并计算每一方案可能的得分。——为比较不同方案的优劣,需向前搜索若干步。Example3274-114根据估价函数,估算当前博弈树节点的得分。7分是最好的格局。在众多的可能格局中,如何达到最好的?8(3)倒推值-------极小极大分析法当端节点的估值计算出来后,再推算出父节点的得分,这样计算出的父节点的得分称为倒推值。对“或”节点,选其子节点中一个最大的得分作为父节点的得分;对“与”节点,选其子节点中一个最小的得分作为父节点的得分;932274-1-1114-2-2643532Example410