FMCにおける各種期待値
本記事は、 Speedcubing Advent Calendar 2016 12日目の記事として書かれたものです。11日目は、TRDさんの「Champly: 目隠し練習用スクランブルアプリ」、 13日目は、Tora_97さんの「3×3について」です。
目次
1. イントロダクション2. ブロックビルディング
3. F2L-1からのエッジ合わせ
4. コーナーインサート
5. エッジインサート
6. センターインサート
7. 解析手法
8. 謝辞
9. 参考文献
10. さいごに
1. イントロダクション
FMCの各ステップに必要な手数の期待値等を計算したので、結果を皆さんにご紹介したいと思います。本記事を読むことで直接的にFMCの実力が向上することはありませんが、 ブロックやスケルトンの解答がいくつかできたときに、そのどれを選べば最も良い結果を期待できるのか、 インサートで大キャンセルが起きたときに、これがラッキーだったのか期待値通りなのか、などを知るための参考になると思います。
本記事では、ブロックビルディングの各サブステップ、F2L-1からのエッジ合わせ、コーナーインサート、エッジインサート、センターインサートに関する解析を行いました。
2. ブロックビルディング
2×2×2→2×2×3→F2L-1のように徐々に拡張していくときに、平均的にどれだけの手数で各ステップを終えることができるのかを計算しました。(追記します)
3. F2L-1からのエッジ合わせ
F2L-1まで完成させた状態で、残り5つのエッジが取り得る配置のパターンは、5! × 2５ / 2 = 1920 [通り]あります。 残りの5つのコーナーは無視して、この5エッジのみを揃えるには最小で何手必要かを調べました。その結果が下表です。
| 手数 | 数 | 割合 |
|---|---|---|
| 0 | 1 | 0.1% |
| 1 | 3 | 0.2% |
| 2 | 0 | 0.0% |
| 3 | 6 | 0.3% |
| 4 | 38 | 2.0% |
| 5 | 76 | 4.0% |
| 6 | 127 | 6.6% |
| 7 | 398 | 20.7% |
| 8 | 627 | 32.7% |
| 9 | 483 | 25.2% |
| 10 | 161 | 8.4% |
| 計 | 1920 | 100.0% |
なんと必ず10手以下で揃えられるという結果になりました。
コーナーとの兼ね合いもあるので必ずしも最小手数で揃えるのがよいわけではありませんが、自分が解いた際に11手以上かかったときは、もう一度考え直したほうがよさそうです。
ちなみに、期待値は7.9手でした。
4. コーナーインサート
Insertion Finderを用いて、約48万のスケルトンを解析し、その結果を集計しました。Insertion Finderでインサートできる3-cycleの数は３つまでなので、今回はインサート３回以下で処理できる全パターンを計算しました。
インサート３回以下で処理できるCO&CPの組み合わせ全23パターンの各種期待値は以下の通りです。
| パターン | インサート回数 | キャンセル | +手数 | 簡単さ |
|---|---|---|---|---|
| CP3 | 1 | 2 (0、 8) | 6.0 | 1 |
| CP5 | 2 | 5.2 (2、 12) | 10.8 | 3 |
| CP3×2 | 2 | 4.6 (0、 13) | 11.4 | 2 |
| CP2×2 | 2 | 6.6 (3、 11) | 9.4 | 7 |
| CP2'×2 | 2 | 7.1 (4、 12) | 9.0 | 6 |
| CO1 & CP3' | 2 | 5.6 (3、 10) | 10.4 | 4 |
| CO2 | 2 | 8.1 (6、 13) | 7.9 | 8 |
| CO3 | 2 | 6.3 (4、 11) | 9.7 | 5 |
| CP7 | 3 | 9.4 (5、 18) | 14.6 | 11 |
| CP3'×2 | 3 | 10.7 (8、 17) | 13.3 | 16 |
| CP2 & CP4 | 3 | 10.9 (8、 17) | 13.1 | 19 |
| CP2' & CP4' | 3 | 11.2 (8、 19) | 12.8 | 20 |
| CP3 & CP5 | 3 | 8.5 (5、 18) | 15.5 | 9 |
| CP3 & CP2×2 | 3 | 9.6 (6、 16) | 14.4 | 13 |
| CP3 & CP2'×2 | 3 | 10.2 (7、 18) | 13.8 | 14 |
| CO1 & CP5' | 3 | 10.2 (7、 18) | 13.8 | 15 |
| CO1 & CP3 & CP3' | 3 | 9 (5、 18) | 15.0 | 10 |
| CO1 & CP2'×2 | 3 | 11.6 (9、 17) | 12.4 | 21 |
| CO1 & CP2 & CP2' | 3 | 11.5 (9、 17) | 12.5 | 22 |
| CO2 & CP3 | 3 | 11.4 (9、 16) | 12.6 | 23 |
| CO2 & CP3' | 3 | 10.9 (8、 15) | 13.1 | 18 |
| CO3 & CP3 | 3 | 9.1 (6、 15) | 14.9 | 12 |
| CO4 | 3 | 11.3 (8、 18) | 12.7 | 17 |
「CP●'」は、いわゆるねじれループを意味しています。
「キャンセル」は、インサートを行った時のキャンセル数の期待値を表しています。参考程度に、各パターンでの最小キャンセル数と最大キャンセル数を、「キャンセル数 (最小, 最大)」のようにカッコ内に記載しておきました。
「+手数」は、結果的にプラス何手でインサートを終えることができるかを表しています。
今回インサートに用いた手順は基本的に全て8手なので、
手数 = 8 × インサート回数 - キャンセル
となっています。
上で基本的にと書いたのは、CP3の全3652スケルトンのうち19個、8手コミュテーターによるインサートをスケルトンのどの位置で行っても完成状態にできないものがあったためです。約0.5%の確率でCP3のインサートに9手以上が必要ということになります。このような場合Cyclic Shifts(10手)をインサートするとうまくいくことが多いようです。
ところで、スケルトンが長ければ長いほどキャンセル数の期待値は大きくなりそうです。実際に計算してみると確かにそのような傾向があったのですが、スケルトンが1手増えるごとにキャンセルが0.1手増える程度の差しかなかったので、今回はスケルトンの長さを気にせずに集計をしました。
また、Insertion Finderは計算にかかった時間も一緒に出力してくれます。どのようなアルゴリズムで最適なインサートを見つけているのかはよく分かりませんが、この時間の大小はインサートの大変さ(どれだけのパターンを探索しなければならないか)と相関がありそうです。
そこで、各種スケルトンの計算にかかる時間の平均を計算し、それを短い順に「簡単さ」として順位付けしました。
ちなみに、今回は100スクランブルで検証をしたのですが、インサート2回以下で処理できるパターンのうち、CP3×2とCP5の2つは14手以下のスケルトンを全てのスクランブルにおいて作成することができました。
参考までに、以下にインサート2回以下で処理できるパターンの、キャンセル数の確率分布を載せておきます。
5. エッジインサート
コーナーと同様に、6万5000種類のスケルトンを解析し、その結果を集計しました。Insertion Finderでは、6～10手のエッジコミュテーター手順を用いてインサートを行っています。
インサート３回以下で処理できるEO&EPの組み合わせ全20パターンの各種期待値は以下の通りです。
| パターン | インサート回数 | キャンセル | 手数 | 簡単さ |
|---|---|---|---|---|
| EP3 | 1 | 2.3 (0, 10) | 6.3 | 1 |
| EP5 | 2 | 6.7 (0, 16) | 10.3 | 3 |
| EP3×2 | 2 | 5.4 (0, 14) | 11.6 | 2 |
| EP2×2 | 2 | 7.4 (2, 16) | 8.5 | 6 |
| EP2'×2 | 2 | 7.6 (2, 15) | 8.5 | 5 |
| EO1 & EP3' | 2 | 6.2 (0, 14) | 10.5 | 4 |
| EO2 | 2 | 8.1 (2, 19) | 8.2 | 7 |
| EP7 | 3 | 11.5 (4, 22) | 13.8 | 11 |
| EP3'×2 | 3 | 12.5 (4, 22) | 12.4 | 15 |
| EP3×3 | 3 | 9.0 (2, 19) | 16.2 | 8 |
| EP3 & EP5 | 3 | 10.0 (1, 19) | 15.0 | 9 |
| EP3 & EP2'×2 | 3 | 11.2 (3, 20) | 13.4 | 12 |
| EP3 & EP2×2 | 3 | 11.1 (2, 20) | 13.7 | 13 |
| EP4 & EP2 | 3 | 12.8 (5, 23) | 11.7 | 19 |
| EP4' & EP2' | 3 | 13.0 (5, 23) | 11.7 | 18 |
| EO1 & EP5' | 3 | 11.7 (3, 21) | 13.1 | 14 |
| EO1 & EP2 & EP2' | 3 | 13.1 (6, 22) | 11.2 | 16 |
| EO1 & EP3 & EP3' | 3 | 9.9 (2, 18) | 15.2 | 10 |
| EO2 & EP3 | 3 | 12.9 (4, 22) | 12.0 | 20 |
| EO4 | 3 | 11.4 (5, 20) | 13.6 | 17 |
今回はインサート手順が必ずしも8手ではないので、キャンセル数と手数の間にコーナーの計算式のような関係はありません。例えばEP3の場合、平均8.6手の手順をインサートし平均2.3手キャンセルする結果、プラス6.3手で完成状態まで持っていけるということになります。
エッジインサートでもコーナーインサートと同程度のキャンセルを期待できそうです。
参考までに、以下にインサート2回以下で処理できるパターンの、キャンセル数の確率分布を載せておきます。
EP3はCP3よりも3手以上のキャンセルが起きやすい一方、キャンセルが全く起きないことも多いようです。
6. センターインサート
あまり行う人はいないと思いますが、FMCチュートリアル(英語)[1]にも記載があるので調べてみました。センターの回転は全部で11パターンあり、全て処理するのに最小でも8手必要でした。
しかし、センターの処理は自由度が高いため、11パターン全てにおいてR, L, F, B, U, Dの全ての回転から始まる8手の手順を作ることができました。したがって、必ず1手以上のキャンセルが起きるので、センターインサートは7手以下で行えるということになります。
そして、インサート位置はスクランブルのどこでもいいので、基本的に2手以上のキャンセルが狙えそうです。
7. 解析手法
ブロックビルディングとF2L-1とセンターインサートの解析は、Cube Explorer[2]を用いて行いました。インサートの解析については、WCAの スクランブラを用いて100スクランブル生成し、それぞれについてCube Explorerでスケルトンを作成しました。 作成したスケルトンから、インサート3回以内で処理できるものを抜き出し、Insertion Finder[3]を用いてインサートを行いました。
8. 謝辞
今回の解析にはInsertion Finderのコンパイル[4]が必要不可欠でした。協力してくださったTRDさんに感謝いたします。
9. 参考文献
[1] FMCチュートリアル(英語) http://fmcsolves.cubing.net/fmc_tutorial_ENG.pdf[2] Cube Explorer http://kociemba.org/cube.htm
[3] Insertion Finder http://mf.qiyuuu.com/
[4] Insertion Finder コンパイル方法 http://www.terabo.net/blog/how-to-compile-insertion-finder/
10. さいごに
マニアックな記事をここまで読んでくださり、ありがとうございました。「この期待値が知りたい」などのご要望がありましたら、お気軽にお問い合わせください。