313

ACぷよ通の配ぷよアルゴリズム

by
低頭ちゃん
低頭ちゃん
セガぷよの配ぷよデータ公開の投稿で、私は「ACぷよ通の配ぷよ生成法は一様ランダムシャッフルそのものではないにしても概ね達成していると考えており、自分なりの根拠もある」という意味のことを書いた。その時点で私が持っていた「根拠」は、他人と共有するにはやや問題があるものだったが、その後の調査で、量的にやや不十分ながら共有可能なデータを作成できたので、二回に分けてACぷよ通の配ぷよを扱うことにする。(特に断らない限り通常の四色対戦に絞って議論し、無関係な話題は適宜省略する。)

まず今回の投稿では、解析によって得られたACぷよ通の配ぷよアルゴリズムについて概説する。「ACぷよ通の」と書いたが、私が実際に解析したのはメガドライブ版ぷよ通である。(注1)ACぷよ通にはセガ製のアーケードゲーム基板「システムC2」が使われたとのことだが、この基板とメガドライブはメインCPU等が共通で、両者間の移植を視野に入れてゲーム開発・マーケティングができるようになっていたようである。ACぷよ通とメガドライブぷよ通はリリースが同時期であり、そのまま流用したコードも少なくなかったと考えてよいだろう。実際、これから述べるように、メガドライブぷよ通の配ぷよアルゴリズムが生成可能な配ぷよは私が調査した範囲で約20億通りに絞られ、これを用いてACぷよ通の対戦動画でツモ予見等が実現できる。このことから、配ぷよ生成に使われているプログラムは、ACとメガドライブで全く同等であると考えてよいであろう。(この投稿を準備中に「SEGA AGES ぷよぷよ通」がリリースされたが、Youtubeのプレイ動画で確認したところ、少なくともオンライン対戦の配ぷよは同じ方法で生成されているようである。)

ただ、ACぷよ通にメガドライブ版にはない配ぷよ選別処理がある等、配ぷよ生成とは別に配ぷよ分布に影響を与えている要因(意図的にせよ、偶発的にせよ)があって、それがACとメガドライブで違う、といった可能性もある。また、メガドライブ版に限っても、現状私が調査できた範囲では、生成可能な配ぷよがどんな分布で選択されるかを予測するのは困難である。この点を補うには、実戦で現れた配ぷよを収集するのが結局早道であろうとの考えから、次回の投稿ではmomoken連戦祭の全試合の配ぷよデータを公開して分析する予定である。

なお、これまでの投稿では、解析によって得られたアルゴリズムを、再実装可能なレベルの詳細まで記述することは避ける、という方針を採ってきた。この投稿でもその方針を守ることにする。(注2)私的な情報共有は可能だろうから、プログラムを見せて欲しい、という人がいるなら対応を検討したいが、実用上有用なプログラムなのかというとそうでもないので、法的なリスクがあるならあまり積極的にはなれないところはある。データを配ぷよの形で公開しようとすると、バイナリ形式でも巨大なサイズになるので、今のところ公開する予定はない。そういうわけで、前回の投稿同様今回も、読者が検証できるデータは提供できない。次回は誰でも検証できるデータを公開する予定である。

これからアルゴリズムの概要を述べるが、配ぷよ生成を再現するために私が書いたプログラムをもとにして記憶で補いつつ書くので、細部の表現は必ずしも本来の実装と一致しない場合があるだろうことを断っておく。また、私が実際に解析で得た情報からやや飛躍した断定等をしている部分があるが、ご了承頂きたい。

使用色選択
まず、三色ルール、四色ルールでそれぞれ使用される色を次の手順で決定する。
  • 赤、黄、緑、青、紫をこの順に(順番はこの概説の範囲ではあまり意味がないが、紫が最後であることには意味がある)並べた列を作る
  • 列の一番目から五番目までの要素を順に、「列の先頭4つから乱数で選択した要素」と交換する。
  • 得られた列の先頭三色、四色をそれぞれ取って配ぷよに用いる
二行目で、交換の対象を列全体でなく先頭四つから選んでいるのはおそらくバグであろう。上記の手順だと、五回目にまだ手を付けていない五つ目の紫を、先頭四つのどれかと交換するので、四色ルールには必ず紫が採用される。任意の四色が採用されるようにしたいなら、交換対象を列全体にすることは考えられるが(調査がやや不十分だが、4つからの選択には範囲指定乱数生成用のサブルーチンが使われていると思われ、選択範囲を5つに変更するのは容易であろう。)、そうして得られるアルゴリズムでは(真の乱数の下でも)一様なシャッフルが実現されないことはよく知られている。(注3)もし後継のコンパイルぷよ実装にそのような修正を施したものがあるなら、三色配ぷよの使用色に多少偏りが出るなどの挙動を示すものと思われる。

