ルービックキューブは26手以内で揃う！ 114
ストーリー by GetSet
昔は体が解法を覚えていたんだがな… 部門より
昔は体が解法を覚えていたんだがな… 部門より
37A 曰く、
マイコミジャーナルによると、 米ノースイースタン大学のコンピュータ科学部の教授と大学院生が、「ルービックキューブは26手以内で揃う」ことを証明したそうです。
これまでは、どんな状態であっても27手以内というのが証明されていましたが、それよりも1手少なくできるとのこと。
実証は、7テラバイトのディスクをRAMの拡張として使用し、秒間1億回のシミュレーションが可能なコンピュータで行ったとのこと。これにより、「ルービックキューブをどのような状態からでも26手以内に揃えられるソリューションを、およそ1秒程度のスピードで見つけ出せる」と豪語しています。
さて、日本の皆さん、クリックしている場合ではありません。これを超える「25手以内」を証明してみませんか？
1).6色のペンキを用意する 2).白を塗る 3)...... (スコア:4, すばらしい洞察)
なぜクリックの話が、と思ったらルービックってハンガリー発なのね.... [wikipedia.org]
Re:1).6色のペンキを用意する 2).白を塗る 3)...... (スコア:2, おもしろおかしい)
#誰もが思いつくけどあえて口にしないネタなのでAC
ディスクIOのネックが課題かなぁ (スコア:3, 参考になる)
自宅でこの手の総当り検証をみてやらせたときは、ディスクが遅すぎで困ったよ。
ラプター + デフラグ + なるだけシーケンシャルな読み込み を心がけても遅いものは遅い。
#資金の問題で RAID0は試していない(w
1CPUで50%以下を常にアプリが食べていて、残りはどうみてもディスクIO待ち。
ひたすらガリガリってアクセス音だけが永遠となりつづけた。
データが数十ギガバイト以上になると i-RAM とかも利用できないし。
数十年後には7TBのメモリがつめるようになって、一瞬で問題が解決できるようになるのかねぇ。
Re:ディスクIOのネックが課題かなぁ (スコア:2, 興味深い)
＞ラプター + デフラグ + なるだけシーケンシャルな読み込み を心がけても遅いものは遅い。
＞#資金の問題で RAID0は試していない(w
総当たりをする、という事が目的なんだったら
ディスクを早くするしかないんですが、
単に探索の為に総当たりをしているのだったら
(ルービックキューブもそうだと思いますが)
データ構造や、アルゴリズムの方を改良した方がいいですよね。
RAID0を使ったところで、全読み込みをするというのであれば高々2倍にしかならないのですから。
それよりは、読むデータを1/10に絞り込む方法を考えた方が余程効果的です。
色々頑張ってどうしようも無くなったときは・・・
その時こそハードでごり押しですね。
# でも、最近ごり押し出来ることが多くなったなぁとは思う
えーと (スコア:2, おもしろおかしい)
Re:えーと (スコア:3, おもしろおかしい)
妖精哲学の三信
「だらしねぇ」という戒めの心、「歪みねぇ」という賛美の心、「仕方ない」という許容の心
Re:えーと (スコア:1)
壊れるから止めましょう。
…シールを剥がして貼り直すのは一枚1手です。
Re:えーと (スコア:1)
どうだっ。
Re:えーと (スコア:3, おもしろおかしい)
Re:えーと (スコア:2, すばらしい洞察)
１．冷蔵庫を開ける
２．揃ってるルービックキューブを取り出す
３．揃ってないルービックキューブを仕舞う
４．冷蔵庫を閉める
Re:えーと (スコア:2, おもしろおかしい)
Re:えーと (スコア:1)
2.手品用の帽子から出す
Re:えーと (スコア:1)
１つの面には９個のパーツが面していて、色は全部で６種類。
各面に６つの色をすべてが含まれる状況を作った場合、各面最低５つを付け外ししなければいけなくなる。
すると、５×６面で、最低３０個の付け外しが必須になる状況を作り出せる。
３０個を付け外ししたばあい、６０手必要。
ということで、「付け外しだけ」でやると、６０手以上必要な状況がありえる。
Re:えーと (スコア:1)
ルービックキューブのブロックは26個です。
＃26手内というのは偶然の一致？
Re:えーと (スコア:1)
面の中央のパーツと、２面に接しているパーツを４つ、角のパーツを１つという組み合わせで、先ほどの条件を満たすとする。
一番効率の悪い中央のパーツに色を合わせる事が出来たとすると、付け外しするパーツは全部で１４個になる。
Re:えーと (スコア:1)
# ボタン一つでバラければいいんだけどねぇ。
# っつーかそれじゃ力いっぱい本末転倒・・・
最強の一手 (スコア:1, すばらしい洞察)
と宣言。
一方日本は (スコア:1, おもしろおかしい)
Re:一方日本は (スコア:3, おもしろおかしい)
リセットボタンで自動的に初期状態に戻る機能を追加するのでは
これで家庭に復旧諦めたキューブが埃かぶることもないですしw
#詳しくないので実現できるか不明…どこかの工学屋さんが趣味で挑戦しないかな。
Re:一方日本は (スコア:2, 興味深い)
http://www.khi.co.jp/kawasakiworld/ht_flash.html [khi.co.jp]
妥当なような気がする (スコア:1)
世界チャンピオンの手順は最適化されているような気がして来た。
# 人間の可能性ってすごい。
Re:妥当なような気がする (スコア:1, 興味深い)
世界チャンピオンでも５０手ぐらいは回しています。
パターン認識と、手順の高速化で10秒台に迫っているのです。
Re:妥当なような気がする (スコア:3, 興味深い)
すぐそばにスピードキュービング日本ランキング一桁が居るので聞いて見ました。曰く、
「だいたい50～60手ぐらいですよ」
との事。
公式ルールでは揃った状態から25手崩した状態で競技開始するらしいのですが、
「あんまり少ない手数が証明されちゃうとルール変えなきゃならなくなるかもですね」
とも言ってましたｗ
ところで (スコア:1)
---
24時間以上起きている頭でスゴイ桁の数字見るとくらくらする・・・
リベンジは68手以内 (スコア:2, 興味深い)
解析方法の概略は自分の日記 [fastwave.gr.jp]に少し書きました。
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
Re:シミュレーションでは証明にならない (スコア:2, すばらしい洞察)
Re:シミュレーションでは証明にならない (スコア:1)
全て揃った状態を、木構造のルートとして、
次の一回の９０度回転操作でできる状態をその子として、
また、次の一回の・・・・・・・・・・・・・・・・・・・・、
を繰り返せば、２６回目の操作までに全ての状態が出現する。
証明終わり。
ところで、ルービックキューブが取り得る状態の数っていくらだ？
６＾５４－回転対称分だから・・・・
ううっ、出直します。
Re:シミュレーションでは証明にならない (スコア:2, 興味深い)
(回した後に回転面を床につければ同じ状態になる)
回す方向は鏡面とすると、無視して考えられる。
最初の一手目は「完成形から一回回した状態」の一パターンしかないので、
完全に揃ってる状態ではなく、一手目を木構造のrootにできるかもしれない、などと思ったり。
#書いた後に不安になってきた。いいのかな？(笑
Re:シミュレーションでは証明にならない (スコア:1, 興味深い)
到達した状態を管理するのにもメモリが大量に必要になります。
逆に不揃いから揃える方向ならば、6面が揃ったというチェックは簡単に実装できます。
また初期状態の全パターンは再帰を使えば簡単に生成できるのでメモリコストは少しですみます。
その各状態から26手まで総当りですが、26手を総当りで試して、26手以内に6面揃えばその初期パターンは26手以内であると確認されるので打ち切れます。
これも再帰を使えば26手までは十分試せるでしょう。
これである初期状態から26手総当りを行っても6面が揃わなければ26手以内では揃わない初期状態があると証明できます。
#どっちにしても計算量は膨大ですね
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
(というか逆方向を取る時点で枝切りされる)
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
こっちのページ [physorg.com]には論文へのリンクがあります。これから読んでみます。
ちなみに世界選手権でいちばんメジャーな解法である「LBL法」では平均56手くらいです。
自分で解きながら数えたこともありますがおおむね50～60手くらいです。
最小手数を競う競技もあります。
紙と鉛筆だけを使って1時間以内に見つかった解の手数を使います(公式ルール [jrca.cc]内のArticle E参照)。
公式世界記録 [worldcubeassociation.org]では28手、非公式記録 [speedcubing.com]では21手というのが今日現在の記録のようです。
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
そこまでの最大手数、そこからの最大手数の和を計算したそうです。
最後のひと工夫でさらに3手縮めているところがミソのようですがまだ理解できていません。
Wikipediaの記事 [wikipedia.org]では、ルービックキューブの最短手数探索法について、
Thistlethwaiteによる4段階法、Kociembaによる2段階法が解説されています。
CoopermanとKunkleの方法は、同じように表記すれば、
G0=<L,R,F,B,U,D>
G1=<L2,R2,F2,B2,U2,D2>
と部分問題を設定した場合に相当します。
CoopermanとKunkleはcosetの要素全体に対して総当たり的に到達可能手数をさがしています。
このような方法だと、必ずG1を通るような経路しか計算していないので、手数のupper boundしか得られません。「G1を通れば26手で解ける状態」にも、G1を一度も通らないようなより短い手数が存在する可能性が残ります。
高田馬場から東京まで、東西線を必ず使うとして、大手町へ出るとか九段下へ出るとか、全部の場合を調べて遅くとも何分で着く、とはわかった。しかし東西線を使わない場合(JRだけとかタクシーとか)は調べていない、というような感じ。
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
最後のひと工夫 (三手縮める) は Kociemba の Cube Explorer で brute force をかけました、ということでしょう。Section 7.3 のまんまです。
Re:シミュレーションでは証明にならない (スコア:1)
Re:シミュレーションでは証明にならない (スコア:1)
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
天気予報は気象モデルを作ってごにょごにょするので、シミュレートしていると言える。
ルービックキューブについてなら、このパズルの本質は各キューブの配置と移動のさせ方のみであり、モデルはそのままルービックキューブ本体であると言える。
実物と同じ振る舞いをするものはエミュレータと呼ばれる。
この場合は「ルービックキューブをエミュレートして解法を探索した」と表現すべきかと。
Re:シミュレーションでは証明にならない (スコア:1, おもしろおかしい)
Re:シミュレーションでは証明にならない (スコア:2, おもしろおかしい)
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
バグの可能性も否定できないので、数学による証明が待たれます。
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
数え上げが数学ではない。という論調が見受けられますが、それは間違いです。
事実が証明できるなら、それは数学です。
エレガントではない、エレファントな解法だ。ってことで好まれないことは事実ですが。
それに、背理法や帰納法だって、最後に待っているのは数え上げでしょ？
かのガウスも、この手の数値実験を好んでいた。といわれています。
Re:シミュレーションでは証明にならない (スコア:1, 興味深い)
四色問題については、「四色問題の証明の『正しさそのもの』を計算機が対話的に検証する」という取り組みがなされています。
同様の手法により、『「ルービックキューブは26手以内で揃う」の証明は正しかった」ことを計算機で実証する人も現れるでしょう。
# 科研費をこのネタで申請するのでAC
Re:シミュレーションでは証明にならない (スコア:1)
「シミュレーションした」と「総当たりした」は，全然違うことだと言いたかったのですが． シミュレーションすることは，証明するための必要条件でも十分条件でもありません．
Re:シミュレーションでは証明にならない (スコア:1)
最低18手 (スコア:4, 参考になる)
まず、状態数は、角(3面見えている)が8個、辺(2面見えている)が12個のピースがあるので、辺のピースを1つ固定するとすれば、38 x 212 x 8! x 11! = 43 252 003 274 489 856 000 通りあります。
最初の1手は18通りの選択肢 (36じゃないですよ) があり、2手目以降は15通りです (17通りでもないです)。ここから、17手以上必要あることが分かります。あとちょっと工夫すると、17手では不足で18手必要というのが分かるようです。
Re:最低18手 (スコア:2, 参考になる)
を証明はできていない，ってんだから18手が要る事は証明されてんでは？
#確か17手で到達可能な全状態数と，ルービックキューブの取り得る全状態数を比較して後者の
#方が大きいから最低でも18手は必要，っていう証明だった気がする．
Re:あながち間違いじゃないな (スコア:2, 参考になる)
ルービックキューブ [wikipedia.org]
しかし、14-15パズル [wikipedia.org]のようにあり得ない配置もあるかもしれないので、単純ではないかも。
Re:あながち間違いじゃないな (スコア:2, 興味深い)
あり得ない状態を数えないでこの数字です。
最後に2で割っているのは、面を回すと辺の置換と角の置換が同時に起こることから来る制約です。
このあたりはHerbert Kociembaのページが詳しいです。
http://kociemba.org/cube.htm
左フレームの「The Mathematics behind Cube Explorer」以下を読みましょう。
手とり足とりわかりやすく解説してくれています。
Re:えっ、 (スコア:1, おもしろおかしい)
Re:丁度良い絵が (スコア:2, おもしろおかしい)
白２面はありえる状態でした。
なので、このキューブは揃えられる可能性が残っています。