「ぷよぷよは計算困難」―パズル・ゲームと最適化アルゴリズム―

はじめに

最近，「一般化ぷよぷよのより強い計算困難性」なる研究を発表しました（東北大学の江藤宏先生，九州大学の木谷裕紀先生との共同研究．国内研究会であるゲームプログラミングワークショップで江藤先生による口頭発表．2021年12月30日現在，pdfはここから取れます）．

これは有名なビデオゲーム「ぷよぷよ」を一人用のパズルと見立てたとき，かつそれを一般化した場合，どの程度難しいものであるのかを（最適化）アルゴリズム論的に分析したものです．今回「最適化技術の応用・実践」に関する記事を集めよう，ということになりましたので，ちょうどよい題材ということで，この研究をより一般向けに解説してみようと思います．一般向けですので証明自体には踏み込まず，既存の定理と得られた定理の意義をおよそわかっていただくことをこの記事の目標とします．ただし「ぷよぷよ」について関してはおよそルール等がわかっている方を対象としています．ぷよぷよ自体をご存じない方はWikipedia や，セガによるぷよぷよポータルサイトをご覧になった上でこの記事を読んでいただけると幸いです．

ぷよぷよのルール

とは言え，まったく前提なしでは説明しづらいのでまずぷよぷよのルールを簡単に紹介しておきます．「ぷよぷよのルールなんて知っている！」という方はこの節は読み飛ばして次の節から読んでいただければと思います．ただし，この記事で使われているぷよ用語はこの節で定義していますので，「なんだこの言葉は？」と思われた場合はこの節に戻って確認されるのが良いと思います．なお，ここで使用する用語は必ずしも公式の用語ではないことに注意ください．

まず「ぷよ」は赤・青・黄などの色付きの物体のことを指し，通常縦12マス×横6マスの格子からなる「フィールド」が舞台となります．ぷよ一つはフィールドの１マス正方に相当します．フィールドには縦方向に重力が働いており，フィールドの一番下を床と言います．プレイヤーはフィールド上部の排出口から順に降ってくる2つ1組のぷよ（組ぷよ）を回転・水平移動させる形で適当に配置する形で遊びます．ぷよは床，あるいは既に固定されたぷよの上に落下するとその位置で固定されます．組ぷよの2つのぷよはつながった形で落ちますが，そのつながりは緩いため，段差ある形で固定されたぷよの上に組ぷよが横2つの形で置かれた場合，そのつながりは切れ，重力に従って落ちます．最初に「ぷよ」は色付きの１マス正方サイズの物体，と説明しましたが，組ぷよとして落ちてくる通常のぷよの他，後述の対戦プレイで現れる「おじゃまぷよ」という特殊なぷよは，相手プレイヤーのプレイによって降ってくるもので，色ぷよとは異なり，１個で降ってくることもあればもっとたくさんの数がまとめて降ってくることもあります．

このように組ぷよやおじゃまぷよがフィールド上部から降ってくる形でぷよが積みあがっていくわけですが，上下左右に同色の色ぷよが並んだ場合，それらのぷよは連結しクラスタを構成します．ただし，連結するのは色ぷよのみで，おじゃまぷよは連結しません．色ぷよのクラスタのサイズが4以上になると，そのクラスタは消滅します．この際，消滅した色ぷよに上下左右で隣接しているおじゃまぷよがあった場合は，そのおじゃまぷよも一緒に消滅します．クラスタに消滅したぷよの上に別のぷよがあった場合，そのぷよは重力に従い落下します．この落下によりぷよの配置は変化しますが，その配置において新たなサイズ４以上のクラスタが生じることがあります．そのような場合も，そのクラスタは消滅します．このように，クラスタの消滅が別のクラスタの生成と消滅を生むことを「連鎖」と呼びます．連鎖数は一連のクラスタの消滅回数として定義します．あるクラスタが消滅したが，それによる配置変化ではサイズ４以上のクラスタが生じなかった場合は連鎖が起こりませんが，便宜上これを「１連鎖」と呼びます．順に落ちてくる組ぷよがフィールド上部まで積み上がり，排出口が塞がれてしまうとゲーム終了となります．

「ぷよぷよ」というゲームには1人ぷよぷよ・対戦ぷよぷよという2つの遊び方がありますが，ここでは1人ぷよぷよを扱います．1人ぷよぷよはパズル型ゲームで，ぷよを消すことによって得られるスコアをできるだけ大きくするのが通常の目標となりますが，プレイ中で起こる連鎖数をできるだけ大きくする（連鎖数最大化）のを競ったり，あるいはフィールド内のぷよを一旦すべて消してしまう（全消し）のを目指したりなど，様々な遊び方があります．いずれの遊び方でも「連鎖」を如何に実現するかがカギであり，連鎖設計こそがぷよぷよのパズル性の根源とも言えます．

