Desde que existen las consolas de juegos, hemos pasado muchos buenos ratos con Mario, Donkey Kong, Burger Time, etcétera, pero quizás nunca habíamos sospechado que estos juegos con considerados del tipo NP-difíciles.
Esto significan que son muy difíciles de resolver computacionalmente, pues el tiempo que toma encontrar la solución se incrementa proporcionalmente según el tamaño del problema; es decir, no es fácil desarrollar un cálculo para resolverlos.
La Universidad Libre de Bruselas y el Laboratorio de Inteligencia Artificial y Ciencias de la Computación del MIT (CSAIL) concluyeron que muchos juegos clásicos de video son problemas del tipo NP-difíciles. Para esto, los investigadores analizaron los juegos y descubrieron que en muchos de ellos hay un elemento de búsqueda y que muchos de los problemas son sobre buscar una trayectoria o arreglar objetos que satisfagan una condición.
Para esta clasificación se consideran cosas como los elementos extra que se necesitan para dificultar que se alcance el objetivo, por ejemplo, apretar determinados botones del control en un tiempo exacto. De hecho, presionar los botones en un tiempo preciso es uno de los factores que prueban la complejidad del juego, pues se basan en el jugador perfecto con velocidad infinita y tiempos de reacción de cero.
Las demostraciones del tipo NP-difícil están basadas en el problemas de saber si una meta es alcanzable desde el punto inicial. Los juegos también se consideran dentro de dicha categoría si el tamaño del tablero se incrementa.
Algunos de los juegos NP-difíciles (con pequeñas modificaciones) son:
- Mario.
- Donkey Kong.
- Legend of Zelda.
- Metroid.
- Pokemon.
Sin embargo, los resultados se aplican sin cambios a:
- Super Mario Bros. 1, 3, Lost Levels.
- Super Mario World.
- Donkey Kong Country 1.3.
- Todos los Legend of Zelda games except Zelda II: The Adventure of Link.
- Todos los juegos de Metroid.
- Todos los juegos de rol de Pokemon.
Con los criterios establecidos quizás habría que considerar que Angry Birds también es un problema del tipo NP-difícil, aunque no puedo afirmarlo. La pregunta que inquieta a muchos es si todos los juegos de plataforma son NP-difíciles. Probablemente no, pero sin duda son más interesantes.
No me extrañaría que en el futuro los fabricantes de juegos pusiesen una leyenda en sus programas indicando si son NP-difíciles o no.
Fuente: i-programmer