Spielen Super Mario Brothers, ist wie ein Super schwer Mathe-Problem zu lösen

Wenn Sie frustriert über Ihre Unfähigkeit, ein Level von Super Mario Brothers schon, ist hier eine Kleinigkeit, um Sie aufzumuntern. Informatiker haben gezeigt, dass eine Ebene in der populären Video-Spiel zu lösen ist gleichbedeutend mit einige der schwierigsten Probleme in der Informatik zu lösen.

Sie sind bekannt als "NP-hart" Probleme, im Gegensatz zu der Klasse, bekannt als "P" Probleme, die relativ leicht zu lösen sind. Ein klassisches Beispiel für ein NP-hart-Problem ist das Traveling Salesman Problem: der Verkäufer muss den kürzesten Weg zum 100 Städte zu besuchen finden.

Es stellt sich heraus, dass die Navigation durch die Level von Super Mario Brothers kann gleichwertig Lösung dieser sehr schwierigen mathematischen Gleichungen, entsprechend MIT dem Informatiker und Ingenieur Erik Demaine. Eine Einschränkung: Demaine und seine Kollegen haben nicht gezeigt, dass die tatsächlichen Niveaus in kommerziellen Versionen von Super Mario Brothers dieser Norm zu erfüllen – nur, daß es ist möglich, Ebenen zu konstruieren, die NP-schwer mit den Rohstoffen der Spielwelt, eine Aufgabe, die ist tatsächlich möglich mit Super Mario Maker. Mehr dazu in einer Sekunde.

Informatiker sind NP-Probleme, besonders interessiert, weil sie die Eckpfeiler der Kryptographie sind. Wie MIT Larry Hardesty 2009 erläutert:

Informatik befasst sich weitgehend mit einer einzigen Frage: wie lange dauert es, einen bestimmten Algorithmus auszuführen? Aber Informatiker nicht geben die Antwort in Minuten oder Millisekunden; Sie geben es im Verhältnis zur Anzahl der Elemente, die der Algorithmus hat zu manipulieren.

Stellen Sie zum Beispiel, dass Sie eine unsortierte Liste von Zahlen, und Sie schreiben einen Algorithmus zur größten finden möchten. Der Algorithmus muss alle Zahlen in der Liste anschauen: es führt kein Weg vorbei, dass. Aber hält es einfach einen Rekord für die größte Zahl, die es bisher gesehen wird, es hat jeder Eintrag nur einmal anzusehen. Der Algorithmus Ausführungszeit ist somit direkt proportional zur Anzahl der Elemente ist es der Umgang mit — welche Informatiker designierten N.

So hast du einen Algorithmus zu finden, die größte Zahl in einer Liste von 100 Nummern (N = 100), die Zeit, die zum Abschließen des Vorgangs proportional zu N ist – sagen wir mal eine Sekunde pro Vorgang. Dinge werden noch komplizierter, wird Ihr Algorithmus mit, sagen wir, herauszufinden, die Abstände zwischen einer bestimmten Anzahl von Flughäfen auf einer Karte beauftragt (wo N ist die Anzahl der Flughäfen). Es dauert länger – drei Stunden eher als eine Sekunde – denn für jeden Flughafen auf der Karte, den Abstand zu den anderen Algorithmus berechnet werden muss. Das eigentliche Problem kommt mit exponentiellen Algorithmen — sagen, eine 1000-stellige Nummer Faktor. Dann dauert es eine satte 9.223372036854775807 Trillionen Jahre um die Aufgabe abzuschließen.

Das ist, wie lange es dauert, um so ein Problem allein zu lösen, aber wenn ein Computer die Antwort gegeben wird, können sie schnell überprüfen, ob die Antwort richtig ist. Betrachten Sie es als, seiend wie ein Rätsel: Es ist schwer, die Antwort erraten, aber sobald wir gesagt, die Antwort scheint offensichtlich.

Also was hat all dies möglicherweise mit Super Mario Brotherszu tun? Ein paar Jahre her, Demaine und seine Kollegen untersuchten eine generische Version einer Videospiel-Struktur nannte sie eine "verschlossene Tür". Diese Version hatte zwei mögliche Zustände für einen Weg durch das Spiel: Es ist sicher, diesen Pfad zu verwenden, oder es ist nicht. Diese beiden Staaten geöffnet oder geschlossen, können die 0en und 1en von Computer-Speicher-Bits entsprechen.