最適化問題「一般化ぷよぷよ」とアルゴリズム設計

ということで，ぷよぷよの連鎖を最適化する問題を考えることにします．もちろん，実際の「ぷよぷよ」にはリアルタイム性による一瞬の判断やいかに精密に操作するか，また次に降ってくる組ぷよの未知性による難しさ・面白さがあるのだと思いますが，ここではそのリアルタイム性・操作性・未知性を無視し，パズルとしてのぷよぷよの本質を考えることにします．となるとリアルタイム性・操作性はともかく，未知性をどう無視するかが問題となります．ここでは，（反則と思われるかもしれませんが）予め「降ってくる組ぷよの列が与えられているものとする」ことにします．実際の「ぷよぷよ」では次に落下する組ぷよはフィールドの枠外に「NEXTぷよ（ネクストぷよ）」として予告されていますので，この仮定はNEXTぷよの枠を十分に大きく取ったこととして解釈することができます．

さらに，最適化アルゴリズム設計の立場からすると，フィールドサイズ「縦12マス×横6マス」は12,6に特化したものではなく「縦hマス×横wマス」に対応できるもの，あるいは色数に関しても実際の３~５色ではなく，任意のc色に対応できるものを考えたくなります．また通常のぷよぷよはフィールドに何もぷよがないところから始まりますが，途中までぷよが積みあがった状態からどう組ぷよを配置していくかも考えたくなります．以上の設定で考えるのが次の二つの問題です：

連鎖数最大化問題
問題：フィールド上のぷよ配置，落下予定の組ぷよ列
答え：それ以降に起きる連鎖数を最大にする各組ぷよの配置

全消し問題
問題：フィールド上のぷよ配置，落下予定の組ぷよ列
答え：最後の組ぷよの配置後にフィールドにぷよが残らないような各組ぷよの配置

それぞれ各問題に対して所望の答えをする「速いアルゴリズムの設計」が最適化アルゴリズム研究の対象となります．

　ただこの「速い」の定義は曖昧です．単にパズルが解ければよいという立場から考えるとあるぷよぷよの最大連鎖問題（あるいは全消し問題）を解くのにあるアルゴリズムをスパコン上で走らせてそれが一瞬で答えを出すならばそれで事足りると言えば事足りるのでしょうが，それだとスパコンがすごいのかアルゴリズムが良いのか区別がつきません．またフィールドサイズが通常の12×6の場合と1200 × 600 の場合とでは当然後者を解くのに時間がかかりそうで，これらを共通の尺度で測るにはどうすべきでしょうか．

　アルゴリズム論ではそこに入力サイズと計算量という概念を導入します．

まず入力サイズですが，上述の連鎖数最大化問題も全消し問題も「問題」はフィールド上のぷよ配置，その時点以降落下予定の組ぷよ列で，これを文字列なりなんなりで与える必要があります．ここではそのサイズ（入力サイズ）をざっくりと $n$ で表すことにします．いきなり $n$ だとごまかされているように感じる場合には，大まかに $n = h w + p $ と思ってください（ただし，フィールドが縦 $ h $ マス× 横 $ w $ マス，降ってくる組ぷよの数が $ p $ ）．

次に，アルゴリズムの計算量は基本演算（四則演算や代入，条件分岐のチェックなど）の回数で測ることにします．この際，問題のサイズに応じる形で基本演算が実施されるので，計算量は入力サイズ $n$ の関数としてあらわされることとなります．ここで，基本演算には色々あるのにそれを一律で「基本演算」と括ってよいのか，という疑問を持つ方がおられるかもしれませんが，そこは一旦無視することにします．これは例えば実際のアルゴリズム実行において，基本演算の種類によって速い遅いの違いが生じることはあるのですが，ほんの数倍の違いであり，入力サイズの変化による影響の方がはるかに大きいためであったりします．似たような理由から，計算量を「入力サイズの関数の形で表す」際には，オーダー記法が用いられることがあります．オーダー記法の詳しい説明はここではしませんが，大まかには多項式関数の場合はその最大次数の項を係数抜きで書いたもの，くらいに思っておいてください．例えば, $ 10n^3+40 n^2+10 n \log n = O(n^3) $ 　のような形で表します．このオーダー記法の採用が妥当であるかどうかは実際にアルゴリズムが適用されるシーンによるのですが，一元的なアルゴリズムの性能比較にはとても便利であるため良く用いられます．

