Kociembaチュートリアル — 準最適な解法
これは何か
このページは、すでに CFOP（または何らかのスピード解法）でキューブを完成できることを前提とします——面 / エッジ / コーナー / 層を知っていて、R U R′ のような記法が読めること。
Kociembaは人間用の解法ではなく、コンピュータによる求解アルゴリズムです：どんなスクランブルを与えても、数十ミリ秒で約20手の解を見つけ出します。人が同じキューブを解くには、通常50手以上かかります。
このページが扱うのは2つのこと：機械がどうやってあの驚くほど少ない手数に到達するのか（2フェーズ帰着）、そしてなぜ20が天井なのか（God's number）。
これは「学んで手で実行する」解法ではありません——覚えるべき手順セットも、ケースの見分け方もありません。コンピュータがどうキューブを準最適に解くかを理解するための概念ページです。
天井とその差
God's number = 20。これは数学的に証明された上限です：どんなスクランブル状態の3×3キューブも、20手以内で解ける——21手必要な状態はひとつもありません。
20が驚きなのは、その対比です：あなたが同じキューブをCFOPで解くと50〜60手。人間の解法は、最適からほぼ2倍離れたところにあります。
この差はどこから来るのでしょうか？ 人間は認識で解きます——有限のケースセット（CFOPなら57のOLL、21のPLL）を見分けて、暗記した手順を適用する。手数の上限は「記憶に保持できるケース数」で決まります。機械はその制約を受けません：数十億規模の状態をカバーする事前計算テーブルを探索し、短い解への経路を直接引き出します。認識には天井がありますが、探索には（ほぼ）ありません。
機械はどうやってそこへ至るのか
機械の強みは「各ステップでの賢い一手」ではありません——問題の帰着です。ソルブを2つのフェーズに分割します：フェーズ1（帰着）はキューブを特殊な制約を受けた形——部分群 G1 ——へ投げ込み、フェーズ2（求解）はそのずっと小さい空間の内側で仕上げます。G1の中では使える手が少ないぶん、解は本質的に短くなります。各フェーズはそれぞれ独自の探索を実行し、合わせた平均は約22手、25手を超えることはめったにありません。 下のデモがこれを再生します——手順ストリップ上のフェーズ1 / フェーズ2の境界線に注目してください：機械がそこで戦略を切り替えるまさにその場所です。
なぜ端から端までの探索ではなく、2フェーズなのでしょうか？ 大域的に最短の解を見つけるには、キューブ状態空間全体を探索する必要があります——直接探索には大きすぎる空間です。2フェーズに分割することで、各探索が事前計算テーブルでミリ秒で終わるサイズまで縮みます。帰着が計算可能性を買う——それがこのアルゴリズムの存在理由です。
形式的な詳細（興味のある人へ）
G1のムーブセット：G1部分群の内部では {U, D, R2, L2, F2, B2} だけが必要です——U/Dは自由に回せますが、R/L/F/Bは180度回転に制限されます。これが「G1の中で解が短くなる理由」の形式的な言明です：選択肢が少なく、短い解を探索できる範囲が広がります。
フェーズ1が帰着させるもの：フェーズ1は3つの座標を同時にゼロへ向かわせます——コーナーの向き twist(3⁷ = 2187) × エッジの向き flip(2¹¹ = 2048) × Eスライスのエッジ位置 UD-slice(C(12,4) = 495)。その積は約 22億——フェーズ1の座標探索空間です。
|G1|（部分群の位数）：帰着後の部分群は約 1.95 × 10¹⁰（約195億） の状態を持ちます——全空間（約4.3 × 10¹⁹）より、ざっと9桁小さい。それが帰着の、数値化された利益です。
なぜ準最適なのか：各フェーズは事前計算された枝刈り表と IDA*（反復深化A*）探索を組み合わせます。テーブルには「ゴールまで最低何手」が格納されており、探索は悪い枝を容赦なく刈れる——数十ミリ秒での求解の鍵です。2フェーズは大域的な最適を保証しませんが、実用上は極めて近い解が出ます。
God's number = 20、その文脈：これはハーフターンメトリック（180度回転を1手と数える）での値です。下界 = 20 は早くから確立されていました——スーパーフリップのような局面はちょうど20手必要です。上界 = 20 は2010年、Rokickiらがコンピュータによる列挙で確認しました（どの状態も完成状態から20手以内）。下界と上界が一致し、God's number は20に確定しました。
God's number の15年の空白：下界20はスーパーフリップによって早く（〜1995年）釘付けにされましたが、上界は Thistlethwaite（1981年）からゆっくりと下がり続け、2010年に Rokicki らが大規模計算でついに20まで絞り込みました。「21手以上必要な状態はない」ことの証明は、予想よりはるかに難しかった——読む価値のある物語です。
次はどこへ
理論的な「天井」を見たところで——でも理論はあなたを速くしません。CFOP に戻り、F2Lを鍛え、認識を研ぐこと。それが実際に手数を下げるものです。
もっと深くへ：God's number の完全な歴史——あの15年の空白、スーパーフリップ、2010年の計算レース——が自然な次の読み物です。その先には最適ソルバー（20手以下を保証）とキューブの形式群論。それぞれ、単独で掘り下げる価値があります。