なぜスーパーマリオは、ほとんどのアルゴリズムよりも数学的に複雑なのか
配管工が姫を救い出すシンプルなプラットフォーマーに見えるかもしれませんが、スーパーマリオは実は理論計算機科学の最も深い謎へと通じる入り口なのです。MITによる新しい研究は、ゲームの特定の構成が数学的に「決定不能（undecidable）」であることを明らかにし、それらが標準的な計算問題の枠を遥かに超えた複雑性クラスに属していることを示しています。
PSPACEからRE-Completeへ：複雑性の劇的な飛躍
長年、MITのエリック・デメイン教授を含む研究者の間では、スーパーマリオはPSPACE複雑性クラスに属するというのが共通認識でした。このクラスには、解決可能ではあるものの、入力サイズが大きくなるにつれて膨大なメモリと時間を必要とする問題が含まれます。PSPACEの問題は困難ではありますが、十分なリソースがあれば、根本的にはコンピュータによって「解決可能」なものです。
しかし、Hayashi Ani、Holden Hall、Ricardo Ruiz、Naveen Venkatからなる学生チームによる最近の研究が、この仮説を打ち砕きました。彼らはレベルエディターやSuper Mario Makerを活用することで、RE-Completeとなる特定のレベルを構築しました。これは、ゲームが決定不能問題の領域に突入したことを意味します。これらの特定のシナリオにおいては、マリオが旗竿や城に無事に到達できるかどうかを常に正しく予測できるコンピュータプログラムを書くことは、数学的に不可能です。
停止問題との関連性
なぜビデオゲームが決定不能になり得るのかを理解するには、アラン・チューリングと停止問題に立ち返る必要があります。チューリングは、与えられたプログラムがいずれ停止するか、あるいは永遠に走り続けるかを判定できる汎用的なアルゴリズムは存在しないことを証明しました。
MITの研究チームは、「帰着（reduction）」と呼ばれる手法を用いて、この論理をキノコ王国に適用しました。スーパーマリオのレベルを「ガジェット（gadgets）」と呼ばれる局所的な構成要素に分解することで、研究者たちはゲームのメカニクス内で複雑な計算論理をシミュレートすることに成功しました。これらのガジェットは論理ゲートとして機能します。土管、足場、そしてクリボーやトゲゾーといった敵を特定のパターンで配置することで、チューリングマシンの挙動を模倣できるのです。その結果、マリオがレベルの終点に到達するかどうかを判定することは、複雑なプログラムが停止するかどうかを判定することと機能的に同一になります。
なぜこれがAIとコンピューティングの未来において重要なのか
この発見は、単なるゲーマー向けの面白い豆知識ではありません。計算の根本的な限界を深く思い知らされるものです。人工知能や自動推論の境界を押し広げていく中で、どれほど処理能力やメモリが利用可能であっても、特定の論理構造は本質的にいかなるアルゴリズムの手にも届かないものであることを認識しなければなりません。
一見シンプルに見える環境が決定不能問題を内包し得ることを証明することで、MIT Hardness Groupは、複雑性理論がいかにインタラクティブなルールベースのシステムに適用できるかを示しました。これは、複雑なソフトウェアの設計、自動化システムの検証、そしてアルゴリズム化が進む世界において何が「計算可能」であるかの境界を理解する方法に、重要な示唆を与えます。
主なポイント
- 決定不能性: 特定のスーパーマリオのレベルは現在RE-Completeに分類されており、プレイヤーがそれらをクリアできるかどうかを完璧に予測できるアルゴリズムは存在しません。
- 複雑性の転換: ゲームは「解決可能だが困難」なPSPACEクラスから、停止問題を反映した決定不能の領域へと移行しました。
- 計算ガジェット: 研究者たちはゲームのメカニクス（土管、敵、足場）を「ガジェット」として使用し、汎用計算をシミュレートする複雑な論理ゲートを構築しました。