さて，計算量の議論にしばしば現れるのが「多項式時間アルゴリズム」という言葉です．「アルゴリズムAが多項式時間アルゴリズムである」というのは，その計算量が入力の多項式関数であるときのことを言います．「多項式関数」というと $n$ も $n^2 $ も $n^{10} $ も $ n^{100} $ も含んでいるためあまりにざっくりしすぎていると思われるかもしれませんが，大まかな分類にはとても便利であるため良く用いられます．次の表は $n $ と多項式関数，指数関数を並べたものですが，仮に1秒間に10¹²回の演算が実行できる計算機があったとして，どの程度の時間がかかるかを表しています（ちなみに，2011年ごろのIntel Core i7 Extreme Edition 990x　が159,000 MIPSという性能ですので1秒間に159×10⁹回の単純命令を実行可能です）．この表をみると $n^5 $ と $2^n $ のところに大きな壁があるのを感じていただけるかと思います．

n	n	n²	n⁵	2ⁿ	n!
10	1×10^-11秒	1×10^-10秒	1×10^-7秒	1.0×10^-9秒	3.6× 10^-6秒
20	2×10^-11秒	4×10^-10秒	3.2×10^-6秒	1.0×10^-6秒	28.1日
50	5×10^-11秒	2.5×10^-9秒	3.1×10^-4秒	1.1×10³秒	9.6× 10³⁶億年
100	1×10^-10秒	1×10^-8秒	0.01秒	401億年

このようにみると，n の大きさにもよりますが，ある程度の大きさの n に対してまで使い物になりそうなアルゴリズムは多項式時間アルゴリズムである（逆は必ずしも真ではないですが），と言ってまあ差し支えないだろう，という気分になってきます．

　ということで話を戻しますと，ぷよぷよの「連鎖数最大化問題」「全消し問題」に対しても効率的な（≒多項式時間）アルゴリズムを作りたい！と考えるのは自然でしょう．

例えば，「全てのありうる配置を試してみる」という全く工夫をしないアルゴリズムの場合，各組ぷよの置く場所・置き方の候補は$4w$（場所が $w$ 通り，回転の仕方が4通り）であるため，その計算時間は $ (4w)^p $ となります．通常のぷよぷよでは $w=6$ であることから，そのようなアルゴリズムの計算時間は最低でも $ 24^p $ 程度の演算が必要と言うことで，当然計算時間は$p$の多項式の形にはならず，$p=20$でも膨大なサイズになります．ちなみに，$24^{20}$演算を上述のコンピュータで一秒間に$159\times 10^9$回のスピードで行った場合，8億年以上かかることになります．一方，仮にこの計算時間を$p^5$（多項式）に下げることができたならば，同様の計算は0.02秒程度で終わることになります．できることなら多項式時間アルゴリズムが欲しい！という気持ちがわかっていただけるかと思います．

計算限界とNP完全問題

ではあるのですが，速いアルゴリズムを作りたいといっても無理なものは無理，と言う場合があります．この辺り，計算に関してはなかなかわかりづらいところもあるので，少し丁寧に説明してみようと思います．「計算」に関する限界ではなく，物理的な意味での限界の例として「時速500キロのスピードを超える車を作ることは不可能である」「光速を超えるスピードの乗り物を作ることは不可能である」という二つの文があったとして，これらはどちらも「不可能」を言っていますがその前提が違います．前者は「現在の技術では」という注釈がつくのに対し，後者は「物理法則的に」の意味での不可能性でそもそもそのようなものが存在しえない，という原理的な意味での不可能性を言及しています．

　「多項式時間アルゴリズムを作れない」という主張をするときも同様で，「今のところ無理」なのか「原理的に無理」なのかをはっきりさせる必要があります．ただ「原理的に無理」を言う際には，物理法則における光速のように原理的な限界と照らし合わせながらの主張が必要です．アルゴリズム設計においても，「光速」に類する原理的な限界は存在するのでしょうか？

