セル・オートマトンとは、互いに隣接しているセルが状態を持ち、それらが隣接しているセルの状態をもとに状態を遷移させていくモデルである。与えられる規則が単純でも、豊かな結果を得ることができる。本研究では、落ちものパズルゲームである「ぷよぷよ」を1次元セル・オートマトンにて実装し、セル・オートマトンのゲームへの応用の可能性を検証した。
オートマトンとは初期状態から開始され、ある内部状態に対してある値が入力されると、どのような状態に遷移するかというシステムである。図1に簡単なオートマトンの例を示す。
1次元セルオートマトンとは、一列に並んでいる格子状のセルにオートマトンを配置し、隣接セルの状態を入力として状態遷移をするものである[1]。本研究では、セルは片無限に配置されているものとする。 また、あるセルの次の状態が、そのセル自身と両隣にある2つのセル、つまり3つのセルで次の状態を算出する3近傍を採用している。つまり、各セルの状態遷移は遷移関数を f とすると次のように表される。
図3では、1次元セルオートマトンの状態遷移の時間経過を表しており、本研究で利用したぷよぷよを左に移動させるための状態遷移を示している。セルの上側に記されている数字は、何番目のセルであるかを表しており、各セルに記されている文字はそれぞれのセルの内部状態を表している。t = 0で初期状態を与えており、t = 1の3番目のセルの状態は、t = 0時の2、3、4番目の3つのセルから算出される出力で決定される。つまり、f (0, 0, b9) = bBという遷移規則を持つ。このような遷移規則に従って全てのセルが一斉に変化する。このセルが更新されるにあたって時間が1ステップ進むことを、1世代進むと一般的に呼ばれている。
2次元セル・オートマトンは、1次元セル・オートマトンを2次元に拡張したものである。2次元セル・オートマトンで用いられる有名な近傍として、ムーア近傍とノイマン近傍がある[2]。この2つの近傍の違いとしては、遷移規則に従うセルの範囲が異なる。図4、5のグレーに塗られている部分が該当の範囲である。ノイマン近傍では中央のセルを含む５近傍に対し、ムーア近傍は９近傍である。
ノイマン近傍では、5近傍のセルの状態によって中央のセルの次のステップの状態が算出される。ノイマン近傍を式に表すと以下のようになる。
ムーア近傍では、9近傍のセルの状態によって中央のセルの次のステップの状態が算出される。ムーア近傍を式に表すと以下のようになる。
この2次元セル・オートマトンには外部総和型というものがある。上記で紹介した2式は、中央のセルを含め隣接するセルに対してそれぞれに遷移規則が定義されるが、外部総和型では、中央のセルを除いた周りのセルの値の合計で、中央のセルの次のステップの状態が算出される。ムーア近傍の外部総和型を式で表すと以下のようになる。
一斉射撃問題とは、1957年にJohn Myhillにより提案された、1次元セルオートマトンが同期するためのアルゴリズムを見付ける問題である[3]。有限の長さを持つ1次元3近傍セル・オートマトンにおいて、セルの一つを将軍とし、それ以外を兵士とする。将軍が射撃命令を下すことにより、将軍を含め兵士全員が、同時刻で射撃状態に移行するように、兵士たちの状態遷移関数を構成する。なお、いくつかの条件があり、情報伝達は将軍、兵士とも1ステップに両隣にしか伝えられない、兵士は一斉射撃になるまでは、射撃状態に入ってはけない、などの制約がある。これにはいくつかの解法が知られている。
ライフゲーム (Conway's Game of Life) は1970年にイギリスの数学者ジョン・ホートン・コンウェイ (John Horton Conway) が考案した生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲームである[4]。セルオートマトンの中でも最も有名であり、2次元セル・オートマトンで内部状態が「生」と「死」のみという非常に簡単なルールで成り立っている。ライフゲームではムーア近傍を採用しており、外部総和型のセル・オートマトンである。なお、以下のルールに従ってセルを黒と白に区別をする。
Panic Shooterとは、2次元セル・オートマトンを用いたシューティングゲームである[5]。このゲームは、StarWarsというルールを使用しており、Generationsと呼ばれるグループに属しているルールである。これは、ライフゲームと同じ外部総和型のムーア近傍であり、状態数が多いことが特徴である。ライフゲームでは生と死のみ、つまり状態数が2であったが、Generationsルールでは生から死に変化するまでいくつかのステップを経て死に至る。このステップ数は、各ルールの状態数によって決まる。また、Generationsルールには共通の表記法があり、S / B / Cと表記される。Sは、生のセルの周囲8セルに生のセルの総和がいくつであるかを意味しており、条件と同じであれば誕生または生存する。Bは、死のセルの周囲8セルに生のセルの総和がいくつであるかを意味しており、条件と同じであれば誕生する。SとBの条件に当てはまらなければ死になる。Cは、状態数を表している。
ここで、StarWarsについて説明をする。このルールは234/2/4と表記される。状態数は4なので、状態は0、1、2、3の4つであり、3は生、0は死を意味している。
固定物体とは、ステップがいくつ進んでも内部状態が変化しないパターンのことである。図10にある内部状態を先ほどのStarWarsのルールに当てはめると、どの部分でも現在の状態から変化はしない。
移動物体とは、ステップが進むにつれて移動しているように見えるパターンのことである。
繁殖型とは、マス目が無限であれば増え続けるパターンである。図14より、新たに作り出されたセル群は、先ほどの移動物体である。右側の作り出している部分が繁殖型である。
シューティングゲームとしても十分に楽しめるが、弾を撃ち込んだ後に炎上するのか跳ね返すのかというような、どのように変化していくのかを見ていると、新たな発見がある。上記で紹介したパターンの物は、このゲームで初期状態で配置されているものだが、遊んでいるうちに上記のものとは違う組み合わせの固定物体であったり、移動物体などを発見することができる。これもまた、セルオートマトンを利用したシューティングゲームならではの面白いところである。
1次元セル・オートマトンでのぷよぷよの実装にあたり、簡単にぷよぷよについて説明する。ぷよぷよのルールを以下に示す。なお、図中の丸みを帯びたキャラクターは、ぷよと呼ばれているため、以下ではぷよとする。
今回、1次元セルオートマトンにてぷよぷよを実装するにあたって、ルールを若干変更した。ぷよの色数を、4色から2色へ減らした。また、落下する個数を、2個1組ではなく、1〜3個へ変更した。これを状態数31、ルール数180の1次元3近傍セルオートマトンで実装した。 1次元2色ぷよぷよの動作の流れの一例を示す。
1次元2色ぷよぷよの解説をするにあたって、図16のような動作を仮定する。まず、青いぷよが2つ落下し、左側に静止する。続いて赤いぷよが落下し、青いぷよの隣に静止する。さらに赤いぷよが2つ落下し、赤いぷよが4つくっつく。同じ色のぷよが4つくっついたので赤いぷよは消去される。このような流れで説明をしていく。
図17より#は左端を表しており、静止状態である。色を区別するため、それぞれの内部状態にa、bを表記している。aは赤色、bは青色を表している。まず、t = 0で初期状態として配置する。青いぷよを左に移動させるために、t = 1の5、6番目に青いぷよが移動するように遷移規則を定義する。7番目にあるbAという内部状態だが、これはこの後にぷよが落ちてきた場合、落下してくるぷよの先頭が障害物があると認識させるために、定義をしている。また、この青いぷよは移動速度を2ステップに1マス進むように定義をしたが、これは2つ以上のぷよが連続して落下してきた際に処理しきれなかったのを回避するためである。
左隅に達したぷよは、壁を貫通することなくそこで留まらなければならない。また、ぷよは4つ以上くっつくと消滅するルールになっているが、4つ以上くっついたかどうかを知るために、ぷよを数える必要が出てくる。そこで、最初に壁に向かって落下するぷよに対して、一番目に停止したというのが分かるように番号を振っていく（図19）。t = 9の一番目を見ると、静止したぷよにb1と内部状態を定義している。t = 10では、2番目の青色のぷよにb2と定義をした。この振られた数字から、壁から何番目に停止しているかが分かる。次に赤色のぷよが落ちてくるが、ぷよが消滅する条件は同色のぷよは4つ以上の時だけである。そのため、落下してくる赤色のぷよの先頭には、先に静止している青色の2番目のぷよを壁と認識させれば良い。落下してくる先頭の赤色のぷよが、b2を認識してa1になるように定義をすれば良い。この後は、先ほどの青色ぷよと同様に番号を振っていく。
図21よりｔ=15で赤色のぷよが落下してくるが、先に静止しているぷよと同色のため、壁とは認識せずにすでに振られている数字に続けて数字を振るように定義をする。この場合は、先に振られている英数字がa2のため、これに続いて振るべき英数字はa3である。a2に続いて、a3、a4と定義をしていく。ここで赤色のぷよが4つくっついたので、この赤色のぷよを消す必要がある。どのようにして消すかだが、t = 18の4つくっついているぷよを見てみると、今は4つとも違う内部状態である。この4つは最終的に消滅させたいが、消えるということはそのときの4つの状態はいずれも0である。よって現在の異なる状態から、4つとも同じ状態へ持っていけば実現できる。
ここで、一斉射撃問題を適用する。t = 18 でぷよが消える条件になっているため、次のステップから一斉射撃を行うための準備に入る。将軍は消去したいぷよから選べば良いが、今回は６番目にある内部状態がa4であるセルを選んだ。t = 19では、a4自身と左側にあるセルa3に一斉射撃の準備段階に入るよう情報を伝達する。t = 20では、t = 19で伝達されたセルがそのセル自身と、両隣のセルにまた情報を伝達していく。同様に次のステップでも伝達を行う。t = 21で消したいぷよ4つが、全て同じ内部状態になる。これで、t = 21の3番目から6番目にあるセルは一斉射撃の状態に入ったことになる。消したいぷよが全て同じ状態なので、これらの内部状態を0に遷移させるのは容易である。
本研究では、1次元セルオートマトンで落ちものパズルゲームである「ぷよぷよ」を実装し、セルオートマトンのゲームの可能性を検証した。今回は、1次元2色ぷよぷよとして遷移規則を定義した。その結果、1次元でぷよぷよが動作する遷移規則は作成できた。
今後の課題としては、遷移規則と初期状態を与えると、作成した遷移規則に破綻がないか確認できるプログラムを作成し、視覚化をする。遷移規則を簡単化やゲームの拡張などをしたいと考えている。また、今回のアルゴリズムを他の分野で応用できるものはないか模索していきたい。
今回作成した、1次元31状態3近傍のセル・オートマトンのルールは、以下からダウンロードできる。
ダウンロード(4KB)