Un fontanero persiguiendo a una princesa a través de tuberías y monstruos parece el argumento más inocente del mundo. Pero según investigadores del MIT, algunos niveles de Super Mario esconden un problema que ningún ordenador —real o teórico— es capaz de resolver.
Determinar si esos niveles pueden completarse resulta ser, al menos, tan complejo como descifrar la encriptación que protege las transacciones financieras. Y según el MIT Hardness Group, el videojuego pertenece ahora a la clase de complejidad más difícil que la ciencia computacional conoce.
El MIT lleva 14 años estudiando Super Mario como problema matemático
Erik Demaine no es un investigador cualquiera. Profesor de ciencias de la computación en el MIT y becario MacArthur —el llamado «premio al genio»—, combina su trabajo en geometría computacional con algo bastante menos esperado: analizar videojuegos como problemas matemáticos serios. Super Mario lleva años siendo su objeto de estudio predilecto, aunque eso no siempre resulte obvio desde fuera.
El MIT Hardness Group, nombre informal del proyecto surgido de su clase sobre pruebas de dificultad algorítmica, lleva más de una década publicando resultados sobre la complejidad matemática del juego. Ya habían demostrado que Mario era más difícil que el problema del viajante de comercio o que la factorización de números grandes —dos retos clásicos de la computación—, pero nadie esperaba lo que vendría después.
En 2023, cuatro estudiantes superaron todas las expectativas previas, incluidas las del propio Demaine.
De PSPACE a RE-Complete: el salto a lo indecidible
Hasta ese momento, Demaine creía que Super Mario pertenecía a la clase de complejidad PSPACE: problemas que los ordenadores pueden resolver en principio, aunque con un coste creciente en tiempo y memoria. Él mismo había declarado que PSPACE era el «hogar permanente» del juego. Se equivocaba.
Hayashi Ani, Holden Hall, Ricardo Ruiz y Naveen Venkat demostraron que estaba equivocado. Usando editores de niveles creados por fans y la plataforma Super Mario Maker, construyeron niveles que son matemáticamente indecidibles: ningún programa puede predecir siempre, de forma correcta, si Mario puede llegar al castillo en esos niveles.
El resultado sitúa a Super Mario en la clase RE-Complete. «Es la clase de complejidad más difícil que podemos imaginar para este tipo de juegos», afirma Demaine.
El Problema de la Parada y la paradoja detrás de lo irresoluble
Para entender qué significa que algo sea indecidible, hay que remontarse a 1936, cuando Alan Turing demostró que ningún ordenador puede resolver todos los problemas posibles. Lo hizo mediante el Problema de la Parada.
La paradoja funciona así. Imagina un ordenador llamado Oráculo que predice si cualquier programa se detendrá o seguirá ejecutándose indefinidamente. Ahora diseña otro, el Contrario, que hace exactamente lo opuesto a lo que el Oráculo predice. Si el Oráculo dice que el Contrario se detendrá, el Contrario seguirá ejecutándose. Si dice que seguirá, el Contrario se detiene. El Oráculo siempre se equivoca, sin excepción posible. El problema es, por tanto, irresoluble.
Los investigadores conectaron Super Mario con esta idea mediante una técnica llamada reducción: convertir un problema desconocido en uno ya conocido. Si dentro del juego puede construirse algo equivalente a un problema indecidible, el juego también se vuelve indecidible.
Gadgets y contadores: cómo se construye un ordenador dentro de Mario
El método parte de descomponer los niveles en lo que los investigadores denominan «gadgets»: fragmentos del entorno que funcionan como interruptores lógicos de verdadero o falso.
Un ejemplo concreto es el gadget de puerta, basado en un Spiny, el erizo del juego. La puerta está abierta cuando el Spiny está a la derecha, cerrada cuando está a la izquierda. Mario puede manipular su posición para simular los estados verdadero y falso de la lógica computacional, algo que parece trivial hasta que se encadena con otros elementos.
Los estudiantes diseñaron también gadgets contadores basados en Goombas. El número de enemigos vivos actúa como variable: aumenta cuando una tubería genera un Goomba y disminuye cuando Mario lo aplasta. Mario solo puede avanzar cuando el contador llega a cero. Al encadenar varios de estos contadores se puede simular cualquier ordenador no cuántico, y con un número ilimitado de enemigos la memoria del sistema es potencialmente infinita, aunque el nivel mantenga el mismo tamaño. «Podrías usarlo para hacer la declaración de la renta, compilar código o ejecutar un modelo de lenguaje», señala Demaine.
Más allá del videojuego: aplicaciones reales de la teoría de gadgets
La teoría de gadgets desarrollada para analizar Super Mario ya ha trascendido las pantallas. Investigadores de la Universidad de Texas en el Valle del Río Grande la han aplicado al estudio de la planificación de movimiento robótico y al modelado de redes de reacciones químicas.
Demostrar que un problema es indecidible también tiene un valor práctico directo: indica a los ingenieros que deben dejar de buscar algoritmos para resolverlo. No es un fracaso; es información útil.
El enfoque lúdico de estos estudios ha atraído a nuevos estudiantes hacia la teoría de la complejidad. Holden Hall, uno de los autores del hallazgo, reconoce que tomó la clase porque sus amigos se apuntaban, sin saber nada del tema. Hoy sigue investigando, y algunos alumnos de Demaine continúan reuniéndose semanalmente para avanzar en el estudio del juego.
Quizás eso sea lo más revelador. Un videojuego de 1985 sobre un fontanero saltarín ha resultado ser una vía de acceso a los límites más profundos de lo que cualquier máquina puede conocer. Vale la pena preguntarse cuántos otros problemas cotidianos esconden, sin que lo sepamos, esa misma profundidad.