コグノスケ


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

link もっと前
2014年5月11日 >>> 2014年4月28日
link もっと後

2014年5月11日

2048の最高得点(その1)

2048の最高得点について考えてみます。

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

この仮定が正しいかどうかがイマイチ分かりませんが…考えるのは後回しにします。この仮定が正しいとして、

  • 必ず左端に新しい数字が出現
  • 常に右に移動

という動きを考えます。

2だけ出てくる場合

新しい数字としては2か4が出ますが、まずは単純にするため2が出続けた場合を考えます。2が出続けた場合の手詰まりの形は、
2, 4, 8, 16, ..., 65536
つまり、
2, 4, ..., 2^(N-1), 2^N
です。

手詰まりになるまで4がいくつ必要か(=4が何回生成されるか、と同意)を考えますと、


マス数: 手詰まり形: 各マスの数字を作るのに必要な4の数
2マス: 2, 4        → 0, 1
3マス: 2, 4, 8     → 0, 1, 2
4マス: 2, 4, 8, 16 → 0, 1, 2, 4
となります。

Nマスにおいて、手詰まりまでに生成された4の数S(N, 4) は、初項1、公比2、項数N-1の等比数列の和と等しいですから、
S(N, 4) = 2^(N-1) - 1
よって得られる点数は、
4 * S(N, 4)
です。

次に8が何回生成されるか?を考えますと、


マス数: 手詰まり形: 各マスの数字を作るのに必要な8の数
4マス: 2, 4, 8, 16 → 0, 0, 1, 2
となります。

生成される新しい数字が倍になり(つまり4が出てくると考える)、マスは1つ減った、と考えるとわかりやすいですかね?
S(N, 8) = S(N - 1, 4)
なので得られる点数は、
8 * S(N - 1, 4)
です。

さらに一般化するとNマスで手詰まりしたとき、それぞれのマスに存在する数は、
2, 4, 8, 16, ..., 2^N
となります。

一般項をAnとおくと、
An = 2^n (ただしn = 1, 2, ..., N)
です。

各数値が何回生成されるかを4を基準に考えると、
S(N + 1, 4), S(N, 4), S(N - 1, 4), ..., S(2, 4)
と表せます。

一般項をSnとおくと、
Sn = S(N + 2 - n, 4) = 2 ^ (N + 2 - n - 1) - 1 = 2 ^ (N - n + 1) - 1
(ただしn = 1, 2, ..., N)
と表せます。

各数値を生成する際に得られる点数は、AnとSnの積を合計した値になります。
0 * S(N + 1, 4), 4 * S(N, 4), 8 * S(N - 1, 8), ..., 2^N * S(2, 4)
しかし2048のルールでは2の生成時に点数は入りませんので、初項A1 * S1を除く必要があります。

記号を使って少しかっこよく書けば、
N
Σ(Ak * Sk) - A1 * S1
k=1
となり、このとき、
Ak * Sk = 2^k * (2^(N - k + 1) - 1) = 2^(N + 1) - 2^k
A1 * S1 = 2^(N + 1) - 2
です、かね。たぶん。

先ほどの最高得点の式、試しにN = 16で計算してみると1835012点、つまり183万点です。経験上2048を1つ作った時点で2万点程度ですので、どれだけ理不尽な数かがわかると思います…。

4だけ出てくる場合

前節では183万点と計算しましたが、新規に生成される数値が4だけだった場合は、手詰まりの形は2だけの時の65536のさらに倍の数字131072まで生成可能です。

つまりNマスで手詰まりしたとき、それぞれのマスに存在する数は、
4, 8, 16, 32, ..., 2^(N + 1)
となります。

一般項をAnとおくと、
An = 2^(n + 1) (ただしn = 1, 2, ..., N)
です。

前節で求めた点数の総和の式に当てはめてN = 16を計算すると3670024点となります。うーん367万点ねー…普通にやっていたらまず無理ですね。

しかし2048では2だけでも4だけでもなく、両方とも新規生成されます。これは4だけが新規生成される場合と比較して、空いているマスさえあれば4を生成することができるため、最高得点はさらに上がある、ということです。

また今度にでも考えます…。

編集者:すずき(2014/05/11 03:24)

