Geografía generalizada
# Geografía generalizada

En teoría de la complejidad computacional, el juego de geografía generalizada es un conocido problema de PSPACE completo .

## Introducción

El juego de palabras encadenadas o juego de la geografía es un juego para niños, típico 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ó con el nombre de la ciudad anterior. La repetición no está permitida. El juego comienza con una ciudad de inicio arbitraria y termina cuando un jugador pierde porque no puede continuar.

### Modelo usando grafos

Para visualizar el juego, se puede construir un grafo dirigido cuyos nodos son cada ciudad 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 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 conducir a la segunda de acuerdo con 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 puede extender el camino pierde. En la figura a continuación se muestra una ilustración del juego (que contiene algunas ciudades de Míchigan).

En un juego de geografía generalizada (GG), reemplazamos el gráfico de nombres de ciudades con un gráfico arbitrario dirigido. 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 segundo 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 lo 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á). Luego $P_2$ elige $N_4$ porque es la única opción restante. $P_1$ ahora elige $N_5$ y $P_2$ elige posteriormente $N_3$ o $N_7.$ Independientemente de la opción de $P_2,$ $P_1$ elige $N_9$ y $P_2$ no tiene opciones restantes y pierde el juego.

## Complejidad computacional

El problema de determinar qué jugador tiene una estrategia ganadora en un juego de geografía generalizado es completo para PSPACE .

### Geografía generalizada está en PSPACE

Sea GG = {<G, b> | $P_1$ tiene una estrategia ganadora para el juego de geografía generalizado en el grafo G a partir del nodo b }. Para mostrar que GG ∈ PSPACE, presentamos un algoritmo recursivo de espacio polinómico que determina qué jugador tiene una estrategia ganadora. Dada una instancia de GG, <G, $n_{start}>$ donde G es un grafo dirigido y $n_{start}$ es el nodo de inicio designado, el algoritmo M procede de la siguiente manera:

En $M(<G,n_{start}>):$

* Medir la cantidad de sucesores del nodo $n_{start}.$ Si es 0, entonces rechazar, porque no hay movimientos disponibles para el jugador uno.
* Construir una lista de todos los nodos alcanzables desde $n_{start}$ por una arista: $n_1,$ $n_2,$ ..., $n_i.$
* Eliminar $n_{start}$ y todas las aristas bordes conectados a él en G para formar $G_1.$
* Para cada nodo $n_j$ en la lista $n_1,$ ..., $n_i,$ llamar a $M(<G_1,$ $n_j>).$
* Si todas estas llamadas son aceptadas, no importa qué decisión tome $P_1,$ $P_2$ tiene una estrategia para ganar, por lo que esta llamada rechaza. De lo contrario (si una de las llamadas rechaza) $P_1$ tiene una opción que evitará cualquier estrategia exitosa para $P_2,$ así que acepta.

El algoritmo M claramente decide GG. Está en PSPACE porque el único espacio de trabajo polinómico no obvio consumido está en la pila de recursión. El espacio consumido por la pila es polinomial porque cada nivel agrega un solo nodo a la pila, y hay a lo sumo n niveles, donde n es el número de nodos en G.

### Geografía generalizada es PSPACE-hard

La siguiente prueba se debe a David Lichtenstein y Michael Sipser.

Para establecer que GG es PSPACE-hard, podemos reducir el problema del juego de fórmulas (que se sabe que es PSPACE-hard) a GG en tiempo polinómico (P). En resumen, una instancia del problema FORMULA-GAME 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 eligiendo valores para sucesivos $x_i$ . $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, suponemos 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 este formulario agregando variables tontas que no aparecen en ψ.

Al construir un grafo G como el que se muestra arriba, mostraremos que cualquier instancia del juego de las fórmulas puede reducirse 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 a la de $P_a.$

La cadena vertical izquierda de nodos está diseñada para imitar el procedimiento de elegir valores para variables en el juego de las fórmulas. Cada estructura de diamante corresponde a una variable cuantificada. Los jugadores se turnan para decidir caminos en cada ramificación. Como 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. 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 pasan por todos los diamantes, nuevamente es 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. Entonces 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 las fórmulas. Recuerde que en el juego de las fórmulas, $P_e$ gana si ψ es verdadero, mientras que $P_a$ gana si ψ es falso. El lado derecho del gráfico 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 insatisfacible. $P_2$ elegirá una cláusula insatisfacible para ganar. Luego, cuando es el turno de $P_1,$ debe elegir un literal en esa cláusula elegida por $P_2.$ Como todos los literales en la cláusula son falsos, no se conectan a los nodos visitados previamente 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 verdadera. Entonces cada cláusula en el 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 realizar y pierde.

### Geografía generalizada planar es PSPACE completa

La geografía generalizada es PSPACE completa, incluso cuando se juega en grafos planares . La siguiente prueba es del teorema 3 de.

Dado que GG plano es un caso especial de GG, y GG está en PSPACE, GG plano está en PSPACE. Queda por demostrar que el GG plano es PSPACE-hard. 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 tal manera que no se crucen tres aristas en un punto, y no se pueden usar dos aristas cruzadas en el mismo juego. Esto no es posible en general, pero siempre es posible para el grafo construido a partir de una instancia del juego de las fórmulas; 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 planar, y el mismo jugador puede forzar una victoria como en el gráfico original: si un jugador elige moverse "hacia arriba" desde V en el juego transformado, ambos jugadores deben continuar moviéndose "hacia arriba" a W o perder inmediatamente. Entonces, moverse "hacia arriba" desde 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 lleva un tiempo que es un múltiplo constante del número de intersecciones de aristas en el gráfico original, por lo que lleva tiempo polinomial.

Por lo tanto, GG planar es PSPACE completo.

### Gráfico bipartito plano con grado máximo 3

GG jugado en gráficos bipartitos planares con un grado máximo 3 todavía es completo en PSPACE, 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. Básicamente,

## Geografía de aristas

Una variante de GG se llama geografía de aristas, donde después de cada movimiento, el borde por el que pasó el jugador se borra. Esto está en contraste 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 geografía de vértices.

La geografía de aristas es PSPACE completa. Esto se demuestra al reducir un problema de decisión de fórmulas booleanas cuantificadas a la geografía de aristas.

## Grafos no dirigidos

También se puede considerar jugar cualquier juego de Geografía en un gráfico no dirigido (es decir, los bordes se pueden atravesar en ambas direcciones). Fraenkel, Scheinerman y Ullman muestran que la geografía de vértices no dirigidos se puede resolver en tiempo polinómico, mientras que la geografía de aristas no dirigida es PSPACE completa, incluso para grafos planares con grado máximo 3. Si el gráfico es bipartito, entonces la Geografía de aristas no dirigida es solucionable en tiempo polinomial.

## Consecuencias

Dado que GG es PSPACE completo, no existe un algoritmo de tiempo polinómico para un juego óptimo en GG a menos que P = PSPACE. Sin embargo, puede que no sea tan fácil demostrar la complejidad de otros juegos porque ciertos juegos (como el ajedrez ) contienen un número finito de posiciones de juego — lo que hace difícil (o imposible) formular un mapeo a un problema de PSPACE completo. A pesar de esto, la complejidad de ciertos juegos aún puede analizarse mediante generalización (p. Ej., En un tablero n × n ). Vea las referencias para una prueba de Go generalizada, como corolario de la prueba de la integridad de GG.

