記事一覧

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

BLDにおけるパリティ処理にかかる手数の比較考察

 BLDのパリティ処理について、主に手数の長さという側面から考えたことを書いていきます。

 パリティ処理とは、エッジの2点交換とコーナーの2点交換が残った場合、それぞれ単独で交換することはできないので、最後にそれぞれの2点交換を一緒に行うことを言います。また、そのために、任意の場所に余ったコーナーとエッジを特定の場所に動かす所も、この処理に含めて言う場合が多いと思います。
 以下では、偶数回の2点交換、あるいは3点交換を行っていき、バッファと任意の場所にエッジとコーナーの2点交換が残った場合から、どれだけの手数で完成させることができるか、その比較を行っていこうと思います。

 ここでは、簡単のために、一つのパリティ処理メソッドで、利用するコーナーエッジ2点交換手順は一種類とします。例えば、TパームやYパーム(のOld Pochmanで使う形)などです。つまり、最終的(4点交換を行う前)には、任意の場所に余っていた二つずつのエッジ、コーナーは必ず決められた場所に来るということになります。どうにかして一定の場所にパーツを持ってこなければなりません。
 よって、パリティ処理に必要な手順は、余ったエッジ、コーナーパーツを特定の場所に持っていく手順+4点交換手順になります。また、この説明から、パリティ処理方法は
1. 4点交換で使う手順
2. エッジ、コーナーを一定の場所に持ってくる方法
の2種類の基準によって分類することが可能になります。
 4点交換で使う手順は自分の知っている限りでは手数にあまり差がないので、以下では2の基準で分類していきたいと思います。

 エッジ、コーナーを特定の場所に持ってくるのに一番わかりやすい方法は、バッファと揃ってない位置に、その特定の場所を加えて3点交換することです。このやり方の場合、2cycle法ではエッジ、コーナーそれぞれに対して2手順が必要になります。3cycle法ではそれぞれ1手順ずつで済みます。
 例えば、DF,DRFバッファの場合は、コーナーについてはDRF,揃っていない場所,DLFで3点交換を行うことで、DRF,DLFの2点交換に必ず持っていくことができます。エッジの場合も同様に、DF,揃っていない場所,UBでの3点交換によりDF,UBの2点交換に必ず持っていけます(cf.WRCC DRFバッファ解説 11.2 )。こうすれば、4点交換はy' R2からのT permにより処理できます。

 一方で、エッジ、コーナーのどちらか一方で、1つのパーツを特定の位置にセットアップできれば、3cycle手順を使う必要がなくなります。この場合、セットアップしない3パーツはセットアップにより動いてはいけません。そのため、揃っていないパーツがどの場所にあっても特定の場所にセットアップするためには、3つのパーツは近い位置に無ければなりません。例えば、上で紹介させて頂いたパリティ処理は、残りのコーナーがULBなどにあれば、R2でセットアップすることができますが、R列にあるとセットアップがとても難しくなります。
 このやり方を用いた有名な例として、M2/OP(Old pochman)法を用いた際のパリティ処理が挙げられます。エッジをUB,ULに残し、コーナーのバッファをUBLにすることで、残ったコーナーが何であっても2手以内のセットアップでRDFに持っていくことができます
(正直、OP以外でセットアップを使うのは逆に無駄が生じてしまうような気がします。あまりよく考えていないのでわかりませんが……。そのため、以下ではセットアップを用いるパリティ処理法をOPに限定して、話を進めていこうと思います)。
 ただ、エッジがDFバッファの場合、エッジの2点交換をUB,ULに持っていくのには少し労力がいります。一番楽な方法は、まずDF,揃っていない場所,UBで3点交換を行った後、DF,UL,UBで再び3点交換を行うやり方です。もう気付いている人も多いと思いますが、この手順間でM2がキャンセルされたものが、いわゆるM2/OP法によるパリティ処理(M2法の1手順+D'L2DM2D'L2Dなど)、というわけです。
 DFバッファでは、キャンセルがあるにせよ、3cycle手順2回分に近い手順を回さなければなりません。M2法ではバッファを動かせないのでどうしようもないですが、3cycle法では、バッファをUBかULにすることで、必要な3cycle手順が1回で済みます。コーナーの方では3cycle手順を回さなくていいので、上述したコーナーとエッジそれぞれで3cycleを回すやり方よりも手順が少なくて済みます。

 まとめると、