コメント一覧

  • りょうさん(2014/06/07 05:42)
    はじめまして.
    私も同じ仮定で考えていたのですが,最高点は3932100点になるとの結果が得られたので,ご報告致します.
  • すずきさん(2014/06/07 20:21)
    >りょうさん
    ご報告ありがとうございます。
    393万点は 2 と 4 が適切に出てくる場合の点数でしょうか?
    2 か 4 だけ出てくる場合を仮定されていれば、私と違う式を導かれたか、私が計算間違いしてますね…。
  • りょうさん(2014/06/08 01:19)
    393万点は,うまいこと 2 と 4 が出てくる場合の点数として求めたものです.
    どちらかのみで仮定して場合はここに書かれているものと同じ結果になりました.
  • すずきさん(2014/06/08 03:48)
    >りょうさん
    なるほど、ありがとうございます。良くポカミスするので、同じ結果が得られて安心しました。
    残るは盤面を 1次元にして良い、という仮定が正しいか?ですが…、残念ながら私はノーアイデアです…。
  • りょうさん(2014/06/08 15:11)
    私もちょくちょくやらかすので同じ結果になった人がいてよかったです.
    私は,
    (2 が出続けるときは) 2^n のタイルを作るには 2 つの 2^(n-1) のタイルが必要で,この 2 つのタイルを合わせるときに 2^n 点加算.
    この 2 つの 2^(n-1) のタイルを 4 つの 2^(n-2) のタイルから作るときに 2^n 点加算.

    これを繰り返して,1 つの 2^n のタイルを作るとき (n-1)・2^n 点加算される,というのをもとに,
    (最高得点)=Σ[n:1…16](上の式)
    から求めてみたんですよね.
    (最終的な式は同じになると思いますが,アプローチのしかたがここのサイトとは少し違った気がしたので一応書いておきます)

    4 のみのときや両方のときも,1 つのタイルによる点数の合計をもとに考えました.

    それで,件の,1 次元に落としていいか,ですが,
    私もノーアイデアですね...
    手詰まり形を考えれば,2 次元のときに 1 次元のときの点数を超えないのは示そうですが...
    下回らないことはどう示せばいいものか...
open/close この記事にコメントする



2014年5月6日

日記検索システム

現在、トップページの入力フォームから、日本語を指定して日記の検索を行うと文字化けする不具合が起きています。

原因は、日記サイトの文字コードをUTF-8に変更した際に、検索システム(Namazu)側の文字コードeuc-jpと食い違ってしまったことです。kakasiは2.3.5にてiconvに対応したらしくUTF-8の文書でも問題なく分かち書きできるようですが、どうもnamazu.cgiがUTF-8の入力に対応していないようです…。

困ったなー。修正できないかどうか、しばし探してみます。

編集者:すずき(2014/05/07 03:40)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年5月3日

無責任

ソ連型システム崩壊から何を汲み取るか──コルナイの理論からを読んで。

役所の税金無駄遣い、失敗だらけの第三セクター、銀行の公的資金注入、赤字企業の経営陣…、などを見る度に感じるイライラは何だろうと思っていたのですが、この記事が見事に説明してくれました。

上記いずれも、決断者はリスクを伴う決断をしますが、生じたリスクは他人に押し付けるという構造になっている、という指摘です。

要するに全員「偉そうに指示したくせに、しくじったらトンズラする無責任野郎」なのです。

見ていて腹が立つわそりゃ。非常にスッキリしました。

メモ: 技術系の話はFacebookから転記しておくことにした。

編集者:すずき(2015/11/29 19:44)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年5月2日

判断ミス

今の偉い人が現役だった1990年くらいから、現在2010年で見たら、ハード規模の増加率と、ソフト規模の増加率はどっちが上なんでしょう(組み込み系で)。

開発人員の割り振りを見る限り、日本の老舗メーカーはどうもハード規模の増加率が上だと判断し、海外のメーカーはその逆だと判断した、ように見えるのです。

どちらの判断が正解か私にはわかりませんが、今の日本メーカーの傾きっぷりを見るに、海外勢が正解だったように思えて仕方ありません。

ハード復権の時代は来るでしょうか…。

メモ: 技術系の話はFacebookから転記しておくことにした。

編集者:すずき(2015/11/29 19:42)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年5月1日

イテレータ

Javaを始めたときにコケたので思い出深いのですが、C++ とJavaってイテレータの概念が全然違いますね。

C++ のイテレータはコレクションの要素そのものを指しています。N個要素を持つ配列aのイテレータitであれば、a.begin() はa[0] を指し、itはa[0] からa[N - 1] の間まで有効な要素を指し続けます。a.end() は存在しないa[N] を指します。

