Completar un juego de "Super Mario Brothers" puede ser difícil, muy, muy difícil.
Esa es la conclusión de un nuevo artículo de investigadores del MIT, la Universidad de Ottawa y Bard College en Simon's Rock. Muestran que el problema de resolver un nivel en "Super Mario Brothers" es tan difícil como los problemas más difíciles en elPSPACE de "clase de complejidad", lo que significa que es incluso más complejo que el problema del vendedor ambulante, o el problema de factorizar números grandes, o cualquiera de los otros problemas difíciles que pertenecen a la clase de complejidad NP más conocida.
En un juego estándar de "Super Mario Brothers", Mario corre a través de un terreno que se desencadena desde el lado derecho de la pantalla. Mientras lucha contra monstruos, debe completar varias tareas, que pueden implicar la navegación de estructuras de ladrillos que pueden elevarse desde el plano del suelo deel juego, pero también puede colgar en el aire sin apoyo. La finalización de un nivel se marca cuando Mario alcanza un asta de bandera.
El nuevo documento no intenta establecer que ninguno de los niveles en las versiones comerciales de "Super Mario Brothers" sea PSPACE-hard, solo que es posible construir niveles PSPACE-hard a partir de las materias primas de "Super Mario"mundo.
El trabajo sigue a un artículo de hace dos años, con dos de los mismos coautores, que mostró que "Super Mario Brothers" es al menos tan difícil como los problemas más difíciles en NP. Pero en ese momento, los investigadores no pudierondeterminar si fue más difícil. "PSPACE es su hogar final", dice Erik Demaine, profesor de ingeniería eléctrica e informática del MIT y coautor de ambos artículos.
Demaine y sus colegas, Giovanni Viglietta, un postdoctorado en ingeniería eléctrica y ciencias de la computación en la Universidad de Ottawa y coautor del artículo anterior; y Aaron Williams, profesor de ciencias de la computación en Bard College en Simon's Rock,presentarán su nuevo artículo en la Conferencia Internacional sobre Diversión con Algoritmos la próxima semana.
Preguntas de proporción
Los científicos informáticos teóricos clasifican los algoritmos de acuerdo con sus tiempos de ejecución, que miden en términos del número de elementos de datos que manipulan los algoritmos. Un algoritmo para encontrar el número más grande en una lista de N números, por ejemplo, tiene un tiempo de ejecución proporcionala N. Un algoritmo que, digamos, calcula las distancias de vuelo entre N aeropuertos en un mapa tiene un tiempo de ejecución proporcional a N ^ 2, porque para cada aeropuerto, tiene que calcular la distancia a cada uno de los demás.
Los algoritmos cuyos tiempos de ejecución son proporcionales a N elevado a una potencia se denominan "polinomios". Un algoritmo polinomial cuyo tiempo de ejecución es proporcional a, digamos, N ^ 3 es más lento que uno cuyo tiempo de ejecución es proporcional a N. Pero esas diferenciaspalidecen en comparación con los tiempos de ejecución de los algoritmos exponenciales, cuyo tiempo de ejecución es proporcional a 2 ^ N.
Si un algoritmo cuyo tiempo de ejecución es proporcional a N tarda un segundo en realizar un cálculo que involucra 100 elementos, un algoritmo cuyo tiempo de ejecución es proporcional a N ^ 3 tarda casi tres horas. Pero un algoritmo cuyo tiempo de ejecución es proporcional a 2 ^N toma 300 trillones de años.
La clase de complejidad NP es un conjunto de problemas cuyas soluciones se pueden verificar en tiempo polinomial, incluso si encontrar esas soluciones lleva, hasta donde se sabe, un tiempo exponencial. Para usar el ejemplo más familiar, factorizar unes probable que el número esté más allá de la capacidad de todas las computadoras del mundo durante la vida del universo, pero verificar una solución, multiplicando los factores, es algo que un teléfono inteligente podría hacer.
Como NP, PSPACE contiene problemas que parecen requerir un tiempo exponencial para resolverse. Pero los problemas más difíciles en PSPACE, los problemas difíciles de PSPACE, también requieren un tiempo exponencial para verificar. En cierto sentido, eso hace que PSPACE sea un lugar natural paraun videojuego para vivir. Descubrir cómo completar un nivel endiabladamente difícil de "Super Mario Brothers" podría llevar mucho tiempo, pero también podría llevarlo navegar ese nivel, incluso con la solución en la mano.
Componentes fundamentales
En su artículo anterior, Demaine, Viglietta y sus colegas describieron una estructura de videojuego genérica a la que llaman puerta cerrada. La estructura debe tener un camino a través de ella que pueda ser seguro para atravesar o no, y debe haber unmanera para que el jugador cambie el estado de la ruta.
Debido a que la puerta cerrada tiene dos estados posibles, puede representar un poco de memoria de computadora, y debido a que tiene un camino a través de ella que se puede abrir o cerrar, puede servir como un elemento de un circuito computacional. Los investigadores pudieronpara mostrar que cualquier problema computacional podría describirse mediante puertas cerradas unidas en la configuración correcta. Si el problema es exponencialmente difícil, entonces averiguar cómo completar el nivel también es exponencialmente difícil.
En el artículo anterior, Demaine, Viglietta y sus colegas demostraron cómo construir puertas cerradas en varias versiones del juego "Donkey Kong Country", pero no pudieron averiguar cómo construir una en "Super Mario Brothers"."Pensamos que era imposible", dice Demaine.
Pero no lo es. La puerta cerrada que se describe en el nuevo documento usa un monstruo del mundo de "Mario Brothers" llamado "espinoso", que se moverá hacia adelante y hacia atrás continuamente entre dos barreras, pero nunca saltará espontáneamente ninguna de ellas. Comola espinosa se acerca a una barrera, sin embargo, Mario puede golpear el piso debajo de ella y enviarla. En la nueva puerta cerrada de los investigadores, si la espinosa está en un lado de una barrera, el camino a través de la estructura es intransitable; si está enel otro, el camino está abierto. Y caminos separados a través de la estructura permiten a Mario golpear a los espinosos de un lado a otro
Diversión y juegos
El resultado podría tener implicaciones más allá del diseño de juegos cada vez más desconcertantes de "Super Mario Brothers". Matemáticamente, los videojuegos no son muy diferentes de los modelos computacionales de sistemas físicos del mundo real, y las herramientas utilizadas para demostrar resultados complejosen uno podría adaptarse al otro.
"Estoy muy entusiasmado con este tipo de pruebas de dureza, y las he estado impulsando mucho en los últimos años", dice Demaine. "Incluso enseñé un curso completo sobre ellas. Soy bastante bueno enellos, solo a través de la práctica, y quería destilar eso de alguna manera en una forma que otras personas pudieran aprender. Así que la clase fue un primer intento de hacer eso. Pero ya es una referencia realmente útil. Voy y miro estas notas de clase todasel momento de ver, '¿Es difícil esa variación de este problema?' "
"Mi esperanza es a través de esta clase y este tipo de documentos para alentar a más personas a hacer esto, porque realmente acumula mucha experiencia que hace que sea más fácil superar los problemas", continúa. "Cuanto más práctica obtenemoscomo colectivo, mejor seremos para resolver este tipo de problemas. Y es importante conocer las limitaciones de los algoritmos ".
Fuente de la historia :
Materiales proporcionados por Instituto de Tecnología de Massachusetts . Nota: el contenido se puede editar por estilo y longitud.
cite esta página :