コグノスケ

2048の最高得点（その2）

先日の続き（2014年5月11日の日記参照）で、2048の最高得点を考えてみます。

前回に引き続き、
仮定: 新しい数字が常に理想的に出現した場合、4x4のフィールドは、横1列の16マスと同等とみなせる、とします。

前回は2だけが出る場合と4だけが出る場合を求めましたが、今回は2と4が適切に出てくる場合を考えます。

1. 「適切」の条件とは？
2. 2048の前半と後半
3. 前半戦
4. ハーフタイム
5. 後半戦

の順に考えたいと思います。

「適切」の条件とは？

求めたい物は最高得点ですので、最も点数が高くなる2と4の出現の仕方を考えます。

2048のルール上、新しく出現する数字には点数が入りません。そのため2と2で4が作れる場面で4が出現しても、点数を損するだけです。

従って4が出なければ手詰まりになってしまう状況以外では、常に2が出現することが「適切」と考えられます。

2048の前半と後半

サッカーに習って（？）2048を前半と、ハーフタイムと、後半に分けて考えます。どのように分けるかというと、

• 前半: 2だけが出続け、手詰まり一歩手前まで
• ハーフ: 4が初めて出現し、最大の数値ができるまで
• 後半: 最大の数値ができてから、手詰まりまで

これだけでは何が何だかわかりませんので、順にご説明します。

前半: 2だけが出続け、手詰まり一歩手前まで

「適切」の考え方に基づけば、なるべく2が多く出る状態が最高得点ですから、まず4は出ず、2のみ出る状態で進められるところまで進める、これをもって前半とします。

前回を読んでいただいた方はお気づきかと思いますが、実はこの条件は前回の「2のみが出続ける場合」そのものです。従って2のみが出続けた場合の手詰まり形の、一歩手前まで2のみで進められる、と考えられます。

例えばN = 5（5マス）で考えてみますと、ずっと2が出続けた場合の手詰まり形は2, 4, 8, 16, 32ですので、手詰まり形の一歩手前は0, 4, 8, 16, 32となります（0は空きマスを意味します）。Nマスの場合に一般化すると0, 4, 8, 16, ..., 2^(N-1), 2^Nです。

これ以上2は出せません（出すとゲームが終わってしまいます）ので、4を出さざるを得ません。2以外を出したので前半は終了とします。

ちなみに前半の得点も前回考えた式と同様に、和Tnは、
N
Σ(Ak * Sk) - A1 * S1
k=1

Ak = 2^(N + 1) - 2^k
A1 * S1 = 2^(N + 1) - 2
です。

ハーフタイム: 4が初めて出現し、最大の数値ができるまで

初めて4が出ましたが、実は4の出番は1度ポッキリです。ハーフタイム開始時点、すなわち初めて4が出現したときの形は、4, 4, 8, 16, ..., 2^(N-1), 2^Nです。

わかりやすくするために、4が出た後は数字が出なくなる（※）と考えて、4の出現によりもたらされる得点について計算しましょう。

例えばN = 5を考えると、開始時点は4, 4, 8, 16, 32です。これをどんどん合成していくと、

 4,  4,  8, 16, 32
 0，8,  8, 16, 32 → + 8点
 0,  0, 16, 16, 32 → +16点
 0,  0,  0, 32, 32 → +32点
 0,  0,  0,  0, 64 → +64点

合計 +120点

となります。一般化すると0, 0, 0, ..., 0, 2^(N+1) まで到達し、4の出現により、ハーフタイム中に得られる得点は8, 16, ..., 2^N, 2^(N+1) の和となります。

これは、初項8、等比2、項a1からaN-1の等比級数ですので、和Unは、
Un = 2^(N+2) - 8
です。

（※）数字が出なくなるなんて考えて良いのか？途中で手詰まりしないのか？という疑問について。こう考えて問題ありません。なぜなら、ハーフタイム中は毎回の移動で、必ず1枚ずつ数字が減るためです。この間にどれだけ2が出現し、最悪どの2も合成できず全て蓄積したとしても、2^(N+1) が出来るまでは絶対に手詰まりになりません。

後半: 最大の数値ができてから、手詰まりまで

ハーフタイムの終了で最大の数値ができたときの形、つまり後半の開始地点の形はt, u, v, ..., y, z, 2^(N+1) という形になります。

