2018年11月、カルガリー大学のジョン・エイコックと、ヨーク大学の考古学者タラ・コプルストンが1本の論文を出しました。1982年のゲームのROMを逆アセンブルして、中身を調べたものです。
迷路がどう作られているかは、これで分かりました。前の記事で書いた32バイトの表と、5マスを見て次の1マスを決める仕組み。そこまでは解けた。
解けなかったのが、なぜその32個の数字なのか、でした。論文はそこを未解決として残しています。
ここから3年半、この表は「誰にも説明できないもの」として扱われます。以下はその期間に何が起きて、どう決着したかの記録です。私が調べたのは公開されている論文と報道だけで、当事者に取材したわけではありません。
酔っ払いが書いた、という話だった
論文が注目されたのは、技術的な発見よりも、そこに載っていた証言のほうでした。
エイコックは2016年、Entombed の最後のプログラマーだったスティーブ・シドリーに話を聞いています。シドリーによると、迷路の生成部分を書いたのは、すでに退職していた別の人物。その人に連絡を取って仕組みを尋ねたところ、酔って朦朧とした状態で思いつき、一晩でアセンブリに落として、そのまま倒れた、と返ってきたそうです。そしていまはもう、どう動くのか思い出せない、と。
この話は速かった。天才が酩酊状態で神がかったコードを書き、翌朝には本人にも読めなくなっていた。プログラミングの伝説として、これ以上ないくらい形が整っています。Hacker News でも Reddit でも議論が沸きました。
翌2019年9月、BBC Future がこの件を記事にします。エイコックのもとには、世界中から「迷路アルゴリズムの理論」が届くようになりました。
そして Entombed のアルゴリズムは、Wikipedia の「コンピュータサイエンスの未解決問題リスト」に載ります。P≠NP問題と同じ一覧に、1982年の Atari 2600 のゲームが並んだ。
余談ですが、この論文にはもうひとつ面白い発見があります。Entombed の乱数生成器には、6507 の INC 命令がキャリーフラグを変えないという仕様を見落としたバグがあって、本来65536あるはずの周期が1200程度に落ちていました。エイコックはこのバグを指紋として使い、533本の Atari 2600 のゲームを調べて、同じバグを持つものを5本見つけています。当時の開発者がコードを回し合っていた痕跡が、バグの形で残っていた。考古学だと思いました。
別の人が出てきた
転機は2021年1月です。The New Yorker Radio Hour が Entombed を取材しました。その過程で、エイコックのチームがたどり着けなかった人物に接触します。ポール・アレン・ニューウェル。
ニューウェルの話は、伝説とはまるで違いました。
当時、彼は映画とテレビの修士課程の学生で、『タワーリング・インフェルノ』のゲーム化に取り組んでいた。必要だったのは、常に通れて、サブルーチン以上のデータを持たなくていい、無限に続く階層の作り方。それを、数学の大学院生だったダンカン・ミュアヘッドに相談した。ミュアヘッドは、やり方が分かると答えた。
議論はバーで行われ、ナプキンにメモを取りながら進んだそうです。その夜、ニューウェルはミュアヘッドを家まで送り、週末にメモをまとめて Atari 2600 で動くようにした。
酒は入っていました。ただ、泥酔してわけの分からないコードを書いたのではなく、飲みながら数学の話をしていた、という状況です。
ニューウェルは、数十年しまい込んでいた開発資料も研究者に渡しています。約500点。初期のプロトタイプ、設計メモ、テスト結果。未発売だった Atari 2600 のゲーム「Amaze」の実物プロトタイプまで含まれていました。Amaze は、あのアルゴリズムを Atari 2600 に最初に載せた作品だったそうです。
なぜ話が食い違ったのか
2022年の論文は、この食い違いをいくつかの角度から見ています。
ひとつは、知的財産としての価値です。あのアルゴリズムは Entombed 以外にも、Towering Inferno や Q*bert、未発売のタイトルで使われていました。詳細を明かしたくないとき、「酔って思いついた、もう覚えていない」は便利な答えになります。
もうひとつは、単純に記憶です。シドリーは最後のプログラマーであって、考案者ではありません。彼が連絡を取った相手が冗談で答えた可能性もあるし、35年前の話が変形した可能性もある。
私はこの部分がいちばん人間くさくて好きです。嘘をついた人がいるわけでもなく、誰かが悪意で話を盛ったわけでもない。伝聞が1回挟まって、35年寝かせたら、別の話になっていた。
3つのルールに還元された
数学的な決着は、2021年4月に付きます。スイスのレオン・メヒラーとフランスのダビッド・ナカッシュが、IEEE Conference on Games で発表した論文です。BBC の記事を読んで研究を始めたそうです。
彼らが示したのは、あの32個の数字が3つのルールから導けるということでした。
ひとつ、2×2の壁のかたまりを作らない。4マスが正方形に全部壁で埋まると、そこが完全な行き止まりになって通路を分断します。だから、そのマスを壁にすると2×2が完成してしまう状況では、必ず通路にする。
ふたつ、壁も通路も幅を1マスに保つ。横に壁が2つ続いてはいけないし、通路が2つ続いてもいけない。これで迷路の密度が決まります。
みっつ、通路をつなぐ。上の行にある通路は、下か右のどちらかにつながっていなければならない。始まりと終わりを持たない通路を作らない。この3つ目が、通れることを保証している核心でした。
この3つを各パターンに当てはめると、壁にするしかない場合と、通路にするしかない場合と、どちらでもいい場合に分かれます。どちらでもいいところが、あの表の 2 と 3、つまり乱数で決める箇所でした。
32個のうち31個は、これで説明が付きました。
残った1個
1つだけ、ルール同士がぶつかるパターンがありました。1つ目のルールは壁にするなと言い、3つ目のルールは壁にしろと言う。同じマスについて、逆の答えが出る。
解決の仕方が、私はここでいちばん唸りました。矛盾を解くのではなく、矛盾が起きる状況にそもそも入らないようにする。1つ手前のパターンで、乱数に任せていた選択を制限して、その状態への遷移を潰す。
矛盾を含んだまま、矛盾に到達しない設計にする。40年前のバーのナプキンに、これが書かれていたことになります。
表はおとりだった
2022年、Internet Archaeology 誌に決定版の論文が出ます。著者はニューウェル本人、エイコック、そしてケイティ・ビットナー。ニューウェルの500点の資料を分析したものです。
その論文が示したことのひとつが、あの32バイトの表は本質ではなかった、という点です。
表は確かに ROM にあります。でもそれは3つのルールを毎回計算しなくて済むように、あらかじめ答えを出しておいた結果に過ぎない。本質はルールのほうで、表はその副産物でした。
逆から読むと、表しか見えません。ROM を逆アセンブルすれば、そこには数字の羅列があるだけで、ルールは残っていない。設計を知らずに実装だけを見ると、副産物が本体に見える。謎の正体は、そこにありました。
メヒラーとナカッシュの論文のあと、Entombed のアルゴリズムは Wikipedia の未解決問題リストから外されています。
難しいままにした理由
ひとつ、ゲームとして面白い話が残っています。
迷路の右端の値を固定すると、3つ目のルールが常に守られて、完全に通れる迷路ができます。ランダムにすると、たまに行き止まりが出る。
オリジナルの Entombed は、ランダムのほうを選んでいました。行き止まりが出るから、壁を壊すアイテムに価値が生まれて、緊張感が出る。数学的に完全な迷路より、不完全なほうがゲームとして面白い。そう判断した跡が、パラメータに残っています。
ニューウェルは後年、Linux 上で OpenGL を使った高解像度版を作り、改良したアルゴリズムで本当に無限で常に通れる迷路の生成に成功したと報告しているそうです。40年越しで、数学的に完全なほうも作った。
次回
ここまでが、公開されている論文と報道から読み取れる範囲です。読んで追いかけただけなので、確かめたとは言えません。
次の記事では、3つのルールから32バイトの表を実際に導出して、JavaScript で動かします。論文に書いてあることが本当かどうかを、自分の手元で確認する回です。
ところで、ご自身が15年前に書いたコードを、いまソースだけ渡されて説明できますか。私は自信がありません。設計を思い出せないまま残っている実装は、たぶん誰の手元にもあります。
参考
- 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）
- Explaining the Entombed Algorithm ── Léon Mächler, David Naccache（2021）。3つの不変条件による導出
- Still Entombed After All These Years ── Paul Allen Newell, John Aycock, Katie Bittner（2022）。開発資料の分析と、考案者本人による証言
コメント