「ぷよぷよ最大連鎖問題」「ぷよぷよ全消し問題」は『多少良い』程度のアルゴリズムを作ることすら絶望的

ビデオゲーム「ぷよぷよ」をテーマにした「一般化ぷよぷよのより強い計算困難性」という研究が行われているそうだ。この研究ではぷよぷよを一人用のパズルと見立てた場合、どの程度難しいものであるのかを（最適化）アルゴリズム論的に分析するというものであるらしい（Ono Laboratory）。

元記事ではこの「ぷよぷよ」における計算困難性について解説したうえで、ぷよぷよの連鎖を最適化する問題を考えるという内容となっている。そのうち『問:フィールド上のぷよ配置、落下予定の組ぷよ列・答:それ以降に起きる連鎖数を最大にする各組ぷよの配置』を示す「連鎖数最大化問題」と『問:フィールド上のぷよ配置、落下予定の組ぷよ列・答:最後の組ぷよの配置後にフィールドにぷよが残らないような各組ぷよの配置』を示す「全消し問題」に対する多項式時間アルゴリズム設計について考察を行っている。

ちなみに最適解を見つけることは困難で、多項式時間アルゴリズムを与えるのは難しそうであるという結論になってしまった模様。

| 数学
|