Geografía generalizada

Para visualizar el juego, se puede construir un grafo dirigido cuyos nodos representan ciudades del mundo. Se añade una flecha del nodo _N1 al nodo _N2 si y solo si la ciudad que etiqueta el nodo _N2 comienza con la letra que termina el nombre de la ciudad que etiqueta el nodo N1 _. En otras palabras, se dibuja una flecha de una ciudad a otra si la primera puede llevar a la segunda según las reglas del juego. Cada arista alterna del grafo dirigido corresponde a un jugador (en un juego de dos jugadores). El primer jugador que no pueda extender el camino pierde. En la siguiente figura se muestra una ilustración del juego (que incluye algunas ciudades de Michigan).

En un juego de geografía generalizada (GG), reemplazamos el grafo de nombres de ciudades con un grafo dirigido arbitrario. El siguiente grafo es un ejemplo de un juego de geografía generalizada.

Definimos a P ₁ como el jugador que mueve primero y a P ₂ como el jugador que mueve segundo, y nombramos los nodos N ₁ a N _n . En la figura anterior, P ₁ tiene la siguiente estrategia ganadora: N ₁ apunta solo a los nodos N ₂ y N ₃ . Por lo tanto, el primer movimiento de P _{1 debe ser una de estas dos opciones.} P ₁ elige N ₂ (si P ₁ elige N ₃ , entonces P ₂ elegirá N ₉ ya que es la única opción y P ₁ perderá). Luego P ₂ elige N ₄ porque es la única opción restante. P ₁ ahora elige N ₅ y P ₂ posteriormente elige N ₃ o N ₇ . Independientemente de la elección de P ₂ , P ₁ elige N ₉ y P ₂ no tiene opciones restantes y pierde el juego.

Sea GG = { ⟨ G , b ⟩ | P ₁ tiene una estrategia ganadora para el juego de geografía generalizado jugado en el grafo G comenzando en el nodo b }; para demostrar que GG ∈ PSPACE , presentamos un algoritmo recursivo en espacio polinomial que determina qué jugador tiene una estrategia ganadora. Dado un caso de GG, ⟨ G , n _inicio ⟩ donde G es un grafo dirigido y n _inicio es el nodo de inicio designado, el algoritmo M procede de la siguiente manera:

En M (⟨ G , n _inicio ⟩):

1. Mide el grado de salida del nodo n _inicial . Si este grado es 0, devuelve "rechazar" , porque no hay movimientos disponibles para el jugador uno.
2. Construye una lista de todos los nodos alcanzables desde _{el inicio} n por una arista: n ₁ , n ₂ , ..., n _i .
3. Eliminar n _inicio y todos los bordes conectados a él de G para formar G ₁ .
4. Para cada nodo n _j en la lista n ₁ , ..., n _i , llamar a M (⟨ G ₁ , n _j ⟩).
5. Si todas estas llamadas devuelven "aceptar" _, entonces, independientemente de la decisión que tome P1 , P2 tiene una estrategia para ganar, por lo que devuelve "rechazar" . De lo contrario (si una de las llamadas devuelve "rechazar "), _P1 tiene una opción que negará cualquier estrategia exitosa para P2 , por lo que devuelve _" aceptar _" .

El algoritmo M decide claramente GG. Está en PSPACE porque el único espacio de trabajo polinomial no obvio consumido es en la pila de recursión. El espacio consumido por la pila de recursión es polinomial porque cada nivel de recursión agrega un solo nodo a la pila, y hay como máximo n niveles, donde n es el número de nodos en G. Esto es esencialmente equivalente a una búsqueda en profundidad .

La siguiente demostración se debe a David Lichtenstein y Michael Sipser . ^{[ 1 ]}

Para establecer la PSPACE-dureza de GG, podemos reducir el problema FORMULA-GAME (que se sabe que es PSPACE-dureza ) a GG en tiempo polinomial ( P ). En resumen, una instancia del problema FORMULA-GAME consiste en una fórmula booleana cuantificada φ = ∃ x ₁ ∀ x ₂ ∃ x ₃ ... Qx _k (ψ) donde Q es ∃ o ∀. El juego lo juegan dos jugadores, P _a y P _e , que se alternan eligiendo valores para sucesivos x _i . P _e gana el juego si la fórmula ψ resulta verdadera , y P _a gana si ψ resulta falsa . Se supone que la fórmula ψ está en forma normal conjuntiva .

En esta demostración, para simplificar, asumimos que la lista de cuantificadores comienza y termina con el calificador existencial, ∃. Cabe destacar que cualquier expresión puede transformarse a esta forma añadiendo variables ficticias que no aparecen en ψ.

