博弈算法综述.doc

《博弈算法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、博弈算法综述学号：2010211894姓名：盛华英1引言（问题描述）博弈论是研究具有斗争或竞争性质现象的数学理论和方法。一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的口常生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。在II常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益，各方必须考虑对

2、手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动案，以及如何找到这个合理的行动方案的数学理论和方法。博弈的核心思想并不复杂，实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合。在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙了节点是从儿了节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局。整棵的博弈树非常庞大，且不同的棋类有所不同

3、，分支因了大的如I韦I棋的博弈树显然要比分支因了小的如国际象棋的博弈树要大得多。博弈程序的任务就是对博弈树进行搜索找出当前最优的一步行根。对博弈树进行极大极小搜索，可以达到这一目的。极大极小搜索，是因为博弈双方所要达到的目的相反，一方要寻找的利益恰是一方失去的利益，所以博弈的一方总是希望下一走步是儿子节点中取值最大者，而另一方恰恰相反。这便形成了极大极小过程。当然，程序不能也没有必要做到搜索整棵博弈树的所有节点，对于一些已经确定为不佳的走步可以将根节点的子树剪掉。而且，搜索也不必真地进行到分出胜负的棋局，只需要在一定深度范围内对局面进行评价即可

4、。只有搜索空间缩小到一定程度,搜索才可以真正地进行。当搜索进行到一定深度，用局面评价机制来评价棋局，按照极大极小的原则选出最优，向上回溯，给出这一局面的父亲节点的价值评价，然后再继续向上EI溯,一直到根节点，最优走步就是这样搜索出来的。在这个过程中，最为重要的是搜索算法，高效的搜索算法可以保证用尽量少的时间和空间损耗来达到寻找高价值的走步。但是真的想要博弈程序根力提高，还必须有一个好的局面评价机制，即估值算法作后后。就是说，用这个估值算法评价的局面价值必须是客观的、正确的，可以确凿的评价局面的优劣以及优劣的程度。2算法综述一、基本博弈搜索算法1

5、＞极大极小值算法（MinimaxAlgorithm）始终站在博弈一方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这一方（有利于另一方）的给予一个较低的价值分数，双方优劣不明显的局面给予一个中间价值分数。在这一方行棋的时候，选择价值极大的儿了节点走步，另一方行棋则选择价值极小的儿了节点走步。极大极小的算法框架：第一步：从s节点出发按宽度有先的方法，生成规定深度范围的博弈树。假设搜索的最大深度为K：初始化博弈树，放入初始节点s入open表；closed:=();repeatifn可直接判定赢、输或平局thenf(n)+00/

6、-00X)else[niexpand(n);add(ni,T);depth:=depth(n)+ladd(ni,open);add(n,closed);remove(n/open);nopen表的第一个节点]untilopen表为空ordepth>k第二步：对该博弈树，自底向上逐级计算每个节点的静态估价函数值。按给定的估价函数计算最底层的静态估价函数值；repeat｛从下往上倒推计算各估计值｝iff(s)onilthen游戏退出或开始走步nclosed表的第一个节点ifnGMax方andf(nci)有值then[f(n)Max(f(nci)｝;

7、remove(n,closed)]ifneMin方andf(nci)有值then[f(n)Min(f(nci));remove(n/closed)]untilclosed表为空；第三步：按找估价函数值决定走步，如果对手响应走步以后，再以当前状态作为起始状态s,转第一步。2、负极大值搜索(NegamaxAlgorithm)1975年Knuth和Moore提出，旨在消除两方面的差别，使算法简洁优雅，核心思想在于:父节点的值是各子节点的负数的极大值。3、Alpha-Beta搜索的增强算法1)在alpha-beta剪枝过程中,初始的搜索窗口往往是从-°

8、°(即初始的alpha值)到+8(初始的beta值)，在搜索进行中再不断缩小窗口，加大剪枝效果。渴望搜索就是渴望从一开始就使用小的窗曰，从而在搜索初起