　残念ながらそのような限界は知られていないのですが，限界の候補とそれを取り巻く理論体系・予想が存在します．「NP完全性」と「P≠NP予想」がそれです．ここでは「P≠NP予想」の中にまでは踏み込みませんが，大まかにはNP完全という計算クラスに属する問題群に対しては，多項式時間アルゴリズムが存在しないという予想で，その真偽の解明が数学ミレニアム懸賞問題の一つにも選ばれています．これを利用するのがアルゴリズム設計の困難性の証明です．つまり，対象問題がNP完全（困難）であることを示してしまえば，多項式時間アルゴリズムの設計が不可能（P≠NPの仮定下で）と言えることになります．NP完全と困難の違いは，とりあえずは「最低でもNP完全なのがNP困難」と思っておいてください．

ぷよぷよに対しては「多少良い」程度のアルゴリズムを作ることすら絶望的

以上を踏まえて，ぷよぷよ「連鎖数最大化問題」「全消し問題」に対する多項式時間アルゴリズム設計について考えることにします．せっかくパズルを解く話をしているのだからできれば「いいアルゴリズムがある！」という話がしたいのですが，残念ながら世の中そんなに都合良い話があるわけではなく，いずれの問題もNP困難であることが知られています．

定理1 [松兼・武永2006]　4色以上のぷよ＋おじゃまぷよありの「ぷよぷよ連鎖数最大化問題」はNP困難
松金　輝久武永　康彦「組合せ最適化問題としてのぷよぷよの連鎖数判定問題」電子情報通信学会論文誌 D Vol.J89-D No.3 pp.405-413 (2006)

定理2 [牟田2005]　2色以上のぷよ＋おじゃまぷよありの「ぷよぷよ全消し問題」はNP困難．
牟田秀俊「ぷよぷよはNP完全」電子情報通信学会技術研究報告. COMP, コンピュテーション 105(72), pp. 39-44, (2005)

ということで，残念ながらP≠NPの仮定の下では，パズルとしてのぷよぷよに対する多項式時間アルゴリズムは存在しないことになりました．

　…と簡単に引き下がってしまってよいのでしょうか．もう少し考えてみることにします．ここで注目するのがぷよの色数です．ぷよぷよは色数が増えれば増えるほど難しくなります（ぷよの色が1色のぷよぷよは明らかに簡単です）．定理１の「4色」を「3色」にすると多項式時間アルゴリズムが作れたりはしないのでしょうか．残念ながら（調べたところ），以下の結果が示されていました．　

定理3 [木場他2011]　3色以上のぷよ＋おじゃまぷよありの「ぷよぷよ連鎖数最大化問題」はNP困難
木場裕矢，宗重成央，上嶋章宏「色数とおじゃまぷよを制限した一般化ぷよぷよの連鎖数判定問題のNP完全性(ワークショップ「娯楽のOR-エンターテイメントの数理」)」，日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2011, pp. 370-371, (2011)

ということで，3色＋おじゃまぷよでも連鎖数最大化問題は難しいわけですが，2色＋おじゃまぷよにしても同様なのでしょうか．こちらは現在のところオープンで難しいとも簡単ともわかっていません．

　次に考えるべきはおじゃまぷよの有無です．おじゃまぷよがない状況でもこれら問題は難しいのでしょうか．以下が知られています．

定理4 [木場他2011]　5色以上のぷよ＋おじゃまぷよなしの「ぷよぷよ連鎖数最大化問題」はNP困難

となると，おじゃまぷよなしの設定で，ぷよ3色，4色のぷよぷよ連鎖数最大化問題は簡単になるのか？という疑問がわきます．ところが，これらの場合でも難しいことはわかりました（今回の結果）．

定理5 [江藤他2021]　3色以上のぷよ＋おじゃまぷよなしの「ぷよぷよ連鎖数最大化問題」はNP困難

全消しはどうでしょう？

定理6 [江藤他2021]　4色以上のぷよ＋おじゃまぷよなしの「ぷよぷよ全消し問題」はNP困難．

このようにこれまで知られていたよりもより厳しい条件でもぷよぷよは難しいことがわかりました．世の中何ともうまくいかないものです．あるいは，今は亡きコンパイルは絶妙に難しいゲーム「ぷよぷよ」を生み出したと言えるのかもしれません．

最後に近似の難しさについても述べておきます．連鎖数最大化問題の場合，連鎖数を最大の組ぷよの配置を求めたいわけですが，この「最大」というのが難しいのであって，「そこそこ大きい」に緩めると簡単になる可能性があるかもしれません．ですがそこまでハードルを下げても依然として難しい，と言うこともわかりました．

定理7 [江藤他2021]　P≠NPの仮定の下で，4色以上のぷよ＋おじゃまぷよありの「ぷよぷよ連鎖数最大化問題」に対する任意の多項式時間近似アルゴリズムの近似比は多項式上界を持たない

