2048游戏:我做了多少动作？

Question

不久之前,2048曾经很受欢迎.每个人都玩了它,很多人发布了很好的截图和他们的成就(我自己).然后在某些时候我开始怀疑是否有可能告诉别人玩多久才能达到那个分数.我进行了基准测试,结果证明(至少在我的Android应用程序上),一秒钟内只能进行一次移动.因此,如果你玩得足够长(并且足够快)你所做的动作数量非常接近于你玩过的秒数.现在的问题是:是否可以使用2048游戏的屏幕截图来计算制作了多少动作.

这是一个示例屏幕截图(实际上我迄今为止对游戏的最大努力):

从屏幕截图中,您可以看到当前时刻的场地布局以及玩家获得的积分数.那么:这些信息是否足以计算我所做的动作数量,如果是这样,算法是做什么的呢？

注意:我想提醒您,只有当两个图块"合并"并且得分的点数是新图块的值(即要合并的图块的值的总和)时,才会对点进行评分.

Answer 1

简短的回答是可以仅使用该信息计算移动的数量.我会解释算法来做到这一点,我会尝试在步骤中发布我的答案.每个步骤都将是一个旨在帮助您解决问题的观察.我鼓励读者在每次提示后单独尝试解决问题.

1. 观察一:每次移动后,只出现一个瓷砖.这个图块是4或2.因此我们需要做的是计算出现的图块数量.至少在我玩游戏的版本上,游戏总是以2个瓦片开始,其中2个随机放置.

2. 我们不关心该领域的实际布局.我们只关心它上面的数字.当我解释算法时,这将变得更加明显.

3. 看到场上单元格中的值,我们可以计算出每次移动后出现2的分数.称之为价值twos_score.

4. 已经出现的四个等于等于twos_score和actual_score除以4 的四分之一.这是正确的,因为从两个2-s形成4我们将获得4得分,而如果4个直接出现我们得分0.拨打四个号码fours.

5. 我们可以计算出在场上形成所有数字所需的两个数量.之后我们需要2 * fours从这个值中减去,因为单个4替换了两个2的需要.叫这个twos.

使用这些观察我们能够解决问题.现在我将更详细地解释如何执行单独的步骤.

如果只有两个出现,如何计算分数？

我将证明,为了形成数字2 ⁿ,玩家将得分(使用归纳法).2n*(n - 1)

• 这些陈述对于2来说很明显,因为它直接出现,因此没有得分.
• 假设对于数字2 ^k的固定k,用户将得分2k*(k - 1)
• 对于k + 1:2 ^{k + 1}只能通过组合两个数值2 ^k来形成.因此,用户将得分(组合的两个数字的得分加上新数字的得分). 这相当于:.这完成了归纳.2k*(k - 1) + 2k*(k - 1) + 2k+1
2k + 1*(k - 1) + 2k+1= 2k+1 * (k - 1 + 1) = 2k+1 * k

因此,如果只有两个人出现,我们需要对棋盘上的所有数字进行迭代,并使用上面的公式累积我们得到的分数.

如何计算在场上形成数字所需的两个数量？

这是很容易注意到,形成所需三三两两的数量2n为2n - 1.可以使用归纳法再次进行严格的证明,但我会将其留给读者.

代码

我将提供解决问题的代码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直接出现.