先月の電子情報通信学会論文誌の「組合せ最適化問題としてのぷよぷよの連鎖数判定問題」を読むことができた。過去にぷよぷよというゲームそれ自体についての論文が無い*1ので、その数理モデルの定義から議論を始めている。で、結論として4色以上のぷよぷよでは、ある盤面と落ちてきたピース列から連鎖数を判定することはNP完全であることを証明している。以後の課題としては、4色以下のときに、NP完全となるかどうか。さらに関連研究で、与えられたぷよが全て落ちたときに、全消しできるかどうかはNP完全であることも分かっているらしい。 ぐぐってみると、第一著者の松金輝久さんは「第2回ぷよマスターズ」決勝戦進出者。趣味が功奏しての論文ということか。 *1:ゲームのWebサイトをリファレンスしている
前置き CiNii - ぷよぷよはNP完全 はてなブックマーク - CiNii - ぷよぷよはNP完全 全て頭に一般化が付きます. 色々結果はありますが, 問題の定式化によって当然難しさが変わりますのでご注意を. 定義は元論文を見て確認してください. 2人ゲーム オセロ PSPACE完全 (岩田, 笠井 1994) 将棋 EXPTIME完全 (安達, 亀川, 岩田 1987) 囲碁 EXPTIME完全 チェッカー EXPTIME完全 (Robson 1984) チェス EXPTIME完全 一般化しりとり PSPACE完全 マスターマインド NP完全 (de Bondt 2004, Stuckman and Zhang 2005) 一般化アマゾン PSPACE完全 (清見, 宇野 2005) シャノンのスイッチングゲーム PSPACE完全 1人ゲーム 一般化詰め将棋 EXPTIME完全 (横
まあ、「衝動買い」ってやつです(苦笑) 現在先行販売中のKlipschのImage X10をビックカメラで購入しました。 7月25日から始まっている先行販売は代理店のネット直販とビックカメラ・ソフマップだけです。普通この手の商品が限定販売となるとApple Storeで販売、と言うのが定番のような気もするのですが、めずらしくビックカメラ・ソフマップ限定です。おかげでポイントが付いていいのですけど(笑) このイヤホンは信じられないところが2つあります。音質と大きさです。結構本質的な部分です。 この写真はUltimate EarsのTriple fi 10Proとの比較ですが、大きさが全然違うのがおわかり頂けると思います。 Triple fi 10Proはその名の通り、バランスドアーマチュアが3基搭載されています(高音用1基・中低音用2基)。そのためハウジングがかなり大きくなってしまいます。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く