数学建模校内竞赛论文

《数学建模校内竞赛论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数学建模校内竞赛论文论文题目：2048游戏问题摘要本文将2048游戏抽象成人机博弈问题，一方面，讨论了任意局面难易程度的评价指标体系的确定方法，主要方法为嵌入陪练算法程序的遗传算法以及模糊模型识别方法。另一方面，对于最优路径问题，我们不仅设计了一种引入哈希表的Alpha-Beta剪枝搜索算法，同时还编写了2048游戏程序用于该模型的检验。针对问题一，为了选取科学、合理的评价指标，本文通过查找文献及对玩家的调查，结合计算机博弈论选择参数的原则，确定了固定值，平滑性，空格数，空格孤立程度这四个参数作为评估函数的指标。首先，对固定

2、值及空格数这两种指标的数据预处理；而后用模糊识别中贴近度来描述平滑性指标的大小；通过空间点模式分析离散趋势中的标准差圆法对空格孤立程度进行计算。确定各指标权重是本问题的难点，对于确定博弈问题不同指标评估参数合理大小的问题，本文采用了编写人工智能算法程序的方法加以解决，本文给出了一种利用陪练算法程序计算适应度的遗传算法，以此确定各指标参数权重。最终迭代150代后得出这四个指标所占权重分别为：固定值为0.04，平滑性为0.45，空格数为0.43，空格孤立程度为0.08。本文建立了模糊难易程度评价模型，通过数据统计结合指派法的方法

3、建立了合理的隶属度函数，通过最大隶属度原则来划分难易程度的等级。并对结果进行了检验，对难易程度进行了有效的区分。48针对问题二，本文在Alpha-Beta剪枝搜索算法的基础上引入哈希表，通过哈希表中记录的历史信息减轻搜索的负担，提高搜索效率。同时本文所给出的程序不仅能够给出当前局面的最佳移动方向，而且还包含了2048游戏功能，因此可以计算从任意局面到最终游戏结束所花费的总步长。然后从游戏结束时玩家的胜负情况、游戏结束花费的总步长、游戏结束时程序总体运行时间三个方面，将本文算法程序与2048游戏网页上的专业软件2048-AI进

4、行了比较。本文随机的以一个小规模初始局面（即空格数较多，固定值较小的局面）为例，使用本文算法程序到达成功的总步长为717步，比专业2048-AI软件路径短206步，程序执行时间缩短30.5%。同样选取其他一些小规模局面实验发现，本文算法程序在解决小规模初始局面问题，可以给出比专业软件2048-AI路径更短的方案，相应的运行时间也更短。关键词：遗传算法模糊识别最大隶属度原则Alpha-Beta剪枝算法哈希表48目录摘要1一．问题重述31.问题背景32.提出问题：3二．问题分析3三．名词解释及符号说明4四．模型假设4五．模型的建

5、立及求解55.1问题一的求解55.1.1评价指标的选取及指标值的计算51）平滑性62）空格数73）空格孤立程度84）固定值105.1.2各指标权重的确定11遗传算法的引入11利用遗传算法确定各指标权重115.1.3评价模型的建立16模糊模型识别的引入165.2问题二的求解205.2.1模型准备205.2.2模型建立211）极大极小搜索算法模型212）引入哈希表的Alpha-Beta剪枝搜索算法模型225.2.3模型求解25六．模型的评价及发展前景296.1模型的优点296.2模型的缺点296.3模型的推广29七．参考文献30

6、八、附录3148一．问题重述1.问题背景当今社会，随着手机行业迅猛的发展，各种手机app也日益火爆。2014年，一款名为“2048”的益智游戏令众多手机玩家身陷其中无法自拔。其游戏界面由4*4个方格组成。每次控制所有方块向同一个方向运动，两个相同数字的方块撞在一起之后合并成为他们的和，每次操作之后会在空白的方格处随机生成一个2或者4，最终得到一个“2048”的方块就算胜利了。如果16个格子全部填满并且相邻的格子都不相同也就是无法移动的话，那么游戏结束。2.提出问题：（1）建立相应的评价体系，评价每个状态下的难易程度；（2）建

7、立合理的模型，计算出任意状态下的最佳路径。二．问题分析本文所需求解的“2048”游戏问题乃归属于人工智能领域极具挑战性的研究方向的计算机博弈问题。博弈在传统意义上指的是一些个人、团体、或其他组织，面对一定的环境条件，在一定的约束条件下，依靠所掌握的信息，同时或先后，一次或多次，从各种可能的行为或策略集合中进行选择并实施，各自从中取得相应结果或收益的过程。我们可以将其理解为一种竞争。这款大受欢迎的“2048”游戏亦是属于人机的博弈范畴之内（玩家向四个方向中的一个移动，然后计算机在某个空格中填入2或4）。针对问题一，其要求建立一

8、套合理的评价体系去评价每个状态下的难易程度。在对“2048”博弈问题的求解中，评价当前的格局显得十分重要，因为其将影响下一步的走法。但同时，评价也是一件非常复杂的事情。首先，我们需要确定与难易程度相关的一系列指标。这在很大程度上依赖于该游戏的具体游戏规则和我们对该游戏的经验知识，因此这个问