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