パスワードを忘れた? アカウント作成
24880 story
おもちゃ

余剰CPU時間を使ってルービックキューブは23手以内で揃うと証明 39

ストーリー by nabeshin
絞り込みは計算リソース次第 部門より
mad-p 曰く

3月に「ルービックキューブは25手以内で揃う!」というトピックがあったばかりですが、そのTomas Rokickiが今度は上限を一気に2手下げて23手としました。キューブフォーラムの記事によると、前回と同じ方法で、Sony Pictures Imageworksのレンダリングファームの余剰CPU時間を使い、約7.8コア・年分の計算時間をかけて、ルービックキューブのどんな状態からでも最大23手で完成できることを示したそうです。このレンダリングファームはスパイダーマン3やSurf's Upの制作に使われました。

今回の探索でも21手必要なキューブ状態は発見されていません。対称形の考察などから上限は20手だろうと予想されています。同じアルゴリズムでこれを証明するには、3500コア・年のCPU時間が必要になるとRokickiは見積っています。さらに速い探索手法が考案されるのが早いか、ムーアの法測で計算機が速くなるのが早いか、さてどっちでしょうね。

参考:
公式ルール(ランダムな25手からランダムな状態に改訂された)
WikiPedia:ルービックキューブの最適解法
Cube Explorer
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by qem_morioka (30932) on 2008年05月08日 17時29分 (#1341075) 日記
    と7000コア準備して半年で解いてしまうとか。

    #あーあ・・・
  • by Anonymous Coward on 2008年05月08日 18時17分 (#1341093)
    dvipsの人?
  • by dodonga (4178) on 2008年05月08日 19時45分 (#1341121) 日記
    dodongaです

    > 今度は上限を一気に2手下げて23手としました。

    これは、”下限”では?と言って見るテスト
    --
    閑話休題
    • 上限 (Re:むしろ) (スコア:4, 参考になる)

      by fcp (32783) on 2008年05月08日 22時02分 (#1341189) ホームページ 日記

      > 今度は上限を一気に2手下げて23手としました。

      これは、”下限”では?と言って見るテスト

      上限で合っています。でも、この手の話に慣れていない人は混乱するかもしれませんね。

      問題となっているのは、完璧な (=常に最小手数を達成する) プレイヤーは何手使えばどの状態からでも揃えられるかです。この問題に対する答えは「神の手数」 (God's Number) と呼ばれることがあります。今まで「神の手数」は 20 以上 25 以下とわかっていたところ、今回 20 以上 23 以下に改善されました。なので、「神の手数」の上限が 25 から 23 に改善されたということです。

      親コメント
  • by Anonymous Coward on 2008年05月08日 16時32分 (#1341051)
    ランダムな25手とランダムな状態はどう違うのでしょう?
    ランダムな25手だと、あんまり崩れていないケースも
    発生するということでしょうか?
    • Re:ランダム? (スコア:3, 参考になる)

      by mad-p (1491) on 2008年05月08日 20時20分 (#1341134)
      ランダムに25手回した後、方向が反転している辺の数を数えて、理論的な分布と比較すという実験が去年行われました(Lucas Garronによる解析 [yahoo.com]、Herbert Kociembaによる解析 [yahoo.com])。40手でも十分なランダム性が得られません。

      改訂されたルールでは、これら4つの座標値をランダムに選んでキューブ状態を作ります。実物のキューブでこれをやるは、いったん部品にバラして組み立てるのがわかりやすいでしょう。そんな方法では大会競技進行に間に合わないので、あらかじめCubeExplorerで準最適解を求めておき、その逆手順でくずします。

      余談ですが、Kociembaの解析の中で、CubeExplorerが「ランダムに座標値を選ぶ」アルゴリズムにバグがあったことが発見されています(座標の上限値が間違っていた)。CubeExplorerは現在、公式ルールで認定されたスクランブラ生成プログラムとなっています。
      親コメント
      • Re:ランダム? (スコア:3, 参考になる)

        by mad-p (1491) on 2008年05月08日 21時04分 (#1341155)
        すいません、推敲してる間に変になっちゃいました。

        「ランダムな状態」とは、ルービックキューブの取り得る状態(4.3×10^19通り)のうちのひとつを等確率で選ぶということです。

        「ランダムにn手回す」のでは、すべての状態が等確率に出現することはなりません。nが十分大きければ「実用上」問題ないレベルにできますが、その「実用上」を「危険率1%」に設定するとn=40でも不足ということです。

        以下の4つの状態を座標と考え、それぞれランダムに選ぶと、ランダムな状態を等確率で生成することができます。
        - 角キューブの方向(3^8/3)
        - 辺キューブの方向(2^12/2)
        - 角キューブの順列(8!)
        - 辺キューブの順列(12!)
        (順列の偶奇性が角と辺とで常に一致する分、どちらかを半分に制限します)。
        親コメント
        • by Anonymous Coward
          ちなみにその4.3×10^19通りの状態中には「あと2手で揃ってしまう」とか「既に揃ってしまっている」といった状態のキューブも含まれると思うのですが、そういったものを排除して難易度をそろえるためにどんな工夫や評価がされているのかも気になるところ。
          それとも、実用上はそんなもんは0.00001%未満の確率でしかランダムには出現しないのでしょうから、全く無視されているのでしょうか。
          • by Deasuke (34806) on 2008年05月09日 11時28分 (#1341388) 日記
            そういう場合は、きっとCubeExplorerを起動した人が「Shuffle」のボタンを押しそこなったと勘違いしてもう一度「Shuffle」のボタンを押すから大丈夫ですよ。
            --
            Best regards, でぃーすけ
            親コメント
      • by tama39 (35891) on 2008年05月09日 23時26分 (#1341690)

        改訂されたルールでは、これら4つの座標値をランダムに選んでキューブ状態を作ります。実物のキューブでこれをやるは、いったん部品にバラして組み立てるのがわかりやすいでしょう。
         1981年頃のI/Oに、解法が載っておりました。プログラムではなく、手順書のようなものでした。
         それを覚えたのち、揃えるところを披露し大喝采を浴びる算段だった当時の私。
         ところが、どうしても最後のエッジキューブ一つだけがそろえられない。

         大見得切った手前もあり、妙な汁が額に浮かぶ浮かぶ。

         聞くとバラけたので組み立てなおしたとのこと。
        # それは海賊版で、バラけやすかったのです。

         いや、ばらして組みなおしたら元に戻らないことがあるんだ、と判断しそう主張したのですが、
        深まる疑惑の視線、飛び交う野次、俺にやらせろうるさいだまれ、といった阿鼻叫喚の地獄絵図が
        展開され、どうやってそれを切り抜けたかは、よく覚えていないのでした。

         で、本題ですが、当時直感的に判断したその点に関しては、どうやら正しかったようで
        http://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%BC%E3%83%93%E3%83%83%E3%8... [wikipedia.org]

         ばらして組み立てたルービックキューブは、元に戻らない状態を取りうる、ということで、ひとつよろしくお願いします。
        親コメント
        • by mad-p (1491) on 2008年05月10日 0時05分 (#1341701)
          > ばらして組み立てたルービックキューブは、元に戻らない状態を取りうる、ということで、ひとつよろしくお願いします。

          ばらしたキューブを好き勝手に組み立てた場合は確かに元に戻る確率は1/12です。ここでは座標値の定義時にその分を考慮しています。

          #1341155 [srad.jp]より、太字部分で3×2×2 = 12です。
          >- 角キューブの方向(3^8/3)
          >- 辺キューブの方向(2^12/2)
          >- 角キューブの順列(8!)
          >- 辺キューブの順列(12!)
          >(順列の偶奇性が角と辺とで常に一致する分、どちらかを半分に制限します)。

          うっかりバラバラになったキューブを組み立てるとき、方向の制約を守るのは簡単ですが、順列の制約を守るのは割と難しいです。競技中にキューブが外れてしまうとあせります。とりあえず組み立てて進めた結果、完成できない状態になっちゃっていることもあるので、ルールでは一度だけ自分で外して正しくなるように組み立て直すことが許されています。この一度の組み直しで方向と順列の制約を両方直さないといけませんから、完成直前で直した方がいいですね。
          親コメント
    • Re:ランダム? (スコア:1, 参考になる)

      by Anonymous Coward on 2008年05月08日 18時01分 (#1341090)
      ・ランダムな25手
       →ランダムに25回回した状態
      ・ランダムな状態
       →ランダムにn回回した状態

      ということでは?

      親コメント
    • by greentea (17971) on 2008年05月08日 19時17分 (#1341115) 日記
      25手あればどのようなパターンにも持っていけることが分かっている今となっては、
      実質的には同じなのではないかと。
      --
      1を聞いて0を知れ!
      親コメント
    • by Anonymous Coward
      「ランダムな状態」も、あんまり崩れてない状態を含むでしょ。
  • by Anonymous Coward on 2008年05月08日 16時51分 (#1341058)
    私が解くと皆が平和になれるのか?
  • by Anonymous Coward on 2008年05月08日 21時29分 (#1341167)
    なんて云うと仰々しい物理法則みたいに聞こえるから
    あっちこっちで拝み奉る香具師がいるけど、単なるおっさんが見つけた
    傾向なんだからな。

    #あれのお陰でどれだけの人間が死ぬ思いで働いてると思ってんだ!!!!!!!

    • by Anonymous Coward on 2008年05月09日 6時52分 (#1341308)
      いや、単なるおっさんというよりインテルの創業者。
      つまりあれは法則ではなくミッションステートメント。もしくは業務命令。
      親コメント
      • Re:ムーアの法測 (スコア:3, すばらしい洞察)

        by nekopon (1483) on 2008年05月09日 12時43分 (#1341420) 日記

        おもしろいけど、LSIはインテル一社ががんばってできるものではなく、製造装置メーカーのがんばりもあってできるものだということを忘れないでほしいのです。

        # つまりアレはベンダーに対する叱咤激励(ひー

        親コメント
      • by Anonymous Coward
        さらに短いサイクルでフラッシュが倍化するとか言った人が半島にいるようだけど、どっちがつらいだろう。
    • by khwarizmi (23623) on 2008年05月09日 9時58分 (#1341360)

      あれは,科学の法則じゃなくて,社員を死ぬほど働かせた場合に企業体が,売り出すチップの性能をどれだけ向上させられるかという社会科学の法則ですので,正しいんじゃないですか.

      役所の人が死ぬほど働いても自分の予算を食いつぶすだけに終わること(パーキンソンの法則)を考えると,なんと生産的なことか

      親コメント
  • by Anonymous Coward on 2008年05月09日 9時38分 (#1341349)
    × ムーアの法測で計算機が速くなるのが早いか

    ○ ムーアの目標で計算機を速くするのが早いか

    科学者でもないのに偉そうに
typodupeerror

犯人は巨人ファンでA型で眼鏡をかけている -- あるハッカー

読み込み中...