计算机博弈算法初步PPT课件

计算机博弈算法初步,名词解释,完备信息动态博弈：是指博弈中信息是完全的，是指每一参与者都拥有所有其他参与者的特征、策略，后动者可以观察到前者的行动，了解前者行动的所有信息。m,n,k游戏：是指m行n列，轮流下子，连成k个棋子判胜。只有先手必胜和平局两种结果。零和博弈：与非零和博弈相对，是博弈论的一个概念，属非合作博弈。指参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为“零”，双方不存在合作的可能。,博弈树,博弈树是指由于动态博弈参与者的行动有先后次序，因此可以依次将参与者的行动展开成一个树状图形。博弈树的特点：(1)博弈的初始格局是初始节点。(2)在博弈树中，或节点和与节点是逐层交替出现的。自己一方扩展的节点之间是或关系，对方扩展的节点之间是与关系。双方轮流地扩展节点。(3)所有自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。所有的算法都将基于博弈树上进行讲解,博弈树实例,根节点：面临选择的当前局面。点节点：不为结束，下面仍有分支的节点叶节点：计算结束，没有分支的节点。,绘制博弈树,对于一个剪刀石头布游戏，我们将规则更改。令甲方先出手，在这之后，乙方再出手。假设我们扮演的是乙方，并且用数字1/0/-1来代表我方胜利/平局/失败。则下图为这个游戏的博弈树。,博弈树的复杂度,一颗完整博弈树的规模是相当可观的天文数字。中国象棋完整博弈树的节点数高达10150，据说地球上全部原子的数目也才有10132。显然是无法全部展开和进行遍历搜索。即使选用搜索速率为1M节点/s的计算机系统，日夜不停地搜索100年，也才只能搜索9层。还达不到一般象棋大师的水平。即或是最简单的牛角棋，如果将博弈树展开15层，还不将无意义的循环走棋的节点计算在内，那有效博弈树的总节点数还接近750万个。需要特别注意的是博弈树不同于一般的搜索树，它是由对弈双方共同产生的一种“变性”搜索树。香农(ClaudeShannon)教授早在1950年就提出了“极大-极小算法”（MinimaxAlgorithm），奠定了计算机博弈的理论基础。,博弈树的复杂度,极大极小思想(Minimax),极小极大思想是指：始终站在博弈一方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这一方（即有利于另一方）的给予一个较低的价值分数，双方优劣不明显的局面给予一个中间价值分数。在博弈一方行棋的时候，选择价值极大的儿子节点走步，其对手方行棋则选择价值极小的儿子节点走步。这就是一个极大极小过程。极小极大值是发展博弈理论的“关键基石”，这是因为博弈论中最基本的概念扩展形式、纯战略、战略形式、随机化、效用函数等都是因极小极大值理论的研究而被引伸出来的，现代博弈理论中的最基本概念“古诺纳什均衡”也是极小极大值理论的派生物。,极大极小思想(Minimax),Minimax算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。由于对弈双方都很理智，都想赢棋，在考虑着法的时候都尽量想让棋局朝着自己的方面转化，所以在同一颗博弈树上，在不同的层面上就要有不同的选择标准。这也就是称之为“变性”搜索树原由。在我方层节点的着法选择是要在其全部子节点中找到评估值最大的一个，即实行“Max搜索”。而在对方层节点的着法选择则是在其全部子节点中要找到评估值最小的一个，即实行“Min搜索”。,极大极小的数学意义,通过极大极小方法，可以在数学上证明一个游戏先手必胜。如刚才改良过的剪刀石头布游戏。,极大极小的数学意义,每一个节点的值由他的子节点中的极值决定。而取极大或极小值取决于博弈者。,利用递归的方式实现,伪代码：FunctionNodeValue(node)/求输入的node节点的值if(isleaf_node)/如果是叶节点returnleaf_node_value;/则返回叶节点的值else/如果不是叶节点returnMinimax(NodeValue(next_node);/再次调用,井字棋：策略最佳,井字棋，英文名叫Tic-Tac-Toe，是一种在3*3格子上进行的连珠游戏，和五子棋比较类似，由于棋盘一般不画边框，格线排成井字故得名。游戏需要的工具仅为纸和笔，然后由分别代表O和X的两个游戏者轮流在格子里留下标记（一般来说先手者为X）那么，为了保证我们的策略最佳，什么地方才是最好的选择？,井字棋：策略最佳,井字棋是一个先手必胜游戏。游戏开始后，先占上一个角（比如左下角），那么对方总共有五种本质不同的应对策略：占据靠近你的那条边，占据靠近你的那个角，占据远离你的那条边，占据远离你的那个角（即对角），以及占据正中央的位置。但是，在这五种策略中，前面四种都是陷阱如果对方不慎选择了前面四种策略中的任意一种，他就必然输掉。然而，如果先手没有占领边角的话，不能达成必胜局面。证明井字棋先手必胜的方法,蒙特卡罗方法(MonteCarlo),对于一个边长为1M的正方形。在其中随意的化一个正圆（范围均在正方形内）。在不能衡量圆的各项数值的情况下，请问怎样尽可能精确的求圆的面积？,蒙特卡罗方法(MonteCarlo),方法：向正方形内随机投掷针，计算投进圆内的针的数量与总投掷数量的比例，即为圆的面积与正方形面积的比例。随着投掷数量的不断上升，其精确度也不断提升。蒙特卡罗方法于20世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆和J.冯诺伊曼首先提出。数学家冯诺伊曼用驰名世界的赌城摩纳哥的MonteCarlo来命名这种方法，为它蒙上了一层神秘色彩。在这之前，蒙特卡罗方法就已经存在。1777年，法国数学家布丰提出用投针实验的方法求圆周率。这被认为是蒙特卡罗方法的起源。,蒙特卡罗方法的应用,.建立随机落子函数。应可以筛选当前所有可以走子的位置，然后随机建立一个。.开始做评估，对于面临的选择。假设在做出这个选择之后，双方开始随机的落子，最终我方胜利的概率是多少？.对比所有选择中我方胜利的概率，将最佳的概率做为我方的选择。蒙特卡洛模拟对局就是从某一棋局出发，随机走棋。有人形象地比喻，让两个傻子下棋，他们只懂得棋规，不懂得策略，最终总是可以决出胜负。这个胜负是有偶然性的。但是如果让成千上万对傻子下这盘棋，那么结果的统计还是可以给出该棋局的固有胜率和胜率最高的着法。,蒙特卡罗方法的实质,蒙特卡罗方法实质上是对以当前局面为根节点的博弈树中的所有叶节