Sokobanゲーム：自動的にボックスを移動

Question

私はすでに、幅優先探索アルゴリズムを使用してキーパーが自動的に移動するときにfunctionallityを実装しました。今度はボックスを自動的に移動したい（キーパーが別のボックスを動かすことなくボックスを移動元から移動先に移動できる場合）。どのように私はそれを行うには？私はBFSを修正しようとしましたが、まだ成功していません。

更新日：私はパズルを解決する必要はありません。代わりに、私はユーザーがマウスでボックスを動かすことができるときに便利なユーザーインターフェイスを開発したいと思っています。このために私は移動シーケンスを計算できるいくつかのアルゴリズムが必要です。しかし、それは単一のボックスを動かすことについてだけであり、そうするために他のボックスを移動しないようにしなければならない。 Wikipedia - Sokobanから

Answer 1

これまでのように幅優先検索を使用します（または希望する場合はA *）が、適切な状態を検索します。

キーパーのパスを検索するとき、状態はグリッドの四角に対応します。しかし、キーパーがブロックを移動する方法を探しているとき、状態はグリッドののペア（キーパー用、ブロック用）に対応します。

これは、最小ではっきりしない例です。私たちは次のようにラベルされた正方形と倉庫番レベルがあるとします。

グリッドがキーパーと1つのブロックが含まれています。状態空間は、キーパーとブロックが占有する四角形のペアで構成されます。下の図には小さな円で描かれた56の状態があります。

行は、この状態空間内で可能な遷移を示しています。細い線はキーパーによる動きに対応しています（双方向です）。太い線は、ブロックを押すことに対応します（したがって、一方向のみに移動します）。あなたが検索する必要がある状態空間です。それに沿って

注ブロック7から始まり、8におけるキーパー場合

は、例えば次にキーパーは、状態空間内の赤の経路に従うことによって8にブロックをプッシュすることができこの経路では、ブロックは位置7-6-5-6-7-8を通過する。ブロックが6位と7位を2度通過するので、ブロックの位置を考慮するだけで、このパスを見つけることはできませんでした。

Answer 2

：

倉庫番は、計算の複雑さの理論を用いて研究することができます。 Sokobanパズルを解決する問題は、 NP-hardであることが証明されています。 3 Sokobanの解答は、倉庫内のボックスを動かすロボット ロボットの設計と比較することができるので、これは人工知能のためにも面白いです。 研究者。さらなる研究は、Sokobanの問題を解決する もPSPACE-completeであることを示している[4]

Sokobanは、その分岐要因（チェスに匹敵する ）だけでなく、その膨大な検索ツリーの深さのために難しいだけでなく、一部の レベルでは1000回以上の「プッシュ」が必要です。熟練した人間のプレイヤーはヒューリスティックにほとんど を依存します。彼らは通常、無駄な数字の または冗長な行を素早く破棄し、パターンとサブゴールを認識することができます。 は検索量を大幅に削減します。

いくつかの倉庫番パズル

は、ドメイン固有の知識を利用して、いくつかの 技術によって強化され、そのようなIDA *など 単剤検索アルゴリズムを使用して自動的に解決することができる。[5]これは、 University of Alberta GAMES Groupによって開発されたSokobanソルバであるRolling Stoneによって使用される メソッドです。しかし、より複雑なSokobanレベル は、最高の自動ソルバーであっても手の届かないところにあります。

これはあなたが知りたいことですか？

ちなみに、Sokobanパズルを最も最適な方法で解くことはNP-hardです。これは、あなたがそれを行う方法を見つけたら、$1,000,000 prizeがあなたを待っていることを意味します。