Ads-728

Ads-728

Psicología

Astrofísica

Genética

Neurociencia

» » » “Mario es difícil”, pertenece a los problemas matemáticos llamados “NP hard”

Si alguna vez te has peleado por completar los juegos clásicos de Nintendo, no te sientas mal, es que son realmente difíciles.

En un análisis sobre la complejidad computacional de los juegos de vídeo, incluidos los de la serie Mario y Legend of Zelda, se prueba que muchos de ellos pertenecen a una clase de problemas matemáticos denominados NP-hard. Esto significa que para un nivel dado de juego, puede ser muy difícil averiguar las posibilidades de un jugador para alcanzar el final. Los resultados sugieren que algunos de estos duros problemas podrían resolverse mediante un juego.

Las versiones comerciales de los juegos están diseñados para ser realizables, por supuesto, pero Erik Demaine, del Instituto de Tecnología de Massachusetts, y sus colegas, estudiaron las versiones sin esas cortapisas. "Estamos trabajando con las mismas reglas, pero somos libres de diseñar los niveles a nuestro gusto", comentaba.

El equipo transformó cada juego en una especie de rompecabezas lógico llamado problema de satisfacibilidad booleana. La cuestión versa sobre si las variables de un conjunto de declaraciones lógicas pueden ser elegidas todas como verdaderas, o si, inevitablemente, dichas declaraciones se contradicen entre sí.

Para cada juego, el equipo construyó las secciones de un nivel donde se obliga a los jugadores a elegir una de las dos rutas (el equivalente a la asignación de variables en un problema de satisfacibilidad booleana). La disposición de los enemigos y de habilidades son equivalentes a los enunciados lógicos. Estos permiten que se complete un nivel, lo que es equivalente a que todas las declaraciones del problema booleano sean ciertas, si el nivel se torna imposible, es equivalente a una contradicción.

Muchos de los juegos de las series de Mario, Donkey Kong, Leyenda de Zelda, Metroid y de Pokémon llegan a ser NP-hard. Eso significa que decidir si un jugador puede completarlo, equivale al menos, a resolver de los problemas más difíciles de los NP, una clase de la complejidad involucrada en el problema P versus NP (ver "la prueba del Millón de dólares") . No todos los juegos de cada serie se incluyeron en la prueba, ya que siguen reglas diferentes.

Para Mario, el equipo quiso demostrar que los juegos son NP-completo, una propiedad adicional que tiene importantes consecuencias. Muchos de estos difíciles problemas se pueden convertir en cualquier problema de la categoría de NP-completo. Entonces, si puedes resolver un problema NP-completo, por ejemplo, al completar un nivel de Mario, significa que habrías resuelto el problema original también.

Esto incluye el problema del viajante de comercio, buscando la ruta más corta entre una serie de puntos, que es de interés real en el campo de la logística, y también el problema de la mochila, que se utiliza para decidir cómo asignar recursos. Así pues, en teoría, se podría convertir un ejemplo de cualquiera de estos problemas en un nivel de Mario, y jugar el juego para intentar resolverlo. Este enfoque sería divertido, apunta Demaine, aunque, probablemente, sería más sencillo resolver directamente el problema de satisfacibilidad.

Los resultados ofrecen noticias mixtas para los diseñadores de juegos, añade Giovanni Viglietta, informático de la Universidad de Pisa, Italia, quien no participó en la investigación. Si se trata de un problema NP-hard, hay que decidir si el nivel puede ser navegado con éxito, y no es fácil para un diseñador comprobar esto. Sin embargo, sí se garantiza que el juego es interesante, ya que los jugadores no pueden decidir si están al frente de la manera correcta o perderse en una zona infranqueable de nivel. "El juego requiere un poco de creatividad e ingenio", dice Viglietta.

Anexo
- La prueba del Millón de dólares -
El mayor problema de la ciencia informática sigue sin resolverse, pero una encuesta revela que los investigadores están más confiados que nunca acerca de su posible solución. Para la solución de un problema P versus NP se abordan cuestiones fundamentales acerca de la computación, aparte que su solución supone ganar 1 millón de dólares, pero eso es otro asunto.
Los científicos intentan acuerdar la cantidad de tiempo que tardarán en resolverlo. P es de la clase de los problemas "fáciles", que pueden resolverse mediante un algoritmo relativamente rápido. NP es de la clase de problemas que son fáciles de comprobar, si se da una respuesta, se puede comprobar en poco tiempo.
Todos los problemas de la clase P están también en NP, pero no se sabe si todos los problemas NP están también en P. Si lo están, entonces el algoritmo correcto rápidamente podría resolver todos los problemas NP. Si no, P ≠ NP y muchos problemas son fundamentalmente difíciles de resolver. Una prueba que, de todas formas vale 1 millón de dólares otorgados  por el Instituto Clay de Matemáticas en Cambridge, Massachusetts.
En 2002, William Gasarch, un informático de la Universidad de Maryland, en College Park, encuestó a 100 investigadores sobre esta cuestión, y el 61 por ciento pensaba que P ≠ NP. Actualmente, Gasarch volvió a encuestar esta vez a más de 150 participantes y comprobaron que P ≠ NP está apoyado hasta por un 81 por ciento.
No obstante, la prueba podría durar más tiempo. Sólo el 53 por ciento respondió que se sabría antes de 2100, y Gasarch considera que se tardará entre 200 y 400 años. Los resultados completos de esta encuesta serán publicados a finales de este año en el noticiario de la Association for Computing Machinery .

- Referencia: NewScientist.com, 14 de marzo 2012 por Jacob Aron

,

«
Next
Entrada más reciente
»
Previous
Entrada antigua
Editor del blog Pedro Donaire

Filosofía

Educación

Deporte

Tecnología

Materiales