MathorCup竞赛优秀论文.docx

《MathorCup竞赛优秀论文.docx》由会员分享，可在线阅读，更多相关《MathorCup竞赛优秀论文.docx（34页珍藏版）》请在课桌文档上搜索。

1、评委一评分，签名及备注队号：10302评委三评分，签名及备注评委二评分，签名及备注选题：A:2048评委四评分，签名及备注题H：基于MonteCarlo局面评估和UCT博弈树搜寻的2048摘要本文首先提出Random-Max-Trees算法来实现人工智能的2048。此算法是通过静态评估函数来求得最优解。但是在实现的过程中出现冗余的现象，当移动方格步数过多的时候，好的评估函数却很难找到，使Random-Max-Trees算法效率降低。随后本论文接受Alpha-Beta算法，是前者的一种改进，在搜寻结点数一样的状况下,可以使搜寻深度达到原来的两倍。在实现的过程中发觉Alpha-Beta严峻依靠于着

2、法的找寻依次。只有当程序挑最好的子节来当先搜寻，才会接近于实际分枝因子的平方根，也是该算法最好的状态。但是在首先搜寻最坏的子节时，Beta截断不会发生，此时该算法就如同Random-Max-Trees一样，效率特殊低，也失去AIPha-Beta的优势，也无法试图通过面的搜寻来弥补策略上的不足。本文接受蒙特卡洛评估对以上模型进行了改进。它通过对当前局面下的每个的可选点进行大量的模拟来得出相应的输赢的统计特性，在简洁状况下，胜率较高的点就可以认为是较好的点予以选择。由于UCT算法能不断依据之前的结果调整策略，选择优先评估哪一个可下点。所以在蒙特卡洛德基础上运用UCT算法提高收敛速度。可求得概率为1

3、00%o对于其次问，接受归纳法以及概率论量化数值，当方格为4x4时，最大能达到2=131072,假如将方格扩展到NXN个，能达到的最大数为最终对模型进行评价。本论文算法是接受JAVA、C+以及MATLAB实现。关键字：Random-Max-Trees；Alpha-beta；MonteCarlo；UTC；概率论基于MonteCarlO局面评估和UCT博弈树搜寻的20481.问题提出2048是最近一款特殊火爆的益智游戏，许多网友自称“一旦玩上它就根本停不下来”。2048游戏的规则很简洁：每次限制全部方块向同一个方向运动，两个相同数字的方块撞在一起之后合并成为他们的和，每次操作之后会在空白的方格处随

4、机生成一个2或者4,最终得到一个“2048”的方块就算胜利了。假如16个格子全部填满并且相邻的格子都不相同也就是无法移动的话，那么游戏就会结束。本文将建立数学模型，解答下列问题：1 .如何才能达到2048,给出一个通用的模型，并接受完成游戏所需移动次数和胜利概率两个指标来验证模型的有效性；2 .得到2048之后，游戏还可以接着玩，那么最大能达到多大的数值呢？假如将方格扩展到N*N个，能达到的最大数是多少？2 .问题分析本文首先基于Random-Max-Trees和Alpha-beta剪枝算法来实现人工智能(Al)的2048。本文认为可以把2048游戏看成是一场人类和计算机的博弈，人类限制全部方

5、块向同一个方向移动并合并，计算机则在空白处随机放置一个“2”或“4”的方块。但是在AI的环境下，博弈双方都是计算机，双方都不理性，所以在AI的环境下，选用更加保守的Random-Max-Trees博弈策略比选用Mini-Max-Tree的更加适当。假如把当前格局作为博弈树的父节点，把下一步全部可能的走法所造成的格局作为树的一个子节点，假如接着运用RandOm-MaX-TreeS算法，则此算法的效率很不志向，会造成许多不必要的步骤。因为每一个子节后面还有子节，可能的状况许多循环往复，直到2048为止，但是并不是全部的节点都必需搜寻完毕，有些节点是不必要的。为了解决这一问题，本文可以接受Alpha

