Investigadores del Instituto Tecnológico de Massachusetts (MIT) han abierto nuevas fronteras en el estudio de la complejidad computacional con un enfoque poco convencional, utilizando el popular videojuego Super Mario Bros. como campo de pruebas. El equipo, dirigido por el profesor Erik Demaine, ha determinado que determinados niveles del juego son indecidibles, es decir, no existe ningún algoritmo capaz de predecir si se podrán superar sin llegar a jugarlos, ni siquiera con el superordenador más potente del mundo.
Este hallazgo surge de un estudio detallado de varios títulos de la franquicia, incluidos New Super Mario Bros y Super Mario Maker, publicado recientemente en el servidor de preimpresión. arXiv.
“De los juegos de Mario 2D lanzados desde New Super Mario Bros., hemos demostrado que todos, excepto Super Mario Wonder, son indecidibles”, afirman los científicos en su estudio.
Super Mario Bros: problemas imposibles de resolver
Utilizando herramientas de complejidad computacional, los investigadores descubrieron que algunos niveles del juego pertenecen a una categoría de problemas matemáticos conocida como NP-hard, cuya resolución se vuelve exponencialmente más compleja. Pero Demaine y su equipo fueron más allá y demostraron que, para determinados niveles, responder si se pueden superar no sólo es difícil, sino imposible.
“No puede ser más difícil”, comentó Demaine a Científico nuevo. “¿Podrás alcanzar la meta? No existe ningún algoritmo que pueda responder esa pregunta en un tiempo finito”, añadió.
En pocas palabras, estos problemas indecidibles, conocidos como RE-complete, no pueden ser resueltos por ninguna computadora, independientemente de su potencia o del tiempo que se le dedique.
“Es fascinante imaginar que la dificultad podría sustituir a la diversión”, dice Demaine. Científico nuevo, quien señala que todavía no entendemos del todo qué hace que un juego sea divertido desde una perspectiva matemática. Sin embargo, la indescifrabilidad inherente a estos niveles podría ofrecer pistas sobre el atractivo de los desafíos que presentan, reflexiona Demaine.
Simulación de una máquina contadora.
Para llegar a estas conclusiones, los investigadores crearon niveles personalizados, llenando un único punto con cientos de enemigos y eliminando los límites de los editores de juegos. Este enfoque les permitió construir una máquina de contar dentro del juego, un modelo teórico que simula el funcionamiento de una computadora.
Utilizando este método, pudieron relacionar el problema con el famoso problema de bloqueo, que establece que no es posible determinar si un programa de computadora terminará o se ejecutará indefinidamente excepto ejecutándolo. Así, demostraron que ningún análisis puede predecir con certeza si se puede completar un nivel.
Estas investigaciones no sólo enriquecen la teoría matemática y computacional, sino que también sugieren una nueva forma de entender los videojuegos y su diseño. Así que la próxima vez que te enfrentes a un nivel de Mario, recuerda que estás ante uno de los acertijos más complejos de la informática.
Felipe Espinosa Wang con información de New Scientist y arXiv.
