ピクロスの次に、もっと歯ごたえがありそうな題材ということで、
を思い出して挑戦し始めたら、狙い通りとはいえ歯ごたえがありすぎてハマり中。最近ブログの更新が少ないのはそのせいだったりする。
丸写しじゃ意味がないので、既存のもののソースコードは見ないで、昔読んだ論文の内容もなるべく忘れてやっているので、ようやく基本的な道具立てが終わって、肝心の袋小路判定をどうするかという部分に入る前の段階。
なので、まだ非常に簡単な問題しか解けない。ここで言うと、screen1,2,3ぐらいしか。
0 1 2 3 4 5 6 7 8 9101112131415161718
0 ■■■■■
1 ■ ■
2 ■田 ■
3 ■■■ 田■■
4 ■ 田 田 ■
5■■■ ■ ■■ ■ ■■■■■■
6■ ■ ■■ ■■■■■ ・・■
7■ 田 田 ・・■
8■■■■■ ■■■ ■足■■ ・・■
9 ■ ■■■■■■■■■
10 ■■■■■■■
試しにscreen1、上の問題を解いた結果を続き部分に貼ってみる。FATALとか出てるのは、出力にRubyのloggerを流用しているためなので気にしないでください。
おまけ
こんな昔からあるのだな。
»続きを読む
by 木戸孝紀
tags:プログラミング 倉庫番
これをきっかけにちょっと調べたら、面白いことになってきたのでメモしておこう。
私が初めて（2番目だったかも）買ってもらったパソコンには倉庫番のソフトが付属していて、ルールの単純さとそこから生み出されるパズルの複雑さの落差に興味を引かれたものだった。
他にこれに匹敵するものはコンウェイのライフゲームぐらいのものではなかろうか。
ソルバ（問題を解くプログラム）の能力はまだ人間に遠く及ばないらしい。十数年前に初めて触った時点ですでにコンピュータの能力は人間を超えているだろうと思っていたのでこれはちょっと意外だった。なんと倉庫番はPSPACE完全問題らしい。
後知恵だが、確かに言われてみれば、解くのにハノイの塔のような再帰的な手順を踏まなければならない問題を作ることができそうだと勘でわかる。
問題のサイズに対して指数関数的な手順数が必要になるということだからPSPACE完全でも不思議ではないな。コンピュータの能力が追いつけていないというのも腑に落ちてきた。
ソルバに興味が出てきた。自分でもやってみたくなってきたが、真面目に文献を当たり始めると自分が思いつくような手段はだいたいすでに試されているようだ。当たり前だが。
で見られる明治大学の研究がパイオニア的存在だそうだ。ソースコードもダウンロードできる。論文はネット上で読めるところは見つからなかったが要旨は上の本に載っている。
はあらゆるテクニックが行使されていて最高に面白い。英語で200ページぐらいあるが読める人は読んでみてはどうだろう。（PostScript形式が読めない人はとりあえずここへ。）
しかしこれだけやってもこれしか解けてないのかという意味で改めて倉庫番というパズルの奥深さと、それを解いてしまう人間の知能の凄まじさに感心する。
この論文に載っている以外の手法でこの先有効になりそうなのはなんだろう。単純に計算力の強化という方向でいくなら並列処理だろうか？ 流行のErlangでソルバを作っている方を見つけた。
しかし計算量を多少増やしたところでとても追っつかないような気もする。人間の思考方法にちょっとでも近づく方法は何かないだろうか？
マップをある程度の大きさのユニットに区切ってユニット同士の繋がりによって手詰まりの判定を高速化するという方法の論文。735円と書いてあるように見えるがそれは印刷の値段で、無料登録でPDFダウンロードが可能。
ユニットをどうやって分けるのか書かれていないのでどの程度実用になるのか不明だが、確かに人間はある程度のまとまりごとに区切ってその関係を見てあたりをつけているように見えるので、ソルバの効率が大きく改善できるとしたらこのあたりが狙い目かもしれないと思える。
おまけ
なんじゃこりゃ（笑）。そこばんアグレッシブというフリーゲームらしい。
by 木戸孝紀
tags:AI プログラミング 倉庫番
すばらしい。個人的に倉庫番系ゲームの最高峰だと思う。冗談抜きで。登場するオブジェクトは床と壁を除けば、
たったこれだけ。ルールも、
- プレイヤーは
- ワニを持ち上げ、運ぶことができる。
- ブルドーザーに乗り、操縦できる。
- ブルドーザーは
- 前後にしか動かせず、横からしか乗り降りできない。
- 前に進む時他のブルドーザーか岩１個を押していける。
- 穴は通ることができないがブルドーザーで岩を押し入れて埋めれば床に変わる。
- 全てのワニを池に入れればクリア。
たったこれだけ。太字で強調したルールがキモで見かけのマップの大きさ、オブジェクトの数からは思いもよらぬ難しさを発揮してくれる。これぞパズルの醍醐味といった感じ。
マップエディット機能まであるので、他の人が作ったマップをぜひともプレイしたいと思って探したのだが見つからなかった。うーん、まずは自分で作って布教するしかないのか……。
by 木戸孝紀
tags:パズル フリーゲーム 倉庫番
木戸孝紀
