組み合わせ最適化問題とぷよぷよ - おびなたん☆
先月の電子情報通信学会論文誌の「組合せ最適化問題としてのぷよぷよの連鎖数判定問題」を読むことができた。過去にぷよぷよというゲームそれ自体についての論文が無い*1ので、その数理モデルの定義から議論を始めている。で、結論として4色以上のぷよぷよでは、ある盤面と落ちてきたピース列から連鎖数を判定することはNP完全であることを証明している。以後の課題としては、4色以下のときに、NP完全となるかどうか。さらに関連研究で、与えられたぷよが全て落ちたときに、全消しできるかどうかはNP完全であることも分かっているらしい。 ぐぐってみると、第一著者の松金輝久さんは「第２回ぷよマスターズ」決勝戦進出者。趣味が功奏しての論文ということか。 *1:ゲームのWebサイトをリファレンスしている
ゲームと困難性 - 186 @ hatenablog
前置き 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完全 (横
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
