没有合适的资源?快使用搜索试试~ 我知道了~
mathorcup数学建模挑战赛获奖论文-第四届A题_20035c.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 7 浏览量
2024-03-14
22:06:38
上传
评论
收藏 1.91MB PDF 举报
温馨提示
试读
24页
mathorcup数学建模挑战赛获奖论文,历届,单项文件,内容丰富,大学生数学,数学竞赛,参考资料
资源推荐
资源详情
资源评论
评委一评分,签名及备注
队号:
20035
评委三评分,签名及备注
评委二评分,签名及备注
选题:
A
评委四评分,签名及备注
2048 游戏玩法
摘要
继游戏“FlappyBird”下架后,一款名为“2048”的游戏受到了大众的追捧,
很多网友称其玩法看似简单,但真正玩起来着实不易。为了解决这一让众多网友
头疼的“学霸”游戏中存在的相关问题,建立了以下模型。
针对问题一,从最根本的组合递推方式入手,通过建立树状图得到了 2048
的基本步骤,根据
mini-max
算法原理,并结合玩法步骤,建立了该游戏的通用模
型。在计算方格移动次数时,考虑到最后一个数字出现的随机性,采用倒推的方
式,得到了完成 2048 的步数。最后,根据 Alpha—beta 剪枝算法,对随机游戏者,
搜集其实验数据进行分析,建立游戏者达到最大数字与所用步数以及成功率的数
学模型,并与上述通用模型做对比分析,从而验证该通用模型是有效的。
针对问题二,运用递归算法和数学归纳法建立最大值模型,讨论在最后值 M
不同取值时最大数
Q
的值,得到
Q
的最大值为 。假设最大值可以达到 ,通
过计算,假设不成立,所以“2048”游戏能达到的最大值为 。运用所建的最
大值模型,找到了递推规律,在 的模式中,假设所能达到的最大值为 ,
通过验证,假设成立,因此最大值为 。
关键字:
Mini-max
算法
Alpha—beta
剪枝算法 递归算法
更多数模资讯和学习资料,请关注b站/公众号:数学建模BOOM
精品课程:https://k.weidian.com/z=camKMb
1
“2048” 游戏玩法
1. 问题重述
“2048”是一款益智游戏,其游戏规则:每次控制所有方块向同一个方向运动,
两个相同数字的方块撞在一起后合并成为的和,每次操作之后会在空白的方格出
随机产生数字2或4,最终得到一个“ ”的方块就算通关。如果16个格子全
部填满并且相邻的格子内的数字都不相同,则无法移动格子,最终游戏结束。
通过建立模型,解决以下问题:
1、 如何达到2048,给出一个通用模型,并采用完成游戏所需移动次数和成
功概率来验证模型的有效性;
2、得到2048后,游戏还可以继续玩,那么最大能达到的数值是多少?如果
方格扩展到 个,能达到的最大数是多少?
2. 问题分析
对于问题一,很多网友自称“一旦玩上它就根本停不下来”,基于这点,通
过搜集网友的试验次数,计算发现,随意的玩法很难达到2048,因此需要建立一
个通用的模型。由于随意移动方块时,若两个相同数所组合的数越大,越难组合
到一起,通过实验发现,这个游戏的基本思想是递归生成,这样固定住了最大数
值,再通过递推累加的方法得到新的最大数。根据这一想法通过 mini-max 算法
建立模型,并且对于所给出的模型,假设了移动的次数。验证该模型的有效性,
玩该游戏的人中随机抽取100人进行试验,计算成功率,因此,通过多次试验得
出结论。验证移动次数与模型有效性时,建立移动次数与每次游戏结束时得到最
大数的散点图,得到回归方程,当组合出2048时需要多少移动次数,是否与假设
相似,如与假设相似,则验证了模型的有效性。
对于问题二,根据递归生成的模型,按照问题一给出的通用模型,将最大数
放在一个角,其余成蛇型一次递减,方格中倒数第二个数为4且最后一个数系统
生成4时,方格才可以移动,游戏继续进行,通过递推累加得到最后一位数,而
剩下的15个方格中按照递推累加法,得到的最后一位数即最大的数字,易得第一
次计算的数为最大,因此得到了“2048”的最大组合值,可以得出此游戏并不是可
以无尽的玩下去。对于 的方格,由数学归纳法,总结出 方格的规律模
型,得到问题的结论。
3. 模型假设
1. 假设每次移动都为有效移动;
2. 假设每次组合只能组合一对;
3. 假设系统随机出现数的位置与试验结果无关;
4. 假设游戏所用步数与玩家自身的主观因素无关。
4. 符号说明
2
最后一个系统随机出的数
方格中最大生成数
结束时组合的最大数
结束时最大值出现的数字
的次数
移动次数
移动步数出现的次数
G
游戏在理想模型下所能达
到的所有有限集
k 后继函数
m 游戏状态
代替问题一中的
每组成功数
每次游戏结束时得到的最
大数
达到的最大数
所用平均步数
次幂数
格子数
5. 模型建立及求解
5.1 问题一
5.1.1 背景
“2048”是最近推出的一款游戏,其游戏规则如下:
· 开始时方格内随机出现两个数字,仅可能为
2
或
4
;
· 玩家可以选择上下左右四个方向,若棋盘内的数字出现位移或合并,视为有
效移动;
· 玩家选择的方向上若有相同的数字则合并,每次有效移动可以同时合并,但
不可以连续合并;
· 合并所得的所有新生成数字想加即为该步的有效得分;
3
· 玩家选择的方向行或列前方有空格则出现位移;
· 每有效移动一步,棋盘的空位
(
无数字处
)
随机出现一个数字
(
依然可能为
2
或
4)
;
· 棋盘被数字填满,无法进行有效移动,判负,游戏结束;
·
棋盘上出现
2048
,判胜。
通过搜集数据
[1]
,该网友一共玩了 4246 次,每次结束时出现最大值的次数
(如表 1)和结束时移动方块出现的次数(如表 2):
表
1
出现最大值的次数
1 7 218
1412
2173
433 2
表
2
移动方块的次数与出现的次数
Y 0~50 50~100 100~150 150~200 200~250
2 362 1458 1556 551
Y 250~300 300~350 350~400 400~450 450~500
247 64 4 1 1
根据搜集数据得出,表 1 中最小值为 8,最大值能达到 1024,经计算数学期
望约为
101
;在表
2
中最小值是
41
,最大值是
468
,中位值
161
,数学期望为
163
。
因此,随意的玩法要到达 2048 比较难,而且用的步骤多,下面建立通用玩
法,增大达到 2048 的成功率并减少移动次数。
5.1.2
Mini-max
算法模型建立
Mini-max
算法(如图
1
)是一个回归的算法,这意味着它毕竟搜索进行到游
戏树的的叶子节点,取得游戏的结局值,再将这些数值按
Mini-max
过程后向传
递上去,直到获得所有内部节点的
Mini-max
值
[2]
。
4
图
1 Mini-max
算法树状图
为建立达到
2048
的通用模型,作如下定义:
一个区间赋值游戏为一个四元方程组(
G
,
m
,
k
,
f
)
,其中
G
为游戏在理想
模型下所能达到的所有有限集, 是游戏的初始状态,k 为后继函数,
是评价函数。 表示状态 可由状态 m
经过合理的步骤完成,通常建立的游戏模型应同时满足以下两个条件:
(1)不存在来回循环的状态。
(2)当游戏结束时,
其中,
0
和
1
分别代表游戏运行者完成后即结束和完成后仍继续闯关下去的
情况,游戏结局为
0
时,成为
minimizer
,结局为
1
时称为
maximizer
,
0
和
1
之
间的数值代表中间结果,即完不成的目标的情况。 代表完成后仍继
续闯关下去的情况, 代表完成后即结束的情况。递归定义函数:
如下:
由上式可知,
max
的值等于运行结果的最大值,
min
的值等于运行结果的最
小值,故得到
mini-max
算法如下:
If return
Else if return
Else if return
5.1.3
Alpha—beta
剪枝算法
单一的 Mini-max 算法得到通用模型比较复杂,由于所要构造数字的数目较
大,因此需要的步骤较多,限制了其移动次数。
利用 Alpha—beta 剪枝算法的工作原理(如图 2),从最大数字开始,详述使
剩余23页未读,继续阅读
资源评论
阿拉伯梳子
- 粉丝: 1662
- 资源: 5735
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功