組み合わせ最適化問題とぷよぷよ

先月の電子情報通信学会論文誌の「組合せ最適化問題としてのぷよぷよの連鎖数判定問題」を読むことができた。過去にぷよぷよというゲームそれ自体についての論文が無い*1ので、その数理モデルの定義から議論を始めている。で、結論として4色以上のぷよぷよでは、ある盤面と落ちてきたピース列から連鎖数を判定することはNP完全であることを証明している。以後の課題としては、4色以下のときに、NP完全となるかどうか。さらに関連研究で、与えられたぷよが全て落ちたときに、全消しできるかどうかはNP完全であることも分かっているらしい。

ぐぐってみると、第一著者の松金輝久さんは「第２回ぷよマスターズ」決勝戦進出者。趣味が功奏しての論文ということか。

*1:ゲームのWebサイトをリファレンスしている