6、-beta剪枝算法。对于第一问为实现2048的这种状况，蒙特卡洛评估是一个很好的解决方法，它通过对当前局面下的每个的可选点进行大量的模拟来得出相应的输赢的统计特性，在简洁状况下，胜率较高的点就可以认为是较好的点予以选择。UCT在蒙特卡洛评估算法的基础上很大的提高了收敛速度，UCT能不断依据之前的结果调整策略，选择优先评估哪一个可下点，基于此策略从而也可以得到其次问的答案。对于其次问，如何计算出最大值是有条件的，对有随机值的问题，我们须要量化数值，假如考虑随机那么就有不确定性，这会使我们无法接近最大值，所以在最起先就干脆规定好，取4来作为加数，因为这是累计的题目，4比2大，所以在有限的范围内，4

7、的总和确定比2的总和大。规定好数值，起先计算最大值。最大值是2的倍数，通过玩2048已经知道相同的数可以合并形成更大的数，合并一个数须要有两个数的空间，通过这一规律我们可以知道当格子都排满的状况下，还是有可能进行数字的合并的，假如可以进行合并的话，那就又增加一个4,这时又是满格的状况，假如合并过的数再次进行和并又再次产生一个空位，那么以此类推用过可以产生15次空格，那么，这15有同时增加了15次4,通过这些新加入的4,数值会进一步的增加。3 .模型的假设1) Alpha-Beta有比Minimax搜寻算法更加精确的评估函数才能保证那些优秀的节点不被过早的剪枝；2)博弈树较小而可以被完全绽开，博

8、弈树叶子节点的价值可以通过输赢关系来确定，搜寻的结果就是最优解；3)博弈树很大而不能被完全绽开时，博弈树叶子节点的价值可以通过静态评估函数计算出来，当静态评估函数较为精确时，就可以得到相应的近似最优解；4 .符号说明D：2048中块数的最大数值N：多数字块数I(x):minimax的最小值Fi(x)：定义在Rn上的实值函数K.第j台机器到目前为止的平均收益7().第/台机器被测试的次数n:全部机器目前被测试的总次数5 .型建立与求解5.1. 问题一5.1.1. Random-MaX-TreeS算法Random-MaX-TreeS是从MinimaX算法变更而来。只是加了一个条件，双方都是非理性的

9、条件下，本质还是MinimaX。Minimax的定义/(x)=zZ(x)=F(x)minF(x)= max iimf(x),xR,(1. 1)/(外=1，2,.,01是定义在宠”上的实值函数。它等价于非线性优化问题minz,(1.2)SL/(x)-zO,i=l,2,.,m(1.3)可用求解约束问题的算法求解问题(L2)-(1.3),从而得到Minimax问题的解。假设在博弈过程中，对方总是选择使得博弈值最小的移动，我方则会选择博弈值最大的移动，对方称为Mirb则我方称为Max,且都是非理性的。由于博弈双方是交替移动的，所以博弈树的结点及其父结点分属于我方与对方其中的一个，其种类分属Max和Mi

10、no博弈树上的每个结点对应于一个深度，叶结点的深度为0。因此，在随意的结点node,对博弈双方均最优的博弈值为Evaluate(note)nMax(node)=:叱表示到目前为全部因子的获胜次数和。明显地，假如2,/v.=V-V.V-V.则乙J2,因此有2当利用UCT算法确定原委哪一个可下点会变成最终的落子点时，总是会选择那个被访问最大次数的可下点。所以，l,.,Zciw利用确定剪枝条件时，被访问最多次数的节点确定不行能满足剪枝条件，这样就保证在运用确定剪枝条件后，依据访问次数做出的最终决策结果将和运用原始的UCT方法保持一样。假如存在明显好于其他节点的可下点，总被访问次数可能在没有达到我们预

11、期的总访问次数时就已经有节点的访问次数突破预料访问次数的一半。因此，在加入确定剪枝条件后，可以提前终止模拟，达到节约时间的作用。5.1.4.4模型的验证分析：移动次数和胜利概率两个指标来验证模型的有效性，须要单独提出移动次数和胜利概率进行分析，移动次数和胜利概率可以通过程序进行实践，程序内部含有移动次数的统计和制定的目标既是移动数值达到2048,自动移至2048是用到了AI,自动的进行实践，AI能够自动且合理的规避无法移至2048的可能，使达到2048成为可能。证明：移动次数是通过Al来进行统计，AI会找到最合理的路径，虽然不会是最短的路径，却是最合理的路径。staticinlineboard

12、_texecute_move(intmove,board_tboard)switch(move)case0:*up*/returnexecute_move_0(board);case 1: *down*returnexecute_move_l(board);case 2: *left*returnexecute_move_2(board);case 3: *right*returnexecute_move_3(board);default:retum0ULL;1)这是Al的方向移动，SWitCh选择方向，move由别的函数赋值来对AI进行路途的选择，从中找到最合理的路途。最合理的路途是表示能够

