コグノスケ


link 未来から過去へ表示(*)  link 過去から未来へ表示

link もっと前
2014年6月13日 >>> 2014年5月31日
link もっと後

2014年6月13日

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

編集者:すずき(2014/06/14 01:35)

コメント一覧

  • 2048playerさん(2024/09/08 16:10)
    私も2048の最高スコアを求めたのですが、このようなページがあまりなく真偽に困っていました。
    (実は自作式が正しいかの真偽のこと。)
    ここで「3932100」という同じ結果があり安心しました。
    私は自作式(1番下に書きました)を使って求めました。
    「仮定(4x4マスのフィールドを16マスの一直線と見なしても、最高得点は変わらない)が本当に正しいのか?」についてですが、
    次のようにすると 1 から 16 までの数字が順に
    一筆書きできるので、フィールドの形状が異なっていても問題ありません。(つまり正しい。)
    もう少し補足すると一直線の番号と4×4マスの番号の一致しているところは同じ数字があると考えると良いです。
    (分かりにくかったらすみません)
    -
    16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 (一直線)
    -
    16 15 14 13
    9 10 11 12
    8 7 6 5
    1 2 3 4 (4×4マス)
    -
    おまけですが、
    3932100(理論値の最高スコア)を出すためには
    2が1966020個
    4が15個 必要です。
    もし現実で3932100のスコアを出すとなると
    2の出る確率が90%
    4の出る確率が10% なので
    (単純計算で)3^3932040/10^1966035で
    約7.217850816 × 10^(-89976)です。
    -----自作式-----
    Msを最高スコア ( 今回は3932100 となる) sをマスの数 ( 今回は16 を代入) Mmをランダムに出る最高数字 ( 今回は4 を代入) mmをランダムに出る最低数字 ( 今回は2 を代入) とすると
    -log2(Mm/mm)+s*mm*{log2(Mm/mm)+s}-2*mm[{log2(Mm/mm)+s}-1]-Σn=0,log2(Mm/mm)-1,(Mm/2^n*Σk=1,n+1,s+nCk)\n-\nです。\n※ nCr (s+nCk)は n! / { (n-r)! * r! } のことです。\nΣn=a,b,f(n) は f(a)+f(a+1)+…+f(b-1)+f(b)のことです。(今回の式はシグマの中にシグマが入っていますが…)\n-\n最後に、この自作式は5日かけて作ったことを書いておきます。
  • 2048さん(2024/09/08 17:16)
    私も2048の最高スコアを求めたのですが、このようなページがあまりなく真偽に困っていました。
    ここで「3932100」という同じ結果があり安心しました。
    私は自作式(次のコメントに書きます)を使って求めました。
    「仮定(4x4マスのフィールドを16マスの一直線と見なしても、最高得点は変わらない)が本当に正しいのか?」についてですが、
    次のようにすると 1 から 16 までの数字が順に
    一筆書きできるので、フィールドの形状が異なっていても問題ありません。(つまり正しい。)
    もう少し補足すると一直線の番号と4×4マスの番号の一致しているところは同じ数字があると考えると良いです。
    (分かりにくかったらすみません)
    -
    16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 (一直線)
    -
    16 15 14 13
    9 10 11 12
    8 7 6 5
    1 2 3 4 (4×4マス)
    -
    おまけですが、
    3932100(理論値の最高スコア)を出すためには
    2が1966020個
    4が15個 必要です。
    もし現実で3932100のスコアを出すとなると
    2の出る確率が90%
    4の出る確率が10% なので
    (単純計算で)3^3932040/10^1966035で
    約7.217850816 × 10^(-89976)です。
  • 2048playerさん(2024/09/08 17:30)
    私も2048の最高スコアを求めたのですが、正しいかどうか困っていました。
    このサイトで「3932100」という同じ結果があり安心しました。
    私は自作式(次のコメントに書きます)を使って求めました。
    「仮定(4x4マスのフィールドを16マスの一直線と見なしても、最高得点は変わらない)が本当に正しいのか?」についてですが、
    次のようにすると 1 から 16 までの数字が順に
    一筆書きできるので、フィールドの形状が異なっていても問題ありません。
    もう少し補足すると一直線の番号と4×4マスの番号の一致しているところは同じ数字があると考えると良いです。
    (分かりにくかったらすみません)
    -
    16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 (一直線)
    -
    16 15 14 13
    9 10 11 12
    8 7 6 5
    1 2 3 4 (4×4マス)
    -
    おまけですが、
    3932100(理論値の最高スコア)を出すためには
    2が1966020個
    4が15個 必要です。
    もし現実で3932100のスコアを出すとなると
    2の出る確率が90%
    4の出る確率が10% なので
    (単純計算で)約7.217850816 × 10^(-89976)です。
  • すずきさん(2024/09/12 21:19)
    コメントありがとうございます。同じ結果になり良かったです。
    4x4が一筆書きで書けることは理解しているのですが、1次元のときには存在しない「上向き」の合成が発生して、合成されずに数字が残ります。それでも1次元と同じである、と言いきれませんでした。
  • 2048playerさん(2024/09/16 01:00)
    返信ありがとうございます。
    コメントが反映されてないと思ってしまい、何回も同じようなコメントを送ってしまいすみませんでした。
    自作式については簡略化中なので、次のコメントで記載します。
  • 2048playerさん(2024/09/26 01:00)
    今のところ最も簡略化した式です。
    -----自作式-----
    sをマスの数 ( 今回は16 を代入) Mをランダムに出る最高数字 ( 今回は4 を代入) mをランダムに出る最低数字 ( 今回は2 を代入) とすると式は
    (最高スコア)=m*[2^x*{2^s*(s+x-2)+4-3x-[Σk=0,x-1,{Σl=0,k,(s-1+lC1+l)/2^l}]}-2] x=log2(M/m) です。(lエルと1いちが見にくくてすみません)\n※ Σn=a,b,f(n) は f(a)+f(a+1)+…+f(b-1)+f(b)のことです。(式には2重シグマが入っていますが…) この式でM=m(つまりmだけ)になるときx=log2(1)=0となり (最高スコア)=m*{2^s*(s-2)+2} と変形できる(シグマがなくなる)のでM=m=2,s=16を代入すると(最高スコア)=1835012となり、M=m=4,s=16を代入すると(最高スコア)=3670024となります。この結果は2014年5月11日の記事の結果と同じになります。
  • 2048player(コメント追加)さん(2024/09/26 01:04)
    最後に、この式を出すのに紙4枚(A4)も使ったのでもっと簡単に出したかったと思ってます。
