画面上のカード対戦は第58ターンで止まっていた。一方の戦場には7,258体ものゾンビがひしめき、防御側のライフはわずか31。16体のゾンビを突撃させるだけでゲームは終わるはずだった。しかしルールエンジンは1回の状態解決に35秒もスタックし、導き出した結論は、たった1体のゾンビで相手をつつくというものだった。
これは開発者Levi Neuwirthが、Rustで自作したマジック:ザ・ギャザリング(MTG)のルールエンジン「Arcana」をテストしていた際に遭遇した光景だ。彼はカードAIの性能を検証するため、64組のメタデッキを用意し、403,200回に及ぶ自動対戦を実行した。その結果、9つのマッチが2時間の制限時間に達し、システムによって強制終了された。
コード自体に無限ループのバグは一切なかった。システムを麻痺させたのは、カードの効果によって引き起こされた「指数の爆発」だった。数千ものクリーチャーが同時に戦場へなだれ込み、微視的な全件探索があっという間に計算リソースを食い尽くしたのだ。
MTGは数学的にチューリング完全であることが既に証明されている。だが、現実のソフトウェアとして実装するのは全く別の工学的課題だ。人間なら一目で勝敗を判断できる盤面でも、プログラムはすべてのクリーチャーについて戦場全体を愚直に再スキャンしなければならない。プレイヤーが放つ「全軍突撃」の一言は、コードの内部では数百万通りもの分岐へと膨れ上がる。
8回の「上陸」で6000匹増殖、指数の暴走が始まる
MTGは1993年に誕生した。各カードには独自のテキストがあり、基本ルールをいつでも上書きできる。連鎖的なシナジーを持つカードが揃った瞬間、ゲーム内の数値は制御不能な勢いで急上昇する。
その代表例が「硬鎧の大群」(Scute Swarm)だ。土地が戦場に出るたびに、自身のトークンコピーを生成する。1体が2体、2体が4体へと、アクションを重ねるごとに倍加していく。
テストでは、ライフゲインカードやトークン倍加アーティファクトと組み合わさった。連続して8回土地を出した結果、戦場には6,561匹もの虫が湧き出た。プレイヤーのライフは26,240点にまで達した。初期ライフが20点のゲームにおいて、この数字は従来のアナログボードゲームの想定限界を完全に突き破っている。
図:Scute Swarmとリリアナの紋章による指数的増殖の比較。縦軸の1目盛りは10倍の膨張を表す。出典:Levi Neuwirth
人間同士がテーブルを挟んでプレイする場合、数個のダイスをカードの上に乗せて「数千匹」とみなせばその場で解決する。だがプログラムは、6,561個のエンティティすべてに対してメモリ上に個別データ構造を割り当てなければならない。
1ターンの解決に35秒、倍加ギミックがメモリを圧迫
虫の大群は凶悪だが、全体除去呪文を1枚撃てば一掃できる。本当にエンジンを致命傷に追い込んだのは、プレインズウォーカー「リリアナ」の奥義だった。この能力は戦場の外に、除去不能な永続の「紋章」を残す。
紋章のルールは極めて簡潔だ。「自分の終了ステップの開始時に、自分がコントロールするゾンビの総数足す2体のゾンビを生成する」。毎ターン、ゾンビの数は前のターンの2倍プラス2になる。わずか8回の誘発で、戦場のゾンビは510体に達した。
対戦相手が除去呪文で盤面を一掃しても、統率者領域に置かれた紋章は壊せない。次のターンには2体のゾンビが戦場に出て、倍加の連鎖が再始動する。この除去不能な自己増殖ループこそが、ルールシステムにとっての悪夢となった。
Neuwirthは停止した対戦のログをフレーム単位で分析した。第52ターン、紋章1回の誘発解決に1.72秒。第54ターンには7.78秒。そして第56ターンには、一気に35.15秒まで跳ね上がった。
図:戦場のゾンビが倍増するたび、1回の状態解決時間は約4.5倍に拡大した。出典:Levi Neuwirth
ゾンビの数が2倍になるごとに、解決時間は約4.5倍に膨張した。アルゴリズムの計算量は超線形に悪化していった。新しいクリーチャーが戦場に出るたび、エンジンは盤面全体を走査し、すべての常在型能力や誘発条件を再評価する。数千のオブジェクト同士が総当たりで相互作用し、ルール検証は計算の泥沼へと沈んでいった。
7000体のゾンビ軍団を抱えながら、単騎特攻しか選べないAI
戦況は第58ターンに突入し、ゾンビの総数は7,258体に達した。防御側のライフは残り31点、ブロッカーも足りていない。わずか16体のゾンビで総攻撃を仕掛ければ、32点のダメージで即座に決着がつくはずだった。
だがここで不条理な事態が起きる。AIは長考の末、パワー2のゾンビ1体だけを攻撃に向かわせた。敵クリーチャーを小さく小突いただけだった。7,000体を超える大軍を従えた圧倒的優勢側が、目の前のリーサル(必勝手順)を自ら見逃したのである。
図:第58ターンのリプレイ画面。1つのスタックに7,234体のゾンビが集約され、相手ライフは31点。出典:Levi Neuwirth
原因は、合法手生成器に組み込まれていた安全装置にあった。数千体のクリーチャーによる複数ターゲットへの攻撃は、組合せ空間が天文学的に爆発する。タイムアウトを防ぐため、作者はコード内で候補手の上限を「1,024通り」に設定していた。
生成器は単体での攻撃手順から優先的に列挙する仕様になっていた。戦場に7,258体ものゾンビがいる場合、単騎攻撃のバリエーションだけで1,024枠の上限が埋め尽くされてしまう。全員攻撃を含む集団アタックの選択肢は、キューの後方に回され、生成すらされなかったのだ。
第44ターン(クリーチャー58体)では229手生成され、そのうち4手は複数体による連携攻撃だった。しかし第50ターンに上限枠へ突き当たると、複数体攻撃の選択肢は完全にゼロになった。処理落ちを防ぐはずの保護ロジックが、皮肉にも必勝の一手を完全に隠蔽してしまった。
人間の直感 vs コンピュータの数百万分岐
人間のプレイヤーであれば、このような盤面での思考は全く異なる。盤面に1万体のゾンビがいようと、各ゾンビの配置や個別攻撃を細かく計算することはない。「総攻撃力が相手のライフを遥かに超えている」という事実だけを確認し、全軍突撃を宣言してO(1)の定数時間でゲームを終わらせる。
しかしコンピュータプログラムには、そうした巨視的な抽象化能力がない。エンジンは微視的な視点に厳密に従い、すべてのエンティティを律儀にデータ構造として分解して扱う。数体のクリーチャーが小競り合いをしている段階では、この全件走査こそが判定の絶対的な正確さを保証していた。
だが規模が臨界点を超えた瞬間、微視的な網羅性は致命的な足かせに変わる。ルールに則った細かなループの積み重ねが、全計算資源を枯渇させた。コンピュータが愚かになったのではない。意味のないミクロな細部に足を取られただけなのだ。
理論上の完全性と工学的な実現可能性の間には、深い溝が存在する。MTGはカードが基本挙動を自由自在に書き換えることを許容し、それがゲームに無限の深みをもたらしている。だがその自由度が指数の増殖と結びついたとき、ルールのシミュレーションは制御不能の限界点へと押し出される。
「500パーマネント」のブレーカーで実験を再起動
大規模な自動テストを完遂させるため、Neuwirthは工学的な是正策を導入した。「戦場のパーマネント数が500個を超えた場合、制御不能とみなして引き分けとする」というサーキットブレーカー(安全装置)である。
この仕組みを導入すると、テストは瞬く間に正常復旧した。これまで2時間停止していたマッチは、新機構によってわずか0.16秒で安全に終了した(パーマネント数576個の時点で中断)。無限の膨張に対して物理的な境界線を引くことが、全体の進捗を保護する第一歩となった。
さらに根本的なリファクタリングも進められている。トークン生成のたびに盤面全体を再スキャンしないよう、頻出状態のキャッシュ機構を追加した。また候補手生成アルゴリズムも見直し、全軍攻撃などのマクロな有力手を優先して探索キューへ割り当てる改良が行われている。
7,258体のゾンビがプログラムを落としたトラブルは、ルールシミュレーションと真の知性との境界線を浮き彫りにした。コンピュータが微視的な分岐を猛烈な速度で辿る一方で、人間は巨視的な常識によって核心を一撃で突く。ルールが指数的な無限増殖を許容する時、マクロな視点を欠いたコードは必ず暴走する。細部を完璧に計算しながら、自らが吐き出した数字の海に溺れていくのだ。
参考リンク:
- Levi Neuwirth 技術ブログ原文
- Arcana オープンソースルールエンジン リポジトリ
- Hacker News コミュニティ議論