博弈算法

博弈算法朱全民对策论(博弈论、游戏论或策略论)田忌赛马早在战国的时候，中国就流行赛马赌胜的游戏。当时齐国的大将田忌就常常与齐国国君齐威王进行赛马，但每次比赛都是田忌输，齐威王赢。这是什么道理呢？原来田忌上、中、下三等马，齐威王也有上、中丁三等马，但田忌的三等马都分别比齐威王的三等马略差一些。田忌输得很不甘心，又想不出什么好的办法。这时候田忌的谋士孙膑就对田忌说，你再去与齐威王赛一次马，而且把赌注押得多一点，这一次我保证你能赢。田忌素来很信任孙膑，就又去邀齐威王赛马，并且押下了每场比赛一千两黄金的大赌注。比赛开始了，齐威王第一场就派出了它的上等马，田忌刚要派他的上等马去应战，孙膑却不让田忌派上等马，而让他派下等马去应战，结果自然是输了。第二场，齐威王派出中等马，孙膑则让田忌出上等马，结果赢回一场。到了第三场，齐威王只有下等马了。田忌则派出了中等马，结果又赢了一场。三场比赛结束，田忌先输一场，后赢两场，总计还是赢了一场，终于赢到了齐威王的一千两黄金。二人有限零和对策首先，参加这个赛局的有两方，一方是田忌，一方是齐威王，所以称“二人策”；其次，田忌有马三等，齐威王也有马三等，双方各用哪一等马去对付对方的哪一等马，其策略个数是有限的，所以又称“有限对策”；最后，每场比赛赌注千金，输方要拿出一千两黄金，而赢方则得到一千两黄金，双方输赢之和恰等于零，所以又称“零和对策”。对于田忌来说，他虽然也有上、中、下三等马，但每等都比齐威王的差，明显地处于劣势的地位。在这样的情况下，如何找到一种最优的策略，使劣势变为优势，就成了田忌能否取胜的关键。赛马策略设田忌的三等马为A、B、C，齐威王的三等马为a、b、c。）很明显，在田忌所有可能采取的六个策略中，有五个都是要输的其中第（1）种输三千两黄金，第（2）（3）（4）（5）种各输一千两黄金只有一个策略，也即是第（６）种策略，才有可能取胜。而孙膑所采取的，正是这个唯一能取胜的策略。我们从他让田忌多下赌注这样有把握的话来看，则可知他对于双方形势的优劣消长，各种策略的利害得失，必然是经过了一番详细的分析和周密的思考的。详细地分析敌我情况，反复地研究各种对策，在所有可能采取的策略中选择一个利多弊少的最优策略，从而使劣势变为优势，最终取得胜利，这正是对策论的基本思想。一个简单的问题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)(2,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(xi=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节点,可考虑最好的情况,故取其子节点的最大值。极大极小的取值过程如上图，极大极小层交互出现，极小层取两个他们的最小值，极大层取他们的最大值。基本博弈搜索算法极大极小值算法（MinimaxAlgorithm）始终站在博弈一方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这一方（有利于另一方）的给予一个较低的价值分数，双方优劣不明显的局面给予一个中间价值分数。在这一方行棋的时候，选择价值极大的儿子节点走步，另一方行棋则选择价值极小的儿子节点走步。负极大值搜索（NegamaxAlgorithm）1975年Knuth和Moore提出,旨在消除两方面的差别，使算法简洁优雅,核心思想在于:父节点的值是各子节点的负数的极大值。极大极小的算法框架第一步：从s节点出发按宽度有先的方法，生成规定深度范围的博弈树。假设搜索的最大深度为K：初始化博弈树,放入初始节点s入open表；closed:=();repeatifn可直接判定赢、输或平局thenf(n)+∞/-∞/0else[niexpand(n);add(ni,T);depth:=depth(n)+1add(ni,open);add(n,closed);remove(n,open);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为奇数)α-β剪枝α-β剪枝Alpha-Beta搜索的增强算法1.渴望搜索（AspirationSearch）在alpha-beta剪枝过程中，初始的的搜索窗口往往是从-∞（即初始的alpha值）到+∞（初始的beta值），在搜索进行中再不断缩小窗口，加大剪枝效果。2.极小窗口搜索（MinimalWindowSearch）用极小的窗口来限制剪枝范围,在根节点处，假定第一个儿子节点为主变量，也就是假定它为最佳走步，对它进行完整窗口(a,b)的搜索并得到一个返回值v，对后面的儿子节点依次用极小窗口(也被称为是零窗口)（v,v+1）来进行搜索，如果搜索返回值大于零窗口，则证明这一分支亦为主变量，对它进行窗口为（v+1,b）的搜索，可是如果返回值小于零窗口，这一分支就可以忽略，因为它的最佳走步还不如已有的走步。Alpha-Beta搜索的增强算法3.置换表（TranspositionTable）在搜索进行中，查询所有的走步，经常会在相同的或者不同的路径上遇到相同的棋局，这样的子树就没有必要重复搜索，把子树根节点的估值、子树的最好走步和取得这个值的深度信息保存在一个称为置换表的数据结构中，下次遇到时直接运用即可。4.遍历深化（IterativeDeepening）算法的过程是，对以当前棋局为根节点的博弈树进行深度为二的遍历，得出其儿子节点的优劣排序，接着再从根节点进行深度为三的遍历，这一次优先搜索上次遍历中得出的最优者，从而加大剪枝效果，以此类推，在进行第三次、第四次的遍历，一直达到限定时间为止。Alpha-Beta搜索的增强算法5.历史启发搜索（HistoryHeuristic）历史启发也是迎合alpha-beta搜索对节点排列顺序敏感的特点来提高剪枝效率的，即对节点排序，从而优先搜索好的走法。所谓好的走法即可以引发剪枝的走法或者是其兄弟节点中最好的走法。一个这样的走法，一经遇到，就给其历史得分一个相应的增量，使其具有更高的优先被搜索的权利。6.杀手启发搜索(KillerHeuristic)杀手启发实际上是历史启发的特例。它是把同一层中，引发剪枝最多的节点称为杀手，当下次搜索时，搜索到同一层次，如果杀手走步是合法的话，就优先搜索杀手。Alpha-Beta搜索的增强算法7.MTD(f)算法MTD(f)搜索的全称是Memory–enhancedTestDriverwithfandn。它是一个较新的算法，在1995左右年由AskePlaat等人提出。functionMTD(n,f)–〉f;g:=f;f+:=+∞;f:=－∞;//f为初值，f+上界，f－下界repeatifg=f－thenγ:=g+1elseγ:=g;g:=alphabeta(n,γ-1,γ)ifgγthenf+:=gelsef－:=g;untilf－≥f+;returng;//g为最好的走步最佳优先算法1.SSS*和DUAL*算法这两种算法即为状态空间搜索（StateSpaceSearch），由Stockman在1979年提出。它们是把极大极小树的搜索看成是对状态图的搜索，在不同的分支上展开多条路径，并且维护一个关于状态图的全局信息表。这两个算法的缺点是：算法复杂，难于理解；额外的数据结构占用空间大；并且维护有序的OPE