祭囃子は遠く、

祭囃子は遠く、

無職のハッピーエヴリディを書いていきます。

ぷよぷよとランダムフィリング

ぷよぷよ プログラミング

こんにちは、すしくんです。

突然ですがみなさんこのツイート知っていますか？

統計物理専攻としてはなかなか興味を惹かれるものがあって、これをこうしたらどうなるんだろう・・・とか色々気になったものです。
しかし、当時はプログラミングが今よりも下手くそだったので、自分で解析することが叶いませんでした。最近は少しマシになったので自分でプログラムを組めたのでこの記事に至ります。


目次

はじめに

タイトルにもある通り今回は先行研究に従い、まずはランダムフィリングで色々条件を変えていったときに連鎖の分布がどう変化するかを見ていきます。具体的にはアスペクト比を保ったままスケールを変えていったときの平均連鎖数や、お邪魔ぷよを一定の割合で入れたときの変化です。
ランダムフィリングとは文字の通りですが、フィールドにぷよをランダムに敷き詰めていくことです。したがって一番の違いは現実のぷよぷよでは不可能な状況も発生するところです。(例えばフィールド真ん中から連鎖が始まる、１２段３列目にぷよがあっても良いなど)
今回はとこぷよや対戦面を含めた盤面への主張はしないので、この場合こうなるんだとかそのくらいに思ってください。


プログラムの流れ

  1. あるスケールでのフィールドに４色のぷよをランダムに配置
  2. 連結を判定し、４連結以上でぷよを消す
  3. 連鎖数を測定
  4. 最初に戻る

拡張されたフィールドにおける連鎖数分布

まずは一応最初にやられている結果をフォローできるか確認しましょう。
また、記号についてですが１３行６列のフィールドをL＝１としています。２６行１２列はL＝２、３９行１８列はL＝３…と最初のフィールドからの倍率を表すものになっています。

L＝１(先行研究)の結果です

f:id:ta_ichi:20180815142208p:plain

ピークの２−３連鎖がほぼ等しく、あとはlinearぽく落ちるとことかも似てるように見えますね。まぁこれでよしとしましょう

次にフィールドを等倍していったときの分布を見てみましょう。

f:id:ta_ichi:20180815142823p:plain

重なってて見えにくいですが、どのサイズもピーク左側が急峻で右側が緩やかな分布になっています。
分布の形自体はこの範囲内で収束しているように見えるため、どのサイズでも左右非対称で有限の歪度がある分布であることは間違いなさそうですね。

分布の形についてはわかったので次は量的なところをみていきます。
この比較だとLをどんどん大きくしていくと分布がどんどん右に動いていくだけで面白くありません。そこで各サイズでの最大連鎖数でスケールされた連鎖数で比較していきましょう。

f:id:ta_ichi:20180815143647j:plain

ピークに注目すると大きなサイズほど０に近づいていっているように見えますね。ここからわかることは、フィールドの最大連鎖数の増え具合よりも、ランダムフィリングしていったときの平均連鎖数の増え具合の方が緩やかということです。
最大連鎖数は\frac{13*6*L^2}{4}と計算していますが、せいぜいL^2のオーダーでしか増えません。一方平均連鎖数はこれを下回っていることが予測されます。

確認のためスケールされた連鎖数の期待値をみてみましょう

f:id:ta_ichi:20180815144838p:plain

緩やかにL→∞に向かって０に収束していきそうな感じが見えてますね。

片対数で見てみましょう(これでlinearならば指数関数的)

f:id:ta_ichi:20180815145006p:plain

うーん、綺麗な下凸でしょうか
両対数はどうでしょう(これでlinearならばべき関数的)

f:id:ta_ichi:20180815145134p:plain

これも微妙ですね、L＝３以上でわりかし線形にも見えますが大まかには上凸でしょうか？

L＝３以上でフィッティングかけてみましょう

f:id:ta_ichi:20180815145534p:plain

小さいサイズはものも見事に外れますね・・・
しかし大事なのはこのべき関数がどうなっているかです。

f:id:ta_ichi:20180815145821p:plain

ax^bという形でフィッティングしているので、−1.4程度で落ちていることがわかりました。
あんまり確かめるまでもなかった気はしますが、スケールサイズLに対して平均連鎖数はL^{0.6}程度のべき関数で抑えられそうということは一応やらないとわからなかったですね。
ただ、統計警察は気づいていると思いますが、これはフィッティング(回帰)させるモデルが多分ダメです。上の画像真ん中あたりのReduced chisquareに注目するとめちゃくちゃ小さいことがわかります、この値はだいたい１程度のオーダーだとよくフィッティングできてるなあという気持ちになるんですがこれは少し疑ったほうがいいですね。(多分)

