目黒キューブフェスト2015 — FMC競技後研究

本記事は、Speedcubing Advent Calendar 2015 の16日目の記事です。
昨日の記事は、CubeVoyage による「クロスの素早い作り方」でした。 明日は Morooka 氏の記事が公開される予定です!楽しみです!

先日 2015年12月13日 (日) に東京都目黒区で開催された「目黒キューブフェスト2015」のFMC競技の反省会をしましょう (WCAリンク: FMCの結果)。 個人的に不満足な結果 (DNF) を残してしまったので、他の競技者の解答を見せてもらったり、本番のスクランブルを研究したりして、今後の競技につなげたいと思います。 本記事では、情報を提供してくださった当日の選手の解答と私の解答を紹介した後、私がいろいろ試してみた結果を報告します。

Read more »

Fewest moves challenge と God’s number

cube20

先日、2015年10月11日にアメリカ合衆国カリフォルニア州アーバインで開催された Irvine Fall 2015Tim Wong 氏が Fewest moves challenge (FMC: 最少手数競技) で 19手 という大記録を達成し世界記録を更新しました。

これまで Fewest moves の世界記録は 20手 で、保持者は

の2人でした。

はじめに (God’s number)

3x3x3キューブ (ルービックキューブ) の God’s number と呼ばれる数字が存在します。

Thumbnail of Google Helps Find Simplest Solution to Rubik’s CubeGoogle Helps Find Simplest Solution to Rubik’s Cube
WIRED
No matter how mixed-up it is, the Rubik’s Cube can be solved in 20 moves or fewer, say a team of researchers who used computer time donated by Google to run complex algorithms to prove it. That means all the 43,252,003,274,489,856,000 positions of the Cube require no more than 20 steps to get the Cube…

God’s number が 20 であるということは、つまりひとことで言うと、
「どのようにスクランブルされた3x3x3キューブでも必ず20手†1以内で完成できる」
ということです。

†1 注釈: ここで言う20手とは HTM (Half Turn Metric) すなわち90度回転・180度回転をともに1手と数える世界での話です。本記事ではHTMのみを考えます。 なお、QTM (Quarter Turn Metric) での God’s number が 26 であることが2014年8月に証明されたのですが (結構最近!)、その話は気が向いたらいつかしたいと思います。 今回はHTMのみを考えます。

Wong 氏の19手という記録は公式大会では初めて God’s number を上回ったことから、 キューバーの間では「神を超えた (sub God)」というジョークがかわされています。

さて、公式大会で God’s number を上回る数字を出したということで、次のような疑問が生じてきます。

Questions:
  1. God’s number is 20 だから、『絶対に』WRを出せない (すなわち、20手未満の解答が存在しない) スクランブルに遭遇してしまう可能性はないのか?
  2. 『絶対に』WRを更新できない (すなわち、19手未満の解答が存在しない) スクランブルに遭遇してしまう可能性はどうなのか?
  3. FMCで出題されたスクランブルからの20手以内の完成手順は一体何通りぐらいあるのか?
  4. FMCで出題されたスクランブルからの19手以内の完成手順は一体何通りぐらいあるのか?

本記事はこの4つの質問に答えていこうと思います。 先に答えを書いてしまうと、

Answers:
  1. そのような確率は 限りなく0に近い (ジャンボ宝くじで1等当選よりずっとずっと低い確率)
  2. 残念ながらこれは起こりうる確率があって、約3%
  3. ランダム状態からの20手以内の完成手順は平均して 約1000通り (ただしこれはかなり大雑把な数字、詳細は後述)
  4. ランダム状態からの19手以内の完成手順は平均して 約80通り (ただしこれも結構アバウトな数字、詳細は後述)

Read more »

Roux始めた

そいえば、Roux method 始めました。

ちなみにすでに公式大会でRouxで解いたことあります (2015-10-13 東北大会 333 1st round)。

動画投稿したら、あさくらもちょさんがコメントしてくれました。

roux-beginner-comment

そだよね〜(o・∇・o)

Read more »

プログラミング言語によるルービックキューブ (3x3x3) ソルバ実装まとめ

raspberry-pi-cube-solver

本記事では、ルービックキューブ 3x3x3 のソルバ (解法プログラム) の実装をまとめます。同時にスクランブルジェネレータ (スクランブル生成プログラム) も紹介します。

ソルバとスクランブルジェネレータの関係

紹介の前に、ソルバとスクランブルジェネレータの関係を簡単に述べておきます。
パズルのスクランブルジェネレータはソルバに強く依存しています。 というのも、ソルバが存在すればランダムステートなパズルの状態から完成状態に至る手順Sを求めることが可能となり、Sの逆手順S’が完成状態からそのランダムステートへのスクランブルシーケンスとなるためです。逆手順を求めるのは一般に容易 (自明) であるため、ソルバが確立されればスクランブルジェネレータも同時に完成できる、と言うことができます。
よってルービックキューブパズルのソルバとスクランブルジェネレータには強い関係があります。

