En la teoría de la complejidad computacional , la geografía generalizada es un problema completo de PSPACE bien conocido .
Introducción
La geografía es un juego para niños , que es bueno para un largo viaje en automóvil, donde los jugadores se turnan para nombrar ciudades de cualquier parte del mundo. Cada ciudad elegida debe comenzar con la misma letra que terminó el nombre de la ciudad anterior. No se permite la repetición. El juego comienza con una ciudad inicial arbitraria y termina cuando un jugador pierde porque no puede continuar.
Modelo gráfico
Para visualizar el juego, se puede construir un gráfico dirigido cuyos nodos sean cada una de las ciudades del mundo. Se agrega una flecha desde el nodo N 1 al nodo N 2 si y solo si el etiquetado de la ciudad N 2 comienza con la letra que termina con el nombre del nodo de etiquetado de la ciudad N 1 . En otras palabras, dibujamos una flecha de una ciudad a otra si la primera puede llevar a la segunda según las reglas del juego. Cada borde alternativo en el gráfico dirigido corresponde a cada jugador (para un juego de dos jugadores). El primer jugador que no pueda extender el camino pierde. En la figura siguiente se muestra una ilustración del juego (que contiene algunas ciudades de Michigan).
En un juego de geografía generalizada (GG), reemplazamos el gráfico de nombres de ciudades con un gráfico dirigido arbitrario. El siguiente gráfico es un ejemplo de un juego de geografía generalizada.
Jugando el juego
Definimos P 1 como el jugador que se mueve primero y P 2 como el jugador que se mueve en segundo lugar y nombramos los nodos N 1 a N n . En la figura anterior, P 1 tiene una estrategia ganadora de la siguiente manera: N 1 apunta solo a los nodos N 2 y N 3 . Por tanto , el primer movimiento de P 1 debe ser una de estas dos opciones. P 1 elige N 2 (si P 1 elige N 3 , entonces P 2 elegirá N 9 ya que esa es la única opción y P 1 perderá). Siguiente P 2 elige N 4 porque es la única opción restante. P 1 elige ahora N 5 y P 2 elige posteriormente N 3 o N 7 . Independientemente de P 2 ' opción de s, P 1 elige N 9 y P 2 no le quedan opciones y pierde el juego.
Complejidad computacional
El problema de determinar qué jugador tiene una estrategia ganadora en un juego de geografía generalizada es PSPACE completo .
La geografía generalizada está en PSPACE
Sea GG = {< G , b > | P 1 tiene una estrategia ganadora para el juego de geografía generalizada que se juega en el gráfico G comenzando en el nodo b }; para mostrar que GG ∈ PSPACE , presentamos un algoritmo recursivo de espacio polinomial que determina qué jugador tiene una estrategia ganadora. Dada una instancia de GG, < G , n inicio > donde G es un gráfico dirigido y n inicio es el nodo de inicio designado, el algoritmo M procede de la siguiente manera:
En M (< G , n inicio >):
- Mida el grado de salida del inicio del nodo n . Si este grado es 0, devuelve el rechazo , porque no hay movimientos disponibles para el jugador uno.
- Construya una lista de todos los nodos accesibles desde n comienzan por un borde: n 1 , n 2 , ..., n i .
- Quite n inicio y todos los bordes conectados a él desde G para formar G 1 .
- Para cada nodo n j en la lista n 1 , ..., n i , llame a M (< G 1 , n j >).
- Si todas estas llamadas devuelven aceptar , entonces no importa qué decisión tome P 1 , P 2 tiene una estrategia para ganar, así que devolver rechazar . De lo contrario (si una de las llamadas devuelve un rechazo ) P 1 tiene una opción que negará cualquier estrategia exitosa para P 2 , por lo tanto, vuelva a aceptar .
El algoritmo M decide claramente GG. Está en PSPACE porque el único espacio de trabajo polinomial no obvio consumido está en la pila de recursividad. El espacio consumido por la pila de recursión es polinomio porque cada nivel de recursividad añade un único nodo para la pila, y hay en la mayoría de n niveles, donde n es el número de nodos en G . Esto es esencialmente equivalente a una búsqueda en profundidad .
La geografía generalizada es difícil de PSPACE
La siguiente prueba se debe a David Lichtenstein y Michael Sipser. [1]
Para establecer la dureza PSPACE de GG, podemos reducir el problema FORMULA-GAME (que se sabe que es PSPACE-hard ) a GG en tiempo polinomial ( P ). En resumen, una instancia del problema FÓRMULA-JUEGO consiste en una fórmula booleana cuantificada φ = ∃ x 1 ∀ x 2 ∃ x 3 ... Qx k (ψ) donde Q es ∃ o ∀. El juego es jugado por dos jugadores, P a y P e , que alternan la elección de valores para x i sucesivos . P e gana el juego si la fórmula ψ termina siendo verdadera , y P a gana si ψ termina siendo falsa . Se supone que la fórmula ψ está en forma normal conjuntiva .
En esta prueba, asumimos que la lista de cuantificadores comienza y termina con el calificador existencial, ∃, por simplicidad. Tenga en cuenta que cualquier expresión se puede convertir a esta forma agregando variables ficticias que no aparecen en ψ.
Al construir un gráfico G como el que se muestra arriba, mostraremos que cualquier instancia de FORMULA-GAME se puede reducir a una instancia de Geografía Generalizada, donde la estrategia óptima para P 1 es equivalente a la de P e , y la estrategia óptima para P 2 es equivalente al de P a .
La cadena de nodos vertical izquierda está diseñada para imitar el procedimiento de elección de valores para variables en FORMULA-GAME. Cada estructura de diamante corresponde a una variable cuantificada. Los jugadores se turnan para decidir los caminos en cada nodo de ramificación. Debido a que asumimos que el primer cuantificador sería existencial, P 1 va primero, seleccionando el nodo izquierdo si x 1 es verdadero y el nodo derecho si x 1 es falso . Luego, cada jugador debe tomar turnos forzados, y luego P 2 elige un valor para x 2 . Estas asignaciones alternas continúan por el lado izquierdo. Después de que ambos jugadores pasen por todos los diamantes, es nuevamente el turno de P 1 , porque asumimos que el último cuantificador es existencial. P 1 no tiene más remedio que seguir el camino hacia el lado derecho del gráfico. Luego es el turno de P 2 para hacer un movimiento.
Cuando el juego llega al lado derecho del gráfico, es similar al final del juego en el juego de fórmula. Recuerde que en el juego de fórmulas, P e gana si ψ es verdadero , mientras que P a gana si ψ es falso . El lado derecho de la gráfica garantiza que P 1 gana si y solo si P e gana, y que P 2 gana si y solo si P a gana.
Primero mostramos que P 2 siempre gana cuando P a gana. Si P a gana, ψ es falso . Si ψ es falso , existe una cláusula insatisfactoria. P 2 elegirá una cláusula insatisfactoria para ganar. Luego, cuando es el turno de P 1 , debe elegir un literal en esa cláusula elegida por P 2 . Dado que todos los literales de la cláusula son falsos , no se conectan a los nodos visitados anteriormente en la cadena vertical izquierda. Esto permite que P 2 siga la conexión al nodo correspondiente en un diamante de la cadena izquierda y lo seleccione. Sin embargo, P 1 ahora no puede seleccionar ningún nodo adyacente y pierde.
Ahora mostramos que P 1 siempre gana cuando P e gana. Si P e gana, ψ es cierto . Si ψ es verdadero , cada cláusula del lado derecho del gráfico contiene un literal verdadero . P 2 puede elegir cualquier cláusula. Entonces P 1 elige el literal que es verdadero . Y debido a que es cierto , su nodo adyacente en el nodo vertical izquierdo ya ha sido seleccionado, por lo que P 2 no tiene movimientos que hacer y pierde.
La geografía generalizada plana es completa con PSPACE
La geografía generalizada está completa con PSPACE, incluso cuando se reproduce en gráficos planos . La siguiente demostración es del teorema 3 de. [1]
Dado que planar GG es un caso especial de GG y GG está en PSPACE, entonces planar GG está en PSPACE. Queda por demostrar que el GG plano es duro con PSPACE. Esto se puede demostrar mostrando cómo convertir un gráfico arbitrario en un gráfico plano, de modo que un juego de GG jugado en este gráfico tendrá el mismo resultado que en el gráfico original.
Para hacer eso, solo es necesario eliminar todos los cruces de bordes del gráfico original. Dibujamos el gráfico de manera que no se crucen tres bordes en un punto, y ningún par de bordes cruzados se pueden usar en el mismo juego. Esto no es posible en general, pero siempre es posible para el gráfico construido a partir de una instancia de FORMULA-GAME; por ejemplo, podríamos tener solo los bordes de los vértices de la cláusula involucrados en los cruces. Ahora reemplazamos cada cruce con esta construcción:
El resultado es un gráfico plano, y el mismo jugador puede forzar una victoria como en el gráfico original: si un jugador elige moverse "hacia arriba" de V en el juego transformado, ambos jugadores deben continuar moviéndose "hacia arriba" a W o perder inmediatamente. Entonces, moverse "hacia arriba" de V en el juego transformado simula el movimiento V → W en el juego original. Si V → W es un movimiento ganador, entonces moverse "hacia arriba" desde V en el juego transformado también es un movimiento ganador, y viceversa.
Por lo tanto, el juego de GG jugado en el gráfico transformado tendrá el mismo resultado que en el gráfico original. Esta transformación toma un tiempo que es un múltiplo constante del número de intersecciones de aristas en el gráfico original, por lo que toma un tiempo polinomial.
Por lo tanto, el GG plano es PSPACE completo.
Gráfico bipartito plano con grado máximo 3
GG reproducido en grafos planos bipartitos con grado máximo 3 sigue siendo PSPACE-completo, reemplazando los vértices de grado superior a 3 con una cadena de vértices con grado como máximo 3. La prueba está en. [1] y usa la siguiente construcción:
Si un jugador usa cualquiera de las entradas a esta construcción, el otro jugador elige qué salida se usará. Además, la construcción solo se puede atravesar una vez, porque siempre se visita el vértice central. Por tanto, esta construcción es equivalente al vértice original.
Geografía de borde
Una variante de GG se llama geografía de bordes , donde después de cada movimiento, se borra el borde por el que pasó el jugador. Esto contrasta con el GG original, donde después de cada movimiento, se borra el vértice en el que solía estar el jugador. En esta vista, el GG original se puede llamar Vertex Geography .
La geografía de los bordes está completa con PSPACE. Esto se puede demostrar usando la misma construcción que se usó para la geografía de vértices. [2]
Geografía no dirigida
También se puede considerar jugar a cualquiera de los juegos de Geografía en un gráfico no dirigido (es decir, los bordes se pueden atravesar en ambas direcciones). Fraenkel, Scheinerman y Ullman [3] muestran que la geografía de vértices no dirigida se puede resolver en tiempo polinomial, mientras que la geografía de bordes no dirigidos es PSPACE-completa, incluso para gráficas planas con grado máximo 3. Si la gráfica es bipartita, entonces la geografía de bordes no dirigida es solucionable en tiempo polinomial.
Consecuencias
Dado que GG es PSPACE-completo , no existe un algoritmo de tiempo polinomial para el juego óptimo en GG a menos que P = PSPACE . Sin embargo, puede que no sea tan fácil probar la complejidad de otros juegos porque ciertos juegos (como el ajedrez ) contienen un número finito de posiciones de juego, lo que dificulta (o imposibilita) formular un mapeo para un problema completo de PSPACE . A pesar de esto, la complejidad de ciertos juegos todavía se puede analizar por generalización (por ejemplo, a un tablero n × n ). Consulte las referencias para obtener una prueba de Go generalizada , como corolario de la prueba de la integridad de GG.
Referencias
- ↑ a b c Lichtenstein, David; Sipser, Michael (abril de 1980). "Go Is Polynomial-Space Difícil" (PDF) . Revista de la ACM . 27 (2): 393–401. doi : 10.1145 / 322186.322201 .
- ^ Schaefer, Thomas J. (1978). "Sobre la complejidad de algunos juegos de información perfecta de dos personas" . Revista de Ciencias de la Computación y Sistemas . 16 (2): 185–225. doi : 10.1016 / 0022-0000 (78) 90045-4 .
- ^ Fraenkel, Aviezri; Scheinerman, Edward; Ullman, Daniel (1993). "Geografía de bordes no dirigidos" . Informática Teórica . 112 (2): 371–381. doi : 10.1016 / 0304-3975 (93) 90026-pág .