ハーフタイムの間も、なるべく4は出ずに2を出すことが最高得点へと繋がることに代わりはありません。例えばN = 5であれば、最大の数値2^N = 64の合成までに4手掛かりますので、2が4枚出てきて2, 0, 2, 4, 64が後半の開始形となります。

一見ややこしそうに見えますが、ご安心下さい。ハーフタイム中に新たに出現した2は、ハーフタイムの開始時に存在していたパネル（4, 4, 8, 16, ..., 2^(N-1), 2^Nと合成されることはありませんので、ハーフタイムの開始時に出現した4がもたらす得点と、その後出現した2がもたらす点数を分けて考えても、最高得点の計算に支障はありません。

従って後半の得点は、0, 0, 0, ..., 0, 0, 2^(N+1) の盤面で得られる点数と同一と考えられます。

一番右のマスと合成できる数値は4のみを出し続けても絶対に作れませんから、使われない死んだマスです。従って後半は1つ盤の大きさが小さくなった状態で、最初からゲームを開始することと同等、と見なせます。

つまり後半に得られる得点はN' = N-1の盤面で得られる点数に等しいです。入れ子みたいなもんですね。

合計点

以上のように、後半戦は1つマスを縮めてもう一度最初からゲームを行うこと、という理解でもう一度2048の最高得点を整理すると、

Nマスの合計点は、
Nマスの前半戦「2のみ出現」ゲームと、Nマスのハーフタイム「2^(N+1) 合成」ゲームと、
N-1マスの前半戦「2のみ出現」ゲームと、N-1マスのハーフタイム「2^((N-1)+1) 合成」ゲームと、
N-2マスの前半戦…
の合計点、となります。

まず、N, N-1, N-2, ..., 3, 2の全ての前半戦の合計点を考えましょう。先ほど導いたTnを足しても構いませんし、個人的には、手詰まり一歩手前までに合成される数を並べて足すと考えやすいと思います。

例としてN = 6までを並べると、下記のようになります。

式で表すと、

16  N-1
Σ  Σ{(2^(k+1)) * (2^(N-k)-1)}
N=2 k=1

です。

      | k
      |   1    2    3    4    5
      | 各数値の合成枚数
      |   4    8   16   32   64  ← 2^(k+1)
------+--------------------------
N   2 |   1
    3 |   3,   1
    4 |   7,   3,   1
    5 |  15,   7,   3,   1
    6 |  31,  15,   7,   3,   1  ← 2^(N-k)-1
------+--------------------------
枚数計|  57,  26,  11,   4,   1
点数計| 228, 208, 176, 128,  64  ← Σ{2^(k+1) * (2^(N-k)-1)}
------+--------------------------
  総計| 804

ちなみにN = 16の場合は、3,407,948点となります。

ハーフタイムですが、Unを足していっても良いですし、N = 2のときは8、N = 3のときは8, 16の和、N = 4のときは8, 16, 32の和、のように順番に増えていく形になるので、個人的には、こちらも各数値の枚数を書くとイメージしやすいかと思います。

合計を式で書くと、

N-1
Σ(2^(k+2) * (N - k))
k=1

です。表にすると、

      | k
      |   1    2    3    4    5
      | 各数値の合成枚数
      |   8   16   32   64  128  ← 2^(k + 2)
------+-------------------------
N   2 |   1
    3 |   1,   1
    4 |   1,   1,   1
    5 |   1,   1,   1,   1
    6 |   1,   1,   1,   1,   1
------+-------------------------
枚数計|   5,   4,   3,   2,   1  ← N - k
点数計|  40,  64,  96, 128, 128  ← 2^(k+2) * (N - k)
------+-------------------------
  総計| 456

となりますので、N = 16の場合は8 * 15 + 16 * 14 + ... + 131072 * 1 = 524,152点です。

以上から、N = 16のときの最高得点は3,407,948 + 524,152 = 3,932,100点となることがわかりました。

残る課題

最初に置いた仮定（4x4マスのフィールドを16マスの一直線と見なしても、最高得点は変わらない）が本当に正しいのか？は証明できていません。

仮定についても説明できれば良かったのですが、私自身、解決のアイデアが特になく、説明できません。困った。

感想

理想的に2と4が出現すれば131072までパネルが作れることはすぐわかりますが、最高得点となると意外と計算が面倒だったように思います。

また、先日の記事（2014年5月11日の日記参照）にコメントいただいた、りょうさんとの結果とも一致して、ホッとしています。