open/close この記事にコメントする



link もっと前
2014年6月13日 >>> 2014年5月31日
link もっと後

管理用メニュー

link 記事を新規作成

<2014>
<<<06>>>
1234567
891011121314
15161718192021
22232425262728
2930-----

最近のコメント5件

  • link 24年10月1日
    すずきさん (10/06 03:41)
    「xrdpで十分動作しているので、Wayl...」
  • link 24年10月1日
    hdkさん (10/03 19:05)
    「GNOMEをお使いでしたら今はWayla...」
  • link 24年10月1日
    すずきさん (10/03 10:12)
    「私は逆にVNCサーバーに繋ぐ使い方をした...」
  • link 24年10月1日
    hdkさん (10/03 08:30)
    「おー、面白いですね。xrdpはすでに立ち...」
  • link 14年6月13日
    2048player...さん (09/26 01:04)
    「最後に、この式を出すのに紙4枚(A4)も...」

最近の記事3件

  • link 24年10月3日
    すずき (10/06 01:33)
    「[Ubuntu 20.04 LTSでxrdpのエラーを再現できるか挑戦] 目次: Linux先日(2024年10月1日の日記参...」
  • link 23年4月10日
    すずき (10/05 15:09)
    「[Linux - まとめリンク] 目次: Linux関係の深いまとめリンク。目次: RISC-V目次: ROCK64/ROCK...」
  • link 24年10月2日
    すずき (10/05 15:08)
    「[VirtualBoxでxrdpのエラーを再現できるか挑戦] 目次: Linux昨日(2024年10月1日の日記参照)のUbu...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 10/06 03:41