コグノスケ

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購入

目次: Android

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に入れ替えたいくらいですけど…。