スーパーマリオブラザーズ。 数学的に解くのは不可能

ここでは、あまり知られていない数学に関する 2 つの事実を紹介します。 まず、単純に解決できない問題がいくつかあります。 これは、あなた個人が十分に賢くないとか、調べるために間違った方法を使用しているという意味ではありません。 疑問、推測、概念は誰にも決して解決されません。 第二に、高度な数学のアイデアのインスピレーションは、予期せぬ場所から得られることがあります。

好例: 現在 arXiv プレプリント サーバー上にある (つまり、まだ査読されていない) 最近の論文は、次のような内容です… スーパーマリオブラザーズ。

それ以降にリリースされた 2D マリオ ゲームの 1 つ New スーパーマリオブラザーズ… を除くすべてのことを示しました。 スーパーマリオワンダー マサチューセッツ工科大学コンピューターサイエンス・人工知能研究所のハーディネスグループの研究チームが執筆した論文には、「それを特定することはできない」と書かれている。

たとえ スーパーマリオワンダー「そうかもしれないことを示唆する証拠がある」[,] 彼らはさらに、「イベントが存在し無限のクリボーを生み出すということを踏まえると、このゲームはまだ非常に新しいものであり、意思決定能力の欠如についてさらに主張するには、ゲームの仕組みを十分に理解するためにさらなる研究が必要である」と付け加えた。

これは実際には何を意味するのでしょうか? 解決不可能な問題とは、本質的には、正しい「はい」または「いいえ」の答えを見つけることが不可能な質問のことです。 この場合、問題はプレイヤーとして、もっとはっきりしていればいいのにと本当に思っていることです。それは単純に「ゲームに勝つことができるか？」ということです。

「これ以上に難しいことはありません」と、マサチューセッツ工科大学のコンピューターサイエンス教授で論文著者の一人であるエリック・デミン氏は言う。 新世界。 「最後までたどり着くことができますか? 限られた時間内にこの質問に答えるアルゴリズムはありません。

さて、このようなことを証明するのは簡単なことではありません。研究助成金を楽しく利用しながら、延々とゲームをプレイすることは明らかに問題外です。 そこで、チームは代わりに、すでに使用されているテクノロジーを使用しました。 10年前 ゲームについては MIT 大学院生のライナス・ハミルトンによる 合図。

「中心的なアイデアは、各カウンターの値を… 合図 この論文では、「レベルはレベル内の特定の場所を占める敵の数で表され、この数は固定サイズのレベルでも任意に大きくできることを利用しています」と説明されています。

正式な言葉で言えば、チームはカウンター マシンをセットアップしていました。これは、一連の「カウンター」を操作することによってコンピューターがどのように機能するかをモデル化する理論的なマシンです。 非常にシンプルです – カウンターが 1 つだけです スーパーマリオブラザーズ。 これには「上」、「下」、「ジャンプ」の命令しか装備されておらず、それ以上は何もありません。しかし、無限の数のクリボーの問題を、はるかに簡単なもの、つまり停止の問題に減らすことができるので、非常に便利です。

それはどういう意味ですか？ さて、コンピュータ プログラムを実行して Go を押します。プログラムの有効期限は切れるでしょうか? それとも永遠に走り続けますか？ これはばかげた質問のように思えるかもしれませんが、これが行き詰まった問題、つまり解決不可能な問題の典型的な例です。 ゲームが停止の問題に帰着する可能性がある場合 – 例: 合図 できる、そしてたくさん スーパーマリオブラザーズ。 ゲーム – それはまた決定不可能です。

「これらの特定の計算が終了しない限り、このマリオのレベルを解くことはできないという考え方ですが、それを判断する方法がないこと、したがって、解くかどうかを判断する方法がないことはわかっています」とデメイン氏はニュー・サイエンティストに語った。 それはレベルを解決することができます。」

言い換えれば、次回誰かが「あなたはくだらないビデオゲームをして時間を無駄にしている」と言ったら、心配しないでください。代わりに、あなたは… 実際には 複雑性理論の分野における解決不可能な問題を解決します。 クリボーや知覚を持った恐竜は単なる粉飾です。

この研究は、 arXiv。