2048の得点計算方法と理論上の最高得点

  • 13
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

ハマってしまいました。
http://gabrielecirulli.github.io/2048/

得点計算方法

  • 2048では、値 2^(n-1) のタイルを2つくっつけると値 2^n のタイルになり、得点 2^n が加算される。
  • 2 のタイルだけで 2^n のタイルを作るまでの得点を a[n] とする
  • 4 を作るには 2 を 2 つくっつければ良く、その時の得点は 4
    • a[2] = 4
  • 2^n を作るには、2^(n-1) を 2つ作り、最後にその2つをくっつける(途中経過がどうあれ、こうなる)。2^(n-1) を作るのに a[n-1] 点、2^n を作って 2^n 点だから、合計は 2a[n-1] + 2^n
    • a[n] = 2a[n-1] + 2^n
  • 両辺 2^n で割り、b[n] = a[n]/2^n とすると、b[n] = b[n-1] + 1, b[2] = 1
  • これを解いて、b[n] = n - 1, a[n] = (n-1)2^n
  • 2048 = 2^11 だから、 2048 が出来るまで 2 のタイルしか出なかったとすると、a[11] = 20480 点得ることになる。
    • 2048 を作った時にだいたい 2 万点くらいなのはこのため。
  • 4 が出現した場合、はじめの「2 と 2 で 4 を作る」というフェーズが無くなるので、2 だけ出現する場合より 4 点少なくなる。
    • つるかめ算と同じ理屈で、「現在までに 4 が何回出たか」がこれによって計算できる

理論上の最高得点

  • 盤面が以下のようになった時が最高得点である
   4    8   16   32
 512  256  128   64
1024 2048 4096 8192
2^17 2^16 2^15 2^14
  • 4 が出現すると 4 点少なくなる
  • 4 を使わないと、上の盤面にならない
  • 従って、要所要所では 4 が出現しつつも、ほとんどの時点で 2 が出現するようなパターンが最高得点であるはずだ。
  • 盤面に存在している数字から、「全部 2 だった時の得点」が計算できる。4が出現した個数を数えることで、理論上の最高得点を計算する。

3 マスあれば 2 だけを使って 8 を作れる

次の手順に従って、3 マスあれば 2 だけで 8を作ることが可能:

[2][ ][ ]
→
[2][ ][2]
→
[2][ ][4]
→
[2][2][4]
→
[2][4][4]
→
[2][ ][8]

n マスあれば、2 だけを使って 2^n を作れる

  • n-1 マスあれば 2^(n-1) を作れる、と仮定する。
  • n マス空いている時、まず n-1 マス 使って 2^(n-1) を作る。
  • すると、n マスのうち 1 マスが 2^(n-1) によって専有されているものの、残りの n-1 マスを使ってもう1つ 2^(n-1) が作れる。
  • 2^(n-1) が 2 つ作れたので、最後にこれを合わせて 2^n を得る。
  • 前項と合わせて、数学的帰納法により、n マスあれば 2^n を作れる。

盤面は 16 マスあるので、2^16 までは 2 を使って作ることが出来る。

2 マス残っているときに 8 を作るのに必要な 4 の数

以下の手順で、4 が 1 度だけ出現すれば、 2 マスで 8 を作ることが出来る

[2][ ]
[2][2]
[4][4] (ここで 4 出現)
[2][8]

3 マス残っている時に 16 を作るのに必要な 4 の数

想像がおっつかないのでもういっこだけ確認してみる。

[ 2][  ][  ]
(中略)
[ 2][  ][ 8] (3 マスあれば、2 だけを使って 8 を作る事ができる)
[ 2][ 2][ 8]
[ 4][ 4][ 8] (ここで 4 出現)
[ 2][ 8][ 8]
[ 2][ 2][16]

n-1 マス残っている時に 2^n を作るには 4 が 1 度だけ出現すれば良い

  • n-2 マス残っている時に 2^(n-1) を作るには 4 が 1 度だけ必要と仮定する。
  • n-1 マス残っていれば、 2 だけを使って 2^(n-1) を作ることが可能
  • 2^(n-1) が 1 マス専有しているため、残りは n-2 マスある
  • 仮定より、4 が 1 度だけ出現すれば 2^(n-1) を作れる
  • 2^(n-1) が 2 つ作れたので、これをもって 2^n を得る。4 は 1度だけしか出現していない。
  • 数学的帰納法により、命題は正しい。

4 は最低 何度出現するか?

   4    8   16   32
 512  256  128   64
1024 2048 4096 8192
2^17 2^16 2^15 2^14
  • 上図において、16 マスを使って 2^17 を作るために 4 が 1 度だけ出現する(1 回目)
  • 残った 15 マスを使って 2^16 を作るために 4 が 1 度だけ出現する(2 回目)
  • (中略)
  • 残った 2 マスを使って 8 を作るために 4 が 1 度だけ出現する(15 回目)
  • 最後の 1 マスは、どうせ動かせないので、実は 2 でも 4 でも構わない。なんなら 3 でも構わない。

以上により

  • 2^17 を 2 だけで作ると a[17] 点得る。
  • 2^16 を 2 だけで作ると a[16] 点得る。
  • (中略)
  • 8 を 2 だけで作ると a[3] 点得る。
  • 最後のマスは加算されない。
  • 最後に、実際には 4 が 15回出現しているので、4 点 × 15 回分は嘘であるから引かなければならない。
  • 以上により、理論上の最高得点は 3932100 点である。
  a[ 3] =      16
  a[ 4] =      48
  a[ 5] =     128
  a[ 6] =     320
  a[ 7] =     768
  a[ 8] =    1792
  a[ 9] =    4096
  a[10] =    9216
  a[11] =   20480
  a[12] =   45056
  a[13] =   98304
  a[14] =  212992
  a[15] =  458752
  a[16] =  983040
  a[17] = 2097152
+             -60
------------------
          3932100

スクリーンショット 2014-07-04 2.13.14.png