ーおまけー
上の図から考えると、Lを大きくしていったときに早く収束するモードと遅く収束するモードがあると考えるのが自然でしょう。そこで補正項を入れてax^b+cx^dという形でフィッティング
f:id:ta_ichi:20180815150541p:plainf:id:ta_ichi:20180815150547p:plain

一応合わせるだけなら可能ですが、本当に合わせただけですね。もっと真面目にモデルを考えないと多分ダメです。

一定の割合でお邪魔ぷよを含むフィールドにおける連鎖数分布

今度はフィールドを固定してお邪魔ぷよをある一定の割合pで混ぜたときの分布をみてみましょう。
期待としては、ほどほどのお邪魔ぷよは多連結を切って連鎖になる方向に向かわせるはずなので、割合に対して平均連鎖数は上凸になる、と思ってました。(ました)

f:id:ta_ichi:20180815161207p:plain

0.05とか0.2とかがお邪魔ぷよの割合です、ダメそうですね、期待はずれです、普通に連鎖が減るだけです。

割合と平均連鎖数の図もみてみましょう。
f:id:ta_ichi:20180815161406p:plain

対数でみてみましょう
片対数
f:id:ta_ichi:20180815161423p:plain
両対数
f:id:ta_ichi:20180815161430p:plain

単調に減少していってますね・・・。

一応フィッティング、よくわからないので２次関数で合わせます。(どうせ適当な冪函数だし)

f:id:ta_ichi:20180815161903p:plain
f:id:ta_ichi:20180815161912p:plain

まぁ微妙ですねw


ただ、そもそもこのヒストグラムの出し方はもしかしたらよくないかもしれません。
おそらくもっとちゃんとやるならば、レプリカ法の精神に乗っ取って

  • ある割合でお邪魔を配置する
  • その隙間をぷよで埋める
  • 連鎖数を測定
  • ２、３を何度も繰り返してヒストグラムを取る
  • 同じ割合でまたお邪魔配置、2へ
  • こうしてできた「あるお邪魔配置でのヒストグラム」のアンサンブル平均をとる

とやるのが良さそうです。(めんどいからやらない)
今の解析でも割と大きなサンプルサイズではあると思うのでそこまで結果は変わらない気がします。

まとめと次の話

簡単にまとめると

  • ランダムフィリングにおいて最大連鎖数がL^2で増えるのに対し平均連鎖数はそれよりも緩やかにしか増えない
  • お邪魔ぷよは単純に平均連鎖数を下げる

といったところですね。

さて、次の進め方ですがアスペクト比を変えるとか、フィールドの倍率変更＋お邪魔とかあると思いますが面白くなさそうなのでもっと違うことをします。
というか本来こっちがやりたかったことなのですが(専門なので)

「あるハミルトニアン(コスト関数)にしたがって統計力学的にフィールドを作る」

ということをやりたいと思います。(統計的にはq-state potts modelと等価)
どういうことかというと、例えばあるハミルトニアン(エネルギーと思ってください)を考えます。

\mathcal{H}=J\sum_{(i,j)_{NN}}^{}\delta_{p_i,p_j}

\delta_{p_i,p_j}はクロネッガーのデルタ、p_i,p_jは最隣接のぷよぷよです。このとき、Jが負だとするとこのエネルギーを最小化する解は「全てのぷよが同じ色」となることはすぐにわかると思います。正だと逆に連結が一切ないフィールドが解です。(piなどには色に対応する数字が入ってると考えてください)

このようにフィールドの状態はある程度この関数でコントロールすることができます。期待的には、フィールド一面に連結している状態と一切連結していないフィールドの中間を見るとそこそこ連鎖してくれそう。
さらに「温度」の概念も導入することで、温度揺らぎからくる効果により「盤面一色がエネルギー最小であるが何個かのぷよは違う色になる」ことができます。
これも連鎖の助けになりそうです。

このことから「ハミルトニアンの式そのもの」と「温度」をうまく組み合すことができればランダムフィリングで得られた平均連鎖数を越すことができるかもしれません。
連鎖数が多い方がエネルギーが低いという式を指定すれば連鎖数は増えるのでは？という意見もあると思います、しかしそれは結果が自明であり面白くないのでやりません。(そうしてできた形を見るのは面白いかもしれません)

また、今回やったことは「任意のハミルトニアンにおけるT→∞の性質」を見たと言い換えることもできます。このあたりも次の記事の導入で話したいと思います。