第8回　倉庫番を解くアルゴリズム：ITpro

　これをきっかけにちょっと調べたら、面白いことになってきたのでメモしておこう。私が初めて（2番目だったかも）買ってもらったパソコンには倉庫番のソフトが付属していて、ルールの単純さとそこから生み出されるパズルの複雑さの落差に興味を引かれたものだった。他にこれに匹敵するものはコンウェイのライフゲームぐらいのものではなかろうか。

倉庫番パズル

　ソルバ（問題を解くプログラム）の能力はまだ人間に遠く及ばないらしい。十数年前に初めて触った時点ですでにコンピュータの能力は人間を超えているだろうと思っていたのでこれはちょっと意外だった。なんと倉庫番はPSPACE完全問題らしい。

日の目を見なかった問題たち その2
日の目を見なかった問題たち その2の追記
Sokoban is PSPACE-complete Draft

　後知恵だが、確かに言われてみれば、解くのにハノイの塔のような再帰的な手順を踏まなければならない問題を作ることができそうだと勘でわかる。問題のサイズに対して指数関数的な手順数が必要になるということだからPSPACE完全でも不思議ではないな。コンピュータの能力が追いつけていないというのも腑に落ちてきた。

倉庫番を解く(Ver2.7)（コンピュータ＆パズル）

　ソルバに興味が出てきた。自分でもやってみたくなってきたが、真面目に文献を当たり始めると自分が思いつくような手段はだいたいすでに試されているようだ。当たり前だが。

Sokoban Maps and other Resources

　で見られる明治大学の研究がパイオニア的存在だそうだ。ソースコードもダウンロードできる。論文はネット上で読めるところは見つからなかったが要旨は下の本に載っている。
カナダAlberta大学のAndreas Junghanns氏の博士論文（Sokoban Homepage）

　はあらゆるテクニックが行使されていて最高に面白い。英語で200ページぐらいあるが読める人は読んでみてはどうだろう（PostScript形式が読めない人はとりあえずここへ）。しかしこれだけやってもこれしか解けてないのかという意味で改めて倉庫番というパズルの奥深さと、それを解いてしまう人間の知能の凄まじさに感心する。

　この論文に載っている以外の手法でこの先有効になりそうなのはなんだろう。単純に計算力の強化という方向でいくなら並列処理だろうか？　流行のErlangでソルバを作っている方を見つけた。

Erlang で分散してみたくて倉庫番solver (nakatani @ cybozu labs)

　しかし計算量を多少増やしたところでとても追っつかないような気もする。人間の思考方法にちょっとでも近づく方法は何かないだろうか？

倉庫番における部分マップの組合せに基づく手詰り判定手法（情報処理学会電子図書館）

　マップをある程度の大きさのユニットに区切ってユニット同士の繋がりによって手詰まりの判定を高速化するという方法の論文。735円と書いてあるように見えるがそれは印刷の値段で、無料登録でPDFダウンロードが可能。

　ユニットをどうやって分けるのか書かれていないのでどの程度実用になるのか不明だが、確かに人間はある程度のまとまりごとに区切ってその関係を見てあたりをつけているように見えるので、ソルバの効率が大きく改善できるとしたらこのあたりが狙い目かもしれないと思える。

おまけ

なんじゃこりゃ（笑）。そこばんアグレッシブというフリーゲームらしい。

　タイトルのバベルとは

聖書におけるバベルの塔

バベルの塔の記事は『旧約聖書』の『創世記』11章にあらわれる。位置的にはノアの物語のあとでアブラハムの物語の前に置かれている。そこで語られるのは以下のような物語である。

もともと人々は同じ1つの言葉を話していた。シンアルの野に集まった人々は、れんがとアスファルトを用いて天まで届く塔をつくってシェム（ヘブライ語、慣習で名と訳されている）を高くあげ、全地のおもてに散るのを免れようと考えた（偽典の『ヨベル書』によれば神はノアの息子たちに世界の各地を与え、そこに住むよう命じていた）。神はこの塔を見て、言葉が同じことが原因であると考え、人々に違う言葉を話させるようにした。このため、彼らは混乱し、世界各地へ散っていった（『創世記』の記述には「塔が崩された」などとはまったく書かれていないことに注意）。『創世記』の著者はバベルの塔の名前を、「混乱」を意味するバラルと関係付けて話を締めくくっている。

