ルービックキューブの地図

ルービックキューブプログラムの別のアプローチ。

前みたいに、評価関数使ってヒューリスティック的に展開してA*探索するのはどうも限界があるらしいから、初めから全ての状態数のデータベースを作ってしまおうというモチベーション。

最近、Java3D使ってルービックキューブの動くＣＧ作って、全自動でランダムにくるくる回して遊んでたら思いついた。





状態遷移を各面右左90°だけの12通りに限定して、1つの状態から12本の枝を伸ばし、各オペレーションに対して次の状態オブジェクトを生成してくっつけていく。

網目みたいに張り巡らされた状態グラフを巡回して、ゴール状態までのステップ数と次のオペレーションを随時更新して、最適パターンに近づけていく方法。

つまりルービックキューブの地図を作ろうと。


して実装してみたら、全状態を網羅するはるか前にメモリが足りなくなった。


まぁ分かってたことだけど。



全状態を網羅してなくても、ランダムに状態遷移していつか既知の状態に辿り着けばゴールに辿り着くことはできる。

樹海で迷った状態から遊歩道を探し出すような感じ。



なんかうまい方法ないかなぁ…。




ソース