配ぷよ列のシャッフル
選ばれた色を使って、次の手順でぷよ列を生成する。
  • 選ばれた四色をABCDとして、ABCDABCD...と順に256個並べた列を作る。
  • 列の後ろの要素から順に、「列全体から乱数で選択した要素」と交換する。
  • 同様に、三色をABCABC...と256個並べた列(Aが一個多くなる)を同じ手順でシャッフルする。
 この手順で一様なシャッフルが得られないのは上で述べたのと同様である。(こちらは範囲指定乱数生成サブルーチンを使わず、乱数から直接8ビット分取ることでぷよを選択しているので、処理の簡略化のために一様でないシャッフルを採用した可能性もある。)特に、ぷよ列中の場所によって色の偏り方に差が生まれることには注意が必要である。ただし、列の長さに比べて要素の種類が少ないので、一様なシャッフルとの差は微妙である。(次回も触れるが、具体的には「列の前の方ほど偏りが小さい」ぷよ列が得られるようである。ただ、その差は小さいので、意図的だったとしても結果的には大した効果は上げていないと思われる。)(2020-01-24 追記:括弧内の前半の記述には私の勘違いがあったようである。ただ、後半の「大した効果はない」という主張には問題はないものと思う。)

ツモの取得
以上の処理によって得た三色、四色のぷよ列を軸ぷよ先の組ぷよ列と見て、次の順に取ってツモを得る。
  • 三色の3組目
  • 三色の2組目
  • 三色の1組目
  • 四色の4組目から128組目
  • 三色の1組目
  • 三色の2組目
  • 四色の3組目以降
メモリ上では四色配ぷよの冒頭二手分が三色配ぷよで上書きされており、二週目はメモリ上のぷよが順に取られているだけである。(注4)

