艦これユーザーアクティビティの冪分布

今人気のブラウザゲーム「艦これ」では、各サーバごとにプレイヤが獲得した経験値のランキングが見られるようになっている。ランキングは毎月始めにリセットされる。月によっては上位者に通常プレイでは入手できないアイテムが配布されたりする。またランキングに応じて「元帥」「大将」「中将」・・・とプレイヤの称号が変わる。ある月に大将になっても次の月はみな新兵からスタートになる。
以下の図はブルネイサーバにおける上位1000位までのプレイヤの12/26と12/27における得点をプロットしたもの。だいたい得点は順位のべき乗、具体的には-1/4乗に比例していることが分かる。こうした冪分布は書籍の売り上げ順位と部数の関係とか、単語の出現順位と頻度などでも見られる。単語の頻度ではだいたい頻度が順位の-1乗となることが分かっている。-1/4乗というのはそれに比較して傾きがゆるい、すなわち、わりとみんな同じ位のエフォートを投入しているということを示唆している。


図の赤い線は上位1%と思われるあたりで、ここで称号が大将から元帥に変わる。このあたりの分布を見ると若干肩があるように見える。おそらく元帥の称号を目指して頑張って、取得したらしばらくペースダウンする人が多いためと思われる。
ちなみにこのあたりの具体的なペースとしては、「2-2のボスを毎日20回倒す」あるいは「4-2のボスを毎日10回倒す」ことでキープ可能なペースで、まあ結構大変な感じ。時間で言うと2〜3時間くらいか。
このゲームでは艦の経験値とプレイヤの経験値は別に設定されていて、艦が育つと火力や装甲が上昇し強くなる一方、プレイヤのレベルが上がるとLv30以上で強力なアイテムが作れるようになるけど、それ以上はあまりご利益はない。
2-2と4-2を比較するとプレイヤの経験値を稼ぐ効率は同じ位だけど、前者は艦の経験値があまりもらえないし、レアな艦も出てこない。一方で4-2は敵も強いので、火力が高いが燃料や弾薬などを多く食う戦艦などを運用する必要がある。燃料・弾薬などの資源は待つことで自然増加し、更にクエスト遂行などで自然増加分の三倍程度まで稼ぐことが可能。ただしそれにはやはり手間と時間がかかる。あるいは課金してそれらの資源を購入することも出来る。課金なしでは毎日4-2を10回というのはおそらく資源的にカツカツだと思われる。もっと課金すれば5-2とかのもっと資源を食うけどもっと効率のいいマップで稼ぐことも可能で、上位10位以内はそうしたマップで稼いでいると思われる。

金と時間とゲーム内資源という三つのリソース。ある人は課金し時間を節約したと考え、ある人は時間をかけて課金分の金を稼いだと考え、ある人は資源と成果のコスパを最適化し時間と金の両方を節約したと考える。三者三様。

4-2周回に投入する資源と時間を最適化する場合、資源を減らすには燃費のよい軽空母などを鍛えて艦載機などの装備をレアで高性能な烈風とか流星とか史実を知ってる者には夢のまた夢のような最新鋭機にする。
時間を最適化するには火力で圧倒すればいいけど、あまり早く倒して連戦すると艦隊の疲労が回復する暇がなくミスが多くなり史実の日本海軍と同じ轍を踏むことになる。これを防ぐには前線で動く戦力の二倍を確保しローテーションするという米軍の用いた方針を取ることになる。

「雪だるま式」は時間の何乗?

Snowball Effect (Wikipedia)
半径Rの雪だるまが深さ1の雪の上を転がることを考えます。

接地面の半径は√Rに比例。速さ1で動かすと、√Rに比例した雪がひっついて体積が増えます。
d(R^3)/dt = 定数*√R
物理屋なら、ここから指数とか出てこないことは一目で分かります。「借金が雪だるま式に」という表現は指数的増加を示唆するけど、雪だるまは指数で成長しない。
明らかに時間のべき乗になることが見えるので、その指数をxとおくと、d(R^3)=3 R^2 dR/dtより 3x-1 = x/2。
したがって Rはt^2/5に比例することに。時間の0.4乗。聞いたことない指数た!
これだと体積は時間の1.2乗に比例。時間に正比例するより少しだけ速い程度。

ばばあと反物質とラグランジュの未定乗数法

あいも変わらずクッキー焼きゲームの話です。
http://orteil.dashnet.org/cookieclicker/

終盤は最も高性能の反物質凝集クッキー製造機を何個買うかだけが重要になって、他の物はオマケ以下になってしまいます。ただし、ばばあの性能はばばあの人数に比例してわずかずつですが上昇していきます。果たして、ばばあが反物質に勝つ日は来るのでしょうか。

手持ちに一定のクッキーがあるとき、それぞれの施設を何個買えば最適かという問題を考えます。数学的には、

  • それぞれの施設の数がx1, x2, x3, ...、クッキー焼き性能がP1, P2, P3, ... として、
  • それを全部買うためのコストが一定、という条件のもとで
  • 合計パフォーマンス x1 P1 + x2 P2 + x3 P3 + ... を最大化する