今回紹介する全てのソルバのアルゴリズムは、現在3x3x3ルービックキューブの最も効率的な解求アルゴリズムである “Kociemba’s Two-phase Algorithm” にもとづいています。コンピュータとルービックキューブ解求アルゴリズムについては以前記事を書いたのでよろしければそちらをご覧ください。

Thumbnail of ルービックキューブをアルゴリズムで解くということルービックキューブをアルゴリズムで解くということ
terabo.net
ルービックキューブを解くアルゴリズムについて書きます.この記事では具体的なアルゴリズムの話はありません.(情報工学的アプローチでの見方です.ルービックキューブを解くアルゴリズムは「群論」とも深く関わりがありますが,私は情報工学系の人間なので...

それでは、ルービックキューブ (3x3x3) ソルバ / スクランブルジェネレータをプログラミング言語ごとに紹介していきます。

Read more »

Insertion Finder コンパイル方法 (CentOS 6)

FMCer にはおなじみの Insertion Finder (通称 IFたん)。
ソースコード公開されてないかなって思ってたら、@uesyuu さんに教えてもらいました (見つけてくれました)。

(古い) Insertion Finderhttp://xuanyan.ws/cube/insertionfinder/

2016-08-01 追記:
上に書いたURLはもう使われていないようです。最新版のソースコードはGitHubにアップされています。
https://github.com/xuanyan0x7c7/insertionfinder

Linux 32bit/64bit 向けにバイナリも配布されていますが、自分で機能を追加したり、カスタマイズすることを考えて自分でコンパイルできるようにしておきたいです。
本記事では、Insertion Finder のコンパイル方法を説明します。 環境は CentOS 6.7 ですが、CentOS 6 なら他のバージョンでも多分同じようにいけるはずです。

2016-10-21 追記:
Cygwinでのインストール方法の記事を書きました。
Insertion Finder コンパイル方法 (CentOS 6)

Read more »

各国のキュービングコミュニティサイト一覧

ルービックキューブの公式大会は World Cube Association (WCA) が代表して管理するポリシー、規則等によって実施されますが、 世界各国はローカライズ化されより現場に近い立場で大会やイベントを運営(大会告知ページとレジストレーションフォームの提供を含む)をしやすくするためや、 普及活動や競技者同士のつながりを支援するために、 多くの場合そのような目的の団体または機関(ここではそれをキュービングコミュニティと呼ぶ)を有しています。 日本の場合、Japan Rubik’s Cube Association (JRCA) がこれに該当します。

本記事では、キュービングコミュニティの一覧をリンク集として示します。 地域の区分は WCA Delegates | World Cube Association に準じています (一部変更)。 追加希望等がありましたら @kotarotrd までご連絡ください。

Read more »

黒素体派?白素体派?

black-and-white-texture

Black and White. Photo from freedigitalphotos.net by prkatarina.

アメリカのキューブを扱うECサイト e3cubestore がInstagramに黒素体と白素体のチェッカーキューブの画像を投稿しています。
恐らく同じ種類のキューブを組合せているものだと思われますが、大きさが違ってガタガタしているように見えます。

Checkerboard! Awesome! @jakerokop #e3cubes #e3cubestore #cubeart #puzzle #speedcube #speedcuber #speedcubing #rubic #rubik #rubix #rubics #rubiks

E3cubestoreさん(@e3cubestore)が投稿した写真 –

Read more »

【多分初心者向け】ルービックキューブ目隠し練習用ツール

本記事では、最近スピソルに投稿されたルービックキューブ目隠し練習用補助ツールを2つ取り上げて紹介します。
Letter Pair Generator」と「ScramBLD」を紹介します。

そもそも目隠しプレイってどうやってやるかとかは以下のサイトらへんを参考にしてください。

ツール紹介記事シリーズ化!?

最近、スピソルのフォーラム (speedsolving.com) を定期的にチェックするようにしています。 具体的にはRSSで新規スレを取得してFeedlyで見ています。

特にソフトウェア板では、面白そうなツールがよく投稿されます。 以前の記事「Web上でルービックキューブをアニメーションする CSS/javascript まとめ」を第1弾ということにして、今回の記事は第2弾、今後自分が気になったツールを不定期で紹介していこうと思います。

今回は、ルービックキューブ目隠し練習用補助ツールである「Letter Pair Generator」と「ScramBLD」を紹介して、所感を述べます。 どちらも本記事公開日の数日以内にスピソル投稿されています。

Read more »

Web上でルービックキューブをアニメーションする CSS/javascript まとめ

Algorithm: Superflip -> Solved-State

Webブラウザ上でルービックキューブをアニメーション表示する方法まとめです.
ルービックキューブをアニメーションする CSS/javascript ライブラリやサイトを紹介します.私の知る限りすべて書いています (2015-03-18 時点 6個掲載)
Web上にルービックキューブをアニメーションを表示することで,文字列だけでは不足するアルゴリズムの視覚化,デモンストレーションによるWebサイトの装飾等が実現可能となります.

CSS/javascript でルービックキューブをアニメーションするといっても,手順を表示するのが目的であったり,ユーザがキューブを操作して画面上のキューブを完成させることが目的であったり,単に回転するキューブを表示させることが目的であったりと,ライブラリ/サイトによって目的は様々ですが,CSS/javascript でアニメーションを実現するというくくりで本まとめではまとめて紹介します.ご自身のやりたいことに合うように適切なものを選択して,それをベースにカスタマイズしてご使用ください.ただしライセンスには気をつけてください.

私も実際にトップページにキューブのアニメーションを配置してみました.後述するRoofpigを使用しています.

ここでは,例えばキューブ画像を表示するライブラリとして有名な VisualCube [1] のように回転アニメーションを伴わないもの,環境によって表示が不可になるjavaアプレットを使用したようなもの [2, 3, 4, 5] ,非常に完成度の高いCSSで実現されているがオープンソースでないもの [6] 等は対象外です.

[1] VisualCube (v0.5.2), http://cube.crider.co.uk/visualcube.php
[2] Virtual Cubes Rubik’s Cube | Instructions | Instructions, http://www.randelshofer.ch/rubik/virtual_cubes/rubik/instructions/instructions.html
[3] Rubik’s Cube Java Applet, http://www.schubart.net/rc/
[4] Jelinek’s Java Applet for the Rubik’s Cube Animation, http://software.rubikscube.info/AnimCube/
[5] Rubik’s Cube Java Applet program, http://ruwix.com/the-rubiks-cube/rubiks-cube-java-applet-software-program-josef-jelinek-animating-rubix/
[6] Rubik’s Cube – Google, http://www.google.com/doodles/rubiks-cube

それでは,紹介していきます.
新たなライブラリ/サイトが公開された等の情報が更新され次第,できるだけ随時このページを更新します.

Read more »

宇宙一馬鹿げたルービックキューブの解き方

去年の記事「ルービックキューブをアルゴリズムで解くということ」に続き,ルービックキューブとアルゴリズム ネタシリーズ第2弾です.
今回は宇宙一無駄な努力をしてルービックキューブを解く方法です.

無駄な努力

スピードキューバ(ルービックキューブを早く解くことを追求する人たち)には常識的に知られていることですが,ルービックキューブは容易に分解できます.

したがって,未完成状態のルービックキューブを分解して,物理的に組み上げることでルービックキューブを完成させることができます.
この一連の操作を目をつぶった状態で実行するとどうでしょうか.
それは多分一生完成しないだろうと予想されるでしょう.全くその通りです.
この手法は言い換えると次のようになります.

アルゴリズムBG:
入力: スクランブルされたキューブ
出力: 完成状態のキューブ
(Step 1) ルービックキューブのパーツを分解する.
(Step 2) 分解したパーツをシャッフルする.
(Step 3) シャッフルされた順にキューブを組み上げていく.
(Step 4) キューブが完成したら終了,完成しない場合 Step 1 に戻る.

コンピュータサイエンスを(ネタ的に)知っている人ならピンとくると思います,これはボゴソートに対応します.

ボゴソート (英語: bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。 ボゴソート – Wikipedia より

こんなの終わるわけないやんと思いますが,「無限の猿の定理」により十分長い時間をかければ完成することは示せます.
完成までの試行回数(キューブが組み上げられた回数は)は平均で $ T_{bg} = (8! \cdot 3^{8} \cdot 12! \cdot 2^{12}) / 2 = 259512019646939136000 $ 回です.
これはエッジの位置と向き,コーナーの位置と向きの全パターンの半分です.
平均がなぜ半分でいいのかよくわかりませんが,以下の文献でそう書いてあったので半分にしてます.
参考文献: Bogobogosortについて – w125のブログ

さて,1回キューブを組み立てるのに1分要すると仮定します.
すると完成するのに 259512019646939136000分 かかる計算になります.これは,493744329617464年,すなわち 493兆7443億年です.
ちなみに地球が誕生したのは46億年前,宇宙が生成されたのが138億年前とされています.

以下の文献により,「無限の猿定理」で最も例に取り上げられる,1秒間に10万文字タイプできる猿がハムレットを執筆するのに $ 10^{360790.5} $ 年要するとされていますので,ハムレットを書くのとルービックキューブを揃えるのは確率的にはルービックキューブを揃える方がずっとずっと簡単なのです.
参考文献: 時間の比較 – ニコニコ動画:GINZA http://www.nicovideo.jp/watch/nm16202721

最良で1回の試行回数で完成しますが,この確率は限りなく0に近です.最悪の場合の試行回数は無限大です.

めげない努力

一旦ばらばらに分解してから組み上げるのはさすがに馬鹿すぎるでしょう.
ちゃんとルービックキューブのパズルらしく面を回転させて完成させます.
しかし,回転させるといってもどの面をどの向きに回転させれば揃うのか一向に見当がつきません.

そこでとりあえずやみくもにトライしてみるとします.
この手法は言い換えると次のようになります.

Read more »