ROEコモン・ソート解析の進み
2010年5月6日 ゲームさて、仮ソートについて、いろいろと分かったこともあり、それをヒントに推測もし、と進めてきたのですが、ひとつ気になっていたことがありました。
仮ソートは、実際のパック・データに存在する、4枚のカード並びだけをつないで作られたソートであるにも関わらず、削除パートとか挿入パートとかが混在する構造になっています。
最初は、
・Aソート部分6枚が、必ずしもひと続きであるとは限らないだろうとか、
・製造工程での誤りが多い製品なのかもしれないとか、
そんなふうに思っていたのですが、思った以上に規則的であることが分かった今となっては、そうした想定はし難いものがあります。
これは、ROEのコモン・ソートは、三階マルコフ過程ではない、ということじゃないでしょうか。
二階じゃないから三階だろう、と思っていたわけですが、三階ですらなかったのかも。
そこで、Ver. 5のデータから作成した三階遷移頻度データから、同一の三枚の並びの後に、異なるカードが出てくるケースを探してみました。
多くのパックでは同じカードが出てくるんだけど、1枚だけ別のが出てくるパックがある、みたいなのは、まあ、エラーかもしれない、と思います。
そういう、1パックだけ違う、というのは、10件ありました。
が、2件以上同じのが出てくると、偶然では片付け難いです。
そういうケースは、5件ありました。
・5,155,175→15 ... 2件 / →86 ... 3件
・41,114,155→78 ... 7件 / →175 ... 2件
・43,68,228→26 ... 8件 / →97 ... 3件
・68,228,26→97 ... 6件 / →145 ... 6件
・121,26,114→155 ... 2件 / →213 ... 5件
仮ソートでは、こういう並びの出現位置をピボットにして、実際のソートの異なる部分がつながってしまっているのじゃないかしら。
さてしかし、それじゃどうしましょうか。
四階マルコフ過程だと思って、もう一度ソートを作り直してみましょうか。
しかし、それにはちょっとデータの数が不足です。
四階遷移頻度のデータを得るには、5枚のカードの並びが必要なので、6枚ソートでは、1パックから2つのデータしか取れません。
bunさんのところで公開されている最新のパック・データ(Ver. 5)は652件ありますが、それでも1304件のデータしか得られないということです。
一方、ソートは、どうやら、120個だか180個だかのデータの入ったソートが3種類か4種類くらいありそうだ、というハナシになってるわけで、そこにはおそらく600種類くらいの四階遷移があるのでしょう。
となると、ソートにはあるけどパック・データ中に含まれない5枚のカードの並びがいっぱいあるだろうと予測されます。
これでは、自動的にソートを得ることはできません。
最低でもこの5倍くらいデータがありませんと。
まあしかし、基本は四階遷移のデータを使いながら、データのないところは三階遷移データを参考にしてソートを作るっていう方法もあるかもしれませんよね。
そこで、四階遷移頻度のデータを作ってみました。
ところが、同一の四枚の並びの次に異なるカードが出てくるケースが本当にないかどうか、その結果を見て確認したところ、ありますなー。
・43,68,228,26→97 ... 3件 / →145 ... 3件
・68,121,26,114→155 ... 1件 / →213 ... 5件
・97,149,174,133→27 ... 1件 / →88 ... 5件
・121,41,114,155→78 ... 4件 / →175 ... 2件
・136,43,68,228→26 ... 6件 / →97 ... 3件
・148,23,108,187→79 ... 2件 / →97 ... 1件
・207,136,27,68→186 ... 3件 / →228 ... 1件
これは、狙ってやってるんですかねぇ。
A1ソートのある部分がA0ソートのある部分と、ちょうど同じ並びになるように設計しているとか。
そうやって、ソート解析をし難くしているとか。
となれば、もう、乗りかかった船です。
ついでに五階遷移頻度も調べました。
しかし、それでもまだ。
・110,136,43,68,228→26 ... 1件 / →97 ... 1件
・136,43,68,228,26→97 ... 3件 / →145 ... 1件
うーむ。
最初はエラー・パックじゃないか、とも思ったんですが・・・。
上と下は、たぶん同じソートのほぼ同じ位置ですよね、これ。
もしもこれがエラー・パックでないのだとすると、実は、「生産中に、ソート中の特定の場所で、A1→Aみたいにソートが切り替わることがあって、これらの2パックは、その切り替わりのところで作られたパックです」みたいなハナシがあるのかもしれないと思ったりも。
そうなると、何階のマルコフ過程である、ということは言えなくなってしまいます。
ともあれ、このデータを使って、ソートの推定をやってみましょうか。
アルゴリズムはこうです。
下準備
(1) 三階前方/後方遷移件数を求める。
各パック・データから、6枚ソート中の4枚の並びをすべて抜き出し、その出現件数を数え上げます。
例えばあるパックにA,B,C,D,E,Fの6枚が含まれているなら、A,B,C,D/B,C,D,E/C,D,E,Fの3つを抜き出します。
これによって例えば、23,149,210,133という並びが5パックに含まれていることが分かります。
これを、23->149->210という3枚の並びから133へと遷移する三階前方遷移件数と呼ぶことにします。
また、同時に、この数を、149->210->133という3枚の並びが23から遷移する三階後方遷移件数とも呼ぶことにします。
(2) 四階前方/後方遷移件数を求める。
各パック・データから、6枚ソート中の5枚の並びをすべて抜き出し、その出現件数を数え上げます。
例えばあるパックにA,B,C,D,E,Fの6枚が含まれているなら、A,B,C,D,E/B,C,D,E,Fの2つを抜き出します。
抜き出されたe1,e2,e3,e4,e5という並びの数を、e1->e2->e3->e4からe5への四階前方遷移件数と呼ぶと同時に、e1からe2->e3->e4->e5への四階後方遷移件数と呼びます。
(3) 五階前方/後方遷移件数を求める。
上と同じ要領で、6枚の並びについて数え上げます。
ソートの推定
(4) 各パックについて、(5)-(9)をやる。
(5) そのパックの先頭5枚の並びを抜き出し、それがソートの一部であると仮定する。
(6) 現在仮定しているソートの先頭の5枚のカードに遷移する五階後方遷移件数の最も大きいカードが、そのソートの直前のカードだと仮定する。そのようなカードが存在しない場合、四階後方遷移件数で試みる。それもない場合、三階後方遷移件数で試みる。
(7) 三階後方遷移件数でも見つからないか、または、同じ5種類のカードが同じ順序で現れるまで、(6)を繰り返す。
(8) 現在仮定しているソートの末尾の5枚のカードから遷移する五階前方遷移件数の最も大きいカードが、そのソートの直後のカードだと仮定する。そのようなカードが存在しない場合、四階前方遷移件数で試みる。それもない場合、三階前方遷移件数で試みる。
(9) 三階前方遷移件数でも見つからないか、または、同じ5種類のカードが同じ順序で現れるまで、(8)を繰り返す。
要するに、実際のパックに含まれるカード並びを種にして、それを他のパック・データにも数多く現れる、なるべく長いデータ列に従う形で前後に伸ばせるだけ伸ばしたカード並びを求めましょう、ということです。
652件の各データについてこれをやってみたところ、55種類のカード列が得られました。
そのうち15件は、長さが6です。
6ってことは、1パックに含まれるこのソートの枚数とおんなじです。
どういうことかというと、それは、その先頭および末尾の3枚の並びが、他のパックのデータと全く共有されていないパックだったということです。
1つ2つなら、エラー・パックなのかも、と思えなくもないですが、エラーだとすると、先頭3枚と末尾3枚の両方にエラーがあるっていうことになり、それもさすがにムリがあるところ。
そんなパックが15個もある、ということは、ソートについて、実データに基づいて確定的なことを言うのは、ムリってことですなー。
・・・などと言うのは簡単ですが。
まあ、それでも何とかなるかならないか、もうちょっとやってみましょう。
見つかったカード列のうち、最長のものは289要素。
でも、キレイなループではなく、数字の「6」の字のように、列の途中に戻っている形になっています。
「6」の下の「o」の部分だけ取り出せばループですが。
この、最長のカード列について、もうちょっと。
このカード列の一部と正確に一致するパック・データは352件あります。
一方、全然一致しないのは27件。
このカード列の201-228番目の範囲は、「削除ゾーン」で、3-199、および、233-251番目の範囲は、「挿入ゾーン」です。
「削除ゾーン」では、パック・データの中に、「削除ゾーン」中の、3で割った剰余が0になる位置のカードを取り除いた断片と一致するものが、26件あります。
「挿入ゾーン」では、パック・データの中に、「挿入ゾーン」中の奇数番の位置の直前にカードを挿入した断片と一致するものが248件あります。
(全部足すと653件で1件多くなるのは、削除と挿入の両方のゾーンの境目のデータで、その両方が生じているのが1件あるからです。)
こうした分析を他のカード列についても行うと、同じ挙動を示すストリークが特定されていくだろうと思います。
それを眺めると、もうちょっと何か分かってくるかもしれません。
その作業を、手作業でやるか、それとも何かプログラムでやるか、どうしようかなー。
仮ソートは、実際のパック・データに存在する、4枚のカード並びだけをつないで作られたソートであるにも関わらず、削除パートとか挿入パートとかが混在する構造になっています。
最初は、
・Aソート部分6枚が、必ずしもひと続きであるとは限らないだろうとか、
・製造工程での誤りが多い製品なのかもしれないとか、
そんなふうに思っていたのですが、思った以上に規則的であることが分かった今となっては、そうした想定はし難いものがあります。
これは、ROEのコモン・ソートは、三階マルコフ過程ではない、ということじゃないでしょうか。
二階じゃないから三階だろう、と思っていたわけですが、三階ですらなかったのかも。
そこで、Ver. 5のデータから作成した三階遷移頻度データから、同一の三枚の並びの後に、異なるカードが出てくるケースを探してみました。
多くのパックでは同じカードが出てくるんだけど、1枚だけ別のが出てくるパックがある、みたいなのは、まあ、エラーかもしれない、と思います。
そういう、1パックだけ違う、というのは、10件ありました。
が、2件以上同じのが出てくると、偶然では片付け難いです。
そういうケースは、5件ありました。
・5,155,175→15 ... 2件 / →86 ... 3件
・41,114,155→78 ... 7件 / →175 ... 2件
・43,68,228→26 ... 8件 / →97 ... 3件
・68,228,26→97 ... 6件 / →145 ... 6件
・121,26,114→155 ... 2件 / →213 ... 5件
仮ソートでは、こういう並びの出現位置をピボットにして、実際のソートの異なる部分がつながってしまっているのじゃないかしら。
さてしかし、それじゃどうしましょうか。
四階マルコフ過程だと思って、もう一度ソートを作り直してみましょうか。
しかし、それにはちょっとデータの数が不足です。
四階遷移頻度のデータを得るには、5枚のカードの並びが必要なので、6枚ソートでは、1パックから2つのデータしか取れません。
bunさんのところで公開されている最新のパック・データ(Ver. 5)は652件ありますが、それでも1304件のデータしか得られないということです。
一方、ソートは、どうやら、120個だか180個だかのデータの入ったソートが3種類か4種類くらいありそうだ、というハナシになってるわけで、そこにはおそらく600種類くらいの四階遷移があるのでしょう。
となると、ソートにはあるけどパック・データ中に含まれない5枚のカードの並びがいっぱいあるだろうと予測されます。
これでは、自動的にソートを得ることはできません。
最低でもこの5倍くらいデータがありませんと。
まあしかし、基本は四階遷移のデータを使いながら、データのないところは三階遷移データを参考にしてソートを作るっていう方法もあるかもしれませんよね。
そこで、四階遷移頻度のデータを作ってみました。
ところが、同一の四枚の並びの次に異なるカードが出てくるケースが本当にないかどうか、その結果を見て確認したところ、ありますなー。
・43,68,228,26→97 ... 3件 / →145 ... 3件
・68,121,26,114→155 ... 1件 / →213 ... 5件
・97,149,174,133→27 ... 1件 / →88 ... 5件
・121,41,114,155→78 ... 4件 / →175 ... 2件
・136,43,68,228→26 ... 6件 / →97 ... 3件
・148,23,108,187→79 ... 2件 / →97 ... 1件
・207,136,27,68→186 ... 3件 / →228 ... 1件
これは、狙ってやってるんですかねぇ。
A1ソートのある部分がA0ソートのある部分と、ちょうど同じ並びになるように設計しているとか。
そうやって、ソート解析をし難くしているとか。
となれば、もう、乗りかかった船です。
ついでに五階遷移頻度も調べました。
しかし、それでもまだ。
・110,136,43,68,228→26 ... 1件 / →97 ... 1件
・136,43,68,228,26→97 ... 3件 / →145 ... 1件
うーむ。
最初はエラー・パックじゃないか、とも思ったんですが・・・。
上と下は、たぶん同じソートのほぼ同じ位置ですよね、これ。
もしもこれがエラー・パックでないのだとすると、実は、「生産中に、ソート中の特定の場所で、A1→Aみたいにソートが切り替わることがあって、これらの2パックは、その切り替わりのところで作られたパックです」みたいなハナシがあるのかもしれないと思ったりも。
そうなると、何階のマルコフ過程である、ということは言えなくなってしまいます。
ともあれ、このデータを使って、ソートの推定をやってみましょうか。
アルゴリズムはこうです。
下準備
(1) 三階前方/後方遷移件数を求める。
各パック・データから、6枚ソート中の4枚の並びをすべて抜き出し、その出現件数を数え上げます。
例えばあるパックにA,B,C,D,E,Fの6枚が含まれているなら、A,B,C,D/B,C,D,E/C,D,E,Fの3つを抜き出します。
これによって例えば、23,149,210,133という並びが5パックに含まれていることが分かります。
これを、23->149->210という3枚の並びから133へと遷移する三階前方遷移件数と呼ぶことにします。
また、同時に、この数を、149->210->133という3枚の並びが23から遷移する三階後方遷移件数とも呼ぶことにします。
(2) 四階前方/後方遷移件数を求める。
各パック・データから、6枚ソート中の5枚の並びをすべて抜き出し、その出現件数を数え上げます。
例えばあるパックにA,B,C,D,E,Fの6枚が含まれているなら、A,B,C,D,E/B,C,D,E,Fの2つを抜き出します。
抜き出されたe1,e2,e3,e4,e5という並びの数を、e1->e2->e3->e4からe5への四階前方遷移件数と呼ぶと同時に、e1からe2->e3->e4->e5への四階後方遷移件数と呼びます。
(3) 五階前方/後方遷移件数を求める。
上と同じ要領で、6枚の並びについて数え上げます。
ソートの推定
(4) 各パックについて、(5)-(9)をやる。
(5) そのパックの先頭5枚の並びを抜き出し、それがソートの一部であると仮定する。
(6) 現在仮定しているソートの先頭の5枚のカードに遷移する五階後方遷移件数の最も大きいカードが、そのソートの直前のカードだと仮定する。そのようなカードが存在しない場合、四階後方遷移件数で試みる。それもない場合、三階後方遷移件数で試みる。
(7) 三階後方遷移件数でも見つからないか、または、同じ5種類のカードが同じ順序で現れるまで、(6)を繰り返す。
(8) 現在仮定しているソートの末尾の5枚のカードから遷移する五階前方遷移件数の最も大きいカードが、そのソートの直後のカードだと仮定する。そのようなカードが存在しない場合、四階前方遷移件数で試みる。それもない場合、三階前方遷移件数で試みる。
(9) 三階前方遷移件数でも見つからないか、または、同じ5種類のカードが同じ順序で現れるまで、(8)を繰り返す。
要するに、実際のパックに含まれるカード並びを種にして、それを他のパック・データにも数多く現れる、なるべく長いデータ列に従う形で前後に伸ばせるだけ伸ばしたカード並びを求めましょう、ということです。
652件の各データについてこれをやってみたところ、55種類のカード列が得られました。
そのうち15件は、長さが6です。
6ってことは、1パックに含まれるこのソートの枚数とおんなじです。
どういうことかというと、それは、その先頭および末尾の3枚の並びが、他のパックのデータと全く共有されていないパックだったということです。
1つ2つなら、エラー・パックなのかも、と思えなくもないですが、エラーだとすると、先頭3枚と末尾3枚の両方にエラーがあるっていうことになり、それもさすがにムリがあるところ。
そんなパックが15個もある、ということは、ソートについて、実データに基づいて確定的なことを言うのは、ムリってことですなー。
・・・などと言うのは簡単ですが。
まあ、それでも何とかなるかならないか、もうちょっとやってみましょう。
見つかったカード列のうち、最長のものは289要素。
でも、キレイなループではなく、数字の「6」の字のように、列の途中に戻っている形になっています。
「6」の下の「o」の部分だけ取り出せばループですが。
この、最長のカード列について、もうちょっと。
このカード列の一部と正確に一致するパック・データは352件あります。
一方、全然一致しないのは27件。
このカード列の201-228番目の範囲は、「削除ゾーン」で、3-199、および、233-251番目の範囲は、「挿入ゾーン」です。
「削除ゾーン」では、パック・データの中に、「削除ゾーン」中の、3で割った剰余が0になる位置のカードを取り除いた断片と一致するものが、26件あります。
「挿入ゾーン」では、パック・データの中に、「挿入ゾーン」中の奇数番の位置の直前にカードを挿入した断片と一致するものが248件あります。
(全部足すと653件で1件多くなるのは、削除と挿入の両方のゾーンの境目のデータで、その両方が生じているのが1件あるからです。)
こうした分析を他のカード列についても行うと、同じ挙動を示すストリークが特定されていくだろうと思います。
それを眺めると、もうちょっと何か分かってくるかもしれません。
その作業を、手作業でやるか、それとも何かプログラムでやるか、どうしようかなー。
コメント