文档介绍:**例1:一字棋游戏。设有如图所求的九个空格,由A,B二个对弈,轮到谁走棋就往空格上放一只自己的棋子,谁先使自已的棋子构成“三子成一线”谁就取得了胜利。设A的棋子用来表示,B的棋子用来表示。*S0S1S2S3S4S5思考:如果X行动,走S1,S2,S3?如果O分别应对S1,S2,S3,应下哪些位置?*如何估计节点/格局的好坏?定义估价函数根据问题的特性信息定义一个估价函数,用来估算当前博弈树节点的得分。估价函数是站在A方立场上估计分数。静态估值站在某一方(如A方),估算当前博弈树节点的得分。1)静态估值例如,当格局对对方(B方)有利时,*估价函数定义(站在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上有可能使○成为三子一线的数目。*e(P)=6–4=*e(P)=5–4=****一字棋极小极大搜索S0S1S2S3S4S5思考:12个棋局,静态估值如下,如果站在X方,最希望的是哪个棋局?如果站在O方,最希望的是哪个棋局?*假定:A先走棋,站在A的立场上。博弈树每次仅扩展两层(A、B各走一步)具有对称性的两个棋局算作一个棋局。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出,对于A来说最好的一步棋是S3,因为S3比S1和S2有较大的倒推值。在A走S3这一步棋后,B的最优选择是S4,因为这一步棋的静态估值较小,对A不利。不管B选择S4或S5,A都要再次运用极小极大分析法产生深度为2的博弈树,以决定下一步应该如何走棋,其过程与上面类似。*2)极小极大分析法当A一方当前有多个行动方案可供选择时,A总是挑选对自己最为有利而对对方最为不利的那个行动。----getthebest当B方行动时,A要充分估计到对方采取对自己最为不利的那个行动。----