Demaine Et Al. gezeigt, dass keine rechnerische Probleme durch verschlossene Türen organisiert in genau der richtigen Konfiguration dargestellt werden könnte. Wenn ein gegebenes Problem exponentiell hart ist, wird also auch, wie man dieses Spiel Level abzuschließen herauszufinden. In anderen Worten, ist das Problem NP-schwer.

Mit den Rohstoffen der Spielwelt, herausgefunden sie, wie man diese Art von verschlossenen Türen in Donkey Kong Countryzu konstruieren. Sie taten das gleiche nicht für Super Mario Brothers. Sie dachten, eine verschlossene Tür in Super Mario war unmöglich und kam zu dem Schluss, dass das Spiel mindestens so hart wie die schwierigsten Probleme in NP. Aber sie konnten nicht endgültig beweisen , das es schwieriger wurde. Für Mathematiker ist eine wichtige Unterscheidung.

"Je mehr Übung bekommen wir als Kollektiv, desto besser sind wir auf diese Art von Problemen zu lösen."

Bei der International Conference on Spaß mit Algorithmen statt diese Woche in La Maddalena, Italien, Demaine wird beschreiben, wie der Schlüssel zum Aufbau einer verschlossenen Tür in Super Mario Brothers , eine Monster namens nutzen ein "stacheligen." Eine stachelige kann zwischen zwei Barrieren im Spiel bewegen, aber kann nicht über sie springen – nicht ohne Marios Hilfe sowieso. Wenn Mario den Boden Unebenheiten ebenso wie die stacheligen Barriere nähert, erscheint es Recht über. Die verschlossene Tür Demaine Et Al. Schließlich konstruiert basiert auf welcher Seite einer Barriere, die stacheligen leuchtet. Wenn es auf der einen Seite ist, ist der Weg offen; Wenn es auf der anderen Seite ist, ist der Pfad geschlossen. Und es gibt getrennte Wege, mit denen Mario, stacheligen von einer Seite zur anderen stoßen können.

Und hier ist warum es nicht nur um Videospiele ist. Mathematiker und Informatiker sprechen oft beweisen die allgemeine Aussage, dass P NP ungleich. Wenn P NP ungleich, dann gibt es keine schnelle und allgemeine Möglichkeit, NP schwierige Probleme zu lösen. Umgekehrt, wenn P NP entspricht, würde das bedeuten, dass auch scheinbar schwierige Probleme schnell und einfachste Lösungen haben könnte. Wir haben nicht nur sie noch gefunden. Und das hat enorme Auswirkungen für die Kryptografie. Unsere geschützten Daten würde anfällig geworden. (Für was es Wert ist, glauben die meisten Mathematiker ist es viel wahrscheinlicher, dass P NP ungleich.)

Verwirrt? Hier ist Simon Singh, Autor von die Simpsons und ihre mathematischen Geheimnisse, geben seine eigene auf P Vs NP, illustriert mit kurzen Ausschnitten aus Die Simpsons und Futurama:

Für solch ein arkaner mathematische Konzept bekommt P Vs NP in der populären Kultur viel zitiert. Es dient als ein Grundstück Punkt in Elementary. Und Charlie Epps, der brillante Mathematiker, gespielt von David Krumholtz in Numb3rs, verwendet das Spiel Minesweeper, um das Konzept zu einer Gruppe von FBI-Agenten in einer frühen Episode zu erklären.

Demaine unterrichtet eine Klasse auf solche Härte Beweise mit Videospielen und denkt, dass dies eine wirksame pädagogische Ansatz sein kann. "Meine Hoffnung durch diese Klasse und diese Arten von Papieren, mehr Menschen dazu zu ermutigen, weil es wirklich eine Menge Know-how, das macht es einfacher aufbauen, Probleme zu erobern", sagte er in einer Erklärung. "Je mehr Übung bekommen wir als Kollektiv, desto besser sind wir auf diese Art von Problemen zu lösen. Und es ist wichtig zu wissen, die Grenzen der Algorithmen."