2048 game: how many moves did I do?

2048 used to be quite popular just a little while ago. Everybody played it and a lot of people posted nice screenshots with their accomplishments(myself among them). Then at some point I began to wonder if it possible to tell how long did someone play to get to that score. I benchmarked and it turns out that(at least on the android application I have) no more than one move can be made in one second. Thus if you play long enough(and fast enough) the number of moves you've made is quite good approximation to the number of seconds you've played. Now the question is: is it possible having a screenshot of 2048 game to compute how many moves were made.

Here is an example screenshot(actually my best effort on the game so far):

From the screenshot you can see the field layout at the current moment and the number of points that the player has earned. So: is this information enough to compute how many moves I've made and if so, what is the algorithm to do that?

NOTE: I would like to remind you that points are only scored when two tiles "combine" and the number of points scored is the value of the new tile(ie the sum of the values of the tiles being combined).

---

The short answer is it is possible to compute the number of moves using only this information. I will explain the algorithm to do that and I will try to post my answer in steps. Each step will be an observation targeted at helping you solve the problem. I encourage the reader to try and solve the problem alone after each tip.

Observation number one: after each move exactly one tile appears. This tile is either 4 or 2. Thus what we need to do is to count the number of tiles that appeared. At least on the version of the game I played the game always started with 2 tiles with 2 on them placed at random.

We don't care about the actual layout of the field. We only care about the numbers that are present on it. This will become more obvious when I explain my algorithm.

Seeing the values in the cells on the field we can compute what the score would be if 2 had appeared after each move. Call that value twos_score .

The number of fours that have appeared is equal to the difference of twos_score and actual_score divided by 4. This is true because for forming a 4 from two 2-s we would have scored 4 points, while if the 4 appears straight away we score 0 . Call the number of fours fours .

We can compute the number of twos we needed to form all the numbers on the field. After that we need to subtract 2 * fours from this value as a single 4 replaces the need of two 2s. Call this twos .

Using this observations we are able to solve the problem. Now I will explain in more details how to perform the separate steps.

How to compute the score if only two appeared?

I will prove that to form the number 2n, the player would score 2 n *(n - 1) points(using induction).

The statements is obvious for 2 as it directly appears and therefor no points are scored for it.

Let's assume that for a fixed k for the number 2k the user will score 2 k *(k - 1)

For k + 1: 2k + 1 can only be formed by combining two numbers of value 2k. Thus the user will score 2 k *(k - 1) + 2 k *(k - 1) + 2 k+1 (the score for the two numbers being combined plus the score for the new number).
This equals: 2 k + 1 *(k - 1) + 2 k+1 = 2 k+1 * (k - 1 + 1) = 2 k+1 * k . This completes the induction.

Therefor to compute the score if only twos appeared we need to iterate over all numbers on the board and accumulate the score we get for them using the formula above.

How to compute the number of twos needed to form the numbers on the field?

It is much easier to notice that the number of twos needed to form 2 n is 2 n - 1 . A strict proof can again be done using induction, but I will leave this to the reader.

The code

I will provide code for solving the problem in c++ . However I do not use anything too language specific(appart from vector which is simply a dynamically expanding array) so it should be very easy to port to many other languages.

/**
 * @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);
}

Now to answer how many moves we've made we should add the two values of the pair returned by this function and subtract two because two tiles with 2 appear straight away.

链接地址: http://www.djcxy.com/p/80498.html

上一篇: 什么是尾巴呼叫优化？

下一篇: 2048比赛：我做了多少次动作？