MathorCup竞赛优秀论文.docx

评委一评分，签名及备注队号：10302评委三评分，签名及备注评委二评分，签名及备注选题：A:2048评委四评分，签名及备注题H：基于MonteCarlo局面评估和UCT博弈树搜寻的2048摘要本文首先提出Random-Max-Trees算法来实现人工智能的2048。此算法是通过静态评估函数来求得最优解。但是在实现的过程中出现冗余的现象，当移动方格步数过多的时候，好的评估函数却很难找到，使Random-Max-Trees算法效率降低。随后本论文接受Alpha-Beta算法，是前者的一种改进，在搜寻结点数一样的状况下,可以使搜寻深度达到原来的两倍。在实现的过程中发觉Alpha-Beta严峻依靠于着法的找寻依次。只有当程序挑最好的子节来当先搜寻，才会接近于实际分枝因子的平方根，也是该算法最好的状态。但是在首先搜寻最坏的子节时，Beta截断不会发生，此时该算法就如同Random-Max-Trees一样，效率特殊低，也失去AIPha-Beta的优势，也无法试图通过面的搜寻来弥补策略上的不足。本文接受蒙特卡洛评估对以上模型进行了改进。它通过对当前局面下的每个的可选点进行大量的模拟来得出相应的输赢的统计特性，在简洁状况下，胜率较高的点就可以认为是较好的点予以选择。由于UCT算法能不断依据之前的结果调整策略，选择优先评估哪一个可下点。所以在蒙特卡洛德基础上运用UCT算法提高收敛速度。可求得概率为100%o对于其次问，接受归纳法以及概率论量化数值，当方格为4x4时，最大能达到2'=131072,假如将方格扩展到NXN个，能达到的最大数为最终对模型进行评价。本论文算法是接受JAVA、C+以及MATLAB实现。关键字：Random-Max-Trees；Alpha-beta；MonteCarlo；UTC；概率论基于MonteCarlO局面评估和UCT博弈树搜寻的20481.问题提出2048是最近一款特殊火爆的益智游戏，许多网友自称“一旦玩上它就根本停不下来”。2048游戏的规则很简洁：每次限制全部方块向同一个方向运动，两个相同数字的方块撞在一起之后合并成为他们的和，每次操作之后会在空白的方格处随机生成一个2或者4,最终得到一个“2048”的方块就算胜利了。假如16个格子全部填满并且相邻的格子都不相同也就是无法移动的话，那么游戏就会结束。本文将建立数学模型，解答下列问题：1 .如何才能达到2048,给出一个通用的模型，并接受完成游戏所需移动次数和胜利概率两个指标来验证模型的有效性；2 .得到2048之后，游戏还可以接着玩，那么最大能达到多大的数值呢？假如将方格扩展到N*N个，能达到的最大数是多少？2 .问题分析本文首先基于Random-Max-Trees和Alpha-beta剪枝算法来实现人工智能(Al)的2048。本文认为可以把2048游戏看成是一场人类和计算机的博弈，人类限制全部方块向同一个方向移动并合并，计算机则在空白处随机放置一个“2”或“4”的方块。但是在AI的环境下，博弈双方都是计算机，双方都不理性，所以在AI的环境下，选用更加保守的Random-Max-Trees博弈策略比选用Mini-Max-Tree的更加适当。假如把当前格局作为博弈树的父节点，把下一步全部可能的走法所造成的格局作为树的一个子节点，假如接着运用RandOm-MaX-TreeS算法，则此算法的效率很不志向，会造成许多不必要的步骤。因为每一个子节后面还有子节，可能的状况许多循环往复，直到2048为止，但是并不是全部的节点都必需搜寻完毕，有些节点是不必要的。为了解决这一问题，本文可以接受Alpha-beta剪枝算法。对于第一问为实现2048的这种状况，蒙特卡洛评估是一个很好的解决方法，它通过对当前局面下的每个的可选点进行大量的模拟来得出相应的输赢的统计特性，在简洁状况下，胜率较高的点就可以认为是较好的点予以选择。UCT在蒙特卡洛评估算法的基础上很大的提高了收敛速度，UCT能不断依据之前的结果调整策略，选择优先评估哪一个可下点，基于此策略从而也可以得到其次问的答案。对于其次问，如何计算出最大值是有条件的，对有随机值的问题，我们须要量化数值，假如考虑随机那么就有不确定性，这会使我们无法接近最大值，所以在最起先就干脆规定好，取4来作为加数，因为这是累计的题目，4比2大，所以在有限的范围内，4的总和确定比2的总和大。规定好数值，起先计算最大值。最大值是2的倍数，通过玩2048已经知道相同的数可以合并形成更大的数，合并一个数须要有两个数的空间，通过这一规律我们可以知道当格子都排满的状况下，还是有可能进行数字的合并的，假如可以进行合并的话，那就又增加一个4,这时又是满格的状况，假如合并过的数再次进行和并又再次产生一个空位，那么以此类推用过可以产生15次空格，那么，这15有同时增加了15次4,通过这些新加入的4,数值会进一步的增加。3 .模型的假设1) Alpha-Beta有比Minimax搜寻算法更加精确的评估函数才能保证那些优秀的节点不被过早的剪枝；2)博弈树较小而可以被完全绽开，博弈树叶子节点的价值可以通过输赢关系来确定，搜寻的结果就是最优解；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算法变更而来。只是加了一个条件，双方都是非理性的条件下，本质还是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和Mino博弈树上的每个结点对应于一个深度，叶结点的深度为0。因此，在随意的结点node,对博弈双方均最优的博弈值为Evaluate(note)nMax(node)=<MAXseSuccessorsc)(MinMax(s).MM.cEs0xxMinMax(s)由此，很自然地得出RandOm-MaX-TreeS算法，用来求出满足一些条件的二人零和博弈问题的博弈值。5.1.2. AIPha-beta剪枝算法Alpha-beta算法是对Minimax算法的优化，运行效率比Minimax更高，自然也比Random-Max-Trees快。Random-Max-Trees算法在检查整个博弈树，效率特殊低的，当步数越来越多的时候，每次搜寻更深一层时，树的大小就呈指数式增长，工作量越来越大，存在着2种明显的冗余现象，自然降低了搜寻的效率。第1种现象是极大值冗余。在图Ip中，节点A的值应是节点B和节点C的值中之较大者。现在已知节点B的值大于节点D的值。由于节点C的值应是它的诸子节点的值中之微小者，此微小值确定小于等于节点D的值，因此亦确定小于节点B的值，这表明，接着搜寻节点C的其他诸子节点E,F,已没有意义，它们不能做任何贡献，于是把以节点C为根的子树全部剪去。这种优化称为Alpha剪枝。在图l-b是与极大值冗余对偶的现象，称为微小值冗余。节点A的值应是节点B和节点C的值中之较小者。现在己知节点B的值小于节点D的值。由于节点C的值应是它的诸子节点的值中之极大者，此极大值确定大于等于节点D的值，因此也大于节点B的值，这表明，接着搜寻节点C的其他诸子节点已没有意义，并可以把以节点C为根的子树全部剪去，这种优化称为Beta剪枝。而Alpha-beta算法是在众多路途里尽可能选择最好的线路。要想通过检查搜寻树的前面几层，并且在叶子结点上用启发式的评价，那么做尽可能深的搜寻是很重要的。下面通过比较来进一步了解Random-Max-Trees算法与Alpha-beta剪枝算法的关系。A.对于一个Min节点，若能估计出其倒推值的上确界Beta,并且这个Beta值不大于Min的父节点（MaX节点）的估计倒推值的下确界Alpha,即AlphaBeta,则就不必再扩展该Min节点的其余子节点了，因为这些节点的估值对Min父节点的倒推值已无任何影响了，这一过程称为Alpha剪枝。B.对于一个Max节点，若能估计出其倒推值的下确界Alpha,并且这个Alpha值不小于Max的父节点（Min节点）的估计倒推值的上确界Beta,即AlphaBeta,则就不必再扩展该MaX节点的其余子节点了，因为这些节点的估值对Max父节点的倒推值已无任何影响了。这一过程称为Beta剪枝。C.一个MaX节点的AIPha值等于其后继节点当前最大的最终倒推值，一个Min节点的Beta值等于其后继节点当前最小的最终倒推值»IDIIEIFI:IDIEF图图l-b接受Alpha-beta剪枝,可以在相同时间内加大Random-Max-Trees的搜寻深度,因此可以获得更好的效果。5.1.3. 问题一模型的建立与求解1）本论文对2048游戏进行抽象化表述：我方：（即游戏玩家）每次可以选择上、下、左、右四个行棋策略中的一种（某些格局会少于四种，因为有些方向不行走）。行棋后方块依据既定逻辑移动及合并，格局转换完成。对方：（计算机）在当前随意空格子里放置一个方块，方块的数值可以是“2”或“4”。放置新方块后，格局转换完成。胜利条件：出现某个方块的数值为“2048”。失败条件：格子全满，且无法向四个方向中任何一个方向移动（均不能触发合并这样分析，于是2048游戏就可化成建立一个模型解决信息对称的双人对弈问题。2）评价当前格局的价值在2048中，除了终局外，中间格局并无特殊明显的价值评价指标，因此须要用一些启发式的指标来评价格局。那些分数高的“好”格局是简洁引向胜利的格局，而分低的“坏”格局是简洁引向失败的格局。本文接受了如下几个启发式指标，如下:(1)单调性单调性指方块从左到右、从上到下均遵从递增或递减。一般来说，越单调的格局越好。(2)平滑性是指每个方块与其干脆相邻方块数值的差，其中差越小越平滑。例如2旁边是4就比2旁边是128平滑。一般认为越平滑的格局越好。(3)空格数这个很好理解，因为一般来说，空格子越少对玩家越不利。所以我们认为空格越多的格局越好。(4)孤立空格数这个指标评价空格被分开的程度，空格越分散则格局越差。(5)对方选择的剪枝在这个程序中，除了接受AIPha-beta剪枝外，在Min节点还接受了另一种剪枝，即只考虑对方走出让格局最差的那一步(而实际2048中计算机的选择是随机的)，而不是搜寻全部对方可能的走法。这是因为对方全部可能的选择为“空格数X2”，假如全部搜寻的话会严峻限制搜寻深度。3.可以找试验玩家获得数据，再进行因子分析，依据这五种因素对到达2048步数的影响确定权重。5.1.4. 问题一模型的改进514.1蒙特卡罗算法蒙特卡罗