2048理论上最高能玩到多少分？
发布时间：2015-01-04 00:00 来源：達聞西的博客
该文也是基于知乎的一个答案。因为前天蛋疼写了个99行蛋疼版2048，所以一时兴起在知乎上搜了搜2048，结果发现了这个问题。看了看，票数最高的两个答案都是错的，所以自己推导了一下。2048的玩法就不赘述了，先来看看相关的规则，因为是Gabriele Cirulli让这个游戏火起来的，以他的源代码为准(Gabriele Cirulli的版本的地址：2048)。
记分规则：在https://github.com/gabrielecirulli/2048/blob/master/js/game_manager.js中的167行：
self.score += merged.value;
分数就是累加游戏过程中新合成方块的数值。
新方块出现的规则：在https://github.com/gabrielecirulli/2048/blob/master/js/game_manager.js的71行：
var value = Math.random() < 0.9 2 : 4;
新方块的取值集为{2, 4}，其中4出现的概率是0.1。
熟悉了规则，先来看一个比较普遍的问题：一般情况下，合成一个不太大的数值，能得到的最高分是多少？
不妨以2048为例子，2048肯定是由两个1024合成的，所以如前所述，在合成2048的这一步，积分是2048，同样1024也是由合成得到的，所以在得到两个1024的这两步，积分是1024*2=2048，以此类推，在>4的情况下，每一步分解的逆过程都会积2048分。因为我们探讨的是理论最高分，当然希望尽可能多的合成新方块，所以不希望4是直接生成的，应该都是由2合成。假设运气足够好，玩的过程中出现的新方块都是2，那么基于以上推导，从2一路合成到2048，理论上的最高分为：
\(2048\times \left( {{\log }_{2}}\left( 2048 \right)-{{\log }_{2}}\left( 2 \right) \right)={{2}^{11}}\times \left( 11-1 \right)=\text{20480}\)
对于任意从2开始合成的\({{2}^{N}}\)这个公式可以推广为：
\({{2}^{N}}\times \left( N-1 \right)\)
有了一般情况的得分计算为基础，来看极限情况：理论上最高分是多少？
要回答这个问题首先要来看2048理论上能达到最终布局是怎么样的，假设能达到的最大的数值为\({{2}^{N}}\)，那么在最后一步合成\({{2}^{N}}\)时一定是占两格的两个\({{2}^{N-1}}\)，那么对这两个\({{2}^{N-1}}\)做最小的展开，也就是保持一个不变，另一个展开为两个\({{2}^{N-2}}\)……如下所示：
\({{2}^{N}}\xleftarrow{\text{merge}}{{2}^{N-1}},{{2}^{N-1}}\xleftarrow{\text{merge}}{{2}^{N-1}},{{2}^{N-2}},{{2}^{N-2}}\xleftarrow{\text{merge}}\cdots \xleftarrow{\text{merge}}{{2}^{N-1}},{{2}^{N-2}},\cdots 16,8,4,4\)
所以依次类推假如要合成\({{2}^{N}}\)，则需要一直展开一个相邻的方块序列直到游戏能产生的方块值，其中序列长度由要展开的级数的初始值决定，比如要展开到\({{2}^{N-M}}\)，则需要的序列长度是\(M+1\)，因为游戏一共16个格子，所以\(M+1=16\)，则\(M=15\)。考虑到需要最大值，所以认为在这样一个序列中，游戏产生的方块是两个4，那么\({{2}^{N-M}}={{2}^{N-15}}={{2}^{2}}=4\)，则\(N=17\)，所以游戏能达到的方块最大值是\({{2}^{17}}=\text{131072}\)。
同样道理，当一个131072已经产生之后，还剩下15个格子，那么这种情况下能产生的最大值为65536，依此类推，14个格子能合成的最大值是32768，……
所以理论上最大值的情况一定是前15个格子的值依次为 \({{2}^{17}},{{2}^{16}},{{2}^{15}},\cdots ,{{2}^{4}},{{2}^{3}}\)，也就是\(131072,65536,32768,\cdots ,16,8\)。
而最后一个格子是2或者4都无所谓，因为不计分。这种布局的一个例子如下(图用我自己写的蛋疼99行代码Python版2048画的)：
因为最后一个4或者2是游戏产生的，所以不计入积分，所以所有的积分都来源于从8到131072的15个数字。回想在第一问里得到的从2开始合成\({{2}^{N}}\)的公式，那么似乎最高分应该是N=3,4,5,…,16,17对应的积分的总和，也就是
\(\sum\limits_{K=3}^{17}{{{2}^{K}}\times \left( K-1 \right)}=\text{3932160}\)
然而，答案并非如此，原因就是上面我关于合成数值的最小格子数占用的分析，当65536合成之后，从2开始合成一个数值需要的最少格子数超过了可用格子数了。比如我们考虑要合成两个65536的情况，也就是第一次合成出131072的情况，如下图：
这是合成出131072必经的一步，注意最左上角的4，这个4显然不可能是由2合成的，而是游戏直接生成，因为对于131072，从4开始合成最少需要的格子数是16，所以只有在需要合成的值是65536或者以下时，我们才有可能从2开始合成出所有的数值，也就是说对于2048这个游戏，只有当\(N\le 16\)时\({{2}^{N}}\times \left( N-1 \right)\)才成立。所以当131072出现时和出现后，计算最终分数的关键就在于算出最少必须产生多少个值为4的方块，那么最后就得从3932160的分数里减去多少个4。
那么什么时候需要游戏必须产生4呢，我们再回到前面关于产生一个数值需要序列长度的推导：前面得出的结论是要展开到\({{2}^{N-M}}\)，则需要的序列长度是\(M+1\)，因为我们希望合成次数尽量最大化，所以要展开到\({{2}^{N-M}}=2={{2}^{1}}\)，则需要的格子数目为\(M+1=N\)，所以在\({{2}^{17}}=131072\)出现前，任何数字都不会需要16个以上的格子，所以也就不需要4的出现。而当需要合成131072时，需要17个格子，而整个游戏只有16个，所以就不能从2开始合成了，于是这是第一次需要4的情况。
当131072已经出现后，可用格子的最大数目是15了，这时候合成\({{2}^{16}}=65536\)也需要一次4了。当65536合成之后，可用格子最大数目变为14，这时候32768的合成也需要产生一个值为4的方块了……于是依次类推，当16合成之后(也用到了新产生的值为4的方块)，为了合成8，最后一次由游戏产生了4，也就是下图：
所以从8到131072，一共15个数字在最后合成的过程中需要4的出现，也就是说理论上能达到的最高分数是：
\(\text{3932160-4}\times \text{15=3932100}\)
当然了，这个毕竟是理论最高分，实际操作起来，几乎是无法达到的，通过不断的悔棋和坚强的毅力达到我前面提过的最终局面也许并不难，但是2和4出现的比率是9:1这点是无法通过悔棋改变。不妨大概估算一下，对于 \(\){{2}^{N}}\(\)可以算出需要\({{2}^{N-1}}\)个值为2的方块，那么对于最终局面，假如不考虑格子数目对生成4的限制，则一共需要：
\(\sum\limits_{K=3}^{17}{{{2}^{K-1}}}={{2}^{17}}-{{2}^{2}}=\text{131068}\)
这么多值为2的方块，减去最后15个必须的值为4的方块，并考虑由于10%的4会生成，并且一个4等价于2个2，所以实际游戏当中玩到最终局面平均生成的方块数目为：
\(\left( 131068-15\times 2 \right)\div 1.1\approx \text{119125}\)
则值为4的方块平均数目约为11915，所以少产生的分数为：
\(\text{11912}\text{.5}\times 4\approx \text{47650}\)
也就是说假如玩到了理论上方块值最大的情况，平均分大约会是
\(3932100-47650=\text{3884450}\)
考虑到4出现的过程服从泊松分布，而在数目这么大的情况下可以用高斯分布来近似，假如很不严格地忽略掉4出现得涨落对总方块数目的影响，则有
\(\sigma {{N}_{4}}\approx \sqrt{11915}\approx \text{109}\)
所以大部分分数会落在以下范围：
\(3884450\pm 3\times 109\times 4=3884450\pm 1308\)
我大概在网上搜了一下，发现玩到最终局面的大都分为两种情况，一种是和我预测的一致在3884450左右的分数，还有一种是在386 附近，是因为Practice mode积分方法不同？版本不同？还是什么别的原因，就不太清楚了。
