ROEコモン・ソート解析の試み

bunさんが、ROEのコモン・ソート解析を始められました。
楽しそうなんですなー。
パックのデータはbunさんのDiaryNoteに置いてあります。

ソートというのは、パックに封入されるカードの並び順を言います。
セットに含まれる全カードは、実は予め並び順が決まっていまして、パックに詰める際には、その並び順のランダムなある場所から、カードを順番に取り出して封入するんですね。
何故そんなことをするかっていうと、その方がパック詰め作業が楽だってこと(人手でやってるわけじゃないでしょうから、機械を作るのが楽ってことでしょう)らしいんですが、詳しくは存じません。
それとは別に、同じパックに特定の色のカードが偏り過ぎないようにするとか、そういうこともあるんだろうと思います。

さて、パックの中にコモン・カードは(最近のパックなら)10枚入ってるわけですが、それらすべてが、ソート中のある場所からのひとつながりの10枚のカードであるかというと、そうではありません。
パックの中の10枚は、例えば前半5枚と後半5枚とか、あるいは(「ラヴニカ」の例ですが)前の6枚と中盤3枚と後ろの2枚とかいう具合に(当時はコモンは11枚入ってたんですよ)、分割されて封入されています。
コモン・ソートの方も複数存在していて、前半5枚はこのソートから、後半5枚はこのソートから、という具合に、ソートによってパック中に封入される位置がそれぞれ異なっています。
この前半5枚とか後半5枚とかを、AソートとかBソートとかいうように呼びます。
今日まで、Aソート用のカードがBソート部分に挿入されたり、その逆だったりする例はありません。今後そうならない保証はありませんが。
通常、同じカードは、複数あるソートの中の1つにのみ現れます(過去には極く少数例外もありましたが)。
なんでそうするかっていうと、これはリミテッド対策だと思います。
つまり、コモン・カードの中にはリミテッドで特に役に立つカードや、一緒に現れることで強化されるカードなんかがありますよね。
そういうものがある程度バラけて出るようにするために、こういう仕掛けになってるんだろうと思います。
「ギルド」のあった「ラヴニカ」がCソートまであったのもそういう理由だったんじゃないかしら。
しかもこのソートの切れ目は、セット毎に固定というわけではなく、あるパックでは6-4だけど、別のパックだと7-3とか5-5とかに分かれている、なんていうこともあります。
しかもその例えば前半6枚も、必ずしもひとつながりってわけじゃありません。
パックによって、その内部が更に4-2に分かれていたり、3-3だったり、2-3-1だったりします。
そういう場合、分かれ目の前と後とでは、それぞれソート中の異なる場所のカードが封入されていることになります。
更に、パックの中の同じ場所に封入されるソートに2種類以上あることもあります。
例えば、Aソートに2種類あって(A-1ソートとA-2ソートなどと呼ばれます)、前半部分には、パックによって、ないし、場所によって、そのうちのどちらかからカードが選ばれて封入される、なんていうふうになってるわけです。

かように、ソートがどういう構造になってるかは調べてみるまで良く分からないのでありますが。
まずは、このセットのおおまかなソート構造を把握することにしましょう。
そのために最初は、全パック・データを並べてみて、任意のコモン・カード2種類の組み合わせについて、それらが両方封入されているパックがどれくらいあるか調べます。
これを、「共起件数」と呼ぶことにします。
共起件数が0であるような組み合わせは、同じソート中の離れた位置にあるカードであることが多いのです。
絶対そうだ、と言えないのは、データが少なくてたまたまってこともあるからです。
でも、多数のデータを集めて大局的に眺めれば、その中に、共起件数が0であるか、または、他のソートのカードに比べて非常に少ない組み合わせが見つかるはずで、それを鍵に、ソート構造を調べようというわけです。
ちゃんとやるといろいろたいへんですが、今回はこういう単純な方法を使いました。

(1) 共起件数の非常に大きいカード2枚をランダムにピックアップし、それら2枚のカードは同じソートに含まれると仮定する。
(2) 同じソートに含まれると仮定した2枚以上のカードとの共起件数が共に0であるカードをピックアップし、それらも同じソートに含まれると仮定する。
(3) 同じソートに含まれると仮定したカードの数が増えなくなるまで、(2)を繰り返す。

というか、これでうまくいかなかったら、原因を考えて、もっとちゃんとやろう、というだけですけれど。
MS-Excelを使って上記のアルゴリズムを実装して分類したところ、ROEの100種類のコモン・カードは、60種類のAソートと、40種類のBソートからなることが分かりました。

