设为首页 - 加入收藏
广告 1000x90
您的当前位置:二四六天天好彩308K文字资料 > 博弈树搜索 > 正文

MathorCup竞赛优秀论文基于MonteCarlo局面评估和UCT博弈树搜索的

来源:未知 编辑:admin 时间:2019-06-06

  MathorCup竞赛优秀论文基于MonteCarlo局面评估和UCT博弈树搜索的2048

  10302评委三评分,签名及备注 评委二评分,签名及备注 选题: A:2048 评委四评分,签名及备注 题目:基于Monte Carlo 局面评估和 UCT 博弈树搜索的2048 摘要 本文首先提出 Random-Max-Trees 算法来实现人工智能的 2048。此算法是通 过静态评估函数来求得最优解。但是在实现的过程中出现冗余的现象,当移动方 格步数过多的时候,好的评估函数却很难找到,使 Random-Max-Trees 算法效率 降低。随后本论文采用 Alpha-Beta 算法,是前者的一种改进,在搜索结点数一 样的情况下,可以使搜索深度达到原来的两倍。在实现的过程中发现 Alpha-Beta 严重依赖于着法的寻找顺序。只有当程序挑最好的子节来当先搜索,才会接近于 实际分枝因子的平方根,也是该算法最好的状态。但是在首先搜索最坏的子节时, Beta 截断不会发生,此时该算法就如同 Random-Max-Trees 一样,效率非常低, 也失去Alpha-Beta 的优势,也无法试图通过面的搜索来弥补策略上的不足。 本文采用蒙特卡洛评估对以上模型进行了改进。它通过对当前局面下的每个 的可选点进行大量的模拟来得出相应的胜负的统计特性,在简单情况下,胜率较 高的点就可以认为是较好的点予以选择。由于UCT 算法能不断根据之前的结果调 整策略,选择优先评估哪一个可下点。所以在蒙特卡洛德基础上运用UCT 算法提 高收敛速度。可求得概率为100%。 对于第二问,采用归纳法以及概率论量化数值,当方格为 。最后对模型进行评价。 本论文算法是采用JAVA、C++以及MATLAB 实现。 关键字:Random-Max-Trees;Alpha-beta;Monte Carlo;UTC;概率论 基于MonteCarlo 局面评估和UCT 博弈树搜索的2048 1.问题提出 2048 是最近一款非常火爆的益智游戏,很多网友自称“一旦玩上它就根本停 不下来”。2048 游戏的规则很简单:每次控制所有方块向同一个方向运动,两个 相同数字的方块撞在一起之后合并成为他们的和,每次操作之后会在空白的方格 处随机生成一个 或者4,最终得到一个“2048”的方块就算胜利了。如果 16 格子全部填满并且相邻的格子都不相同也就是无法移动的话,那么游戏就会结束。本文将建立数学模型,解答下列问题: 如何才能达到2048,给出一个通用的模型,并采用完成游戏所需移动次数和成功概率两个指标来验证模型的有效性; 得到2048 之后,游戏还可以继续玩,那么最大能达到多大的数值呢?如 果将方格扩展到N*N 个,能达到的最大数是多少? 2.问题分析 本文首先基于Random-Max- Trees 和Alpha-beta 剪枝算法来实现人工智能(AI) 的2048。本文认为可以把2048 游戏看成是一场人类和计算机的博弈,人类控制所 有方块向同一个方向移动并合并,计算机则在空白处随机放置一个“2”或“4” 的方块。但是在 AI 的环境下,博弈双方都是计算机,双方都不理性,所以在 AI 的环境下,选用更加保守的 Random-Max-Trees 博弈策略比选用 Mini-Max-Tree 的更加适当。如果把当前格局作为博弈树的父节点,把下一步所有可能的走法所 造成的格局作为树的一个子节点,如果继续使用Random-Max-Trees 算法,则此算 法的效率很不理想,会造成许多不必要的步骤。因为每一个子节后面还有子节, 可能的情况很多循环往复,直到2048 为止,但是并不是所有的节点都必须搜索完 毕,有些节点是不必要的。为了解决这一问题,本文可以采用 Alpha-beta 剪枝算 对于第一问为实现2048的这种情况,蒙特卡洛评估是一个很好的解决方法, 它通过对当前局面下的每个的可选点进行大量的模拟来得出相应的胜负的统计特 性,在简单情况下,胜率较高的点就可以认为是较好的点予以选择。UCT 在蒙特卡 洛评估算法的基础上很大的提高了收敛速度,UCT 能不断根据之前的结果调整策 略,选择优先评估哪一个可下点,基于此策略从而也可以得到第二问的答案。 对于第二问,如何计算出最大值是有条件的,对有随机值的问题,我们需要量 化数值,如果考虑随机那么就有不确定性,这会使我们无法接近最大值,所以在 最开始就直接规定好,取4 来作为加数,因为这是累计的题目,4 大,所以在有限的范围内,4 的总和肯定比2 的总和大。规定好数值,开始计算最大值。最大 的倍数,通过玩2048已经知道相同的数可以合并形成更大的数,合并一个 数需要有两个数的空间,通过这一规律我们可以知道当格子都排满的情况下,还 是有可能进行数字的合并的,如果可以进行合并的线,这时又是满格的情况,如果合并过的数再次进行和并又再次产生一个空位,那么以此类 推用过可以产生15 次空格,那么,这15 有同时增加了15 次4,通过这些新加入 的4,数值会进一步的增加。 3.模型的假设 Alpha-Beta有比 Minimax 搜索算法更加准确的评估函数才能保证那些优秀的 节点不被过早的剪枝; 博弈树较小而可以被完全展开,博弈树叶子节点的价值可以通过胜负关系来确定,搜索的结果就是最优解; 博弈树很大而不能被完全展开时,博弈树叶子节点的价值可以通过静态评估函数计算出来,当静态评估函数较为准确时,就可以得到相应的近似最优解; 4.符号说明 D:2048 中块数的最大数值 N:无数字块数 minimax的最小值 台机器被测试的次数n:所有机器目前被测试的总次数 5.型建立与求解 5.1. 问题一 5.1.1 Random-Max-Trees 算法 Random-Max-Trees 是从Minimax 算法改变而来。只是加了一个条件,双方都 是非理性的条件下,本质还是Minimax。 Minimax 的定义 minmax 上的实值函数。它等价于非线)可用求解约束问题的算法求解问题(1.2)-(1.3),从而得到 Minimax 问题的 假设在博弈过程中,对方总是选择使得博弈值最小的移动,我方则会选择博弈值最大的移动,对方称为Min,则我方称为Max,且都是非理性的。由于博弈双 方是交替移动的,所以博弈树的结点及其父结点分属于我方与对方其中的一个, 其种类分属Max 和Min。博弈树上的每个结点对应于一个深度,叶结点的深度为0。 因此,在任意的结点node,对博弈双方均最优的博弈值为 (node) (node) inMax(node)=(MinMax(s)) (MinMax(s)) seSuccessors seSuccessors Evaluate note MAXMIN 由此,很自然地得出Random-Max-Trees算法,用来求出满足一些条件的二人 零和博弈问题的博弈值。 5.1.2. Alpha-beta 剪枝算法 Alpha-beta 算法是对Minimax 算法的优化,运行效率比Minimax 更高,自然也 比Random-Max-Trees 快。Random-Max- Trees 算法在检查整个博弈树,效率非常低 的,当步数越来越多的时候,每次搜索更深一层时,树的大小就呈指数式增长, 工作量越来越大,存在着 现象是极大值冗余。在图1-a 中,节点 的值中之较大者。现在已知节点 的值应是它的诸子节点的值中之极小者,此极小值一定小于等于节点D 的值,因此亦一定小于节点B 这表明,继续搜索节点C的其他诸子节点E, F,„已没有意义,它们不能做任何贡 献,于是把以节点 为根的子树全部剪去。这种优化称为Alpha 剪枝。在图 1-b 是与极大值冗余对偶的现象,称为极小值冗余。节点 的值应是它的诸子节点的值中之极大者,此极大值一定大于等于节点 为根的子树全部剪去,这种优化称为Beta剪枝。 Alpha-beta算法是在众多路线里尽可能选择最好的线路。要想通过检查搜 索树的前面几层,并且在叶子结点上用启发式的评价,那么做尽可能深的搜索是 很重要的。下面通过比较来进一步了解 Random-Max- Trees 算法与 Alpha-beta 对于一个Min节点,若能估计出其倒推值的上确界Beta,并且这个 Beta 值不大于Min 的父节点(Max 节点)的估计倒推值的下确界 Alpha,即 Alpha Beta,则就不必再扩展该Min节点的其余子节点了,因为这些节 Min父节点的倒推值已无任何影响了,这一过程称为 Alpha 剪枝。 对于一个Max 节点,若能估计出其倒推值的下确界 Alpha,并且这个 Alpha 值不小于 Max 的父节点(Min 节点)的估计倒推值的上确界 Beta, Beta,则就不必再扩展该Max 节点的其余子节点了,因为这 Max父节点的倒推值已无任何影响了。这一过程称为 Beta 剪枝。 一个Max节点的Alpha 值等于其后继节点当前最大的最终倒推值,一个 Min 节点的Beta 值等于其后继节点当前最小的最终倒推值 图1-a 图1-b 采用Alpha-beta 剪枝,可以在相同时间内加大Random-Max- Trees 的搜索深度, 因此可以获得更好的效果。 5.1.3. 问题一模型的建立与求解 本论文对2048游戏进行抽象化表述: 我方:(即游戏玩家)每次可以选择上、下、左、右四个行棋策略中的一种(某 些格局会少于四种,因为有些方向不可走)。行棋后方块按照既定逻辑移动及合并, 格局转换完成。 对方:(计算机)在当前任意空格子里放置一个方块,方块的数值可以是“2” 或“4”。放置新方块后,格局转换完成。 胜利条件:出现某个方块的数值为“2048”。 失败条件:格子全满,且无法向四个方向中任何一个方向移动(均不能触发 合并)。 这样分析,于是2048 游戏就可化成建立一个模型解决信息对称的双人对弈问 评价当前格局的价值在2048 中,除了终局外,中间格局并无非常明显的价值评价指标,因此需要 用一些启发式的指标来评价格局。那些分数高的“好”格局是容易引向胜利的格 局,而分低的“坏”格局是容易引向失败的格局。 本文采用了如下几个启发式指标,如下:解释: (1)单调性 单调性指方块从左到右、从上到下均遵从递增或递减。一般来说,越单调的 格局越好。 (2)平滑性 是指每个方块与其直接相邻方块数值的差,其中差越小越平滑。例如 旁边是128平滑。一般认为越平滑的格局越好。 (3)空格数 这个很好理解,因为一般来说,空格子越少对玩家越不利。所以我们认为空 格越多的格局越好。 (4)孤立空格数 这个指标评价空格被分开的程度,空格越分散则格局越差。 (5)对方选择的剪枝 在这个程序中,除了采用 Alpha-beta 剪枝外,在 Min 节点还采用了另一种剪 枝,即只考虑对方走出让格局最差的那一步(而实际2048 中计算机的选择是随机 的),而不是搜索全部对方可能的走法。这是因为对方所有可能的选择为“空格数 2”,如果全部搜索的话会严重限制搜索深度。 3.可以找实验玩家获得数据,再进行因子分析,根据这五种因素对到达 2048 步数的影响确定权重。 5.1.4. 问题一模型的改进 5.1.4.1 蒙特卡罗算法 蒙特卡罗(Monte Carlo)方法也称为随机模拟方法,是一种最优有限的搜索方 法。它的基本思想是,为了求解数学、物理、工程技术以及生产管理等方面的问 题,首先建立一个概率模型或随机过程,使它的参数等于问题的解:然后通过对模 型或过程的观察或抽样试验来计算所求参数的统计特征,最后给出所求解的近似 在应用蒙特卡罗方法解决2048问题的过程中,大体上有如下几个内容: 根据概率统计模型的特点和计算实践的需要,尽量改进模型,以便减小方差和降低费用,提高计算效率。 建立对随机变量的抽样方法,其中包括建立产生伪随机数的方法和建立对所遇到的分布产生随机变量的随机抽样方法。 给出获得所求解的统计估计值及其方差或标准误差的方法。5.1.4.2 UCT 算法(UCB treesearch)UCT又名UCB TreeSearch,是上限信心界(Upper confidence bound,UCB)在 Tree Search 上的应用。UCB 策略是为了解决相互独立且收益率不同的因子,获得尽 可能大的回报的最佳策略。大致上来说,每一次操作 UCB 会根据每一个因子目前 的平均收益值,加上一个额外的参数,得出本次操作此因子的 UCB 值,然后根据 此值,挑选出拥有最大 UCB 值的因子,作为本次操作所要选择的因子。其中,所 谓额外参数,会随每一台因子被选择的次数增加而相对减少,其目的在于让选择 因子时,不过分拘泥于旧有的表现,而可以适度地探索其他因子。 UCB 公式的一般型式: Score Exploitation Exploration 在实践中,检定效果较好的一个UCB公式表示如下: 2log 是所有机器目前被测试的总次数。Tree Search 开始时,UCT 会建立一棵 Tree,然后: 利用UCB公式计算每个子节点的 UCB 值,选择UCB 值最高的子节点 直到遇到叶节点,则计算叶节点的收益值,并依此更新根节点到此一节点路径上的所有收益值 由根节点的所有子节点中,选择平均收益值最高者,作为最佳节点,此一节点,就是UCT 的结果。 5.1.4.3 改进的模型 其中 ,这是因为获胜次数永远受到访问次数的限制。先用 表示到目前为止所有手臂被访问的次数和, 当利用UCT 算法确定究竟哪一个可下点会变成最终的落子点时,总是会选择 那个被访问最大次数的可下点。所以, 利用绝对剪枝条件时,被访问最多次数的节点绝对不可能满足剪枝条件,这样就保证在使用绝对剪枝条件 后,根据访问次数做出的最终决策结果将和使用原始的UCT 方法保持一致。 如果存在明显好于其他节点的可下点,总被访问次数可能在没有达到我们预 期的总访问次数时就已经有节点的访问次数突破预计访问次数的一半。因此,在 加入绝对剪枝条件后,可以提前终止模拟,达到节省时间的作用。 5.1.4.4 模型的验证 分析:移动次数和成功概率两个指标来验证模型的有效性,需要单独提出移 动次数和成功概率进行分析,移动次数和成功概率可以通过程序进行实践,程序 内部含有移动次数的统计和制定的目标既是移动数值达到2048,自动移至2048 用到了AI,自动的进行实践,AI 能够自动且合理的规避无法移至 2048 的可能, 使达到2048 成为可能。 证明: 移动次数是通过AI 来进行统计,AI 会找到最合理的路径,虽然不会是最短的 路径,却是最合理的路径。 static inline board_t execute_move(int move, board_t board) up*/return execute_move_0(board); case down*/returnexecute_move_1(board); case /*left*/returnexecute_move_2(board); case /*right*/returnexecute_move_3(board); default:return ~0ULL; 这是AI的方向移动,switch 选择方向,move 由别的函数赋值来对AI 进行路 线的选择,从中找到最合理的路线。 最合理的路线是表示能够在成功合并成2048 的前提下分数最高,且路径也少, 通过程序的运行能够输出结果: 可以从上图的结果中看到,当玩到2048 时一共移动了 11700 步,分数是 316700,但是这个结果并不是唯一的,因为每一次开始的数值都是不一样的,那 么AI 对于不同的情况给出的操作也是不同的,所以这也是答案不唯一的原因。但 是通过多次的模拟总结,发现移动的次数是离散的,散点状的分布在10000到15000 之间,这个我们可以用函数分部的方式来进行分析。 AI 能够100%的运行并成功达到2048,所以这个成功率是100%的。 5.2 问题二模型的建立与求解 本文发现2048中每一格都是2n 的整数,通过相同2n 的数块结合形成2n+1的数 块,同时在移动的过程中产生新的数块,包括21和22两种数块,且是随机均等几 形成一个22需要2个21,且需要两个数块来形成一个数块。形成一个23需要2个22,如果都是22的情况则需要2个数块形成一个数块,同 理如给出1个22的情况和2个21的情况同时存在时,需要三个数块形成一个数块。 同理可知24,25直至2n 次,可以用2个2n-1来形成。 假设在16格中存在最大数X,且环境最为理想 则假设X=2n 形成一个2n 两个2n-1,作为最理想的情况来求解 10 假设已经存在一个2n-1,另一个2n-1便由2个2n-2形成,同时已经存在一个 2n-2,那么另一个2n-2由2个2n-3形成,以此类推,我们可以发现每一个2次数级 都拥有一个数块,而2048这款游戏有4X4的16个数块,那么我们可以推断出16个数 块存在16个不同的数级。因为移动中随机产生的数有2和4,那么我们便独立讨论 当数从21开始,那么最高数值便是21+15=216 16256 128 64 32 512 1024 2048 4096 8192 16384 32768 65536 当数从22开始,那么最高数值便是22+15=217 1632 512 256 128 64 1024 2048 4096 8192 131072 65536 32768 16384 作为理想化的推断,以每次都是4出现的线,假定之后一直都是选定的数,作为理想情况。 为最大数值X=4的情况 初始情况为2个2时,可合并成4,此时产生一个4,剩下14个数块 移动生成8,再次产生一个4,剩下一14个数块,D 再次移动产生4,合并产生16,剩下14个数块,D为16 以此类推我们可以发现,当数块为奇数个时必剩下4 D=错误!未找到引用源。 11 当X=2的情况,则可以推断出: D=错误!未找到引用源。 如果将方格扩展到N*N 个,能达到的最大数是多少? 使用数学归纳法来证明。 之前已经证明出来,在理想的环境下,4X4的16格内最大的数值是217, 而当只有一个数块的时候,最大值的情况只有4 取4时,f(4)max=131072假设当n=k 为自然数),命题成立。证明 当n=k+1时命题同样成立。 当n=4时,D=错误!未找到引用源。 所以当n=k 时,D=错误!未找到引用源。 成立,得出D=错误!未找到引用源。则,n=k+1时,D=错误!未找到引用源。 错误!未找到引用源。-错误!未找到引用源。(错误!未找到引用源。) =错误!未找到引用源。-错误!未找到引用源。 =错误!未找到引用源。-错误!未找到引用源。 =错误!未找到引用源。 上述可证: D=错误!未找到引用源。 当只有一个数块时取k=0作为特殊情况,其余时候,k 为给定值 当22时:D=错误!未找到引用源。=32 1232 16 当33时:D=错误!未找到引用源。 =1024 16128 64 32 256 512 1024 当44时:D=错误!未找到引用源。 =131072已经证明了 所以以此类推可知: =错误!未找到引用源。验证程序见附录。 13 6.模型的评价 从问题出发,建立了数学模型,用大量的数据进行验证,实现2048提供 了理论依据。 在第一问中,博弈树往往很大,而好的评估函数却很难找到,制约了极小极大算法的应用范围; 本文模型的建立和求解几乎只是从统计的角度出发的。14 7.参考文献 周明明,UCT算法在计算机围棋中的应用与改进 2012(增刊):330-06 刘宇,Monte_carlo方法在计算机围棋中的应用 47(12) 岳金朋,中国象棋Alpha_Beta搜索算法的研究与改进 2009-04 45(2) 张加佳-基于UCT 算法的非完备信息多人军旗博弈系统 哈尔滨工业大 2008年12 闫冰-IMRT中基于 MonteCarlo 模拟数据的C_S 算法研究合肥工业大学 吴哲-关于Roesser离散状态空间模式 《东北大学学报(自然科学版)》1982. 吕志明-基于符号对象函数的离散状态空间方程求解电气电子教学学 杨成梧-一般2_D线性常系数离散状态空间_省略_稳定性的一类Lyapunov 方法[J];南京理工大学学报;2000 年02 [10]代码 public class MinMaxTree

  public static ITree Max(int deep, ITree tree) //定义一个bestTree用于存放参数tree 的子节点中,权重最大的一个节点 ITree bestTree deep--;//循环判断子节点的权重 15 foreach (ITree 用来存放当前节点t的子节点 //获取子节点返回的最小权重权重值的节点 ITree //将权重值赋值给t,然后将t的同级节点,赋值给bestTree t.weight it.weight;bestTree it.weight;bestTree //返回bestTreereturn bestTree; returntree;

  public static ITree Min(int deep, ITree tree) ITreebestTree deep--;foreach (ITree it.weight;bestTree it.weight;bestTree returnbestTree; returntree; Alpha-beta剪枝算法代码 int AlphaBeta(int depth, int alpha, int beta) //如果层数为0或者已达最终状态则返回本步棋的估值 if(depth IsGameOver())return Evaluate(); for(each possible move){ MakeMove(); int val -beta,-alpha); UnMakeMove(); if(val beta){return val; alpha){alpha returnalpha;//返回最好的值 %UCT搜索的代码:y(full_board); current_node.PlayMovingMove(orientation); NewProfit(t_node, returnBestChild(full_board); %2048/*2048*/ #include

  int code[4][4]={0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0};/*游戏中的16 个格子*/ int temp[5];/*中间变量*/ int move=0;/*移动次数*/ int score=0;/*分数*/ void print(void)/*显示游戏界面*/ system(CLS);/*清屏*/printf(2048\n); printf(W--UP A--LEFT S--DOWN D--RIGHT 0--EXIT\n); printf(Score:%d Move:%d\n,score,move); printf(Made Yanjisheng\n);printf(-------------------\n);/*显示横向分隔线d,code[i][j]);/*显示数字和分隔线*/ intadd(void)/*对中间变量数组进行处理*/ intchange=0;/*判断数组是否有改变,0 不变,1 变化*/ do if(temp[i]!=temp[i+1])change=1;/*当一个0 后面不是0 时数组改变*/ temp[i]=temp[i+1]; temp[i+1]=0; change=1;/*当两个非零相同的数相加时数组改变*/score=score+temp[i];/*加分*/ temp[i-1]=temp[i-1]*2;temp[i]=0;

本文链接:http://mzi-ads.com/boyishusousuo/547.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top