Al construir un gráfico G como el que se muestra arriba, demostraremos que cualquier instancia de FORMULA-GAME se puede reducir a una instancia de Geografía Generalizada, donde la estrategia óptima para P ₁ es equivalente a la de P _e , y la estrategia óptima para P ₂ es equivalente a la de P _a .

La cadena vertical izquierda de nodos 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 caminos en cada nodo de ramificación. Como asumimos que el primer cuantificador sería existencial, P ₁ va primero, seleccionando el nodo izquierdo si x ₁ es verdadero y el nodo derecho si x ₁ es falso . Luego, cada jugador debe tomar turnos obligatorios, y después P ₂ elige un valor para x _2. Estas asignaciones alternas continúan hacia abajo por el lado izquierdo. Después de que ambos jugadores pasan por todos los diamantes, es nuevamente el turno de P ₁ , porque asumimos que el último cuantificador es existencial. P ₁ 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órmulas. Recordemos que en el juego de 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 ₁ gana si y solo si P _e gana, y que P ₂ gana si y solo si P _a gana.

Primero demostramos que P ₂ siempre gana cuando P _a gana. Si P _a gana, ψ es falso . Si ψ es falso , existe una cláusula insatisfactoria. P ₂ elegirá una cláusula insatisfactoria para ganar. Luego, cuando sea el turno de P ₁ , deberá elegir un literal en la cláusula elegida por P _2. Dado que todos los literales en la cláusula son falsos , no se conectan con nodos visitados previamente en la cadena vertical izquierda. Esto permite a P ₂ seguir la conexión al nodo correspondiente en un rombo de la cadena izquierda y seleccionarlo. Sin embargo, P ₁ ahora no puede seleccionar ningún nodo adyacente y pierde.

Ahora demostramos que P ₁ siempre gana cuando P _e gana. Si P _e gana, ψ es verdadero . Si ψ es verdadero , cada cláusula en el lado derecho del grafo contiene un literal verdadero . P ₂ puede elegir cualquier cláusula. Entonces P ₁ elige el literal que es verdadero . Y como es verdadero , su nodo adyacente en el nodo vertical izquierdo ya ha sido seleccionado, por lo que P ₂ no tiene movimientos que hacer y pierde.

La geografía generalizada es PSPACE-completa, incluso cuando se juega en grafos planares . La siguiente demostración proviene del teorema 3 de ^{[ 1 ] .}

Dado que GG planar es un caso especial de GG, y GG pertenece a PSPACE, entonces GG planar también pertenece a PSPACE. Resta demostrar que GG planar es PSPACE-difícil. Esto se puede probar mostrando cómo convertir un grafo arbitrario en un grafo planar, de manera que una partida de GG jugada en este grafo tenga el mismo resultado que en el grafo original.

Para ello, basta con eliminar todos los cruces de aristas del grafo original. Dibujamos el grafo de forma que no haya tres aristas que se crucen en un punto, y que ningún par de aristas que se crucen pueda utilizarse en el mismo juego. Esto no es posible en general, pero siempre lo es para el grafo construido a partir de una instancia de FORMULA-GAME; por ejemplo, podríamos tener solo las aristas de los vértices de las cláusulas involucradas en los cruces. Ahora reemplazamos cada cruce con esta construcción:

El resultado es un grafo planar, y el mismo jugador puede forzar la victoria como en el grafo original: si un jugador decide moverse "hacia arriba" desde V en el juego transformado, ambos jugadores deben continuar moviéndose "hacia arriba" hasta W o pierden inmediatamente. Por lo tanto, moverse "hacia arriba" desde V en el juego transformado simula el movimiento V→W del juego original. Si V→W es un movimiento ganador, entonces moverse "hacia arriba" desde V en el juego transformado también lo es, y viceversa.

Por lo tanto, el juego de GG jugado en el grafo transformado tendrá el mismo resultado que en el grafo original. Esta transformación requiere un tiempo que es un múltiplo constante del número de intersecciones de aristas en el grafo original, por lo que su tiempo es polinomial.

Por lo tanto, el GG planar es PSPACE-completo.

GG jugado en grafos bipartitos planares 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 utiliza la siguiente construcción:

Si un jugador utiliza cualquiera de las entradas a esta construcción, el otro jugador elige qué salida utilizará. Además, la construcción solo se puede recorrer una vez, ya que el vértice central siempre se visita. Por lo tanto, esta construcción es equivalente al vértice original.