ホームページへ戻る 開発ノートメニューへ戻る
倉庫番を解く(Ver2.7)

 
 「倉庫番」は奥が深い面白いテーマです。実際2ケ月間「倉庫番オンリー」のコンピュータライフを過ごすことになりました。まだまだ不満は残りますがちょっと疲れました。またいつかバージョンアップ出来れば良いのですが.....

テスト版(Ver1.1)から公開版(Ver2.7)まで

(Ver1.1)当初のテスト版(19997/08/15 HP公開)
 基本アルゴリズムは、「ハッシュ法(幅優先探索)」です。普通の「15パズル」とか「箱入り娘」とかの「スライディングブロックパズル」は殆どこれでおしまいなのですが、倉庫番には人間味のある特有なルールがあり、アルゴリズム的に工夫の余地が大いにある様なのです。当初のテスト版[8×8(荷物4個)]では、次の2つの枝刈りを組み込みました。
「デッドゾーン(進入禁止域)」
 一端ここに荷物を運んだらもう脱出不可能な場所があります。そんな地帯を事前に調査しておきます。(右図は1例)



「フリーズチェック(凍結状態検査)」
 全く身動きが取れなくなってしまった状態かをチェックしながら探索を進めます。(右図は1例)



(Ver1.2)最短解とは「手数」or「歩数」?
 荷物を押す回数について最小解(最小手数)を見つけるのがプログラム上合理的なのですが、解答表示でおもいっきりバカな動きをしたりします。歩く歩数について最小解(最短歩数)を見つける様に変更しまた。しかし、これによってメモリ消費が増えプログラムも大きくなってしまった。(どうしよう)

(Ver1.3)凍結状態を先読みする
 「フリーズチェック」は完全に凍結してしまった場合にその局面を探索から外します。しかし、まだ凍結してないが将来必ず凍結してしまう状況があります。これは閉空間を形成している荷物付近で発生します。
「局所探索法(閉空間ミニ探索)」
 閉空間を形成している局所部分を抽出して、ここだけでミニ探索を実行してみます。(右図は1例)




(Ver1.4)未完に終わった超高速手詰まりチェック
 残念なことに「局所探索法」は手間のかかるチェック法です。さらに、「デッドゾーン」「フリーズチェック」「局所探索法」のいずれでもチェック出来ない手詰まりパターンがあります。図がその例で、つまり、デッドゾーンは状況により変化するのです。ここでこれら総てを統合して、しかも高速にチェックしてしまう方法を思い付きました。
 
「多次元テーブル高速チェック法」
 「デッドゾーン」とは、荷物1個で許されないパターンのことです。同様に荷物2個の組み合わせで許されないパターン、荷物3個の組み合せで許されないパターンがあると考え方を統合する。これらのパターンを事前調査して多次元配列変数に登録しておきます。(しかし、プログラムが難しくて未完成です)



 
(Ver1.5)逆解き法は使えます
 この頃に「倉庫番INDEX」のおきやす氏とメールのやり取りがあり、大変貴重な情報を頂きました。
1992年頃に、「倉庫番自動解析プログラムコンテスト」(シンキングラビット開催)があり、優秀賞(審査員特別賞)は倉庫を逆から(格納された状態から)解くプログラムだったと言うのです。これにはシビレました。そして、私はこのアイデアをこんな風に応用しました。
 
「逆解き挟みうち法」
 解答発見までの通常の探索量は図の青と水色の合計面積です。しかし「逆解き法」を併用させ、途中で両者の探索の衝突地点を探す様にすると、水色の探索部分は不要になるのです。これで探索量は約半分になります。
(Ver1.6)笑って下さい「運が良けりゃ君」
 この頃になると、「最小手数」とか「最短歩数」とかはどうでもよくなりました。解けなければ何んにもならないのです。爆発的に増大する探索量をなんとしても押えたいという気持ちで、こんなことをしてみました。

「運が良けりゃ君」
 乱数を発生させ、その結果しだいで探索を間引きする。(情けない失敗策でした)

(Ver2.7)集団お見合いは男女同数がいい(19997/10/03 HP公開)
 「逆解き挟みうち法」はみごとに成功しました。しかし、探索結果の内部状態を調べてみると、先ほどの図のようには成っていなかったのです。両者の探索量の増加傾向はまちまちで、もっと贅肉を切り落せるのです。
 
「間口幅調整式逆解き挟みうち法」
 両者の探索パターンの増加傾向に違いがあると左図のように水色の探索部分が無駄なのです。そこで、両者の探索先端の間口幅に大きな差が生じないように、どちらの探索を優先するかを随時調整しながら進行します。すると右図のようにスッキリします。

 
 さて、ここでホームページへの公開に踏み切りました。バージョン番号の付け方がおかしい様ですが、左がjava言語版の通し番号で右がC言語版の通し番号です。使用したアルゴリズムは下の通りです。また結局、荷物を押す回数について「最小手数」を求めるようにしました。メモリ消費を押えることを重要視したからです。javaアプレットでは、グレードの低いマシンを使っている人のことを考えると局面の保存に2M程度のメモリーしか使えないようなのです。これは10万パターン分です。
 また、Ver1.1と比べると約20%の探索量だけで解を発見出来るようになっています。
「ハッシュ法(幅優先探索)」(Ver1.1)
「デッドゾーン(進入禁止域)」(Ver1.1)
「フリーズチェック(凍結状態検査)」(Ver1.1)
「局所探索法(閉空間ミニ探索)」(Ver1.3)
「間口幅調整式逆解き挟みうち法」(Ver2.7)
ダウンロード

 私のヘタクソなプログラムのソースコードをダウンロード出来ます。(画像は右クリックでコピー)

・ソースコード soko207.java (1997/10/15 24:00 update)
・その他の必要なファイル
item0.gifitem1.gifitem2.gifitem3.gifitem4.gif
item5.gifitem6.gifitem7.gifitem8.gif
・アプレットサイズ width=400 height=364
 このソースコードはバグ取りで時々更新されることがあります。
 参考になる部分があればご自由に応用改良してかまいませんが、参考資料(高橋謙一郎作)として紹介して下さいね。


 
付記1(1997/10/07)
 公開から3日後の10月6日に知ったことですが、「倉庫番自動解析プログラムコンテスト」(シンキングラビット開催)で最優秀賞を受賞した方は、京都大学の山根正也氏(幅優先探索(二分探索木)で最短歩数)だったそうです。二分探索木法だとハッシュ法よりポインタ分にメモリが食われるし、ましてや最短歩数を求めるとなるとなおさらメモリを食われるはず。(何か魔物を仕組んだな)
 また、1994年にbit誌で「倉庫番を解くプログラム」として、明治大学の上野篤氏と中山康氏と疋田輝雄氏(たぶん幅優先探索で最小手数(格納順番を考慮した方法が組み込まれているとのこと))が発表されているそうです。
 機会があれば同一環境上で競ってみたいものです。最も開発のコンセプトに違いがあるのですが....
 
付記2(1997/10/11)
 疋田輝雄氏(明治大学)のHPを発見して「倉庫番を解く」論文を拝見させて頂きました。基本アルゴリズムは幅優先探索でなく「最良優先探索」という初めて聞くものでした。また、上の(Ver1.4)に例示したチェック不能な問題も解決しておられました。
 同一環境上で競ってみたところで、私の方に勝ち目はないことがハッキリしました。


ホームページへ戻る 開発ノートメニューへ戻る