原初史といわれ、史実とは考えられないアブラハム以前の創世記の物語の中で、バベルの塔の物語は世界にさまざまな言語が存在する理由を説明するための物語であると考えられている。と、同時に人々が「石のかわりにれんがを、しっくいの代わりにアスファルトを」用いたという記述から、古代における技術革新について触れながらも、人間の技術の限界について語る意味があると考えられる。

　（Wikipediaより引用）のこと。というわけだからテーマはディスコミュニケーションと格差。とにかく話が通じない。全ての登場人物と全ての登場人物の間で話が通じない話ばかり。

　モロッコ・日本・アメリカ・メキシコの4地域を舞台に、モロッコ人一家、アメリカ人夫婦、夫婦の子供たちと子守のメキシコ人のおばちゃん、日本の聾唖の女子高生とその父親あたりの主要人物たちの数日間が淡々と描かれる。

　全部が一丁のライフル銃で繋がってはいるわけだが、宣伝と違って別にこの銃を巡って思いも寄らない展開に進んでいくということはない。がっかりしたという人も多いみたいだが、本当は世界中が因果で1つに結びついているはずなのに現実はあまりにもバラバラだということを描きたい映画なのだから、これは宣伝の方法が間違っているんだろう。

　ただし日本編は話題になったポケモン光線がかなり強烈な上、なんという思考回路この女子高生は間違いなく色情狂みたいなストーリーなので間違ってカップルや家族連れで見てしまった人は気まずいことこの上なかっただろう。全体としてはかなり面白かった。

おまけ

まあ世界の言語が多様なおかげでこんな空耳ソングを楽しめもするわけだ。感謝感謝。（下ネタ全開注意！！）

　固定リンクのURLを見ているとこのエントリが300個目のエントリになるようなので記念にちょっと大風呂敷を広げてみることにする。このブログへは「ポルポト 笑ってはいけない 泣いてはいけない」等の検索フレーズでのアクセスが毎日のようにある。多くが映像の世紀に関連する検索だと推測される（参考）。こんな特に意識もせずに書いたエントリに未だにアクセスがあるということは、映像の世紀がいかにすごい番組だったかを顕著に示すものだろう。

　21世紀版映像の世紀が作られるとしたら、それについて確実に言えることはツインタワーに突っ込む航空機から始まるだろうということ以外に何かあるだろうか。私はあると思う。それは20世紀版より面白くないだろうということだ。

　文明は進歩する。今日は昨日よりも、明日は今日よりも進歩する。同時に進歩の速度そのものも早くなっていき、全体としては指数関数的な成長をする。当たり前だと思うかも知れない。これを不変の真理だと思っている人もいるかも知れない。

　いや、かも知れないどころではなく実際にそう思っている人はいる。つい最近も「文明の発達はどんどん加速して指数関数的に成長して特異点に達するから人類は21世紀中には滅亡するかもしれない」と大真面目に語っている本を書店で見た（5/25追記：『今世紀で人類は終わる?』という本だったっぽい。愛・蔵太の少し調べて書く日記より）。

　確かに文明は今日まで指数関数的に成長してきたように見える。だからそれが今後も永久に続くかのように思ってしまうのも無理もないことではあると思う。しかしよく考えればそんなはずはないことはわかる。地球も宇宙も自然法則も無限ではないから指数関数的な成長はいつまでも続けられない。必ずどこかに限界はある。

　限界がある成長はシグモイド曲線で描かれるような経過を辿る。この場合も明日は今日より、今日は昨日より徐々に進歩していくということは変わらない。しかしある時点を過ぎればこれまで常に加速していた進歩の速度が減速に転ずることになる点（グラフ上の変曲点）がどこかにあり、それをいつか通り過ぎることになる。

　それはいつだろう？　そもそも文明の進歩やその速度に明確な定義が与えられるかどうかが怪しいとしても、私はかなりの確信をもってそれは20世紀のどこかであったろうと考える。すでに通り過ぎているのである（考えている時間スケールからすると今通り過ぎようとしていると言った方が適切かもしれない）。

