「ぷよぷよ最大連鎖問題」「ぷよぷよ全消し問題」は『多少良い』程度のアルゴリズムを作ることすら絶望的 35
ストーリー by nagazou
なるほどわからん 部門より
なるほどわからん 部門より
ビデオゲーム「ぷよぷよ」をテーマにした「一般化ぷよぷよのより強い計算困難性」という研究が行われているそうだ。この研究ではぷよぷよを一人用のパズルと見立てた場合、どの程度難しいものであるのかを（最適化）アルゴリズム論的に分析するというものであるらしい（Ono Laboratory）。
元記事ではこの「ぷよぷよ」における計算困難性について解説したうえで、ぷよぷよの連鎖を最適化する問題を考えるという内容となっている。そのうち『問:フィールド上のぷよ配置、落下予定の組ぷよ列・答:それ以降に起きる連鎖数を最大にする各組ぷよの配置』を示す「連鎖数最大化問題」と『問:フィールド上のぷよ配置、落下予定の組ぷよ列・答:最後の組ぷよの配置後にフィールドにぷよが残らないような各組ぷよの配置』を示す「全消し問題」に対する多項式時間アルゴリズム設計について考察を行っている。
ちなみに最適解を見つけることは困難で、多項式時間アルゴリズムを与えるのは難しそうであるという結論になってしまった模様。
元記事ではこの「ぷよぷよ」における計算困難性について解説したうえで、ぷよぷよの連鎖を最適化する問題を考えるという内容となっている。そのうち『問:フィールド上のぷよ配置、落下予定の組ぷよ列・答:それ以降に起きる連鎖数を最大にする各組ぷよの配置』を示す「連鎖数最大化問題」と『問:フィールド上のぷよ配置、落下予定の組ぷよ列・答:最後の組ぷよの配置後にフィールドにぷよが残らないような各組ぷよの配置』を示す「全消し問題」に対する多項式時間アルゴリズム設計について考察を行っている。
ちなみに最適解を見つけることは困難で、多項式時間アルゴリズムを与えるのは難しそうであるという結論になってしまった模様。
【動画】クリスマスプレゼントを届けよう！ (スコア:2)
こういうの [itmedia.co.jp]もAIが自動で作りやすくなるといいな
NP完全問題 (スコア:0)
NP完全問題のWikipedia記事 [wikipedia.org]にテトリスやぷよぷよが出て来たのは印象に残ってる。
近似すら無理なのか…と言いたいけど現実問題人間と競える程度のAIは普通に実装できてる気がするし、人間だって計算量は多項式時間だからその上を目指してるんだろうな。
パズルゲームで人間を喜ばす以上のことを目指す必要はないと思うけど、でも出来たら便利。
パズルゲームって実装は割と簡単な部類のイメージだけど、敵AIの実装は結構難しい…のは何だって同じか。
ちょっと数学知識があれば計算量が大幅に減ったりしそうだし、こないだ話題になった数学が役に立つ例かな。
Re:NP完全問題 (スコア:1)
通常の縦12×横6・3～5色程度なら力業でもなんとでもなる。
件の研究では、縦h×横w・c色に一般化していて、そうなると効率の良いアルゴリズムが求められるけど、それが無理だ、という話。
Re: (スコア:0)
ちなみに、、、
元祖ぷよぷよ通のNPCは擬人化アルゴリズムとして4キャラが存在し
処理強弱によって 各パートを処理してます
Re: (スコア:0)
人間を喜ばす系の敵AI実装と大分切り口違うよ。
Re: (スコア:0)
実装割と簡単って
消しルーチンくっつき判定を高効率に無駄なく出そうとすると結構難しいんじゃね？
Puyo Puyoだけに (スコア:0)
PP完全問題、なんつて
Re: (スコア:0)
？？？
何と比べて？ (スコア:0)
ソースのブログ読んでも書いてなかったんだけど『多少良い』って何だよ。
コンパイルだかセガだかの開発者が実装した辛めのCPUには『多少良い』アルゴリズムが使われてるんじゃないの？
Re:何と比べて？ (スコア:2)
定理1 [松金・武永2006] 4色以上のぷよ＋おじゃまぷよありの「ぷよぷよ連鎖数最大化問題」はNP困難
定理2 [牟田2005] 2色以上のぷよ＋おじゃまぷよありの「ぷよぷよ全消し問題」はNP困難．
定理3 [木場他2011] 3色以上のぷよ＋おじゃまぷよありの「ぷよぷよ連鎖数最大化問題」はNP困難
定理4 [木場他2011] 5色以上のぷよ＋おじゃまぷよなしの「ぷよぷよ連鎖数最大化問題」はNP困難
定理5 [江藤他2021] 3色以上のぷよ＋おじゃまぷよなしの「ぷよぷよ連鎖数最大化問題」はNP困難
定理6 [江藤他2021] 4色以上のぷよ＋おじゃまぷよなしの「ぷよぷよ全消し問題」はNP困難．
定理7 [江藤他2021] P≠NPの仮定の下で，4色以上のぷよ＋おじゃまぷよありの「ぷよぷよ連鎖数最大化問題」に対する任意の多項式時間近似アルゴリズムの近似比は多項式上界を持たない
つまり，「ぷよぷよはアルゴリズム設計論的には絶望的に難しく，ほんのささやかな精度保証付きアルゴリズムすら存在しそうにない」ことが示されたことになります．
ただ，これら結果はあくまで「どんな問題例に対しても」「確実に精度保証する」アルゴリズムを作るのが難しいという話で，通常のぷよぷよとは議論の前提が異なるので注意が必要です．
以上は記事リンク先より雑に書き抜き。
多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。
https://ja.wikipedia.org/wiki/%E5%A4%9A%E9%A0%85%E5%BC%8F%E6%99%82%E9%96%93 [wikipedia.org]
…ことになるが、例えば多項式時間多対一帰着や多項式時間チューリング帰着を用いる。もしもあるNP困難問題を解ける多項式時間の機械が存在すれば、それを利用すればNPに属する任意の問題を多項式時間で解くことができる。
https://ja.wikipedia.org/wiki/NP%E5%9B%B0%E9%9B%A3 [wikipedia.org]
「ぷよぷよはNP困難」で済むような。
Re: (スコア:0)
NP困難で多項式時間のアルゴリズムが存在しないというのは周知の前提で、さらに近似比の精度保証が入力の多項式以下となるような多項式時間近似アルゴリズム（ブログではこれを「多少良い」程度のアルゴリズムと呼んでいるっぽい）ですら存在しないというのが今回の発表だから、「ぷよぷよはNP困難」だけじゃ不十分なんだな。
Re: (スコア:0)
先ず、ぷよぷよというゲームのゲームデザインが秀逸であったと褒め称えるべきであろう。
Re: (スコア:0)
#4181281が書いてるように「人間を喜ばす系の敵AI実装と大分切り口違うよ。」
目的は「連鎖数最大化」や「全消し」の手順を求めるアルゴリズムで、対戦アルゴリズムではなく詰めぷよを解くアルゴリズムのようなもの。
『多少良い』とは最適解ではなく近似解を求めること。
Re: (スコア:0)
下手に要約せず「任意の多項式時間近似アルゴリズムの近似比は多項式上界を持たない」と明示した方がいいよな
あるいはこれを表す専門用語を定義した方がいい
お前専門用語やったんかい！というものはあるけど、計算量の分野で「多少良い」はさすがに専門用語ではないだろ
Re: (スコア:0)
それだと私は理解できずにスルーして読まなかっただろうけどね
「多少良い」は門外漢にもすんなり理解できて良い表現でしたよ
Re: (スコア:0)
「最適解を求めるアルゴリズムの処理時間が青天井」は「良いアルゴリズムが作れない」かと関係ないだろ
ただ処理時間の天井が付かない盤面サイズで決まらないってだけ
Re: (スコア:0)
専門用語だったら上界持たないで通じるわけで、わざわざ定義するのはどうだろう。
この分野をやってたときは…自分も「多少しかよくならない」と言ってた気がする。
Re: (スコア:0)
コンピューター側はぷよの順番が予めパターン化されてる前提で連鎖を組んでるとかじゃないの
Re:何と比べて？ (スコア:2)
おじゃまぷよの存在があるので、事前の予想は役に立たない気がします。
反則と思われるかもしれませんがって (スコア:0)
ぷよが出てくる順番があらかじめ全部分かってることにするって
そりゃ反則だよw
Re: (スコア:0)
より簡単な方でもできないって話なんで、これで問題ない
オフライン/オンラインアルゴリズムとかそんな話か
Re: (スコア:0)
緩い条件ですら駄目だから、より厳しい条件ではもっと駄目だって話だぞ
Re: (スコア:0)
既知の場合は一通りだけ計算すればよくて、
未知の場合は全組み合わせを計算しなくちゃいけないから
「より厳しい」って理解でOK？
Re:反則と思われるかもしれませんがって (スコア:1)
別ACですが、全部知っていても(全組み合わせの総当たり以外では)完璧には解けないのに、一つ先しか知らないのに完璧に解けるわけないよね、ってことです。
(逆に、一つ先だけ見て良い結果が出せるなら、全部知ってても一つ先だけ見るときと同じ戦略で良いわけで、全部知ってる方が難しいってことはないかな、と。)
未知だと将来何が来るか分からない状況で、現時点の判断をしていかないといけないことに対し、知っていれば先を意識した判断ができるので、既知の方が当然簡単です。
あと何手か猶予ある段階で、今連鎖始めるか、継続して連鎖増すか…という話とか、既知なら先見て選択する戦略も可能ですが、未知なら連鎖を確実に増やせる状況なのか・ゲームオーバーになるパターンが後にないか？とか、より考えて判断しないといけないですし。
Re: (スコア:0)
一つしか先が見えない前提での最適戦略（人間にとっての最善解）は
全部既知の場合の最適戦略（全知全能神にとっての最善解）より結果が劣るのは当然明らかだけど、
アルゴリズムの問題としては両者は全然別の問題なんじゃないかと思うんだけど
> (逆に、一つ先だけ見て良い結果が出せるなら、全部知ってても一つ先だけ見るときと
> 同じ戦略で良いわけで、全部知ってる方が難しいってことはないかな、と
例えばN回コイントスをするゲームでは、人間は全部表に賭けるだけで人間としてベストの成績が出せるけど
神はそうじゃないので、全部知ってる方が難しい場合もあると思う
Re: (スコア:0)
いや、全部知ってても、1回先しか知らないふりすると、この問題は1回先だけ知ってる場合と同じ結果にできるじゃないですか。
仮に1回先の方が簡単な側面あったとしても、全部知ってる方は何も考えずに1回先だけみて同じことすればいいのです。
この特性があるので、この問題は全部知ってる方が制約緩い(簡単)って話になります。
ここら辺は、オンラインアルゴリズムの競合比とかあたり調べればいいのかなと思います。
Re: (スコア:0)
成績だけでいえばその通りですが、問題は計算量でしょう
N回コイントスの例で言うと、たしかに神は人間の真似をすれば勝率0.5は出せますが、それは神の最善戦略ではありません
「神が勝率1.0を出す為に何をすればいいか」と、「人が勝率0.5を出すために何をすればいいか」は全く異なる問題なのであって、
前者で計算量が必要だからといって、後者ではもっと必要になるということにはならないでしょう
実際、コイントスでは、人は全く計算する必要なく人にとっての最善戦略を実現できるのですから
今回のぷよの計算はあくまで前者、神のための最善解と、それに必要な計算量を示したにすぎないと思うのですが
Re: (スコア:0)
あぁ、簡単という言い方が微妙なんですが、全部知ることができるなら、1個先しか知らない問題の解き方を全部再現できるわけです。
で、その前提で、全部知ってても解けないってどういうことか？と考えて下さい。
全部知ってる方の解き方には、1個先知ってる方の解き方が全部含まれます。
で、全部知ってる方に解く方法ない、というなら、1個先知ってる方にも同様に解き方はないという話が成立します。
したがって、全部知ってる方で総当たり以外手段ない、といえば、自動的に1個先だけの方にもマトモな解き方が無いが成立します。
解けないという方向で証明しようとするなら、全部知ってるオフラインの方を考えるのが簡単という話になります。
Re: (スコア:0)
ちょっと補足しておきますと、今回連鎖数とかの最適化の話になるので、最良の答え(例えば最大連鎖)にたどり着かないといけない、という前提に注意してください。
1個先と、全部知ってる方のどちらも、最良の結果を出さないといけません。
勝つとかそういう話はなく、最良の結果が出せるかだけが問題になります。
で、前述のとおり全部知ってる方は1個先の戦略は利用できるので、1手先と同等か、より良い結果が出せます。
そのうえで、全部知っていたとしても、(P≠NPなら)最良の結果に多項式時間のオーダーでたどり着く方法が無いというのが結論です。
コイントスの例は微妙なのですが、別に勝率1.0出そうとするわけでなく、最良の戦略はどうなるかという話だけなので、それが勝率0.5なら1手先と同じ戦略とれば良いという話です。
この話は最良の結果を出せるか、と問われていて、常に勝て、と言ってるわけではないです(最良の結果出せるなら、勝ちが引き分けにはなりますが)。
Re: (スコア:0)
こちらは（全知全能神しか知り得ない、反則をしないと辿り着けないような）最良の答えには全く興味ないって立場なので
「最良の答えに辿り着かないといけない、という前提」の話をされても困ります
次善以下の答えしか得られないが、人間でも実行可能なアルゴリズム（とそのための計算量のオーダー）は、
神にしか使えない最良の答えを求めるアルゴリズムとは別の話だし、どっちが簡単かも自明じゃないですよね、という話です
「最良の戦略はどうなるか」じゃなくて、「最良の戦略は（どうせ実行不能だから）どうでもいいよ」なんですよ
Re: (スコア:0)
いや、大本の問題がそれを求めてないので、ということです。
この話のうち、NP困難を示す部分は、最良の結果で解けるかどうか？で、結論は全部知ってても解けない(から、今までの話から1手でも解けない)です。
(効率的な近似解がないという話のところは…まぁこれも似た様な話で1手先読みでも同じと証明できます)
実際どう解くかというところは、近似解だすとかしない限りは重要じゃないんですよね。
そして、そういう手法を見つけなくても答え出せないことを証明する方法が、NP困難とかそういうところにはあります。
あとこれ全知全能じゃないと解けないような反則を前提とし
Re: (スコア:0)
> いや、大本の問題がそれを求めてないので、ということです
たしかにその問題設定であれば先読みは問題にならない（より緩い条件設定になる）ですね
そういう話をされてたんですね、やっと分かりました
Re: (スコア:0)
でもあれ、ルールによってはある程度は決まってたような……
Re:反則と思われるかもしれませんがって (スコア:1)
初期のぷよ通の攻略本で読んだ記憶では、「対戦開始時に128組？の配牌を作成して、それを順番に落とす。その際、各色のぷよは同数になるようにする。128組落とし終わったら、おなじ配牌を最初から順番に落とす。」という仕様だったような。
（対戦の場合は、1pも2pも同じ配牌が落ちてくる）
計算量勝負が確実 (スコア:0)
高性能GPUを複数台使って、計算量ごり押しで最適解を見つけるのがいい