これをきっかけにちょっと調べたら、面白いことになってきたのでメモしておこう。
私が初めて（2番目だったかも）買ってもらったパソコンには倉庫番のソフトが付属していて、ルールの単純さとそこから生み出されるパズルの複雑さの落差に興味を引かれたものだった。
他にこれに匹敵するものはコンウェイのライフゲームぐらいのものではなかろうか。
ソルバ（問題を解くプログラム）の能力はまだ人間に遠く及ばないらしい。十数年前に初めて触った時点ですでにコンピュータの能力は人間を超えているだろうと思っていたのでこれはちょっと意外だった。なんと倉庫番はPSPACE完全問題らしい。
後知恵だが、確かに言われてみれば、解くのにハノイの塔のような再帰的な手順を踏まなければならない問題を作ることができそうだと勘でわかる。
問題のサイズに対して指数関数的な手順数が必要になるということだからPSPACE完全でも不思議ではないな。コンピュータの能力が追いつけていないというのも腑に落ちてきた。
ソルバに興味が出てきた。自分でもやってみたくなってきたが、真面目に文献を当たり始めると自分が思いつくような手段はだいたいすでに試されているようだ。当たり前だが。
で見られる明治大学の研究がパイオニア的存在だそうだ。ソースコードもダウンロードできる。論文はネット上で読めるところは見つからなかったが要旨は上の本に載っている。
はあらゆるテクニックが行使されていて最高に面白い。英語で200ページぐらいあるが読める人は読んでみてはどうだろう。（PostScript形式が読めない人はとりあえずここへ。）
しかしこれだけやってもこれしか解けてないのかという意味で改めて倉庫番というパズルの奥深さと、それを解いてしまう人間の知能の凄まじさに感心する。
この論文に載っている以外の手法でこの先有効になりそうなのはなんだろう。単純に計算力の強化という方向でいくなら並列処理だろうか？ 流行のErlangでソルバを作っている方を見つけた。
しかし計算量を多少増やしたところでとても追っつかないような気もする。人間の思考方法にちょっとでも近づく方法は何かないだろうか？
- 倉庫番における部分マップの組合せに基づく手詰り判定手法（情報処理学会電子図書館）
マップをある程度の大きさのユニットに区切ってユニット同士の繋がりによって手詰まりの判定を高速化するという方法の論文。735円と書いてあるように見えるがそれは印刷の値段で、無料登録でPDFダウンロードが可能。
ユニットをどうやって分けるのか書かれていないのでどの程度実用になるのか不明だが、確かに人間はある程度のまとまりごとに区切ってその関係を見てあたりをつけているように見えるので、ソルバの効率が大きく改善できるとしたらこのあたりが狙い目かもしれないと思える。
おまけ
なんじゃこりゃ（笑）。そこばんアグレッシブというフリーゲームらしい。
コメント
倉庫番がPSPACE-completeということですが，任意の問題サイズにしたときなので，一般に与えられる問題の難易には直接結びつかないかと．
まあ，ある程度は結びつくでしょうが．
＞天さん
そうそう、そういうことが重要になってくる。興味があったら論文の内容そのものについてもちょっと書こうかとも思うけど。どうしようかなあ。
倉庫番がそこまで複雑なものだったとは確かに意外ですね。
自分の解き方は、論文にあるようにある程度ブロック分けして、荷物を置く場所までのルートを確保。
あとはルートを維持しながら試行錯誤という感じですね。
試行錯誤中は動かせるけど手詰まりになる形を意識していれば、効率が良くなる気がします。