Pac-Man demostró ser NP-Hard por la teoría de la complejidad computacional

En los últimos años, algunos matemáticos dedicados han comenzado a estudiar la complejidad computacional de los videojuegos. Su objetivo es determinar la dificultad inherente de los juegos y cómo podrían estar relacionados entre sí y con otros problemas.

Hoy, Giovanni Viglietta de la Universidad de Pisa en Italia revela un cuerpo de trabajo hercúleo en esta área en el que clasifica una gran cantidad de juegos de las décadas de 1980 y 1990, incluidos Pac-Man, Doom, Tron y muchos otros.

El trabajo de Viglietta consta de varios pasos. El primero es determinar la clase de complejidad computacional a la que pertenece el juego. A continuación, averigua si saber cómo resolver el juego también te permite resolver muchos otros problemas en la misma clase, una propiedad que los teóricos de la complejidad llaman 'dureza'. Finalmente, determina si el juego está completo, lo que significa que es uno de los 'más difíciles' de su clase.

Su enfoque es relativamente sencillo. Primero trabaja a través de una serie de pruebas que muestran que cualquier videojuego con propiedades específicas de juego cae en una cierta clase de complejidad.

Luego clasifica los juegos de acuerdo con las propiedades de juego que tienen.

Por ejemplo, un tipo de juego involucra a un jugador que se mueve a través de un paisaje visitando varios lugares. Él llama a esto 'recorrido de ubicación' y un ejemplo sería un juego en el que ciertos elementos están esparcidos por un paisaje y el objetivo es recolectarlos todos.

Algunos juegos de recorrido de ubicación permiten que cada ubicación se visite solo una vez. Los denominados juegos de senderos de un solo uso pueden incluir carreras de descenso.

Luego, usa la teoría de grafos para demostrar que cualquier juego que exhiba tanto recorrido de ubicación como rutas de un solo uso es NP-hard, que es la misma clase de complejidad que el problema del viajante de comercio.

Resulta que Pac-Man entra en esta categoría (la prueba consiste en distribuir píldoras de poder por el laberinto de una manera que imponga caminos de un solo uso).

También muestra cómo los juegos caen en otras categorías de complejidad. Por ejemplo, los juegos que cuentan con almohadillas de presión para abrir y cerrar puertas son difíciles de PSPACE si cada puerta está controlada por dos placas de presión. Doom entra en esta categoría.

Y así.

La lista resultante es impresionante. Estos son algunos de sus resultados:

Boulder Dash (First Star Software, 1984) es NP-hard.

Deflektor (Vortex Software, 1987) está en L.

Prince of Persia (Brøderbund, 1989) es PSPACE-completo.

Tron (Bally Midway, 1982) es NP-hard.

Para obtener la lista completa y el razonamiento, consulte el documento a continuación.

Eso ha sido claramente una labor de amor para Viglietta, dado el título de su artículo: ¡Los juegos son un trabajo difícil, pero alguien tiene que hacerlo!

Curiosamente, dice que este tipo de análisis es innecesario para los juegos modernos. Los juegos comerciales más recientes incorporan lenguajes de secuencias de comandos equivalentes a Turing que permiten fácilmente el diseño de acertijos indecidibles como parte del juego, dice.

En cierto modo, eso hace que estos juegos antiguos sean aún más encantadores.

Ref: arxiv.org/abs/1201.4995 : ¡Jugar es un trabajo difícil, pero alguien tiene que hacerlo!

esconder