という問題となります。よく出てくるタイプの問題で、こういう一定コストの元でパフォーマンスを最大化する、という問題は最も典型的な例でしょう。この種の問題を解く方法としてラグランジュの未定乗数法があります。数学的な定義を習って知ってる人は多いでしょうが、具体的なイメージを持っている人は少ないでしょう。じつはこのクッキーの問題は具体的にイメージするのに最適な問題となっています。
ラグランジュの未定乗数法の処方箋に基づいてこの問題を解くと、

  • 各施設を1つ買い足すときのコストの施設間の比率が、
  • 各施設を1つ買い足した場合のパフォーマンス増加(この問題では一台あたりの性能)の施設間の比率に等しい

となります。これをどう解釈すればいいでしょうか。
金に糸目を付けなければ、性能のいいものをがんがん買えばよくて、性能に比例した台数を買い増せばOKです。しかしコスト一定という条件があると、あっちを減らしてこっちを増やし、性能が増える方法をうまくやりくりして探すということになります。そういうやりくりを可能な限りやり尽くした状態というのが最適な状態です。
もう小手先のやりくりでこれ以上改善はできない、という状態だと、改善の方向はもう使えるコストを増やすしかない、という状態になります。すなわちパフォーマンスの増える方向と、コストの増える方向が一致する、という状態。これがコスト増加の比率とパフォーマンス増加の比率が一致するという条件の意味です。
これで数学の話は終わり。以下では実際に計算します。

各施設を1つ買い足すときのコストは

  • 初期コスト*(1.15の台数乗)

初期コストは上から

  • 15, 100, 500, 3000, 10000, 40000, 2e5, 1.66e6, 123e6, 4e9

一台あたりの性能は最大強化の状態で上から

  • 2000~20000, 150000~250000, 80, 224, 800, 2080, 8000, 133312, 1.7e6, 17.6e6

(台数は100~1000程度を想定)

施設間のコストの比率がパフォーマンス比率に一致するということは、各施設のパフォーマンス/コスト比が全ての施設で同じ、となる。計算すると

  • パフォーマンス/(初期コスト*1.15^台数)

比較基準として反物質の値を使うと
パフォーマンス/(初期コスト*1.15^台数) 
 = 反物質のパフォーマンス/(反物質の初期コスト*1.15^反物質の台数)
両辺の対数を取ると

  • log(パフォーマンス/初期コスト) - log(1.15)*台数 = Log(17.6e6/4e9) -log(1.15)* 反物質の台数

整理すると

  • 台数 = 反物質の台数 +( log(パフォーマンス/初期コスト) - log(17.6e6/4e9) )/log(1.15)

右辺のプラスなんたらは、ばああとカーソルを除いてずっと一定なので、各施設の台数は常に反物質の台数+一定値、となる。たとえば反物質が100なら、ばああとカーソルの性能増加を考えなければ上から

  • 213, 190, 125, 120, 121, 118, 115, 120, 108, 100

となり、反物質を一台買い足すごとに各施設も全て一台ずつ買えばいい。ばばあとカーソルはパフォーマンスが微増していくけど、たとえ微増でなく100倍1000倍に激増したとしてもlogの中に入っているので影響は小さく、上記の台数の差は数十台程度変化するだけ。
施設の数が増えて反物質1000とかになると、施設の数の差の10程度は無視できるくらいになるので、各施設が全パフォーマンスに寄与する割合は単純に一台当たりのパフォーマンスの比率になり、結局ほとんど反物質だけの寄与になってしまう。このバランスが崩れるのはばばあの単体性能が反物質と並ぶようになる時になる。
ばああの単体性能÷反物質の単体性能 = 0.0015 + 0.000074*ばばあ人数+0.000093*ポータル台数
ポータル台数=ばばあ人数-70程度なので、上式が1になるのはばばあ6018人の時。またカーソルが反物質に並ぶのはトータル建物数が75000の時。

結論:無理。

厳密な計算

続きを読む

クッキークリッカーの最適戦略

最近話題のこれ。
http://orteil.dashnet.org/cookieclicker/
ぼーと待ってるとクッキーが生産されます。貯まったクッキーを使って施設やバーチャンを買います。すると単位時間あたりクッキー生産量(CpS)が増えます。それでまた施設を買って、という倍々ゲーム。工場やら魔界への門やらタイムマシンやら反物質まで使ってクッキーの生産量が10^n倍になっていきます。
いかに短時間で、いかにCpSを倍々に増やすか、というゲーム。したがって戦略としては Log(CpS)の時間微分を最大にする、となります。
何かを購入する場合のコストがCost、CpSの増分がΔCpSとすると、Costだけクッキー貯めるには待ち時間Tw=Cost/CpS秒必要、購入すると Log(CpS)の増分はLog(1+ΔCpS/CpS)。したがって評価関数としては Log(1+ΔCpS/CpS)/Tw が使える。これが高い順番に購入していけばいい。
評価関数としてはもっと直感的に、そのペースで例えば1時間ほど増やし続けた場合のCpS複利で何倍になるかという量、
R(3600)=(1+ΔCpS/CpS)^(3600/Tw) が使える。
300 MCpSの場合に各施設のTwを横軸、R(3600)-1を縦軸にプロットした図。この図で上から選んでいけばいいけど、Tw=数時間というのもある。寝てる間につけっぱにしとくか、ババアポカリスプで楽しんで大当たりを使うか。


