■

昨日の夜からずっと変愚蛮怒やってたら1日が終わってしまった。今週休み1日しかないのにもったいないことをしている気がする。
Diablo3の発売日が5/15に決まったらしい。就職したときくらいからずっと「Diablo3が出る頃にデスクトップPC新調するかー」と思っていたんだけど、いつの間にかノートPCがメインになったり、メーカー製デスクトップを弟からもらったりとかしてて、新しいデスクトップに対する需要がなくなっていることに気がつく。どうするかな。PCIeスロットが空いてた気がするから適当にグラボ買ってきて刺せばいいんじゃないかという気はする。しかしメモリ4GBだともうメイン機としては厳しいからなあ。うまく使い分けを考えるか。
任天堂の「マリオ」、「ドンキー・コング」、「ゼルダの伝説」、「メトロイド」、「ポケモン」がNP困難であるという論文が出たらしい(→http://arxiv.org/abs/1203.1895)。そういえば何年か前にテトリスがNP完全だって論文も出てたなー。日記を調べてみるとこういう(→http://d.hatena.ne.jp/Htok/20050816#p3)ことらしいので、研究室バックアップの中に埋もれてる気がするなあ。当時はよくわからんとか書いてるけど、これって与えられたテトラミノの順列に対して、「消せる列数を最大にする」「テトリス回数を最大にする」「一番高い列の高さを最小にする」「ゲーム終了までに一番多くのミノを配置する(消すのは不可？)」がそれぞれNP完全って話だったのね。一般化したぷよぷよもNP完全(入力の盤面とピース列からn連鎖可能かの判定)ってのもテトリスと同じく2005年くらいに出てたねえ。あと図情の図書館まで論文のコピーを取りに行ったのがあった気がするけどなんだったっけ。この手のゲームの論文というと、ドミニオンのAIに関する論文もPDF落としたっきりになってる気がする。あーいや一応「ドミニオンとはどういうゲームか」みたいなところまでは読んだ気がする。
変愚蛮怒。アンドロイド狂戦士でようやく*勝利*した。勝利コメントにも書いたけど3年ぶり3回目。