terabo.net 人生ラボラボ
Fewest moves challenge と God’s number
先日、2015年10月11日にアメリカ合衆国カリフォルニア州アーバインで開催された Irvine Fall 2015 で Tim Wong 氏が Fewest moves challenge (FMC: 最少手数競技) で 19手 という大記録を達成し世界記録を更新しました。
Tim Wong (from USA) just got the 3x3x3 FMC single WR (19) at Irvine Fall http://t.co/2bucmuJgPR
— Cubecomps (@cubecomps) 2015, 10月 11これまで Fewest moves の世界記録は 20手 で、保持者は
- Rami Sbahi 氏 (2015年、Michigan 2015) ( 解法解説ビデオ)
- 岡山友昭 氏 (2012年、Czech Open 2012) ( 解法紹介ビデオ)
の2人でした。
はじめに (God’s number)
3x3x3キューブ (ルービックキューブ) の God’s number と呼ばれる数字が存在します。
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)」というジョークがかわされています。
神を超えた男 Tim Wong
— Kotaro Terada (@kotarotrd) 2015, 10月 11ついに神を超える者が現れたか…
— Morooka (@morooka_cube) 2015, 10月 12さて、公式大会で God’s number を上回る数字を出したということで、次のような疑問が生じてきます。
- God’s number is 20 だから、『絶対に』WRを出せない (すなわち、20手未満の解答が存在しない) スクランブルに遭遇してしまう可能性はないのか？
- 『絶対に』WRを更新できない (すなわち、19手未満の解答が存在しない) スクランブルに遭遇してしまう可能性はどうなのか？
- FMCで出題されたスクランブルからの20手以内の完成手順は一体何通りぐらいあるのか？
- FMCで出題されたスクランブルからの19手以内の完成手順は一体何通りぐらいあるのか？
本記事はこの4つの質問に答えていこうと思います。 先に答えを書いてしまうと、
- そのような確率は 限りなく0に近い (ジャンボ宝くじで1等当選よりずっとずっと低い確率)
- 残念ながらこれは起こりうる確率があって、約3%
- ランダム状態からの20手以内の完成手順は平均して 約1000通り (ただしこれはかなり大雑把な数字、詳細は後述)
- ランダム状態からの19手以内の完成手順は平均して 約80通り (ただしこれも結構アバウトな数字、詳細は後述)
Read more »
続・コンピュータ将棋が熱い！おもしろい！
数日前にコンピュータ将棋を知ったという記事を書きました。
そこでは、将棋のゲーム木は膨大なサイズだから、棋士の思考と単純に比較してコンピュータは不利であるようなことを考えてました。
その後、2015年4月4日に 第4局「村山慈明七段 vs. ponanza」 が行われました。
早速、棋譜が公開されています。
金井恒太五段による観戦記も公開されました (2015-04-11追記)。
結果は、ponanzaが勝利してコンピュータ将棋側が勝ったのですが、その対局に関して第3局で対局したやねうら王の開発者であるやねうらおさんが自身のブログで次のようなことを書いています。
Read more »
コンピュータ将棋が熱い！おもしろい！
電王戦FINAL
電王戦FINAL [1] というイベントが進行中です。棋士 vs. コンピュータの将棋対局です。 私はこれの第1局と第2局を見て、コンピュータ将棋の世界というのを初めて知りました。
第1局は「斎藤慎太郎 五段 vs Apery」でした。 結果は斎藤慎太郎五段の勝ち。 斎藤慎太郎五段の勝ちがほぼ確定してからのAperyの王手ラッシュは人間 vs. 人間の対局には見られない状況になったため、様々な意見が飛び交っています [2, 3] 。
第2局は「永瀬拓矢 六段 vs Selene」でした。 結果は永瀬拓矢六段の勝ち。人間側の2連勝です。 この対局では永瀬六段の角行の成らず（王手）と指したところでSeleneのアルゴリズムが想定外の動きをしました。 相手の角の自陣への成らずは局面として想定していなく、認識できずに別の手を指し王手放置でSeleneの反則負けという、なんだかこれまたコンピュータらしい内容でした [5, 6, 7]。
コンピュータ将棋は波乱しか起きないのか！ 私はすっかり面白さに取り込まれてしまいました。
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 »
ルービックキューブをアルゴリズムで解くということ
ルービックキューブを解くアルゴリズムについて書きます．この記事では具体的なアルゴリズムの話はありません．
（情報工学的アプローチでの見方です．ルービックキューブを解くアルゴリズムは「群論」とも深く関わりがありますが，私は情報工学系の人間なので群論は全くわかりません．）
※ この記事はルービックキューブを解くアルゴリズムの概念的なものを説明した記事です． 実際のルービックキューブを我々人間が解くやり方は以下のページをおすすめします．とてもわかりやすく書かれています．
ルービックキューブの解き方はじめに
まず，いくら時間をかけて良いという環境のもとであればルービックキューブを単に解くということは実は非常に簡単なタスクです．
ただ，それをいかに効率良く解くか，というのが非常に重要なことで，多くの人々の興味の対象でもあります．
その手順がアルゴリズムです．
本記事ではルービックキューブを解くアルゴリズムの概念を説明した後，既存手法を 1)人間的アプローチ，2)コンピュータ的アプローチのそれぞれでごくごく簡単に分析し，自分がこれから試してみたいことをまとめます．
Read more »