13、在胜利合并成2048的前提下分数最高,且路径也少,通过程序的运行能够输出结果：可以从上图的结果中看到，当玩到2048时一共移动了11700步，分数是316700,但是这个结果并不是唯一的，因为每一次起先的数值都是不一样的，那么Al对于不同的状况给出的操作也是不同的，所以这也是答案不唯一的缘由。但是通过多次的模拟总结,发觉移动的次数是离散的,散点状的分布在Ioooo到15000之间，这个我们可以用函数分部的方式来进行分析。AI能够100%的运行并胜利达到2048,所以这个胜利率是100%的。5.2问题二模型的建立与求解本文发觉2048中每一格都是2n的整数，通过相同2n的数块结合形成2n+l的数

14、块，同时在移动的过程中产生新的数块，包括21和22两种数块，且是随机均等几率的。形成一个22须要2个21,且须要两个数块来形成一个数块。形成一个23须要2个22,假如都是22的状况则须要2个数块形成一个数块，同理如给出1个22的状况和2个21的状况同时存在时，须要三个数块形成一个数块。同理可知24,25直至2n次，可以用2个2nT来形成。假设在16格中存在最大数X,且环境最为志向则假设X=2n形成一个2n两个2nT,作为最志向的状况来求解假设已经存在一个2n-L另一个2nT便由2个2n-2形成，同时己经存在一个2n-2,那么另一个2n-2由2个2n-3形成，以此类推，我们可以发觉每一个2次数级

15、都拥有一个数块，而2048这款游戏有4X4的16个数块，那么我们可以推断出16个数块存在16个不同的数级。因为移动中随机产生的数有2和4,那么我们便独立探讨当数从21起先，那么最高数值便是21+15=2162481625612864325121024204840968192163843276865536当数从22起先，那么最高数值便是22+15=217481632512256128641024204840968192131072655363276816384作为志向化的推断，以每次都是4出现的话，可知217为最高数值。X=2或者4,假定之后始终都是选定的数，作为志向状况。N为剩下的数块数D为最