これはメガドライブ版の挙動であるが、AC版の二週目の挙動等については検証しきれていないところがあることを断っておく。(なお、momoken連戦祭の次の試合では130手目までが観測できる。https://youtu.be/CQBNW0TNzDI?t=11186

乱数生成器の挙動
配ぷよ生成に使われている32ビットの乱数生成器はゲーム中の他の場面でも呼び出されており、おそらく汎用のものであろう。(注5)この乱数生成器は三種類の32ビット値を参照しており、一つは直前の乱数値、他の二つはそのときたまたまレジスタに入っていた値である。レジスタの一方はデータレジスタで、頻繁に上書きされるので、配ぷよ生成中は直前の処理によって値が決まる。もう一方はスタックポインタで、配ぷよ生成時は呼び出し箇所に応じた定数になっている。そのため、乱数生成器も含めた配ぷよ生成の挙動は、配ぷよ生成直前の32ビット乱数値だけで完全に決定できる。

結果として、配ぷよ生成器の初期状態は高々2^32=4294967296通り想定すればよいのだが、初期状態が違っていても途中で合流するパターンがあるため、生成される配ぷよはそれより少なく、2282510154通りである。また、この約20億通りの中には非常によく似た配ぷよが含まれている。(使用色がちがうが配列が似ているものも多数含まれていると思われる。)配ぷよパターンの確定に必要な冒頭手数は最小で7手だが、最大で128手、すなわち一意なツモ予見が最後までできないパターンがある。(もっとも、確定に手数を要するパターンは基本的にはよく似た配ぷよが他にもあるというだけなので、大部分のツモは冒頭十数手で一意に確定するものと思われる。)

こうして得られる配ぷよ集合に、連戦動画等に見られるACぷよ通の配ぷよが含まれていることを確認できる。例えば、次回の投稿で扱うmomoken連戦祭の配ぷよは、全てこの集合に含まれている。従って、メガドライブぷよ通の配ぷよ実装はACぷよ通と同じだと考えてよいであろう。AC版とメガドライブ版が全く同じ実装を採用していたとしても、スタックポインタの値がずれることは考えられるが、実際には同じ値のままでツモ予見が可能なので(逆に、スタックポインタの値を変えると生成される配ぷよ集合は大きく変わるようである)、少なくとも通常の対戦に関しては、その点も込めて全く同じ実装になっていることが予想される。

上で述べた「2282510154通り」というのは2^32通り全ての初期値が可能だという前提で得られるものなので、現実に出現しうる配ぷよがもっと少ないことは考えられる。実際このアルゴリズムで、適当な初期値から配ぷよ生成だけを繰り返していると、数千通りの配ぷよしか生成されない、といったことが起こる。実機の稼働時には、配ぷよ生成以外の用途で乱数生成器が使われる際にレジスタの値から多様性が補充されていると思われるが、そうした挙動も考慮した上で生成可能な配ぷよ数がどの程度になるかというと、現状私にはっきりしたことは分からない。配ぷよ生成の合間に数パターンの乱数生成処理を挟むと、生成されうる配ぷよは容易に数億に達するので、億単位の配ぷよが、少なくとも配ぷよ生成器の出力の段階では実機でもあらわれるものと考えているが、詳細な解析は今後の課題である。また、この点については、メガドライブ版だけ調べても、AC版の挙動を推測できる十分な証拠は得られないかもしれない。(注6)

結局ACぷよ通の配ぷよの偏りはどうなのか?
私が配ぷよアルゴリズムを解析した目的は、ACぷよ通の配ぷよの偏りがどんな性質を持っているかを知ることにある。上記のアルゴリズムだけ見る限り、既に述べた通り、生成される配ぷよは「一様なシャッフルで得た四色配ぷよの頭を同様の三色配ぷよで上書きしたもの」と、非常に似通ったものになるはずである。すなわち、つみ氏の解析(https://puyo-camp.jp/posts/104263)等に基づくなら、現行セガぷよより偏りが大きいとみられる、一様シャッフルによる128手色均等と大差ないことになる。実際に、次回の投稿で述べる通り、配ぷよ生成時の32ビット初期値を一様独立に取るなどした場合、上記のアルゴリズムが生成する配ぷよが持つ偏りを適当な指標で評価すると、128手色均等のものと近い値になる。

ただ、これも既に述べた通り乱数生成器の挙動には把握しきれていないところがあり、対戦中の乱数生成器の呼び出しパターンと配ぷよアルゴリズムが絶妙にかみ合って色の偏りに一定の傾向が加わる、というようなことがあり得ないとは言い切れない。仮にそのような問題がなかったとしても、配ぷよ生成とは別に、偏った配ぷよを選別する機構が実装されている、といった可能性もある。これについては、メガドライブ版についても調査は不十分だが、AC版にメガドライブ版とは違う処理が入っている可能性を考えると、現状私が調査できる範囲を超える。

そういうわけで、プログラム解析によって「ACぷよ通の配ぷよの偏り」に関する結論を出すのはひとまず断念し、実戦で現れた配ぷよの解析に移る。
momoken連戦祭の配ぷよ分析

余談・現行セガぷよの配ぷよはなぜあんなに少ないのか?
現行セガぷよの対戦の配ぷよパターン数は、これまで知られている限り、オンライン、オフラインとも65536通りに限定されているようである。この挙動は、配ぷよ生成時に「乱数」の初期値を人工的に16ビットに制限することによって得られており、少なくとも現行配ぷよの導入時点では意図的な処置だったと考えられる。

具体的にどんな意図があったのか、という問題には、つみ氏が「ダメツモ排除のため」という説を提唱している。(https://puyo-camp.jp/posts/104263

解析で得られたアルゴリズムを踏まえるなら、ぷよ通の時点では、配ぷよ生成の段階で現行配ぷよにみられるようなパターン数制限を課す方針はなかった可能性が高いように思える。生成後に自動的なダメツモ選別が行われている可能性は、現状私の調査範囲では否定することはできない。ただ、もしぷよ通当時にそのような自動選別ができていたとすると、セガぷよ環境が「生成時に数万通りに制限して開発段階でチェックする」という方針になっているなら退化ということになる。また、仮に何か選別があったとしてもACぷよ通の配ぷよ数は現行セガぷよより多かったと想像できる。そうでなければ、ACでも現行環境に匹敵する程度の配ぷよ一致が報告されているはずだが、実際にはそうはなっていないように思えるからである。(もっとも、本当にAC時代に配ぷよ一致が今より少なかったのかは今後の検討課題ではある。)つまり、現環境はパターン数の点でも、AC通等より退化しているということになる。

いずれにせよ、ダメツモの管理がパターン数制限の理由なのだとすると、どこかの時点でぷよ通当時のダメツモ管理(あるいは、ダメツモ管理をしなかったこと)に問題があると認識され、配ぷよ数を制限する方向に向かったということになる。その際、配ぷよは65536もあれば十分に決まっている、といった判断があったのだろうか。

配ぷよ数制限に関する他の論点としては、何度か引用した5ch投稿にある、「オンライン対戦の通信プロトコルが16ビットで配ぷよ指定するようになっていて、その部分の実装に手を付けるのを開発側が回避してきたのではないか」というものもある。これは仕様が維持された事情の説明にはなっているかもしれないが、そもそも65536で十分という判断の根拠がなんだったのか、という問題は残る。また、通信プロトコルが原因なら、オフライン対戦の方まで配ぷよパターンを制限する積極的な理由がない、という問題もある。

もちろんこれらは憶測で、実際の理由がなんであったかは、公式アナウンスでもない限り確定はできないだろう。

権利関係のこと
この投稿のために私が行った解析、および結果の(この投稿程度の粒度での)公開に、法的な問題はないと考えている。ただ、この点について私の知識で正確な判断は下せないので、識者から納得のいく形で問題の指摘があれば、表現の変更等対応を検討する。


(注1)おそらく同様の解析の先例はあるだろう。ACぷよ通についてもROMを吸い出して遊んでいた人々は少なくないようなので(「ROMを吸い出して」ではなく「誰かが吸い出したROMで」なのかもしれないが、実態がどうだったのか、権利上問題はなかったのかなど、私は詳しくは知らない。興味を持たれた方は識者に取材するなりして調査されるのがよいだろう。)、配ぷよアルゴリズムを詳しく知っている人もいるかもしれない。私自身の解析はやや中途半端なところでとどまっているので、先例の情報が出てくるのではないかと期待して様子見していた部分はあるのだが、私の知る限りはっきりした情報は出てきていないようなので、自分の解析結果に基づいて投稿することにした。

(注2)この種の情報の公開が法的にどの程度制限されるのか私はよく知らないので、「実は(配ぷよ程度なら)アルゴリズムを完全公開しても問題ない」といった話があるなら、詳しい方の意見を伺いたい。

(注3)一様なシャッフルを得たいなら、フィッシャー・イェーツ法等を用いればよい。そうしなかったのが意図的なのかどうかは分からないが、「一様かどうかは知らないが、特にこだわる必要はない」といった判断があったとしてもおかしなことではないだろう。

(注4)この挙動がなぜ採用されたのかは私にはわからない。前提として
  • 色数(レベル)選択前の時点でNEXTフィールドにぷよを描画したいなら、少なくとも二手目までは三色にする必要がある
  • 対戦中は配ぷよ列から三手分(NEXTと操作中のぷよ)を読み出すことになるので、「三手分読み出し」の状態を試合開始時点から維持した方がプログラムが簡単になる可能性はある
といったことは考えられるが、実際の挙動がこれだけで説明できるようには思えず、開発時に何か混乱があったのかもしれない。

(注5)あまり詳細な調査をしていないのでやや憶測が混ざるが、ぷよぷよ20thの配ぷよ生成は少し事情が違っている。(2020-02-02追記 ここで問題にしているのはオフライン対戦の配ぷよである)20thでは32ビットの汎用乱数生成器の出力を16ビットに制限して、配ぷよ生成用の32ビット乱数生成器に与えている。後者は乱数というより、16ビットの配ぷよIDをぷよ列に対応付ける機構の一部とみなすこともできるかもしれない。ただし、どちらの「乱数生成器」も同じパラメータの線形合同法である。なお、この投稿を準備中に、テトリスTAS等のために行われているぷよテトの解析で、関連する情報が得られていることを知った。例えばhttps://www.youtube.com/watch?v=L5nGTGvPZUIの解説には、20thの解析で得られた情報と符合する部分がある。動画中に1973という数が出てくるが、これは配ぷよ生成時に乱数生成器が呼び出される回数と一致していて興味をひかれるところである。

(注6)乱数生成器の初期化に関する問題も検討が必要かもしれない。メガドライブ版の乱数生成器は定数で初期化されているようで、その後ユーザー入力のタイミング等で次第に多様性が増すものと思われる。AC版については、エミュレーター上で使用する際起動直後の多様性確保のためのノウハウがあった、というような話も伝わっているようだが、私は詳しいことは知らない。いずれにせよ、実機での連戦開始時等には十分多様性を確保できていると考えてよいだろう。
更新日時:2020/02/02 14:50
(作成日時:2020/01/19 21:13)
コメント( 0 )
コメントするにはログインが必要です
シェア