2048比赛：我做了多少次动作？
2048以前很流行。 每个人都玩过它，很多人用他们的成就（我自己）完成了很好的截图。 然后在某个时候，我开始怀疑是否有可能说出某人玩了多长时间才能达到那个分数。 我进行了基准测试，结果发现（至少在我的Android应用程序中），一秒钟内只能做一个动作。 因此，如果您踢得足够长（足够快），您所做的移动次数与您所玩过的秒数相当接近。 现在的问题是：是否有可能拥有2048游戏的截图来计算进行了多少次移动。
下面是一个示例截图（实际上是我迄今为止在游戏中所做的最大努力）：
从截图中可以看到当前场地布局以及玩家获得的积分数量。 所以：这个信息是否足以计算我做出了多少动作？如果是这样，那么算法是什么？
注：我想提醒你，只有当两个瓷砖“结合”并且得分的数量是新瓷砖的价值（即被拼合的瓷砖的价值的总和）时才得分。
简短的答案是可以仅使用此信息来计算移动次数。 我会解释算法来做到这一点，我会尝试在步骤中发布我的答案。 每一步都是针对帮助您解决问题的观察。 我鼓励读者在每个提示后尝试单独解决问题。
观察第一：每移动一次后，就会出现一个图块。 这个瓦片是4或2.因此，我们需要做的是统计出现的瓦片数量。 至少在我玩游戏的游戏版本上，总是从2个瓦片开始，随机放置2个瓦片。
我们不关心该领域的实际布局。 我们只关心其上的数字。 当我解释我的算法时，这将变得更加明显。
看到场上单元格中的值，我们可以计算出每次移动后出现2分时的分数。 调用该值twos_score 。
出现的四分之一等于actual_score分twos_score和actual_score除以4.这是事实，因为从两个2-s形成一个4我们将得4分，而如果4直接出现，我们得分0 。 调用fours 。
我们可以计算出形成场上所有数字所需的两个数。 之后，我们需要从这个值中减去2 * fours ，因为单个4取代了两个2的需要。 称此为twos 。
使用这些观察我们能够解决问题。 现在我将更详细地解释如何执行单独的步骤。
如果只有两个出现，如何计算分数？
我将证明为了形成数字2n，玩家可以得到2 n *(n - 1)个积分（使用归纳法）。
2 k *(k - 1) 2 k *(k - 1) + 2 k *(k - 1) + 2 k+1 （的得分被组合的两个数字加上比分为新号码）。 这等于：
2 k + 1 *(k - 1) + 2 k+1 = 2 k+1 * (k - 1 + 1) = 2 k+1 * k 。 这完成了归纳。 为了计算得分，如果只有两个出现，我们需要遍历棋盘上的所有数字，并使用上面的公式积累我们得到的分数。
如何计算形成场上数字所需的二进制数？
更容易注意到形成2 n所需要的二进制n是2 n - 1 。 严格的证明可以再次使用归纳法完成，但我会将其留给读者。
代码
我将提供用c++解决问题的c++ 。 但是，我不使用任何语言特定的东西（appart来自vector ，它只是一个动态扩展的数组），所以它应该很容易移植到许多其他语言。
/**
* @param a - a vector containing the values currently in the field.
* A value of zero means "empty cell".
* @param score - the score the player currently has.
* @return a pair where the first number is the number of twos that appeared
* and the second number is the number of fours that appeared.
*/
pair<int,int> solve(const vector<vector<int> >& a, int score) {
vector<int> counts(20, 0);
for (int i = 0; i < (int)a.size(); ++i) {
for (int j = 0; j < (int)a[0].size(); ++j) {
if (a[i][j] == 0) {
continue;
}
int num;
for (int l = 1; l < 20; ++l) {
if (a[i][j] == 1 << l) {
num = l;
break;
}
}
counts[num]++;
}
}
// What the score would be if only twos appeared every time
int twos_score = 0;
for (int i = 1; i < 20; ++i) {
twos_score += counts[i] * (1 << i) * (i - 1);
}
// For each 4 that appears instead of a two the overall score decreases by 4
int fours = (twos_score - score) / 4;
// How many twos are needed for all the numbers on the field(ignoring score)
int twos = 0;
for (int i = 1; i < 20; ++i) {
twos += counts[i] * (1 << (i - 1));
}
// Each four replaces two 2-s
twos -= fours * 2;
return make_pair(twos, fours);
}
现在回答我们已经做了多少动作，我们应该添加由这个函数返回的对的两个值，并减去两个值，因为两个具有2的tile直接出现。
链接地址: http://www.djcxy.com/p/80497.html上一篇: 2048 game: how many moves did I do?
下一篇: What are the mathematical/computational principles behind this game?