MathorCup竞赛优秀论文.docx
《MathorCup竞赛优秀论文.docx》由会员分享，可在线阅读，更多相关《MathorCup竞赛优秀论文.docx（43页珍藏版）》请在冰点文库上搜索。
MathorCup竞赛优秀论文
评委一评分，签名及备注
队号：
10302
评委三评分，签名及备注
评委二评分，签名及备注
选题：
A:
2048
评委四评分，签名及备注
题目：
基于MonteCarlo局面评估和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；MonteCarlo；UTC；概率论
基于MonteCarlo局面评估和UCT博弈树搜索的2048
1．问题提出
2048是最近一款非常火爆的益智游戏，很多网友自称“一旦玩上它就根本停不下来”。
2048游戏的规则很简单：
每次控制所有方块向同一个方向运动，两个相同数字的方块撞在一起之后合并成为他们的和，每次操作之后会在空白的方格处随机生成一个2或者4，最终得到一个“2048”的方块就算胜利了。
如果16个格子全部填满并且相邻的格子都不相同也就是无法移动的话，那么游戏就会结束。
本文将建立数学模型，解答下列问题：
1.如何才能达到2048，给出一个通用的模型，并采用完成游戏所需移动次数和成功概率两个指标来验证模型的有效性；
2.得到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比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）:
定义在
上的实值函数
:
第
台机器到目前为止的平均收益
:
第
台机器被测试的次数
:
所有机器目前被测试的总次数
5．型建立与求解
5.1.问题一
5.1.1Random-Max-Trees算法
Random-Max-Trees是从Minimax算法改变而来。
只是加了一个条件，双方都是非理性的条件下，本质还是Minimax。
Minimax的定义
（1.1）
是定义在
上的实值函数。
它等价于非线性优化问题
（1.2）
（1.3）
可用求解约束问题的算法求解问题（1.2）-（1.3），从而得到Minimax问题的解。
假设在博弈过程中，对方总是选择使得博弈值最小的移动，我方则会选择博弈值最大的移动，对方称为Min，则我方称为Max，且都是非理性的。
由于博弈双方是交替移动的，所以博弈树的结点及其父结点分属于我方与对方其中的一个，其种类分属Max和Min。
博弈树上的每个结点对应于一个深度，叶结点的深度为0。
因此，在任意的结点node，对博弈双方均最优的博弈值为
由此，很自然地得出Random-Max-Trees算法，用来求出满足一些条件的二人零和博弈问题的博弈值。
5.1.2.Alpha-beta剪枝算法
Alpha-beta算法是对Minimax算法的优化，运行效率比Minimax更高，自然也比Random-Max-Trees快。
Random-Max-Trees算法在检查整个博弈树，效率非常低的，当步数越来越多的时候，每次搜索更深一层时，树的大小就呈指数式增长，工作量越来越大，存在着2种明显的冗余现象，自然降低了搜索的效率。
第1种现象是极大值冗余。
在图1-a中，节点A的值应是节点B和节点C的值中之较大者。
现在已知节点B的值大于节点D的值。
由于节点C的值应是它的诸子节点的值中之极小者，此极小值一定小于等于节点D的值，因此亦一定小于节点B的值，这表明，继续搜索节点C的其他诸子节点E,F,…已没有意义，它们不能做任何贡献，于是把以节点C为根的子树全部剪去。
这种优化称为Alpha剪枝。
在图1-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，即Alpha
Beta，则就不必再扩展该Min节点的其余子节点了，因为这些节点的估值对Min父节点的倒推值已无任何影响了，这一过程称为Alpha剪枝。
B.对于一个Max节点，若能估计出其倒推值的下确界Alpha，并且这个Alpha值不小于Max的父节点（Min节点）的估计倒推值的上确界Beta，即Alpha
Beta，则就不必再扩展该Max节点的其余子节点了，因为这些节点的估值对Max父节点的倒推值已无任何影响了。
这一过程称为Beta剪枝。
C.一个Max节点的Alpha值等于其后继节点当前最大的最终倒推值，一个Min节点的Beta值等于其后继节点当前最小的最终倒推值
图1-a图1-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）对方选择的剪枝
在这个程序中，除了采用Alpha-beta剪枝外，在Min节点还采用了另一种剪枝，即只考虑对方走出让格局最差的那一步（而实际2048中计算机的选择是随机的），而不是搜索全部对方可能的走法。
这是因为对方所有可能的选择为“空格数×2”，如果全部搜索的话会严重限制搜索深度。
3.可以找实验玩家获得数据，再进行因子分析，根据这五种因素对到达2048步数的影响确定权重。
5.1.4.问题一模型的改进
5.1.4.1蒙特卡罗算法
蒙特卡罗（MonteCarlo）方法也称为随机模拟方法，是一种最优有限的搜索方法。
它的基本思想是，为了求解数学、物理、工程技术以及生产管理等方面的问题，首先建立一个概率模型或随机过程，使它的参数等于问题的解:
然后通过对模型或过程的观察或抽样试验来计算所求参数的统计特征，最后给出所求解的近似值。
在应用蒙特卡罗方法解决2048问题的过程中，大体上有如下几个容:
1）对求解的问题建立简单而又便于实现的概率统计模型，使所求的解恰好是所建立模型的概率分布或数学期望。
2）根据概率统计模型的特点和计算实践的需要，尽量改进模型，以便减小方差和降低费用，提高计算效率。
3）建立对随机变量的抽样方法，其中包括建立产生伪随机数的方法和建立对所遇到的分布产生随机变量的随机抽样方法。
4）给出获得所求解的统计估计值及其方差或标准误差的方法。
5.1.4.2UCT算法（UCBfortreesearch）
UCT又名UCBforTreeSearch,是上限信心界（Upperconfidencebound,UCB）在TreeSearch上的应用。
UCB策略是为了解决相互独立且收益率不同的因子,获得尽可能大的回报的最佳策略。
大致上来说，每一次操作UCB会根据每一个因子目前的平均收益值，加上一个额外的参数，得出本次操作此因子的UCB值，然后根据此值，挑选出拥有最大UCB值的因子，作为本次操作所要选择的因子。
其中，所谓额外参数，会随每一台因子被选择的次数增加而相对减少，其目的在于让选择因子时，不过分拘泥于旧有的表现，而可以适度地探索其他因子。
UCB公式的一般型式:
在实践中，检定效果较好的一个UCB公式表示如下:
是第
台机器到目前为止的平均收益，
是第
台机器被测试的次数，
是所有机器目前被测试的总次数。
TreeSearch开始时，UCT会建立一棵Tree，然后:
1）从根节点开始
2）利用UCB公式计算每个子节点的UCB值，选择UCB值最高的子节点
3）若此子节点并非叶节点（从未拜访过的节点），则由此节点开始，重复
（2）
4）直到遇到叶节点，则计算叶节点的收益值，并依此更新根节点到此一节点路径上的所有收益值
5）由
（1）开始重复，直到时间结束，或达到某一预设次数
6）由根节点的所有子节点中，选择平均收益值最高者，作为最佳节点，此一节点，就是UCT的结果。
5.1.4.3改进的模型
其中
代表第
个因子，
表示第
个因子目前被访问的次数，
表示第
个因子目前获胜的次数，其中
，我们可以知道，
并且
，这是因为获胜次数永远受到访问次数的限制。
先用
表示到目前为止所有手臂被访问的次数和，
表示到目前为所有因子的获胜次数和。
显然地，如果
，，则
，因此有
当利用UCT算法确定究竟哪一个可下点会变成最终的落子点时，总是会选择那个被访问最大次数的可下点。
所以，
利用绝对剪枝条件时，被访问最多次数的节点绝对不可能满足剪枝条件，这样就保证在使用绝对剪枝条件后，根据访问次数做出的最终决策结果将和使用原始的UCT方法保持一致。
如果存在明显好于其他节点的可下点，总被访问次数可能在没有达到我们预期的总访问次数时就已经有节点的访问次数突破预计访问次数的一半。
因此，在加入绝对剪枝条件后，可以提前终止模拟，达到节省时间的作用。
5.1.4.4模型的验证
分析：
移动次数和成功概率两个指标来验证模型的有效性，需要单独提出移动次数和成功概率进行分析，移动次数和成功概率可以通过程序进行实践，程序部含有移动次数的统计和制定的目标既是移动数值达到2048，自动移至2048是用到了AI，自动的进行实践，AI能够自动且合理的规避无法移至2048的可能，使达到2048成为可能。
证明：
移动次数是通过AI来进行统计，AI会找到最合理的路径，虽然不会是最短的路径，却是最合理的路径。
staticinlineboard_texecute_move（intmove,board_tboard）{
switch（move）{
case0:
/*up*/returnexecute_move_0（board）;
case1:
/*down*/returnexecute_move_1（board）;
case2:
/*left*/returnexecute_move_2（board）;
case3:
/*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,作为最理想的情况来求解
假设已经存在一个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
2
4
8
16
256
128
64
32
512
1024
2048
4096
8192
16384
32768
65536
当数从22开始，那么最高数值便是22+15=217
4
8
16
32
512
256
128
64
1024
2048
4096
8192
131072
65536
32768
16384
作为理想化的推断，以每次都是4出现的话，可知217为最高数值。
X=2或者4，假定之后一直都是选定的数，作为理想情况。
N为剩下的数块数
D为最大数值
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
以此类推我们可以发现，当数块为奇数个时必剩下4
D=
当X=2的情况，则可以推断出：
D=
如果将方格扩展到N*N个，能达到的最大数是多少？
使用数学归纳法来证明。
之前已经证明出来，在理想的环境下，4X4的16格最大的数值是217，
而当只有一个数块的时候，最大值的情况只有4
可证当n取1时，f
（1）max=4
当n取4时，f（4）max=131072
假设当n=k时（k≥n0，k为自然数）,命题成立。
证明当n=k+1时命题同样成立。
当n=4时，D=
所以当n=k时，D=
当n=k成立，得出D=
则，n=k+1时，D=
-（）
=-
=-
=
上述可证：
D=
当只有一个数块时取k=0作为特殊情况，其余时候，k为给定值
当2×2时：
D==32
4
8
32
16
当3×3时：
D==1024
4
8
16
128
64
32
256
512
1024
当4×4时：
D==131072已经证明了
所以以此类推可知：
N×N=
验证程序见附录。
6．模型的评价
1模型的优点
1）博弈树叶子节点的价值可以通过胜负关系来确定，最优解明显；
2）搜索深度大，搜索速度快；
3）从问题出发，建立了数学模型，用大量的数据进行验证，实现2048提供了理论依据。
2模型的缺点
1）在第一问中，博弈树往往很大，而好的评估函数却很难找到，制约了极小极大算法的应用围；
2）在第一问中，通过全面的搜索来弥补策略上的不足，不太可能；
3）本文模型的建立和求解几乎只是从统计的角度出发的。
7．参考文献
[1]周明明，UCT算法在计算机围棋中的应用与改进2012（增刊）：
330-06
[2]宇，Monte_carlo方法在计算机围棋中的应用47（12）
[3]岳金朋，中国象棋Alpha_Beta搜索算法的研究与改进2009-0445
（2）
[4]王晖，基于高阶差分方法半参数回归模型参数估计及其minimax性质[D];华中师大学;2012年
[5]加佳-基于UCT算法的非完备信息多人军旗博弈系统 工业大学2008年12月
[6]闫冰-IMRT中基于MonteCarlo模拟数据的C_S算法研究工业大学
[7]吴哲-关于Roesser离散状态空间模式《东北大学学报（自然科学版）》1982.
[8]吕志明-基于符号对象函数的离散状态空间方程求解电气电子教学学报
[9]成梧-一般2_D线性常系数离散状态空间_省略_稳定性的一类Lyapunov方法[J];理工大学学报;2000年02期
[10].zhihu./question/23141069
8．附件
%Random-Max-TreesJava代码
publicclassMinMaxTree
{
///
///
///
///深度
///ITree
///ITree
publicstaticITreeMax（intdeep，ITreetree）
{
//定义一个bestTree用于存放参数tree的子节点中，权重最大的一个节点
ITreebestTree=null;
if（deep>0）
{
deep--;
//循环判断子节点的权重
foreach（ITreetintree.list）
{
//it用来存放当前节点t的子节点
//获取子节点返回的最小权重权重值的节点
ITreeit=Min（deep，t）;
if（bestTree==null）
{
//将权重值赋值给t，然后将t的同级节点，赋值给bestTree
t.weight=it.weight;
bestTree=t;
}
else
{
//和下一个节点比较，找出权重最大的一个节点
if（bestTree.weight{
t.weight=it.weight;
bestTree=t;
}
}
}
//返回bestTree
returnbestTr
升级会员 