正規表現だけで「DOOM」を動かすことに成功、1フレームの描画に約180秒

プログラマーのアーテム・リトキン氏が、文字列の検索や置換に使われる「正規表現」だけで名作FPS「DOOM」を動作させるプロジェクト「DOOM on regex」を公開しました。DOOM on regexはレジスタやRAM、フレームバッファ、DOOM本体、WADデータまでのすべてを約96.6MBの1本の文字列に収め、544個の置換ルールだけで動く仮想コンピューターを構築しており、DOOMの画面を1フレーム描画するには5台のマシンによる並列処理で約1399万回の置換が必要とされ、所要時間は約180秒とのことです。

DOOM on regex - find & replace as a computer
https://4rh1t3ct0r7.github.io/doom-regex/

GitHub - 4RH1T3CT0R7/doom-regex: DOOM running on nothing but regex find-and-replace. One 96 MB string, 544 rules, byte-identical to native DOOM · GitHub
https://github.com/4RH1T3CT0R7/doom-regex

正規表現とは、テキストの中から特定の文字列を検索したり、条件に一致した部分を別の文字列に置き換えたりするための仕組みです。通常はメールアドレスや電話番号の抽出、文章の一括変換などに使われますが、複雑な条件分岐や文字列操作を組み合わせることで計算処理も表現できます。

DOOM on regexでは、DOOMを正規表現で直接書き直しているわけではありません。正規表現による検索と置換だけで動作する小型の32bit仮想CPU「RVM-1」を作り、その仮想CPU上でDOOMを実行しています。DOOM本体は、移植しやすい形に整理された実装であるdoomgenericを、Cコンパイラの8ccとELVMを用いてRVM-1の命令列へ変換したものです。

以下のGIFアニメーションでは、左側でDOOMの画面1フレームが描画され、右側では実行中の置換ルールが流れていきます。左側で明るい緑色に光っているのは、その時点の置換によって書き込まれているピクセルです。壁は縦1列ずつ、床は横方向のひとまとまりずつ塗られ、筆が止まっている間はBSPツリーをたどって次に描く対象を決めています。


正規表現による置換を反復する仕組みは古典的な計算モデルの1つであるマルコフアルゴリズムそのものであり、理論上は通常のコンピューターと同じ種類の計算を実行できる「チューリング完全」な仕組みだとのこと。そのため、正規表現だけでDOOMを動かせること自体はもともと可能なはずだった、とリトキン氏。実際に問う価値があったのは、宇宙が熱的死を迎える前に動かし切れるかどうかと、途中でズルをしていないことをどう証明するかという2点だったとリトキン氏は述べています。

仮想コンピューターの状態は、約96.6MBに及ぶ1本の巨大な文字列として保存されています。この文字列にはCPUのレジスター、RAM、実行するプログラム、画面を保持するフレームバッファ、DOOMのゲームエンジン、ステージやグラフィックなどを収録したWADデータ、入出力領域などがすべて平文で格納されています。

実行時には、ドライバーが544個の正規表現による置換ルールを決められた順番で繰り返し確認します。その時点で最初に条件が一致したルールを1回だけ適用し、文字列の一部を別の文字に書き換えるという処理が、仮想コンピューターの1ステップに相当します。ルールを削除すると残るのは動作しない巨大なテキストファイルだけであり、計算や命令の解釈を外部のプログラムに任せているわけではないとリトキン氏は説明しています。

例えば、仮想CPUが数値を加算する場合は、512項目で構成された加算用の表を正規表現で参照し、繰り上がりを引き継ぎながら計算します。メモリへのアクセスでは、アドレスを構成する各ビットに応じてジャンプ距離を組み立て、二分木のような仕組みで約96.6MBの文字列内にある目的の位置へ直接移動します。文字列全体を毎回先頭から検索しないことで、処理時間を短縮しています。

以下の画像で緑色で表示されている部分は、正規表現による置換処理で現在書き換えられているピクセルです。画面は一度に生成されるのではなく、壁や床などの領域が少しずつ描かれます。

そして、以下のように仮想CPUを動かす正規表現ルールが並んでおり、「fetch」や「mov」といった処理が置換ルールとして再現されています。

最初に動作したバージョンの処理速度は毎秒わずか7回の置換にとどまり、1フレームのうち最後の29万5000回の置換を処理するだけでも12時間を要したとのこと。その後、アドレスの各桁をたどって目的の位置へ直接ジャンプする仕組みの導入、メモリ領域のフラット化、置換しても変化しない長い前半部分をコピーしない工夫などによって、PCRE2のJITコンパイルを有効にした状態で処理速度は1コア当たり毎秒約8万回まで改善されました。

約1399万回の置換処理を経て完成したDOOMの1フレーム。これはDOOMの第1ステージである「E1M1」のタイムデモの60フレーム目にあたり、リトキン氏によれば通常のDOOMが描画した同じフレームとバイト単位で一致し、SHA-256のハッシュ値も一致したとのことです。さらに、1フレームだけではまぐれの可能性があるとして、同じタイムデモの160フレーム目から259フレーム目までの100フレームも計算しており、約12億5000万回の置換を費やしたうえで100フレームすべてが通常のDOOMとバイト単位で一致したとしています。

最終的な計算は5台のマシンに分散して実行され、約3分に1フレームが生成されます。一般的なゲームが1秒間に数十フレームを表示することを考えると極端に低速ですが、リトキン氏はこの操作感について「反射神経が求められるシューティングゲームというより、ショットガンを使った文通チェスに近い」と説明しています。

Windows向けには実際の正規表現マシンを動かせるデモも公開されています。WASDキーまたは方向キーで移動し、Ctrlキーで射撃、スペースキーでドアを開けることが可能で、入力内容はファイルに記録された後、仮想CPUの入出力命令を通じてDOOMに渡されます。デモ画面ではDOOMの描画と並んで、どの置換ルールが実行され、何を読み取り、どの文字を書き込んだのかもリアルタイムで確認できます。

なお、リトキン氏は正しく動作していることを担保するため、同じ命令セットをPythonで実装したリファレンスエミュレーターを用意し、1回置換するごとに文字列がエミュレーターの状態とバイト単位で一致するかをテストで検証しています。リトキン氏によると、固定された正規表現ルールを循環的に適用し、DOOMのようなゲームや映像を動作させた既知の例はほかにないとのこと。DOOM on regexはソースコードがGitHubに公開されているほか、デモもリリースされています。