前者のやり方ではコーナー3cycle+エッジ3cycle+4点交換
後者のやり方では、DFバッファの場合はエッジ3cycle+エッジ3cycle-M2*2+4点交換(+1,2手セットアップ)

 となり、手順数にはそれほど大きな差がないことがわかります(4点交換については、上の例だとT perm+2手セットアップとY perm-2手+2手セットアップを比べることになり、大差ないです)。ただ、2cycleで解いている場合は、前者の3cycleに2倍近い手数がかかるのに対して、後者では手数が変わらないため、明らかに後者の方が手数が少ないです。
 また、OPを使い、かつUBバッファの場合はエッジ3cycle+4点交換(+セットアップ)で済むので、上の二つよりも手数が短くなります。


 以上は、分析をそのまま行った際のやり方ですが、分析を工夫することで、2点交換を一定の場所に持ってくる作業を省略することができます。以下ではこのやり方を交換分析法と表します(自分が今適当に名付けました)。
 この一例が、コーナーの分析を先に行い、パリティがあることが分かった場合に、エッジの分析ではUBとULを逆のものとして行う、というやり方です。この例では、パリティ処理はOPを使用します。ここでは詳しいやり方は書きませんが、この動画(3BLD parity のやり方)で解説されているので、知りたい人は見てください。
 自分が計算したところ、このやり方で分析を行った場合、分析する文字数は平均ではプラマイ0でした。詳しい計算はスピソルに書き込んだので参照してください。もしかしたらこのブログにあげ直すかもしれません。
 つまり、1文字増える場合と1文字減る場合が同じ確率だということです(実際は3文字増減するパターンもありますが、簡単のためここでは説明を省略します。同様な議論が可能です)。1文字減る場合は、手順数のみ比較すると、本来余るはずだったエッジに何の操作もせずにエッジ交換が行われたということになります。1文字増える場合は、1回の3cycle手順を行うことでエッジ交換が行われたことになります。平均すると、エッジを特定の2点交換に持ち込むために、3cycle手順1/2回分が必要だということになります。
 例えば、本来の文字数が11文字の場合、それが交換分析法により10文字になる確率と12文字になる確率が同じだということです。11文字の場合は、10文字を処理した後、残りの一文字を4点交換に持ち込むためにある手順を行いますが、この分析法により、10文字だけ処理すればよい確率と12文字処理する確率が半々になります。
 DFバッファの場合は、エッジをUL,UBの2点交換に持ち込むために、3cycle手順2回分-M2*2(=M2手順2回分)が必要でした。これが3cycle手順1/2回になるのですから、大幅な短縮と言えるでしょう。だいたい10手ぐらいでしょうか。M2法を用いていたとしても、3cycle手順一回分-M2(=M2手順1回分)の短縮が見込めます(M2手順が2回必要になる確率と0回で済む確率が半々なため)。
 ただ、もし元々UBバッファにしていた場合は、3cycle手順1回のみで2点交換に持ち込むことができるため、差し引きで3cycle手順1/2回分の省略にしかなりません。だいたい4,5手ぐらいでしょうか。これを大きいとみる人はあまりいないんじゃないかと思います。

 また、コーナーとエッジそれぞれで3cycleを行うパリティ処理方法にも、交換分析法は適用できます。ただ、コーナーとエッジどちらかを分析するまではパリティの有無が分からないため、コーナーとエッジのどちらか一方にしか使えません。
例えば、DFバッファでDF,DBに交換を残したい場合は、上でULとUBを交換したようにDFとDBを交換します。バッファが絡むので少し異なってきますが、基本的には同じことをやるだけです。
 文字数については、バッファが絡む場合については計算していないのでわかりませんが、UB,ULと同様に考えられ、平均文字数には変化がないと推測しています(計算したらブログに書くかもしれません)。そのため、この場合でも3cycle手順1回使っていたものが3cycle手順1/2回の短縮にしかならないと考えられます。
 もちろんバッファが絡まない2点に交換を残すこともできるので、その場合はこの分析法が有用になってきます。バッファを絡めるかどうかに関わらず、交換分析法を使った最終的な手数は同じになります(3cycle手順1/2回分が必要)。
 また、コーナーでも同様に行えます。UBLバッファでUBL,UBRに2点交換を残したい場合は、UBL,UBRを入れ替えて分析します。ただ、これもエッジの場合と同じだけの短縮にしかなりません。

 以上をまとめると、交換分析法を適用した時にかかる手順は、

コーナー、エッジそれぞれで3cycle手順を行っていた場合は
コーナー3cycle+1/2*エッジ3cycle+4点交換(エッジ、コーナー逆転も可)

M2/OPを利用していた場合は
1/2*エッジ3cycle+4点交換

となり、明らかに後者の方が手数が少ないことがわかります。これは、前述したように、OPでは1,2手のセットアップにより、コーナーの2点交換を特定の位置に持ってきていることによるものです。


 以上の議論より、手数が一番少なく済むのは、分析でUB,ULを交換して行い、OPを用いてパリティ処理する場合です。要するに、エッジとコーナーのうち片方に交換分析法を適用し、もう片方を簡単なセットアップからの4点交換で処理すれば、パリティ処理の手順を少なく済ませられるということです。この考え方を利用すれば、新たな、手数の少ないパリティ処理法を作れるのではないか、と思います。
 この考え方を発展させれば、エッジとコーナー両方を簡単なセットアップで済ませるのが一番手数が短いことになります。ただ、そうするためには複数の4点交換手順が必要になってくると思うので、習得に相当な労力がかかると思います。また、セットアップに2手もかけていると、上記の方法とほとんど手数の差が無くなってしまうので、なかなか難しいのではないか、と思います(上位の人がどのようなパリティ処理方法を用いているのかわからないので、推測に過ぎませんが)。

 もちろん、手数が短いやり方が一番良いと言っているわけではなく、分析方法や、バッファによる3cycle手順の回しやすさなども絡んでくるのでどれが良いかは一概には言えません。自分に合った方法を探すのが一番だと思います。
 個人的には、交換分析法を用いた、手順の少ないパリティ法を使うのが良い、と考えています。分析に少し工夫が必要ですが、慣れれば問題ないそうです(自分はまだ試していないのでわかりません。試していないのに薦めるってどうなんだ……と思われるかもしれませんが)。
 ただ、BLDにまだ慣れていないうちは、交換分析法は使うべきではないと思います。パリティ処理の手数を多少減らそうとするよりも、通常の分析に慣れることを優先した方がいいです。手数を減らせると言っても10手前後なので、それ以外の部分で速くしていく方が効率的です。

 パリティ処理の知識があまりないので、議論に穴がある可能性が高いです。もし抜け漏れ、ミス等がありましたら指摘して頂けると助かります。
スポンサーサイト

コメント

コメントの投稿

非公開コメント

プロフィール

Y.Y

Author:Y.Y
3BLD,MBLDをメインにやっています。

公式記録
3BLD 1/3: 30.62/34.85
MBLD 18/20

最新コメント

カテゴリ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。