16、大数值X=4的状况初始状况为2个2时，可合并成4,此时产生一个4,剩下14个数块移动生成8,再次产生一个4,剩下一14个数块，D为8随机移动，产生一个4,剩下13个数块，D为8再次移动产生4,同时合并4,产生2个8,剩下13个数块，D为8再次移动产生4,合并产生16,剩下14个数块，D为16以此类推我们可以发觉，当数块为奇数个时必剩下4dw=4三+X1(当X=2的状况，则可以推断出:rC0=27:二(2J)D=假如将方格扩展到N*N个，能达到的最大数是多少？运用数学归纳法来证明。之前已经证明出来，在志向的环境下，4X4的16格内最大的数值是217,而当只有一个数块的时候，最大值的状况只有4可证

17、当n取1时,f(l)max=4当n取4时，f(4)max=131072假设当n=k时(k&n,k为自然数)，命题成立。证明当n=k+l时命题同样成立。r=4-+(4-当n=4时，D=他=4 + 所以当n=k时，D/当n=k成立,得出D乙J则，n=k1W, DJaD = 2i -if)仰+4侬亡U(D-+I：W)=fcl*j上述可证：D二产”当只有一个数块时取k=0作为特殊状况，其余时候，k为给定值当2X2时：D=421*=32483216当3X3时：D=M1=1024481612864322565121024当4X4时：Dr*1=131072已经证明白所以以此类推可知：NxN二日验证程序见附录

18、。1310726.模型的评价模型的优点D博弈树叶子节点的价值可以通过输赢关系来确定，最优解明显；2）搜寻深度大，搜寻速度快；3）从问题动身，建立了数学模型，用大量的数据进行验证，实现2048供应了理论依据。模型的缺点D在第一问中，博弈树往往很大，而好的评估函数却很难找到，制约了微小极大算法的应用范围；2）在第一问中，通过全面的搜寻来弥补策略上的不足，不太可能；3）本文模型的建立和求解几乎只是从统计的角度动身的。7.参考文献1周明明，UCT算法在计算机围棋中的应用与改进2023（增刊）：330-062刘宇，MontJCark）方法在计算机围棋中的应用47（12）3岳金朋，中国象棋AlPha_Be

19、ta搜寻算法的探讨与改进202304454王晖,基于高阶差分方法半参数回来模型参数估计及其minimax性质D;华中师范高校;2023年5张加佳-基于UCT算法的非完备信息多人军旗博弈系统哈尔滨工业高校2023年12月6闫冰-IMRT中基于MonteCarlo模拟数据的C_S算法探讨合肥工业高校7吴哲一关于ROeSSer离散状态空间模式东北高校学报（自然科学版）1982.8吕志明基于符号对象函数的离散状态空间方程求解电气电子教学学报9杨成梧一般2_D线性常系数离散状态空间一省略稳定性的一类Lyapunov方法J;南京理工高校学报;2000年02期10:/Zhihuquestion2314106

20、98.附件%Random-Ma-TreesJava代码publicclassMinMaxTree(/深度/ITree/ITreepublicstaticITreeMax(intdeep,ITreetree)(定义一个bestTree用于存放参数tree的子节点中，权重最大的一个节点ITreebestTree=null;if(deep0)(deep;循环推断子节点的权重foreach(!Treetintree.Iist)(/it用来存放当前节点的子节点获得子节点返回的最小权重权重值的节点ITreeit=Min(deept);if(beslTree=null)(将权重值赋值给l,然后将I的同级节点

21、，赋值给beslTree(.weight=it.weight;beslTree=t;)else(和下一个节点比较，找出权重最大的一个节点if(bestTree.weightit.weight)(1,weight=it.weight;beslTree=t;/返回bestTreereturnbestTree;)returntree;)/Min/深度/ITree/ITreepublicstaticITreeMin(intdeep,ITreetree)(ITreebestTree=null;if(deep0)(deep-;foreach(!Treetintree.list)ITreeit=Max(de

22、ep,t);if(bestTree=null)(,weight=it.weight;bestTree=t;)else(if(bestTree.weightit.weight)(1,weight=it.weight;bestTree=t;returnbestTree;)returntree;)%Alpha-beta剪枝算法代码intAlphaBeta(intdepth,intalpha,intbeta)(假如层数为O或者已达最终状态则返回本步棋的估值if(depth=OIsGameOverO)returnEvalualeO;for(eachpossiblemove)MakeMoveO;intva

23、l=-AlphaBeta(depth-1,-beta,-alpha);UnMakeMoveO;if(val=bela)returnval;)if(valalpha)alpha=val;returnalpha;返回最好的值)%UCT搜寻的代码：OrientationUelPlayer:NeX【Move(COnSlFullBoard&full_board)constintmc_count=O;while(mc_countkMonteCarloGameCount)FullBoardcurrent_node;Orientationorientation=MaxUcbMove(full_board);c

24、urrent_node.Copy(full_board);current_node.PlayMovingMove(orientation);NewProfit(Ht_node&mc_count);)returnBestChild(full_board);)%2048/*2048*/#include#include#include#include#includeintcode441=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;/*游戏中的16个格子*/intIemP5;/*中间变量*/intmove=。;/*移动次数*/intSCOre=0;/*分数*/voidPrint(V

25、oid)/*显示游戏界面*/(inti,j;SySlemdCLS);/*清屏*/printf(2048n);printf(1,W-UPA-LEFTS-DOWND-RIGHT0-EXITn);prinlf(Score:%dMove:%dn,score,move);prinlf(MadebyYanjishengXnn);printf(,显示横向分隔线*/for(i=0;i=3;i+)(for(j=0;j=3;j+)(if(codeij1=0)printf(,);/*0显示空格*/elsePrinIf(|%4d”,COdeij);/*显示数字和分隔线*/printf(nM);/*显示横向分隔线*/i

26、ntadd(void)/*对中间变量数组进行处理*/(inti;int1=0;intChange=O;/*推断数组是否有变更，0不变，1变更*/do(for(i=0;i=3;i+)(if(tempi=O)(if(tempi!=tempi+1)Change=1;/*当一个0后面不是0时数组变更*/tempij=tempi+l;tempi+l=O;)/*去掉中间的0*/t+；while(tv=3);/*重复多次*/fbr(i=l;i=3;i+)(if(tempi=(empi-1)(if(tempi!=O)(Change=1;/*当两个非零相同的数相加时数组变更*/score=score+tempi

27、;/*力IJ分*/)tempii-1=iempi-1*2;tempii=0;/*把两个相邻的相同的数加起来*/dofor(i=0;i=3;i+)if(tempi=O)(tempil=tempi+l;temp(i+l=0;)/*去掉中间的O*/t+；while(l=l)/*仅当数发生变更时添加新数*/(do(i=(unsigned)rand()%4;j=(unsigned)rand()%4;)while(codeij!=0);if(unsigned)rand()%4=0)(codeij=4;)else(COdeij=2;/*随机选一个空格填上2或4*/)move+;/*增加次数*/)PrinI(

28、);/*显示*/inpul=gelch();/*输入方向*/Change=O;switch(input)caseO:/*退出*/printf(Areyousuretoexit7(yn);input=getchar();if(input=yinput=Y)exit(0);break;caseW:casew:/*上*/for(j=0;j=3;j+)(for(i=0;i=3;i+)(IemPi=codeij;/*把一列数移到中间变量*/)temp4=0;change=change+add();for(i=0;i=3;i+)(COdeij=empi;/*把处理好的中间变量移回来*/)break;cas

29、e,A:casea:/*左*7for(i=0;i=3;i+)(for(j=0;j=3;j+)(IemPj=codeijl;/*把一行数移到中间变量*/)(emp4=0;change=changeadd();fr(j=0y=3y+)(codeij=lempj;/*把处理好的中间变量移回来break;caseS:case,s*T*/fbr(j=0;j=3y+)(fbr(i=0;i=3;i+)(IemPi=code3-ij;/*把一列数移到中间变量*/)(emp4=0;change=change+add();for(i=0;i=3;i+)(COde3-ij=iempi;/*把处理好的中间变量移回来*

30、/)break;case,D:cased:/*右*/for(i=0;i=3;i+)(for(j=0u=3ij+)(IemPm=Codei3-j;/*把一行数移到中间变量*/)tempi4=0;change=change+add();for(j=0;j=3;j+)(COdei3-j=iempj;/*把处理好的中间变量移回来*/)break;)gameover=l;fbr(i=0;i=3;i+)for(j=0y=3y+)if(codeiUl=O)gameover=0*全部格子都填满则游戏结束*/printf(Gameover!n);getch();return0;%2048求move的步数以及达到

31、的最大值/*2048*/#include#include#include#include#includeintcode441=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;/*游戏中的16个格子*/inttemp5;/字中间变量*/intmove=。;/*移动次数*/intSCOre=O;/*分数*/voidPrint(Void)/*显示游戏界面字/(inti,j;SySlemCCLS);/*清屏*/printf(2048n);printf(1,W-UPA-LEFTS-DOWND-RIGHT0-EXITn);prinlf(Score:%dMove:%dn,score,move

32、);prinlf(MadebyYanjishengXnn);printf(,显示横向分隔线*/for(i=0;i=3;i+)(for0=O;j=3;j+)(if(codeijl=0)(prinlf(,);/*0显示空格*/)else(Primf(%4d,codeiJU);/*显示数字和分隔线*/)printf(,n);/*显示横向分隔线*/intadd(void)/*对中间变量数组进行处理*/inti;intt=0;iniChange=O;/*推断数组是否有变更，0不变，1变更*/do(for(i=0;i=3;i+)(if(tempi=0)(if(tempi!=tempil)Change=1;/*当一个0后面不是0时数组变更*/tempi=temp(i+ll;tempi+l=0;)/*去掉中间的0*/I+；while(l=3);/*重复多次fbr(i=l;i=3;i+)(if(tempi=tempi-1)(if(tempi!=O)(Chan