32バイトの表が、40年間だれにも説明できなかった｜Atari 2600 の迷路生成

32個の数字が並んだ表があります。0 と 1 と 2 と 3 だけ。それが1982年のゲームの中で、迷路を1マスずつ決めていました。

その表がなぜ機能するのかを、40年近く誰も説明できませんでした。プログラムを書いた本人にも。

私はこのゲームを遊んだことがありません。持っているのは、後年の研究者が残した解析結果と、そこから読み取れる仕組みだけです。以下は、公開されている論文と報道を読んで、自分なりに追いかけた記録になります。実機やエミュレータでの動作確認はしていません。

32バイトの表

先に答えを出しておきます。Entombed というゲームには、迷路を1マスずつ決めていく処理があって、その判断のすべてがこの32個の数字に入っています。

0 は壁を置く。1 は通路にする。2 と 3 は、そのときの状況で決める。それだけの表です。

この表を使うと、行き止まりのない迷路が生成されるとされています。プレイヤーが進める道が常に残る。なぜそうなるのかを、当時の開発者は説明できませんでした。2018年に学者が調べても分からず、Wikipedia の「未解決問題」の一覧に載りました。

以下は、その表がなぜ生まれたのかという話です。答えは、当時のハードウェアの側にありました。

128バイトのメモリ

Atari 2600 は1977年の家庭用ゲーム機です。数字を並べると、いまの感覚では信じにくいものが出てきます。

CPU は MOS 6507、1.19MHz。RAM は128バイト。キロでもメガでもなく、バイトです。ROM のカートリッジは4KB。画面は160×192、色は128色のうち同時に使えるのがごくわずか。

128バイトというのは、この段落を UTF-8 で書いたら入りきらない量です。ゲームの状態、プレイヤーの座標、スコア、残機。全部そこに収めます。

もうひとつ、フレームバッファがありません。いまのゲーム機は画面1枚分の絵をメモリに描いてから表示しますが、160×192 のドットを保持するだけで数キロバイト要ります。128バイトでは持てない。

だから Atari 2600 は、テレビの走査線が画面を上から下へ描いていく、その1本1本に合わせて、プログラム側が「次はこの色」と間に合わせで指示を出します。当時の開発者はこれを「ビームを追いかける」と呼んでいました。1行ぶんの猶予は 76 クロックサイクル。そのあいだに次の行の準備を終える。間に合わなければ画面が崩れます。

4KB に迷路を入れる

Entombed は1982年、US Games から出ました。ゾンビの追ってくる迷路を、ひたすら下へ降りていくゲームです。迷路は終わらない。降り続けるかぎり、新しい迷路が上から現れます。

ここで問題になるのが容量です。ROM は4KB。ゲームのプログラム、グラフィック、音、全部込みで4KB。迷路のデータを持つ余地はありません。

解き方はひとつしかない。作るしかない。プレイヤーが降りるたびに、その場で迷路を生成する。

ただし、ランダムに壁を置くだけでは駄目です。行き止まりができると、プレイヤーが降りられなくなってゲームが破綻します。必ず通れる迷路を、その場で、数バイトの処理で作る。それが要求されていたことでした。

5つのマスを見る

実際の処理を追ってみます。迷路は左右対称なので、生成するのは左半分の8マスだけ。右は鏡写しにします。

1マスを決めるとき、周囲の5マスを見ます。真上、左上、右上、左、そして左の左。この5マスがそれぞれ壁か通路かで、組み合わせは 2 の5乗で32通り。

その32通りに対して、答えが1つずつ用意されている。それがあの表です。32バイトというのは、32通りの状況に対する32個の答えでした。

5マスの状態を2進数として読むと、0 から31 の数字になります。その数字を添字にして表を引く。出てきた値が 0 なら壁、1 なら通路。2 と 3 のときだけ、乱数を使って決めます。

処理としては、これで終わりです。分岐も再帰もない。表を引くだけ。

誰も説明できなかった部分

ここまでは仕組みの話で、読めば分かります。分からないのは、なぜこの32個の数字だと必ず解ける迷路になるのかのほうです。

表の中身に規則性が見つかりません。0 と 1 と 2 と 3 が、一見でたらめに並んでいます。1つでも数字を変えると行き止まりが出る、と論文には書かれています。それなのに、この並びだと出てこない。

ふつう、こういうアルゴリズムには証明が付きます。この手順を踏めばこの性質が保たれる、という説明が。Entombed の表には、それがありませんでした。動くことは分かる。なぜ動くのかが分からない。

しかも、当時の開発者に聞いても答えが出てこなかった。この点が、後年この件が「未解決問題」として扱われる理由になります。

余談ですが、私はこの構図に見覚えがありました。動いているコードの、なぜ動くのかを説明できない状態。自分のプラグインにも、書いた当時の判断を思い出せない箇所があります。40年前の32バイトを笑えません。

もうひとつの謎、壊れた乱数

表を引いた結果が 2 か 3 のとき、乱数を使うと書きました。その乱数生成器にも問題があります。

Entombed が使っているのは線形帰還シフトレジスタという方式で、8ビットの値を回しながら次の値を作ります。この方式は、正しく作れば255通りの値を一巡してから最初に戻るとされています。

ところが Entombed の実装は、ある状態に入ると 0 から抜け出せなくなると報告されています。乱数が乱数でなくなる。それでもゲームは成立していました。迷路の生成が表に強く支配されているので、乱数の質が悪くても壊れない。

意図してそう作ったのか、たまたま壊れなかったのか。そこも分かっていません。

5人で作った4KB

Entombed の関係者は5人います。1982年の Atari 2600 のゲームとしては多い。当時は1人で全部作るのが普通でした。

クレジットには Steven Sidley の名前が載っているそうです。ただし後の調査で、迷路のアルゴリズムを考えたのは別の人物だったことが分かります。そして、それが分かるまでに36年かかりました。

次の記事では、2018年に学者がこの32バイトを調べ始めてから、Wikipedia の未解決問題の一覧から削除されるまでを追います。「酔っ払ったプログラマーが書いた」という伝説が、どこから来てどこで食い違ったのか、という話です。

参考

• Atari 2600 hardware ── ハードウェア仕様
• Racing the Beam ── 走査線に合わせた描画手法
• Entombed: An Archaeological Examination of an Atari 2600 Game ── John Aycock, Tara Copplestone（2018）。迷路生成の逆アセンブル解析
• The maze puzzle hidden within an early video game ── BBC Future（2019）