追記

上記は一手だけの評価で先読みはしてない。
例えば一時間待ちの手が最善という状況で、最善ではないけど時間のかからない手を先に打ち、CpSが微増して一時間の待ち時間が減るという状況があるかもしれない。
待ち時間がTa、CpSが1+Δa倍になる最善手があり、別の手は待ち時間Tb,倍率1+Δbになるとする。a,bの順でやった場合とb,aでやった場合の時間はTa+Tb/(1+Δa) と Tb+Ta/(1+Δb)。後者のほうが小さいという条件を計算すると結局、上の評価関数がbのほうが高いという条件になる。
先読みなしの最適化でグローバルな最適化までできてしまう。結構底が浅い。

桜開花の熱力学

一般に農学分野では、植物や虫の変化の進捗は平均気温を積分した量で決まるという考え方をするようです。
ある温度で活性化する化学反応の生成物が閾値に達して変化を誘発すると考えると、単純な温度の積分よりはアレニウスの式を積分する方が自然だろうな、と思ってましたが気象庁の使ってる式を見たら正にそうなってました。
http://www.data.jma.go.jp/sakura/data/cb/sakura.html
まあ単純な積分と比較して精度がいいかどうかは検証が必要でしょうけど。
http://www.yoho.jp/event/kenkyuseika2011/data/02ppt.pdf
ん、微妙ですね。ab initio より ad hoc。こういった式は当たってナンボですからね。エレガントさとか関係ない。

昆虫が成虫になる時期も同様の方法である程度予測できそうです。虫の種類ごとにパラメータが違うでしょうけど。
参考 "Effects of temperature on development, survival and reproduction of insects: Experimental design, data analysis and modeling"
http://www.usu.edu/beetle/documents/Regniere_etalJInsectPhys2012.pdf

結局何が言いたいかというと、ヒラヤマコブハナまだあーーー!!!!

追記

気象庁の式をexp(-E/kT)の式に直すとE= 80kJ/mol になるようです。有機物とか絡んだ反応はだいたいそのオーダーのようで。

グラフを切る

「最高のカレーを作れ」問題 https://codeiq.jp/ace/yuki_hiroshi/q210
面白いです。別の例に例えると、128人の集団を2つの組に分けます。仲のいいペアは、なるべく同じ組になるようにしたい、という問題。
128個の粒子を用意して、仲のいい同士が引き合い、それ以外は反発するようにして動かすと以下のようになりました。

なんとそういう設問でしたか。集団を二つに切るなら、左の太線で切れば11組の好き同士を分断するだけで済みます。これがおそらく最適解。右が12本でわずかに違うところが絶妙。

確実に最適解を求めるアルゴリズムも、複雑だけどあります。以前の自分の日記から引用

最大流/最小切断定理
たとえば東京都内から筑波に人が一斉に移動するというシチュエーションを考える。東京に核ミサイルが落ちてきて筑波にシェルターがあるとか。このとき何時間で避難可能か、という問題を解くには可能な東京から筑波への最大「流量」を求める必要がある。都内でいくら道路が広くても利根川あたりで橋が少なくて橋の交通量の合計が例えば車100台/分だったらこれ以上の交通量が発生しないように都内で規制しないと渋滞になってしまう。ほかにボトルネックがない場合にはこの「車100台/分」が求める最大流量となる。つまり出発点とゴールを分断する線をいろいろ引いてそれを横断する道路のキャパシティの合計を計算したとき、あらゆる線の引き方のうちでキャパシティが最小になる引き方のキャパシティ(最小切断)が最大の流量を与える。最大流を求める多項式時間のアルゴリズムが存在するので、逆に最小切断の問題は最大流の問題に置き換えて多項式時間で解くことが出来る。

このパワポが面白いです: http://www.c.csce.kyushu-u.ac.jp/~makiyama/rinkou/KINJI/kinji4.ppt

現在最速のアルゴリズムは以下で実装されているようです。
Hao-Orlin アルゴリズムC++クラス: http://lemon.cs.elte.hu/pub/doc/0.6/a00225.html

技術的詳細

  • 引力エネルギーをR^2, 斥力エネルギーをR^-2にしてます。同じ次数で符号だけ変えるとうまくいきません。
  • 利根川河川敷でよくマイマイカブリとか探すんですけど、対岸に渡れる場所が10km間隔くらいで、マジ困ります。
  • ランダム磁場強磁性Isingモデルの基底状態は上記アルゴリズムで求まります。
  • 解いてからだいぶ後で記事かいたんで問題うろ覚えで256個と書いてたけど、実際は128個でした