3x3 ルービックキューブの数理状態を対象に、 深層学習で候補を出し、最後は厳密探索で最短手数を証明する ことに絞ったプロジェクトです。
単に state string を解くだけではなく、
- 学習モデルをどう shortest search に組み込むか
- 学習済み推定器の挙動を GUI でどう見せるか
- 近似と厳密性をどう分離するか
を 1 つのリポジトリで説明できる形にしています。
- 状態表現・回転処理・入力検証を自前で扱える
- 深層学習を「予測器」として設計し、探索に接続できる
- 学習モデルだけに頼らず、厳密探索で正しさを回収する設計判断ができる
- GUI で探索過程を可視化し、挙動を説明できる
- 学習データの作り方まで含めて 1 本の作品として完結させている
このプロジェクトの中心は AI 単体で shortest を言い切ること ではありません。 現実には、深層学習の推定だけで最短手数を保証するのは説明も検証も難しくなります。
そこでこのリポジトリでは、次の分担にしています。
- guided search: 学習済みモデルの value / policy で有望な枝を探す
- exact proof: reverse database + forward BFS で「それより短い解がない」ことを証明する
この構成だと、AI を使う意味と shortest を扱う誠実さを両立できます。
- 54 facelets state の表現と検証
- 深さ 5 の reverse database 構築
- value head / policy head を持つ学習済み MLP
- beam search による guided candidate 探索
- reverse database + forward BFS による shortest proof
- Tkinter GUI による探索トレース可視化
- 再学習用の
train-demoコマンド
同梱している demo checkpoint は、以下の exact データで学習しています。
- 深さ 0〜5: solved から reverse BFS で厳密列挙
- 深さ 6: 6 手スクランブルを生成し、深さ 5 以内に存在しないものだけ採用
学習設定:
- reverse database depth: 5
- epochs: 12
- sample_depth5: 20,000
- sample_depth6: 20,000
最終 epoch の指標:
- validation value accuracy: 0.772
- validation policy top-1: 0.774
- validation policy top-3: 0.927
詳細は src/rubiks_cube_neural_search/resources/training_metrics_demo.json を参照してください。
デフォルト設定は次のとおりです。
- reverse database depth = 5
- proof forward depth = 5
この場合、最短手数の厳密保証は最大 10 手まで です。
- 10 手以内なら
optimality_proven=trueで返せます - それより深い局面は guided candidate は返せますが、最短証明まではしません
rubiks-cube-neural-shortest-search/
├── README.md
├── LICENSE
├── THIRD_PARTY_NOTICES.md
├── docs/
│ ├── architecture.md
│ ├── demo-run.md
│ └── training-notes.md
├── pyproject.toml
├── requirements.txt
├── requirements-dev.txt
├── src/
│ └── rubiks_cube_neural_search/
│ ├── __init__.py
│ ├── __main__.py
│ ├── cli.py
│ ├── constants.py
│ ├── cube.py
│ ├── dataset.py
│ ├── encoding.py
│ ├── exact_db.py
│ ├── gui.py
│ ├── model.py
│ ├── moves.py
│ ├── notation.py
│ ├── search.py
│ ├── trainer.py
│ ├── validator.py
│ └── resources/
│ ├── cube_net_demo.pt
│ └── training_metrics_demo.json
└── tests/
├── test_exact_db.py
├── test_model.py
├── test_moves.py
├── test_notation.py
├── test_search.py
└── test_validator.py
python -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt
pip install -e .cube-neural solve-scramble "R U R' U' F2"出力例:
{
"solution": "F2 U R U' R'",
"move_count": 5,
"optimality_proven": true,
"guided_move_count": 5,
"guided_nodes_expanded": 0,
"proof_nodes_expanded": 3502,
"reverse_db_depth": 5,
"proof_forward_depth": 5,
"elapsed_seconds": 1.4884
}cube-neural solve-state UULUUFRDDLRULRRLRRFFFUFFDFFFUUDDDDDDBLULLBLLRBRRBBBBBBcube-neural guiGUI では次を確認できます。
- スクランブル適用後のキューブ状態
- guided search の先頭ノード
- proof search の層ごとの進み方
- 推定された top moves
- 最終解の再生
cube-neural train-demo --output-checkpoint artifacts/cube_net_demo.pt --output-metrics artifacts/training_metrics_demo.jsonMLP は「残り何手くらいか」と「次にどの手が有望か」を予測します。 最短性の保証までは持たせていません。 この切り分けにより、モデルが多少外しても設計全体は破綻しません。
浅い深さの exact data は reverse BFS から直接作っています。 そのため、
- どこまでが厳密データか
- 深さ 6 サンプルをなぜ exact と言えるか を README とコードの両方で説明できます。
GUI は solved / scramble の表示だけではなく、
- guided phase
- proof phase
- top moves
- solution replay
を分けて見せます。 面接で「学習モデルが何をしていて、最終的な shortest はどう保証しているか」をそのまま説明できます。
- 3x3 全域で最短を厳密保証する solver をこの作品の主題にはしていません
- その代わり、深さ 10 までの shortest proof に範囲を切り、設計の意図を明確にしました
- モデルは小規模 MLP に留め、探索への接続と可視化を主題にしています
pytest含めている検証:
- move / notation の基本動作
- legality validator
- reverse database の深さ確認
- model の入出力 shape
- shallow horizon での exact proof
- policy/value だけでなく symmetry augmentation を入れる
- reverse database を pattern database に差し替えて保証範囲を広げる
- guided search を beam から best-first に拡張し、候補発見を高速化する
- GUI で frontier の比較表示や layer statistics を追加する
- 深さ 7 以上の exact data を別ジョブで蓄積してモデルを強化する
docs/architecture.md: ハイブリッド探索の設計理由docs/training-notes.md: 教師データと学習方針docs/demo-run.md: 同梱 checkpoint のサンプル実行結果