没有合适的资源?快使用搜索试试~ 我知道了~
mathorcup数学建模挑战赛获奖论文-第四届A题_10466c.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 200 浏览量
2024-03-14
22:06:37
上传
评论
收藏 506KB PDF 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/88965862/0001-bd23bd2c34c1452b3ee19c9cea8c2d6a_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
23页
mathorcup数学建模挑战赛获奖论文,历届,单项文件,内容丰富,大学生数学,数学竞赛,参考资料
资源推荐
资源详情
资源评论
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/release/download_crawler_static/88965862/bg1.jpg)
评委一评分,签名及备注
队号:
10466
评委三评分,签名及备注
评委二评分,签名及备注
选题:
A
评委四评分,签名及备注
题目:“2048”游戏的数学基础及其取胜策略研究
摘要
近期,有一款名为“2048”的策略益智游戏风靡网络。其简单的规则使游戏
易于上手,却又蕴含不少数学知识使人难以获胜。本文从无计算机辅助分析和有
计算机辅助分析两个角度,建立了两个求解“2048”问题的模型,并通过数学方
法求得了 2048 所能玩到的最大方格数,且将结论推广到
NN
的情况。
针对问题一,我们首先通过逻辑分析建立了无计算机辅助的初等策略模型,
之后又在此基础上运用博弈论的方法建立了有计算机辅助的博弈策略模型。在初
等策略模型中,我们得到了“ 2048”游戏中合成
2
k
需要的步数及至少需要的空间,
进而证明了游戏中将方格按 S 形递减排列的稳定性,从而提出了玩家在游戏中必
须采用的取胜策略。在博弈策略模型中,我们将“2048”游戏以博弈论的视角进
行解读,建立了描述游戏过程的博弈论模型,并参考极小极大化算法和 alpha-beta
剪枝的思路,通过建立静态估价函数,借助计算机辅助试验,分析玩家的最优决
策。该方法的成功率达到了 72%,平均成功操作步数为 895 步。
针对问题二,我们首先分析得到了一个重要的结论:游戏所能达到的最大方
格数值仅与游戏本身有关。之后,通过反证法和数学归纳法得出,在
44
的情况
下,当系统最后出现 4 时得到最大数值,为 131072,在
NN
的情况下,当系统
最后出现 4 时得到最大数值,为
1
2
NN
。
关键字:策略益智游戏;博弈论;静态估价函数;历史启发
更多数模资讯和学习资料,请关注b站/公众号:数学建模BOOM
精品课程:https://k.weidian.com/z=camKMb
![](https://csdnimg.cn/release/download_crawler_static/88965862/bg2.jpg)
- 1 -
“2048”游戏的数学基础及其取胜策略研究
1. 问题的重述
近期,有一款名为“2048”的策略益智游戏风靡网络。其简单的规则使游戏
易于上手,却又蕴含不少数学知识使人难以获胜,因而具备一定的研究价值。该
游戏局面有
44
共16个方块,初始局面为2个数值为2的位置随机的方块。玩家可
控制所有方块同时往上下左右方向移动,相邻相同数值的方块相撞则合并为一个
方块,且该方块数值为前一个方块数值的两倍。每次操作后空白处会随机出现一
个数值为2或4的方块。最终局面得到数值为2048的方块即为获胜。若16个格子被
填满且无法移动即为游戏失败。
我们将首先建立一个模型,探讨能够使得玩家在“2048”游戏中尽量获胜的
策略。由于游戏每次移动后出现方块的位置和数值随机,故该模型将从最终获胜
的概率和达到目标所要移动方块的次数来衡量取胜策略的有效性。
其次,通过实际操作发现,当游戏达到2048后,一般还能进行移动格子的操
作。所以我们将通过建立相关的的模型来分析该游戏中方格所能达到的最大数值。
进一步的,我们将探讨在
NN
个方格的情况下,游戏所能达到的最大数值。
2. 模型假设
(1)“2048”游戏的版本为问题重述里描述的版本,其中 2 以 80%的概率出现;
(2)玩家在游戏过程中不允许采用“undo”等反悔策略;
(3)玩家在游戏获胜,即达到“2048”后,可以选择继续操作以达到更大数值
的方块;
(4)玩家允许使用计算机等设备进行辅助分析。
3. 符号说明
k
G
:第
k
轮游戏;
k
S
:第
k
轮游戏开始时的局面;
ij
s
:将
k
S
视为矩阵时
k
S
的元素;
k
X
:第
k
轮游戏玩家做出的决策;
k
Y
:第
k
轮游戏系统做出的决策;
![](https://csdnimg.cn/release/download_crawler_static/88965862/bg3.jpg)
- 2 -
k
M
:第
k
轮游戏玩家做出决策后的局面;
k
S
:第
k
轮游戏开始时的所有可行局面集合;
k
X
:第
k
轮游中玩家的允许决策集合;
k
Y
:第
k
轮游戏系统的允许决策集合;
k
M
:第
k
轮游戏玩家做出决策后的可行局面集合;
k
f
:玩家在第
k
轮游中的决策函数;
k
g
:系统在第
k
轮游中的决策函数;
(.)V
:静态估价函数;
k
n
:
k
S
的空白方格数
k
n
;
max
k
:
k
S
中最大值;
k
stg
:
k
S
中方格数值的标准差;
(.)d
:位置赋分函数;
:
16
1
{}
i
i
为
k
S
对应的序列;
(d)
:
16
(d)
1
()
{}
i
i
是将
16
1
{}
i
i
中元素按从大到小排列后的更序序列。
4. 问题的分析
2.1.“ 2048”取胜策略问题的分析
2.1.1.“2048”取胜策略问题的实质
“2048”游戏的数学依据即为 2 的次方的累加。因此,取得游戏胜利的关键
因素在于当前局面的最大值,方块可移动的空间以及当前局面各个方格中数值的
关系。这就涉及到以下几个问题:
1. 如何提升当前局面中方块的最大数值。
2. 如何保持当前局面中剩余的空白方格数。
3. 如何缩小当前局面中相邻方块的差值。
4. 如何保持相邻方块的大小顺序关系。
5. 如何增加当前局面中所有方块数值的多样性。
因此,“2048”取胜策略问题的实质就是设计一套操作策略,使得能够在增
加方块数值多样性、保持相邻两个方块的大小关系的同时,降低相邻两个方块的
![](https://csdnimg.cn/release/download_crawler_static/88965862/bg4.jpg)
- 3 -
差值,以期得到数值相同、位置相邻的方块,从而通过抵消增加局面中方块的最
大值,并增加空白方格的数目。
2.1.2.“2048”取胜策略问题的解决思路
根据上一小节的分析,我们得到了“2048”问题的实质,因此,解决“2048”
问题,也就是要解决上一小节提到的五个小问题。对此,我们首先将从定性分析
的角度建立了玩家在无计算机辅助情况下的初等策略模型,其包含了一系列独立
的策略,玩家依据这些策略进行游戏;之后,我们将结合博弈论、动态规划的一
些思想,融合最小最大化算法和 alpha-beta 剪枝的方法,参考无计算机辅助的
初等模型的思路,建立一个有计算机辅助的博弈策略模型,从而解决该问题。
2.2.“ 2048”最大值问题的分析
2.2.1.“2048”最大值问题的实质
从人机博弈的角度来看,“2048”游戏所能达到的最大值问题,实质是在假
设玩家采取全局最优策略且系统时刻作出有利于玩家的决策的情况下,分析游戏
所能达到的最终局面。
2.2.2.“2048”最大值问题的解决思路
由于在分析最大值问题的时候,已经假设玩家采取的是全局最优策略,且系
统也采取有利于玩家的决策,故游戏的最终局面已经与游戏的过程没有关系,而
仅与游戏本身的性质相关。所以我们可以单纯的通过分析游戏的性质(包括各种
限制),用纯数学的方法得到该问题的解答。也正因为该问题仅与游戏本身的性
质相关,故很容易将结论推广到
NN
的情形。
5. 模型的建立与求解
5.1 问题一的模型及求解
5.1.1.无计算机辅助的初等策略模型
(1)重要的结论
定理 5.1.1.在“2048”游戏中,若只出现 2,则合成
2
k
至少需要
1
21
k
步;若只
出现 4,则合成
2
k
至少需要
2
21
k
.
证明:用数学归纳法,易得。
定理 5.1.2. 在“2048”游戏中,若只出现 2,则合成
2
k
至少需要
k
个格子;若只
出现 4,则合成
2
k
至少需要
1k
个格子.
证明:用数学归纳法。以只出现 2 为例,显然,当 k=1 时成立;假设当 k=p 时
成立,则当 k=p+1 时,为了合成
1
2
p
,需要两个相邻的
2
p
,我们首先合
成一个
2
p
,使用了 p 个格子;再合成一个
2
p
,使用了 p 个格子。由于在
合成第二个
2
p
时,第一个合成好的
2
p
占据了一个格子,所以合成
1
2
p
总
![](https://csdnimg.cn/release/download_crawler_static/88965862/bg5.jpg)
- 4 -
共至少需要 p+1 个格子。只出现 4 的情况类似,证毕。
定理 5.1.3.在“2048”游戏中,将已经合成好的方格按照从大到小的顺序按照 S
形排列是稳定的,即满足玩家的操作对已经合成的方格排列影响最小.
证明:首先,S 形排列可以逐层将界面填满;其次,对于已经填好的一行,玩家
可以在之多三个方向上移动其他方格而不改变已经排列好的方格,故 S
形排列是稳定的。
(2)取胜策略
[1]
按照(1)中的三个定理,,结合 2.1 的分析,我们得到了如下的取胜策略。
a.将最大数放在最角落(如图 5.1
1
)
由于最大数在移动的时候大多无法合并,所以将其固定在最角落保证其不影
响其他数值的合并。
图 5.1 图 5.2
b.以最大数角落为起点按数值从大到小依次横向排列
这样做当较大数附近出现可以合并的数的时候可以及时合并,可以减小最大
数与相邻数的数值差距且留出更多空白格子(图 5.2)。
c.维持最大数所在行始终满格
这样可以保证最大数位置稳定不会随其他格子移动而移动(图 5.3)。
d.最大数在下方则不按向上方向键,在上方不按向下方向键
这样可以保证最大数始终处于角落,最大数一旦离开角落很难恢复原位(图
5.4)。
1
图片 5.1 到图片 5.4 取自 http://www.gezila.com/raiders/11551_pic.html#p=1
剩余22页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/fcd62adb0120465d9af280215b0ff722_snowtshan.jpg!1)
阿拉伯梳子
- 粉丝: 1660
- 资源: 5735
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
最新资源
- java-leetcode题解之第111题二叉树的最小深度.zip
- java-leetcode题解之第110题平衡二叉树.zip
- java-leetcode题解之第109题有序链表转换二叉搜索树.zip
- java-leetcode题解之第108题将有序数组转换为二叉搜索树.zip
- java-leetcode题解之第107题二叉树的层序遍历II.zip
- java-leetcode题解之第102题二叉树的层序遍历.zip
- java-leetcode题解之第103题二叉树的锯齿形层序遍历.zip
- java-leetcode题解之第104题二叉树的最大深度.zip
- java-leetcode题解之第173题二叉搜索树迭代器.zip
- java-leetcode题解之第100题相同的树.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback-tip](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)