次に、判明したソートで、元のデータを色分けしてみました。
すると、どのパックも例外なく、前半6枚がAソート、後半4枚がBソートであることが分かりました。
(まあ、製造工程のエラーか、またはパックのカード名の写し間違いと思われる、一部の誤りはあったりもしたのですが。)
しかし、この段階では、A-1/A-2やB-1/B-2の有無は分かりません。
ともあれ、ROEはだいぶ単純な構造であるようです。

続いて、各ソートの並び順の解析に移りましょう。
ソートというのは要するにマルコフ過程ですので、マルコフ過程の最尤推定をしてやればいいことになります。
が、ひとつのカードはソート中に複数回出現するので、単純マルコフ過程ではありません。
しかし、2種類の同じカードが、ソート中の異なる位置に同じ順序で現れるというケースはこれまでにはなかったので、今回もないだろうと仮定すると、それはつまり二階のマルコフ過程です。
(平たく言うと、パックの次のコモン・カードの確率は、その直前の2枚のカードによって定まる、ということです。)
じゃあ、二階マルコフ過程の最尤推定プログラムを書けばいいわけですね。
これもちゃんとやるといろいろ面倒なので、今回は大幅に単純化して、次のようにしてみました。

下準備
(1) 各コモン・カードが現れる各パックについて、そのカードの次に現れるカードが何であるか調べ、その割合を求める (一階遷移頻度と呼びます)
　　　これで、例えば、《闇の追い返し》が出てきたら、その次は46%の割合で《勇者のドレイク》である、なんてことが分かります。
(2) 同じくそのカードの次の次に現れるカードが何であるか調べ、その割合を求める (一階二段遷移頻度と呼びます)
　　　これで、例えば、《戦装飾のシャーマン》が出てきたら、その次の次は34%の割合で《霜風の発動者》である、なんてことが分かります。

ソートの推定
(3) 一階遷移頻度の特に高い2枚のカードをランダムに選び、その順でソートに含まれていると仮定します。
(4) 現在仮定しているソートの最後のカードからの一階遷移頻度と、その一つ前のカードからの一階二段遷移頻度の積が最大であるカードが、ソートのその次のカードであると仮定します。
(5) 積の値が0でないようなカードを選べなくなるか、同じ2種類のカードが同じ順序で現れるまで、(4)を繰り返します。

本当は、こういうふうにするんじゃなくて、直前の二種類のカードが与えられたときに、次のカードが何であるかに関する割合(二階遷移頻度)を求めて推定しないといけないんですが。
それをやると、例えば60枚のAソートの場合、60^3=216,000通りの配列数式の計算をMS-Excelくんにやらせないといけなくなり、自動とは言え、うちのWin2000のパソコンでは日が暮れちまうんですなー。
その間ネット・サーフィンもMOもできないし。
というか、うちのExcel 2000では、そんな大量の数式を一枚のシートに置いておけません。
そういうわけで、上記はその実現可能な近似版です。

さて、awkスクリプトを使って上記のアルゴリズムを実装して実行してみました。
ところがどっこい、期待したようなソートが見つかりませんなー。
つまり、ソート中の全カードが一定量(普通は2枚)ずつ含まれるようなソートにならないのです。

原因をいろいろ考えました。
いちばん考えられるのは、

・やっぱり、近似じゃダメで、二階遷移頻度を求めないとダメ。

ですね。
そうかもしれませんなー。
あるいは、

・実は三階マルコフ過程である(ソート中に、2枚の同じカードが同じ順序で出てくる箇所が複数ある)。

という可能性もありますね。
それなら、三階マルコフ過程だと思って計算すればいいだけだから簡単ですが(近似でいいなら、ですけど)。
最悪なのは、

・ソートが細切れ過ぎて、ソート上で並んでいる3枚のカードが実際にその順でパックに含まれるケースがあまり多くなく、計算した一階二段遷移頻度がソートを反映していない。

ですか。
これはちょっとめんどいですね・・・。

その可能性がどのくらいあるかと思って、実際のパックのデータについて、一階遷移頻度が低い組み合わせのカードが並んでいるデータにマーキングしてみました。
すると、けっこうあります、そういう場所。
どうも、ROEのソートは、わりかし細切れで封入されているのかもしれません。
そうだとすると、500件程度のデータでは、出現頻度に基づく解析を行うにはちょっと少ないのかも・・・。

さあ、どうしよう。
ちょっと考えてみます。