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

ハマってしまいました。
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