C++ のイテレータ

begin()                                        end()
|                                              |
a[0]   a[1]   a[2]   ... a[N - 2]   a[N - 1]   a[N]
|      コレクションの有効範囲       |

C++ 方式の利点は、イテレータが何を指すのか直感的に理解しやすく、イテレータ経由での要素の書き換えや削除のイメージが沸きやすいことです。

欠点はbegin() は参照して良いのに、end() は参照してはいけない、という非対称な仕様になってしまうことです。例えば、逆転イテレータ(reverse_iterator)を実装するとbegin() をend(), ++ を -- として扱うだけでは作れずに、悲しい思いをします。

Javaのイテレータは要素と要素の「間」を指しています。Javaにbegin(), end() はありませんが、対比のため無理やり書くと下記のようなイメージです。

Javaのイテレータ

 begin() = iterator()                           end() = hasNext() がfalse
 |                                              |
   a[0]   a[1]   a[2]   ... a[N - 2]   a[N - 1]
   |      コレクションの有効範囲       |

Java方式の利点はbeginとendが対称的になることです。もうbeginとendで悲しい思いをすることはありません。

欠点は書き換えや削除の対象がわかりづらいことです。特に双方向イテレータ(ListIterator)が顕著なので、もう少し詳しくご紹介しましょうか。

Javaコレクションの仕様ではイテレータが「最後に返した要素」が書き換え(set)や削除(remove)の対象、となります。ListIteratorは進む/戻るのどちらもできますから、イテレータの現在位置の「直前」あるいは「直後」どちらかの要素が対象となります。下記に図示します。

JavaのListIteratorのset()/remove() の対象

最後の操作がnext() だった場合
------------------------------
       set()/remove() の対象
       |    現在位置
       |    |
a[0]   a[1]   a[2]   ...


最後の操作がprevious() だった場合
----------------------------------
            現在位置
            | set()/remove() の対象
            | |
a[0]   a[1]   a[2]   ...

現在位置が全く同じでもset()/remove() の対象が変わる、この動きは正直ややこしいです。

利点の両立は難しいでしょうから、あとは皆さんの好みでしょうか。私は対称性を取ってJava方式に一票かなあ…。

編集者:すずき(2014/05/01 12:03)

コメント一覧

  • IKeJIさん(2014/05/02 13:04)
    常に内部イテレータを使うべき(極論)
  • すずきさん(2014/05/06 00:51)
    >IKeJIさん
    内部イテレータって foreach ですか?
    コレクションの要素が多すぎて単純な全列挙→フィルタで処理できないときや、イテレータを飛ばしたり戻したりするのが難しそうです。
  • IKeJIさん(2014/05/11 04:11)
    foreachに限らず、eachとかmapとかfoldとかそういうのも含めて考えてました。

    > コレクションの要素が多すぎて単純な全列挙→フィルタで処理できないときや、イテレータを飛ばしたり戻したりするのが難しそうです。

    どういう処理でしょう?何か例がありますか?

    俺みたいな低能力プログラマには外部イテレータは難しすぎる気がします。
    もし、for文を書かないといけない時は、椅子に座りなおして、コーラを取ってきてから、気合を入れてかきます。
  • すずきさん(2014/05/11 17:53)
    >IKeJI さん

    >どういう処理でしょう?何か例がありますか?

    特殊すぎる処理で申し訳ないですが、現に困ってるのは、
    「最初の 4バイトがタイプで、最初の 4バイトがサイズ、そのあとサイズ分だけのデータが続く」
    というバイナリを見るとき、もし A, B, C と並んでいれば頭から順に解析できますが、A, C, B と並んでいる場合は頭から順に解析することができない、という構造です。

    さらに C は数 GB あったりして、とにかく全部メモリに置くという作戦もとれません。

    今は外部イテレータにして、わからない部分は飛ばして、位置だけ「仮 C」として覚えておき、後で読む、としていますが、それを foreach や map や fold でどうやって書くのか思いつきませんでした。

    特に Scala の場合、map や fold を List に対してぶちかますと、List の全要素に対して述語の評価を行うので、List の要素が数 GB 以上になると map や fold が現実的な時間で帰ってきません。


    >俺みたいな低能力プログラマには外部イテレータは難しすぎる気がします。
    >もし、for文を書かないといけない時は、椅子に座りなおして、コーラを取ってきてから、気合を入れてかきます。

    たしかに for + 外部イテレータは面倒くさいです。
    外部イテレータ以外の方法があれば使ってみたいんですけど…。
