スーパーマリオブラザーズをクリアするのはNP問題よりも難しかった!

スーパーマリオブラザーズをクリアするのはNP問題よりも難しかった! 1

実は数学の問題を解いていたのか...。

不朽の名作であるスーパーマリオブラザーズ。実はこのゲーム、コンピュータサイエンスにおける難問「NP問題」よりも難しかったんです!

この事実は、マサチューセッツ工科大学(MIT)やオタワ大学の研究者たちによって明らかになりました。彼らは、発表した論文「Super Mario Bros. Is Harder/Easier than We Thought」の中で、スーパーマリオブラザーズがNP問題よりも難しいということを数学的に証明しています。

ただ、この表現には少し不正確な部分があります。正確には、NP問題よりも難しいステージを(マリオメーカーなどで)作ることができるということが示されているんです。

NP問題って何?

いったいどうやって、マリオがNP問題よりも難しいことを証明したんでしょうか? その証明方法について説明する前に、「そもそもNP問題って何?」というところを説明したいと思います。

NP問題とはざっくりいうと、「ある答えが正しいかどうかは簡単にわかるけれど、正しい答えを見つけるのが難しい」ような問題の総称です。ここでいう簡単、難しいとは、コンピュータを使って現実的な時間で計算できるかどうかを意味しています。

つまりNP問題とは「解のチェックは短時間でできるけれど、正しい解を現実的な時間内で見つけるのは難しい問題」のことです。

現実世界には、NP問題に分類される問題はたくさんあります。たとえば、巡回セールスマン問題とよばれるNP問題があります。巡回セールスマン問題とは、複数の都市と都市間の距離が与えられたときに、すべての都市を1度だけ巡回し出発地に戻ってくるような最短経路を見つける問題です。このように現実世界において重要な問題には、NP問題が数多くあります。

「鍵付きのドア」

さて肝心の証明方法ですが、彼らは「鍵付きのドア」という概念を使って、マリオがNP問題よりも難しいことを証明しました。

彼らは、マリオを鍵付きドアを含む構造物として抽象化しました。この構造物には必ず鍵付きドアを追加するルートが含まれているものとします。またルート上にある鍵付きドアは、開いているか閉まっているか2つの状態を持っており、プレーヤーは鍵付きドアの状態を変えることができるとします。

鍵付きドアは2つの状態を取ることができるので、コンピュータにおけるビット(0と1)で表すことができます。研究者たちは、この鍵付きドアを使って数学的な問題を表現できることを示しました。したがって、鍵付きドアを使って表された数学的な問題が、NP問題よりも難しいことを証明できれば、マリオがNP問題よりも難しいことを証明できることになるんです。

トゲゾーが重要

残る問題は、マリオ内のオブジェクトを使ってどうやって鍵付きドアを作るかということです。この問題を彼らは、トゲゾーを使ってクリアしました。

トゲゾーは障害物に挟まれているとき、その障害物の間をずっと往復していて、障害物を乗り越えたりすることはできません。しかし、もしトゲゾーがブロックに乗っている場合、マリオが下からトゲゾーが乗っているブロックを頭突きすることで、トゲゾーを飛ばして障害物を越えさせることができます。

このように、トゲゾーとブロックをうまく配置することで、マリオの中で鍵付きドアを表すことができます。障害物のどちら側にトゲゾーがいるかによって、ドアが閉まっているのか開いているのかを表現するわけです。あとは、この鍵付きドアを使って表した数学的な問題が、NP問題よりも難しいことを証明するだけです。

正直なところ論文を読んでも「へえ〜」という言葉が出てくるだけで、内容を理解するのはかなり難しいです(笑)。マリオを数学的にここまで分析するなんて、研究者の方は本当にすごいですね。

ちなみに、テトリスぷよぷよもNP問題だそうですよ

image by Christine Daniloff/MIT

source: “Super Mario Brothers” is hard

Jennifer Ouellette - Gizmodo US[原文

(tmyk)