世界トップキューバーのソルブを解析してみた
はじめに
初めまして。今回は休日にpythonを使って遊んでいたのですが、ちょっとだけ形になるような結果が出てきたので説明とともに記録として残しておきたいと思いこの記事を書いています。
この記事の概要は、
の2部構成になっています。
もともとはキューブを解くのが上手い人の解法を解析してみたら役に立つ結果が得られるのではないか？という思いから始めてみました。
あとは面白そうだったから。気づいたら土曜日が終わっていました。
少し長いですがよければお読みいただけると嬉しいです。
この記事のためのルービックキューブ基本事項
話の内容上ルービックキューブを揃えたことのない方には伝わらない用語が多く出てきます。基本的に随時解説を挟みますがこれだけは知らないと読みすすめられないと思われる「回転記号」というものについて説明します。知っている人は飛ばしてもらって構いません。
回転記号
崩れたキューブを6面完成状態までもっていく一連の動きのことを「ソルブ」と言います。
それぞれのソルブの中には様々な動きをや指使いが駆使されていますが、それを細かく分解していくと最小単位は「いずれかの面を90度回転させる」という動きに落とし込むことができます。
ルービックキューブはさいころと同じ六面体で、それぞれの面を90度ずつ独立して動かすことができます。そして例えば右(Right)の面を時計回りに90度動かすことを『R』という記号で表すことができます。逆時計回りなら『R’』、180度なら『R2』です。
実際のルービックキューブの状態と回転記号を対応させると下の写真のようになります。
R ↓ ↑ R'
U (Up) ↓ ↑ U'
他にもいくつかの記号はあるのですがここでは細かく知らなくて大丈夫です。要するに「アルファベットの並びが何かしらの動きを表している」とだけ分かってください。
昔のキューブの揃え方を解説しているサイトなどではいちいち画像とともに「右の面を180度回転！」などと書いてあったりするのですが、回転記号を用いることで「ここからR U R'」のように記すことができるので説明や情報交換が格段に楽になりました。グローバルな記号なので海外のキューバーの解説も読むことができます。
もっと詳しく知りたい方は
などを参考にしてください。
データを集める
本題です。
忙しい人向け要約
- Fazのao100 Reconstructionを引っ張ってきて整理します
- あとでJaydenのao50も使います
キューバーは自分のソルブを見直したり上手い人のソルブを参考にするためにソルブを上記の回転記号に起こす行為をしばしばします。崩れたキューブをもとに戻して終わりという刹那的な作業をもう一度丁寧になぞりなおして形(文字)に残すため、「Reconstruction」などと呼ばれたりしています。
一例です(僕のソルブです)。//のあとはコメントなので深く気にしないでください
F R D L2 F' D2 //cross R' U' R y U' R U R' //F2L#1 L U L' U' y'L U' L' //F2L#2 U' R U' R' y' U' R' U R //F2L#3 R U2 R' U' R U' R' //F2L#4 R U R' U' R' F R2 U R' U' F' //OLL R’ U’ F’ R U R’ U’ R’ F R2 U’ R’ U’ R U R’ U R //PLL
今回はデータセットして世界王者のFeliks Zemdegsのソルブを用います。 彼はスピードキューブをやっているなら一度は聞いたことがあるであろう選手だと思います。多数の世界記録や入賞経験を持ち、つい最近も全米大会で優勝を果たしています。 (下の動画の14:20あたりから出てくる黒い長袖パーカーの選手です。上手い人が集う大会は見ているだけでも楽しいので時間のある方はぜひ全編見てみてください。)
CubingUSA Nationals 2018 3x3 Finals!
世の中は広いもので、彼のソルブを100回分まとめて書き起こしたよ！という人がいたのでありがたくそれを使わせてもらいます。
これはおそらく作業量的に相当なものでホントにありがたいです。これがなかったらこの記事作ろうと思わなかった...
とりあえず書き起こされたものをせっせとコピーして上のReconstructionが100個詰まったテキストファイルを作成します。(実をいうと手作業でやっていたのでここが一番面倒でした... もっとうまいやり方があると思うのですが100個くらいならこっちのほうが早いやろと思って終わらせました。ゆくゆくは自動的に収集できるようにしたいですね)
テキストに集約したデータにはコメント、改行、一部特殊な記法が混じっているのでpythonで処理し回転記号だけのワンライナーにします。以下のような一文が1ソルブを表しており最終的に100行分のファイルになります。
x D F' R U R' y R2 D U R U R' U' R U R' y U' R U' R' U D' R U' R' D U R U' R' U R U' R' U R U' R' U U R U2 R' y U' R' F R U' R' F' R R U R' F' R U2 R' U2 R' F R U R U2 R' U
ここからはこれを処理していきます。
n-gramを抽出してみる
忙しい人向け要約
- まとまった指使いの参考になればいいなと思って4-gramを抜き出してみた
- スレッジハンマーが思ったより使われてなくて驚いた
- 頻出パターンの指使いを練習しておくと役に立つかもしれない
n-gram
n-gramとは文章の中にどんな単語やフレーズが含まれているかを調べる手法であり、検索や文章の分類、また自動的な文章生成などに用いられています。具体的には文章の中に含まれる、n連続の単語/文字のパターンが何回ずつ出てきたかを数え上げるという手法です。特にn=1,2,3のときをunigram,bigram,trigramと言います。
簡単に例だけ説明します。例えば次の文
日曜日が終わると月曜日がくる。
に対してunigram,bigram,trigramを適用すると以下のような結果が得られます。
unigram 日:3, 曜:2, が:2, 終:1, わ:1, る:2 ... ... bigram 日曜:1, 曜日:2, 日が:2, が終:1, わる:1 ... ... trigram 日曜日:1, 曜日が:2, 日が終:1, が終わ:1 ... ...
このような辞書をどでかい日本語文章のデータに対して作成すると「今日は」とか「歩いて」みたいな文字列がたくさん出てくることに気づいたり「ね折さ」みたいな文字列が出てきたらなんかおかしいということに気づけるというわけです。 今回やりたいのは前者の「よく出てくるものを特定」のほうで、上手い人のソルブによく出てくる動きを探してそれを意識的に真似すれば効率の良いソルブに近づけるのではないか！？というのが目論見でした。
セクシームーブ(R U R' U') やスレッジハンマー(R F' R' F) のように4手で名前のついているひとまとまりの手順があること、またあまり短いとそれぞれの違いがあまりなくうまい事特徴を見出せなさそうだと思ったため今回はn=4を採用しました。またR2 とR2' は区別せず、前処理段階で同じ動作として扱っています(書き起こしの際にR2' を使う人と使わない人がおり表記ゆれがあるため)。
結果
以下のようになりました。
まず驚いたことは、ほとんどRもしくはUの組み合わせのみで構成されておりLやFがほとんど使われていなかったことです。結果を見る前はスレッジハンマーは絶対に入ってくると思っていたのですが画面に映らないほど下のほうに追いやられていました。
上位が似たような手順ばかりでパッとしないなと思っていたのですがこの画像を見た方から「(利き手で素早く回すことのできる)RU系を中心に回すことがやはり大事」とのコメントをいただき、もしかして意識的にこれだけ徹底的にRU系で固めているのかと思うと世界チャンピオンの恐ろしさを感じました。先読みしまくって次のF2Lの形をある程度操作していてもおかしくない気がする...
もっとデータがあれば各個人ごとのソルブを集めてそれぞれの4gramを作ってみたいのですが、100ソルブ単位で解析されているキューバーはなかなかいないのが現状です。おそらく自分のソルブで作るのが早い気がするので、ao100を測りながらついでにデータも作ってみようかと思います。
Byte Pair Encoding
次はByte Pair Encodingを施してみます。これが最初に思いついてやりたかったものでした。
忙しい人向け要約
- 長さを4に限定せず柔軟に頻出パターンを調べる
- OLL、PLL(のようなもの)を抜粋できた
- 頻出パターンの指使いを練習しておくと役に立つかもしれない(再掲)
Byte Pair Encodingとは
Byte Pair Encodingは、ngramのような情報を抽出するためのアルゴリズムではなくどちらかというと情報圧縮のためのアルゴリズムです。また近年は機械翻訳のための前処理などにも利用されています。
一言で説明すると、「一番多く出てくる記号のペアを新しい記号に置き換え、それを一定回数繰り返していく」というアルゴリズムです。
例えば以下のような単語たちが出てきたとします。
lowest graetest biggest pig guess
この単語たちそれぞれに対して、アルファベットでbigramを取ると、「es」というペアが一番多く出てきています。そこでこれを新しい記号、例えば「1」とします。
low1t graet1t bigg1t pig gu1s (1 = es)
次に多いのは「1t」ですね。
low2 graet2 bigg2 pig gu1s (1 = es, 2 = est)
さらに「ig」をひとくくりにします。
low2 graet2 b3g2 p3 gu1s (1 = es, 2 = est, 3 = ig)
というふうに圧縮していくことができます。情報圧縮という観点で見れば長くて何回も出てくる記号列があるほど効果を発揮します。逆に辞書(対応表)を保持しておかなければならないので特徴のないデータに対して行うと損になってしまう気もしますが...
圧縮の際に作成された辞書を見ることで副次的によく出てくるパターンを知ることができます。パターンの長さが固定されているngramと違い柔軟に抜き出してくることができます。
結果
ということで、この処理を上で集めておいたデータセットに対して行った結果が以下のような辞書を作成できました。 もう少しデータセットを増やしたいと思い、トッププレイヤーの一人であるJayden Mcneilのソルブを50個引っ張ってきて追加してあります。
番号が若いほど先に出てきた(=頻度の高い)パターンです。1始まりでないのは元のデータにR2などが混ざっているからです。さすがにFazやJaydenはR4,U5みたいなソルブはしないでしょう....
流石に2手のパターンが先に出てくるのは当然としか言えないのですが、上位に食い込んでいる4手パターンなどはやはり相当頻出な手順ということですね。
また、データの中で3回以上出現したものという縛りを付けたうえで得られた辞書を、パターンの長さ順に並べてみました。
キューブをしている人で勘のいい方なら気づくかもしれませんが、長い系列なのによく出てくるということはOLLやPLL(キューブを早く揃えたいと思っている初級者~中級者あたりの人が覚える特定の手順です)などが該当する可能性があるということです。
実際に目視で確認してみると、いくつかのパターンが発見されました。
目論見通りOLL,PLLのようなものが抜き出せており喜んでいます。
この下にも何種類もパターンがあるのですが全部を解説するのは難しいので後ほど整理して上げておこうかと思います。
気になる方は見てください。
終わりに
まず、途中からキューブそろえたことない人を置いてきぼりにする解説になっていてすみませんでした。
さすがに逐一解説していくのは無理でした... 深く知りたい人はキューブを買って始めてみよう！
思いつきでやってみた作業でしたが予想以上に楽しかったです。 身近にあるデータを定量的に解析してみるのは面白いですね。
せっかく上手い人のソルブを解析したので自分の上達にも活かせたらいいなと思っています。
ただ作業をしていて実感したのはもっとデータが欲しいということですね。
webから自動収集する方法を考えてもいいのですが 、不特定多数のキューバーから自分のソルブを入力してもらうのが楽なんじゃないかなあと思います。
実はせっかくデータを集めたのでついでに「機械学習の手法を用いてCFOPかRouxかを判断する」というものも作ったのでそれを皆に遊んでもらえる形にしてついでにデータ収集も行えたらいいなと考えています。
とりあえず記事にはしますがアプリケーションを作るのは先になりそうです。
何はともあれここまで長い文章を読んでいただきありがとうございました。
もし次もあればお願いします。
