博弈算法与游戏策略

博弈算法与游戏策略朱全民一个简单的问题Grundy博弈有一堆数目为n的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如选手甲把n分成两堆后，轮到乙就可以挑其中一堆来分，如此进行下去，直到有一位选手先无法把钱币分成不相等的两堆时就得认输。状态空间图(3,3,1,Min)(6,1,Max)(7,Min)(5,2,Max)(4,3,Max)(5,1,1,Min)(3,2,2,Min)(4,2,1,Min)(4,1,1,1,Max)(3,2,1,1,Max)(3,2,2,1,Max)(2,2,1,1,1,Min)(3,1,1,1,1,Min)(2,1,1,1,1,1,Max)CBA与或图规则：if(x1,…,xn,Max)and(xn=y+z,yz)then(x1,…,xi-1,y,z,xi+1,…,xn,Min)上图节点A是Max的目标，而节点B,C则是Min的目标。搜索策略需要考虑的问题是：对Min走后的每一个Max节点,必须证明Max对Min可能的每一个棋局对弈后能获胜，即Max必须应付Min的所有的招法，这是一个“与”的含义，因此，含有Max的节点可看成与节点。对Max走后的每一个Min节点,只须证明Max有一步走赢就可以，即Max只要考虑走一步棋使Min无法招架就成，因此含有Min的节点可看成“或”节点。这样对弈过程的搜索图就呈现出“与或图”的形式。Grundy的与或搜索图估价函数极大极小搜索策略是考虑双方对弈若干步之后，从能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。为此，要定义一个静态估价函数f,以便对棋局的势态作出优劣估值，这个函数可根据事态优劣特征进行定义，一般规定有利于Max的势态f(p)取正值，有利于Min的势态f(p)取负值，势均力敌，f(p)=0因此，f(p)=+∞，表示Max赢，f(p)=-∞表示Min赢。规定，顶点的深度为0，Max表示程序方，Min表示对手方对于Min节点,应考虑最坏的情况,故其估计值应取其子节点的最小值,而对于Max节点,可考虑最好的情况,故取其子节点的最大值。极大极小的取值过程如上图，极大极小层交互出现，极小层取两个他们的最小值，极大层取他们的最大值。极大极小的算法框架第一步：从s节点出发按宽度有先的方法，生成规定深度范围的博弈树。假设搜索的最大深度为K：初始化博弈树,放入初始节点s入open表；closed:=();repeatiff(s)nilthen游戏退出或开始走步;ifn可直接判定赢、输或平局thenf(n)+∞/-∞/0else[niexpand(n);add(ni,T);depth:=depth(n)+1add(ni,open);add(n,closed);nopen表的第一个节点]untilopen表为空ordepthk极大极小的算法框架第二步：对该博弈树，自底向上逐级计算每个节点的静态估价函数值。按给定的估价函数计算最底层的静态估价函数值；repeat{从下往上倒推计算各估计值}iff(s)nilthen游戏退出或开始走步nclosed表的第一个节点ifn∈Max方andf(nci)有值then[f(n)max{f(nci)};remove(n,closed)]ifn∈Min方andf(nci)有值then[f(n)min{f(nci)};remove(n,closed)]untilclosed表为空;第三步：按找估价函数值决定走步，如果对手响应走步以后，再以当前状态作为起始状态s，转第一步。#棋游戏在九宫棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线，谁就取胜。设程序方Max用黑子“●”，而对手Min用白子“○”估计函数：f(p)=所有空格都放上黑子后，Max的三子成线总数-所有空格都放上白子后，Min的三子成线总数若p为Max方获胜，则f(p)=+∞p为Min方获胜，则f(p)=-∞右图的f(p)=6-4=2由f(p)0可以看出，这个棋局的对Max有利。○●深度为2的#棋游戏的搜索过程(1)深度为2的#棋游戏的搜索过程(2)深度为2的#棋游戏的搜索过程(3)α-β剪枝α-β剪枝α剪枝：若任一极小值层节点的β值小于或等于它任一先辈极大值层节点的α值，即α(先辈层)≥β(后继层)，则可终止该最小值层中这个min节点的搜索过程。这个min节点最终的倒推值就确定为β值。β剪枝：若任一极小值层节点的α值大于或等于它任一先辈极大值层节点的β值，即α(后继层)≥β(先辈层)，则可终止该最大值层中这个max节点的搜索过程。这个max节点最终的倒推值就确定为α值。α-β效率分析若以理想的情况搜索，即对Min先扩展最底估计值节点，对Max先扩展对高估计值的节点，则搜索深度为d，分支个数为B时，用α-β剪枝，生成的端节点数最少，为n=2Bd/2(d为偶数),n=B(d+1)/2+B(d-1)/2-1(d为奇数)博弈搜索的时间复杂度分析