近似アルゴリズムというのは最適解を見つけることを目指すが厳密な意味での最適解の導出にはこだわらず，ある程度良い解が得られるならばそれで満足する，と言うものです．その「ある程度良い解」であるかどうかを表す近似比という概念を導入し，これを一定の精度に保つことを目標とします．

問題 $I $ に対するアルゴリズム $ A $ の近似精度（近似比）を $A(I)/OPT(I) $ で定義したとします（ただし， $OPT(I) $ で問題 $ I $ の最適値， $ A(I) $ でアルゴリズム $A(I) $ で問題 $I $ に対する $A $ の出力値を表すとします）．今， $A(I) $ の値は大きければ大きいほど良く，ただ $OPT(I) $ を超えることはできませんからこの値は常に1以下となり，また1に近ければ近いほど（つまり大きければ大きいほど）うれしいことになります．例えば，どのような $ I $ を持ってきても$$A(I)/OPT(I) \ge 　0.8$$が成立しているならばこのアルゴリズムの近似精度は80%であるという保証がなされることになりますので，なんとなく悪くないような気になるかもしれません．ということで，この「0.8」の部分にあたる数字をできるだけ大きくするような，多項式時間アルゴリズムを作りたい，と思うわけですが，この定理7は「そんな考えは甘い」ということを示しています．0.8どころか，どんな多項式 $ f(n) $ を持ってきたとしても( $ n $ は入力サイズ），$$A(I)/OPT(I) \ge 　1/f(n)$$ の保証ができる多項式時間アルゴリズムは存在しない（P $\neq $ NPの仮定下で），と言っているのです．例えば仮に $ f(n)=n^2 $ で精度保証ができるとした場合でも， $n=100 $ として, $1/f(n)=0.0001 $ で，やっと0.01%の精度保証ができる程度で全くうれしくないわけですが，ここではそんなささやかな精度保証すらできない，と言っていることになります．つまり，「ぷよぷよはアルゴリズム設計論的には絶望的に難しく，ほんのささやかな精度保証付きアルゴリズムすら存在しそうにない」ことが示されたことになります．

ただ，これら結果はあくまで「どんな問題例に対しても」「確実に精度保証する」アルゴリズムを作るのが難しいという話で，通常のぷよぷよとは議論の前提が異なるので注意が必要です．

最後に

残念ながら「ぷよぷよ最大連鎖問題」「ぷよぷよ全消し問題」は，色数が少なくて，おじゃまぷよなしの設定でも，多項式時間アルゴリズムを与えるのは難しそう，という結果になってしまいましたが，これはがっかりするべきことなのでしょうか．面白いパズルは大抵の場合計算困難であるという説もあります．これはシステマティックにアプローチすることにより簡単に（≒高速に？）解けてしまえるパズルであるならばそれは面白くない，という考え方に基づくものでしょう．となるとこれら困難性は必ずしも悪いとも言えないようにも思います．実際，Eppsteinのページに集められている良く知られているゲーム・パズルの結果はいずれも何らかの意味で計算困難になっています（15-パズル，麻雀, ラッシュアワー, 上海, 倉庫番, 碁, Hex, マスターマインド, オセロ, リバーシなど）．あるいは，有名なパズルである数独も一般化すると，それが正しい数独の問題例であるかどうかを判定するのがNP完全であることは良く知られています．別の見方をすると，ぷよぷよも色数などを十分制限したとしても，これらのゲーム・パズルと同様，面白いパズルなのだ，ということが言えるのかもしれません．

この記事で紹介したぷよぷよや，上のEppsteinのページで紹介されているゲーム・パズル以外にも計算困難性がわかっているゲーム・パズルは数多くあります．一方，大貧民（大富豪）を「1枚だししかできない」形に制限した「単貧民」と呼ばれるゲームには，高速に必勝判定ができるという結果もあります（木谷先生，大渡さん（AIアスリート），小野による研究）．これらは，チェス，将棋，囲碁などに対する「強いゲームAIを設計する」というアプローチとは異なりますが，アルゴリズム論的・計算論的に「そもそもどの程度難しいのか？」を考えるという意味でいろいろな方に興味を持ってもらえる研究であろうと思っています．

2022年3月21日数理情報学専攻研究アクティビティ, 計算量理論, 研究紹介, 最適化特集, 数理情報学専攻, 自然情報学科, 数理情報系, 組合せ最適化, アルゴリズム

Posted by 小野廣隆