技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 在2048里能够得到的最大的数是多少?

在2048里能够得到的最大的数是多少?

浏览:2707次  出处信息

   Michael Brand 在 Using your Head is Permitted 趣题站 2014 年 4 月的谜题中提出了一个这样的问题:在最近非常流行的小游戏 2048 中,你能得到的最大的数是多少?

   在这里,我们简单描述一下游戏的规则。游戏在一个 4 × 4 的棋盘上进行,棋盘里填有一个个的“数块”,每个数块上都写有某个形如 2n 的正整数。每一步,你需要从上、下、左、右四个方向中选取一个方向,按下对应的方向键之后,所有的数块都会“落”到这个方向;若有两个同种的数块在此过程中发生碰撞,则它们的值会相加起来,并合成一个新的数块。然后,系统会在棋盘中随机选择一个空白位置,并在此生出一个新的数块,上面写有数字 2 或者数字 4 (两种情况之比为 9 : 1)。游戏开始时,棋盘上会自动生成两个随机的数块,你的目标就是通过有限步的操作,得出一个写有 2048 的数块。当然,即使得到了 2048 这个数块,游戏也不会自动结束,你还可以向更大的数发起挑战。于是就有了我们刚才的问题:理论上,这个游戏当中能够得到的最大的数是多少?

   可以证明,我们永远不可能在 2048 当中玩出 218 这个数。

   让我们把棋盘上的所有数全部加起来,并在累加过程中不断关注当前总和的二进制表达。如果棋盘里的数分别是 2, 4, 16, 64, 16, 2 的话,累加结果的二进制表达依次为 10 → 110 → 10110 → 1010110 → 1100110 → 1101000 。你会发现,由于棋盘上的每个数都是形如 2n 的正整数,因而把它加进总和之后,这个总和的二进制表达里最多只会多出一个数字 1 (如果发生了进位,数字 1 的个数可能会不变甚至减少)。这意味着,如果最终棋盘上的所有数之和的二进制表达当中一共有 k 个数字 1 ,那就说明刚才至少有 k 个数在相加,换句话说棋盘里至少有 k 个数块。

   容易看出,每走一步之后,棋盘上的所有数之和都会增加 2 或者 4 。如果最终棋盘上出现了一个 218 ,就说明棋盘上的所有数之和至少是 218 ,那么在此之前棋盘上的所有数之和一定经历过 218 - 2 或者 218 - 4 。前者的二进制表达为 11 1111 1111 1111 1110 ,这里面有 17 个数字 1 ,超过了棋盘里总的格子数,因而显然是不可能的。后者的二进制表达是 11 1111 1111 1111 1100 ,这里面有 16 个数字 1 ,正好是棋盘里总的格子数。这说明,此时棋盘刚好被填满, 22, 23, 24, …, 217 这 16 种不同的数块各有一个。这意味着棋盘里不但没有空白的格子,也没有相同种类的数块可以合并,此时玩家直接就死掉了!因而,我们是没有办法得到 218 的。

   因此, 217 = 131072 成为了 2048 这个游戏中数块大小的一个理论上限。但是,我们真的能弄出 131072 吗?看上去,我们好像只需要构造出下图所示的局面就行了,但这个局面本身能否实现,还有待进一步讨论。 Michael Brand 猜测,理论上 131072 也是无法得到的,但他不能证明这一点。我虽然在网上看见过很多网友宣称自己打出过 131072 ,甚至有的网友发出了最后几步的视频(比如这里),但由于我从来没有看到过完整的演示过程,因而也持怀疑态度。期待万能的网友们能够提供一种简洁有效的构造解,来说明当运气足够好的情况下,我们有办法打出 131072 ;或者找到一个更好的证明方法,足以说明 131072 也是理论上不可能实现的。

建议继续学习:

  1. 2048-AI程序算法分析    (阅读:4730)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1