Matemáticos descubren un problema imposible de resolver en los juegos de Super Mario

Investigadores han demostrado que determinar si algunos niveles del popular videojuego Super Mario Bros se pueden superar es imposible.

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 prueba. El equipo, liderado por el profesor Erik Demaine, ha determinado que ciertos niveles del juego son indecidibles, es decir, que no existe un algoritmo capaz de predecir si se pueden superar sin jugarlos realmente, incluso con el superordenador más potente del mundo.

Este hallazgo proviene de un estudio detallado de varios títulos de la franquicia, incluyendo New Super Mario Bros y Super Mario Maker, publicado recientemente en el servidor de preimpresos arXiv.

"De los juegos de Mario en 2D publicados desde New Super Mario Bros., hemos demostrado que todos, excepto Super Mario Wonder, son indecidibles", afirman los científicos en su estudio.

La investigación reveló que ciertos niveles de Super Mario Bros, como los de New Super Mario Bros y Super Mario Maker, no solo son difíciles, sino indecidibles.

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 conocidos como NP-duros, cuya resolución se vuelve exponencialmente más compleja. Pero Demaine y su equipo fueron más allá y demostraron que, para ciertos niveles, responder si se pueden superar es no solo difícil, sino imposible.

"Más difícil no se puede", comentó Demaine a New Scientist. "¿Puedes llegar a la meta? No hay algoritmo que pueda responder a esa pregunta en un tiempo finito", agregó.

En pocas palabras, estos problemas indecidibles, conocidos como RE-completos, no pueden ser resueltos por ningún ordenador, sin importar su potencia o el tiempo que se le conceda.

"Es fascinante imaginar que la dificultad podría ser un sustituto de la diversión", dice Demaine a New Scientist, quien señala que aún no comprendemos completamente qué hace divertido a un juego 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.

Esta investigación no solo destaca la complejidad de algunos videojuegos, sino también la capacidad de estos para ilustrar problemas matemáticos avanzados.

Simulación de una máquina contadora

Para llegar a estas conclusiones, los investigadores crearon niveles personalizados, llenando un solo punto con cientos de enemigos y eliminando los límites de los editores de juegos. Este enfoque les permitió construir una máquina contadora dentro del juego, un modelo teórico que simula el funcionamiento de un ordenador.

Con este método, pudieron relacionar el problema con el famoso problema de la parada, que establece que no es posible determinar si un programa informático finalizará o se ejecutará indefinidamente, salvo ejecutándolo. Así, demostraron que ningún análisis puede prever con certeza si un nivel podrá completarse.

Estas investigaciones no solo 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 se enfrente a un nivel de Mario, recuerde que está lidiando con uno de los enigmas más complejos de la computación.

Felipe Espinosa Wang con información de New Scientist y arXiv.