Teorema 3.1. Decidir si es posible llegar a un punto cualquiera de un nivel de Super Mario Bros es un problema NP-completo.
¿Estamos ante un candidato a un premio de investigación IgNobel? Posiblemente. Investigadores de Bruselas y del MIT han publicado un estudio (PDF) en el que afirman que distintos juegos clásicos de Nintendo son problemas NP-completos. Los juegos analizados son Super Mario Bros, Donkey Kong, Legend of Zelda, Metroid y Pokémon.
Para los no informáticos, el concepto de NP-completo puede ser algo abstracto, pero se podría resumir por ser "un problema muy gordo, tanto que un ordenador no podría encontrar una solución óptima en un tiempo razonable".
En el estudio se analiza la cuestión de si es posible determinar si un punto dado de una "fase" o "nivel" es alcanzable por el jugador. "Simplemente" eso. La construcción matemática que construyen los autores consiste en una serie de variables (e.g. "Super Mario ha crecido") y una serie de artilugios o condiciones (e.g. "un bloque que debe ser destruido").
Cada fase se construye por tanto como una interconexión de estos bloques, siendo el objetivo encontrar un camino desde un punto inicial a uno final (el "objetivo de la fase"):
Las demostraciones usan conceptos avanzados de análisis de complejidad computacional, como el problema 3SAT ("3-satisfiability") al que los autores demuestran que se pueden reducir casi todos los juegos clásicos, por lo que recomiendo que si quieres saber más leas el paper... ¡pero bajo tu responsabilidad!
No hay comentarios:
Publicar un comentario