open/close この記事にコメントする



2014年4月28日

神の一手

コンピュータ将棋の電王戦が非常に話題になっていました。盛り上がりについて行けていませんが、結果だけ聞くとプロと勝負できるまでになったとか、こりゃすごい。

チェッカーは神の一手(全手読み切った上での、最善の一手)がわかるそうですが、チェス、将棋、囲碁は探索範囲が広すぎるのでほぼ不可能でしょう…。神の一手は興味深いですが、わからないからと言ってコンピュータ将棋が弱くなるわけでもなく、今後、コンピュータ将棋はもっと盛り上がることでしょう。

将棋の探索範囲の広さは1局面にざっと80通り(※)指せて、終局まで110〜120手くらい指すので、探索空間は80^120程度です。10のべき乗がお好きなら、
10^x = 80^120の自然対数取って、
x * ln10 = 120 * ln80
x = 120 * ln80 / ln10 = 228.5
となって10の228乗くらい、と見積もれます。調べてみると一般的には10^220と言われているようです。ややズレたのは、なんでだろ…。

(※)歩が9枚(1通り * 9)飛(16通り)角(最も動けて16、動けなくて8なので、間を取って12通り)王(8通り)金(6通り * 2)銀(5通り * 2)桂(2通り * 2)香(最も動けて9、動けなくて0なので、間取って4.5通り * 2)として、1局面80通り、駒を取られても再び置けるため、指せる手の平均値はほぼ変わらない、とした。

囲碁はどうか?

コンピュータ囲碁はどうだろう?と調べてみると、2006年にモンテカルロ法(1手ずつデタラメに置いて、勝ちの確率が高い手を探す)を採用した強いソフトが出て、今やアマ有段者並の強さとのこと。こちらもすごいですね…。

モンテカルロ法はリバーシや囲碁などの性質を非常に上手く使っています。リバーシや囲碁は1手指せば1つ空きマスが減るため、メチャクチャに打っても必ず終局にたどり着ける、という性質があります。これを上手く利用して、メチャクチャに打った手の中で勝率が高い手はどれか?を探すそうです。

囲碁では有効なモンテカルロ法ですが、将棋への適応は難しいようです。なぜなら将棋はデタラメに指しても終局に近づかない(ループして盤面が戻ってしまう)ためです。

並べられることの多い、将棋と囲碁ですが、探索方法一つとっても違いがハッキリ出ていて面白いですなー。

編集者:すずき(2014/04/29 16:47)

コメント一覧

  • よしだあさん(2014/04/29 22:24)
    囲碁はモンテカルロ法なんて使ってるんやね。
    将棋にしても囲碁にしても、ぜんぜん分野違いの理論が取り入れられて強くなってるってのは、とてもおもしろいなー。
  • すずきさん(2014/05/01 07:13)
    >よしだあ さん
    専門外のことでも深く理解しておくと良いことありそうだね。
    ただ知っているだけじゃ応用効かないから、どれくらいやるべきかは難しそうだけど…。
open/close この記事にコメントする



link もっと前
2014年5月11日 >>> 2014年4月28日
link もっと後

管理用メニュー

link 記事を新規作成

<2014>
<<<05>>>
----123
45678910
11121314151617
18192021222324
25262728293031

最近のコメント5件

  • link 21年3月13日
    すずきさん (03/05 15:13)
    「あー、このプログラムがまずいんですね。ご...」
  • link 21年3月13日
    emkさん (03/05 12:44)
    「キャストでvolatileを外してアクセ...」
  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」

最近の記事3件

  • link 24年3月25日
    すずき (03/26 03:20)
    「[Might and Magic Book One TASのその後] 目次: Might and Magicファミコン版以前(...」
  • link 21年10月4日
    すずき (03/26 03:14)
    「[Might and Magicファミコン版 - まとめリンク] 目次: Might and Magicファミコン版TASに挑...」
  • link 24年3月19日
    すずき (03/20 02:52)
    「[モジュラージャックの規格] 古くは電話線で、今だとEthernetで良く見かけるモジュラージャックというコネクタとレセプタク...」
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

最終更新: 03/26 03:20