　21世紀版映像の世紀もきっと面白いだろうが、20世紀版ほどには面白くないだろう。22世紀版はもっと、23世紀版はもっともっとつまらないだろう。5000年後にも、10万年後にも、56億7千万年後にも、半永久的に映像の世紀は最も面白い映像の世紀であり続けるだろう。我々は人類の（ことによると宇宙の）歴史上最もドラスティックな時代に生きていたのだというのが私の予想だ。

　「そんな馬鹿な話があるか！」という反論がありそうな気がする。「お前は何を言ってるんだ！　世界を見てみろバイオもITも何もかもますます加速して進歩し続けてるじゃないか。確かに無限の指数関数的成長があり得ないというのはわからないでもない。しかし何らかの限界に近づいて速度が鈍り始めるなんてのはまだまだ先、少なくとも何千年・何万年単位の未来の話だろう」と。

　まったくその通りだと思う。私もずっとそう思っていた。今のように考えるようになったのはいつの頃からか忘れたが、たぶんまだ10年は経っていない。このような反論に答えて納得してもらうのは果てしなく大変だと思う。この結論に至るまでの道筋と結論から導かれる思考は多岐にわたるので、これから折に触れて書くことにする。

おまけ

スケールの壮大な話だったので荘厳な音楽を。パイプオルガンはかっこいいなあ。

地上でもっとも凶々しいＳＦ
合成脳のはんらん（合成怪物）

　ずいぶん前に読んだ覚えのあるはずの上のリンクの文章がなぜかはてブの注目エントリに上がっていた。私もこの本は小学校の図書館で読んで強く記憶に残っている。今思えばSFに限らず私の趣味一般、たとえば登場人物皆殺し系の悲劇的というか破滅的な結末の話が好きだったりすることなどにかなり影響を与えているような気がする。

　「『脳に意識がある』ということが重大な秘密である」という部分が致命的に時代遅れである以外は今でも（というか今でこそ）通用する面白い話だと思う。多少設定変えてハリウッド映画としてリメイクでもしてくれんかな。無理だろうけど。

おまけ

トラウマ繋がり。かなり昔からあるトリップ系Flash。キモ美しい。

　「複雑系関係でいい本知りませんか？」というリクエストが（リアルで）あったので備忘がてらまとめてみました。

　基本は圧倒的にこれがおすすめ。なんと言ってもローレンツ本人の手によるだけあって非常にわかりやすい。図表が豊富なのも良い。下のは4冊は応用編。生物・物理・宇宙論・数学等との関連。どれも甲乙付けがたいぐらい最高に面白いですぞ。

6/1 追記

　もうちょっとあっさり読みたいという人は複雑系ブームのきっかけになったこの本をお薦め。文庫一冊で歴史と基本思想を広く当たれる。

おまけ

プルシェンコの有名なあれ。なんかもう圧倒的。いろんな意味で。

イラク戦争に費やした4560億ドルがあれば何ができるか - GIGAZINE

　このエントリを見て何か懐かしい既視感をおぼえたと思ったらこの本だった。面白くてインパクトがあることは認めるけどあまりフェアとは思えない。こういう宣伝が必ずしもフェアじゃなきゃいけないと思っているわけではないけど。

　（単に日常レベルの物事に換算するということ以外で）最大のポイントは「AがBまたはCまたはDまたはEまたは〜に相当する」という内容を「AがBとCとDとEと〜の全部に相当する」かのように錯覚させることだろう。他にどんな技巧が凝らされてそうか一度自分の頭で考えてみるのがいいんじゃないかと思う。こういった数字リテラシーに関しては下の本がおすすめ。

飢餓の娘

　母が家に置いていったので読んでみたが、これ自体はそこまで面白いとは思わなかった。『ワイルドスワン』と似たような内容で、そちらの方が面白かった。

　これまでの経験を思い出してみると、近代中国に関する文学で本気で面白いと思ったのは『大地』と『阿Q正伝』。後者は短いし青空文庫でも読めるのでまだの人にはおすすめ。

タクシー全面禁煙巡るコラム、中日新聞に抗議４０件

5月10日3時18分配信 読売新聞

