コグノスケ

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日の日記参照）にコメントいただいた、りょうさんとの結果とも一致して、ホッとしています。

植物とは何か

2005年の話ですが、読んでみて面白かった記事のご紹介です。
ハテナという生物：植物になるということ - （社）日本植物学会 研究トピック 1

素人が持つ植物に対する概念をブチ壊す、生物の奥深さを感じることができます。文章は多めですが、素人にもわかりやすいです。

2種類の植物

現在の分類上では植物は、陸上植物、紅色植物、灰色植物など、シアノバクテリアとの共生により葉緑体を獲得した生物群を指すそうです。一次植物、アーケプラスチダと呼ばれています。

シアノバクテリアとの共生ではなく、一次植物との共生（二次共生）により葉緑体を獲得した生物群がいます。二次植物と呼ばれています。例えば、クロララクニオン藻はアメーバの仲間で、見た目もアメーバっぽいのですが、緑藻（一次植物）との共生により植物化したと考えられています。

植物への変化

二次共生と一言で言っても、色々な段階があります（ちゃんとした解説は、図 6 二次共生による葉緑体獲得のステージ、を見てください）。

• （相手は別の生物）利用して最後に壊すか、捨てる
• （相手の核、ミトコンドリア残存）支配下に置く
• （相手の核残存、ミトコンドリア消失）融合を始める
• （相手の核、ミトコンドリア消失）完全に融合する

二次共生する植物の中でも、タイトルの「ハテナ」は 1番目と 2番目の間に位置する生物として注目されているようです（そう直接は書いていませんが、雰囲気から察するに）。

せっかく持って生まれた捕食機能を捨ててでも、変化を続ける様子は、生物の原動力「生き残るためなら何でもやってやる」の真骨頂って感じがして面白いですね。

Chromecast

Google Chromecast を買いました。PC やスマホで見つけた面白いページ、面白い動画を家族に見せるのに便利です。わざわざテレビでもう一度検索する必要はありません。

テレビのネットワーク機能で使っていたのは DLNA と YouTube くらいですが、YouTube はテレビからの検索結果と PC からの検索結果が違っていたりして、非常に使いづらいです。文字も打ちづらいし、もうテレビの YouTube を起動することはないでしょう。

Miracast もできれば DLNA すら不要になって便利でしたが、残念ながら私の持っているスマホでは Chromecast への Miracast はできないようです。うーん、残念。

テレビはモニタへ？

このままだと、テレビを含む AV 機器の諸機能はスマホに吸い取られ、テレビはこのまま HDMI モニタと化すでしょう。そうなればアジア勢中心の安売り競争へ突入は避けられません。そこに日系メーカーの居場所はあるでしょうか…？

困った Windows 8

サブ PC へのリモートデスクトップ接続が切れた？と思ったら、「このコンピューターへの接続数は制限されていて、すべての接続は現在使用されています。後で接続するか、またはシステム管理者に問い合わせてください。」とのこと。

また出たな…このメッセージ、と思って日記を見直すと、前に見たのは半年以上前（2013年 10月 18日の日記参照）のようです。しかしサブ PC の使用頻度は 1か月に数回なので、Windows 8 だと割と頻繁に起きる現象なのかもしれません…？

この問題、何が困るって電源を強制 OFF する以外の復旧方法が無いことです。我が家のデスクトップ PC は未だ Windows 7 ですが、リモートデスクトップ経由のアクセスが多いため、Windows 8 にアップグレードする気が起きません。

これが何度も起きるような問題なら、サブ PC も Windows 7 に入れ替えたいくらいですけど…。