パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

余剰CPU時間を使ってルービックキューブは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
      「ランダムな状態」も、あんまり崩れてない状態を含むでしょ。

開いた括弧は必ず閉じる -- あるプログラマー

処理中...