　名古屋地区で今月１日から始まったタクシーの全面禁煙について、中日新聞社（本社・名古屋市）の常務・編集担当の小出宣昭氏（６２）が４月２９日の朝刊で否定的な意見を掲載したところ、「たばこの害を、どう考えているのか」などの抗議が同社に相次いでいることが９日、わかった。

　ＮＰＯ法人「日本禁煙学会」（東京）も小出氏に抗議文を送付した。

　愛煙家である小出氏は、コラムの中で、全面禁煙について「決め方にいささかの薄っぺらさを感じる」とし、タクシーは「個別選択的な乗り物」であり、「全車禁煙という一律主義に本能的な危険を感じる」と書いた。

　中日新聞社には９日までに抗議のメールや手紙が約４０通届き、「喫煙を正当化するな」などの電話もあるという。

最終更新:5月10日3時18分

　『最後の喫煙者』を連想するなという方が無理なニュース。

REVの日記　@はてな - 喫煙関係メモ
はてなブックマーク - REVの日記　@はてな - 喫煙関係メモ

　あたりも参照。ちなみに私は完全な非喫煙者なので世界の禁煙化の流れに逆らう気はないしその理由もない。喫煙者にとっては理不尽に感じることは理解できるが、その程度の意味では世の中に理不尽でないことなんてそうそうあるもんじゃない。

　天の邪鬼精神ぐらいは常に発揮しておくべきだとは思うのでこうして『最後の喫煙者』を読むことをおすすめするわけだが。ついでに最近読んだものの中ではグレッグ・イーガンの『繭』も微妙に関連あるかも。

　ニコニコ動画がゲーム動画を見るのにちょうど良い環境と書いたが、それを象徴するようなのがこれ。SFC版ドラクエ3のタイムアタック（実時間）の世界新記録なんだそうな。まだ最初の方しか見ていないが確かにこれはすごい。

　私はFC・SFC・GBC版合わせて10回以上は通してプレイしているはずなのに、全てが驚きの連続だ。以前書いたドラクエ3の自由度の高さを改めて思い知らされる。

　エミュレータでクイックセーブ・ロードを駆使するいわゆる神プレイとは違って実機でのリアルタイムプレイなので、操作ミスや運の影響もきっちり受けている。すごい緊張感である。

前回までのあらすじ：
地下一階の探索を進めるクロード一行。新しい仲間のガウフをレンジャーにしてみるもののアイテム採取スキルは特定の場所でしか使えないらしい。しかたなく再びカナをパーティーに戻してレベル上げと一階の探索を進めることになったのだった。
（注意：進行状況に応じたネタバレあり）

　これも読もう読もうと思って後回しになっていた。いわゆるカンブリア大爆発についての本。カンブリア大爆発についてはとにかく『ワンダフル・ライフ』が有名だが、この本でのグールドは、人間の進化が偶然の結果であるという意見（それは正しいと思うが）を強調するあまり、バージェス動物の異質性・多様性を過大に強調してしまった面があり、カンブリア大爆発などと言うのはただの誇張で実際は何も特別なことなど起きてはいなかったという反論もあった。

　この意見の対立は結局のところどちらも半分ずつ正しかった。確かにこの時期だけ遺伝の仕組みに何か特別なことが起きて全ての生物のボディプランが百花繚乱して進化の可能性が試されたなどということはなかった。遺伝子レベルではあくまで予想されるような漸進的な進化がその以前から変わることなく続いていた。

　同時に、たとえ外見的にだけであっても、この時代の生物が爆発的と言ってもよい多様性を見せたこと、とりわけ軒並み硬組織を発達させたことは依然として変わりなく、しかもその理由ははっきりしていなかった。この本で紹介されている光スイッチ説は『外見が多様化したのは視覚の誕生によって生物の取り得るニッチが多様化すると同時に外見が死活的に重要になったから』だというもの。

　この説を取材した新聞記者が出版前日になって編集長から「本当に新説なんだろうな？」と念を押されたというエピソードが載っているように、思わず「そんなの当たり前じゃないの？」と反応してしまいそうになるほど明解で説得力のある説だ。かなりの確率で真実を言い当てているだろうと思える。