文档介绍：博弈算法综述
学号:2010211894 姓名:盛华英
1 引言(问题描述)
博弈论是研究具有斗争或竞争性质现象的数学理论和方法。一般认为,它既是现代数学的一个新分支,也是运筹学中的一个重要学科。对策论发展的历史并不长,但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系,并且处理问题的方法又有明显特色。所以日益引起广泛的注意。在日常生活中,经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益,各方必须考虑对手的各种可能的行动方案,并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动案,以及如何找到这个合理的行动方案的数学理论和方法。
博弈的核心思想并不复杂, 实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合。在博弈的任何一个中间阶段, 站在博弈双方其中一方的立场上, 可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局, 它的儿子节点是假设再行棋一步以后的各种棋局, 孙子节点是从儿子节点的棋局再行棋一步的各种棋局, 以此类推, 构造整棵博弈树, 直到可以分出胜负的棋局。整棵的博弈树非常庞大, 且不同的棋类有所不同, 分支因子大的如围棋的博弈树显然要比分支因子小的如国际象棋的博弈树要大得多。博弈程序的任务就是对博弈树进行搜索找出当前最优的一步行棋。对博弈树进行极大极小搜索, 可以达到这一目的。极大极小搜索, 是因为博弈双方所要达到的目的相反, 一方要寻找的利益恰是一方失去的利益, 所以博弈的一方总是希望下一走步是儿子节点中取值最大者, 而另一方恰恰相反。这便形成了极大极小过程。当然, 程序不能也没有必要做到搜索整棵博弈树的所有节点, 对于一些已经确定为不佳的走步可以将根节点的子树剪掉。而且, 搜索也不必真地进行到分出胜负的棋局, 只需要在一定深度范围内对局面进行评价即可。只有搜索空间缩小到一定程度, 搜索才可以真正地进行。当搜索进行到一定深度, 用局面评价机制来评价棋局, 按照极大极小的原则选出最优, 向上回溯, 给出这一局面的父亲节点的价值评价, 然后再继续向上回溯, 一直到根节点, 最优走步就是这样搜索出来的。在这个过程中, 最为重要的是搜索算法, 高效的搜索算法可以保证用尽量少的时间和空间损耗来达到寻找高价值的走步。但是真的想要博弈程序棋力提高, 还必须有一个好的局面评价机制, 即估值算法作后盾。就是说, 用这个估值算法评价的局面价值必须是客观的、正确的, 可以确凿的评价局面的优劣以及优劣的程度。
2 算法综述
一、基本博弈搜索算法
1、极大极小值算法(Minimax Algorithm)
始终站在博弈一方的立场上给棋局估值,有利于这一方的棋局给予一个较高的价值分数,不利于这一方(有利于另一方)的给予一个较低的价值分数,双方优劣不明显的局面给予一个中间价值分数。在这一方行棋的时候,选择价值极大的儿子节点走步,另一方行棋则选择价值极小的儿子节点走步。
极大极小的算法框架:
第一步:从s节点出发按宽度有先的方法,生成规定深度范围的博弈树。
假设搜索的最大深度为K:
初始化博弈树,放入初始节点s入open表; closed:=