Geografía generalizada

El juego comienza con una ciudad de inicio arbitraria y termina cuando un jugador pierde porque no puede continuar.

Para visualizar el juego, se puede construir un grafo dirigido cuyos nodos son cada ciudad del mundo.

En la figura a continuación se muestra una ilustración del juego (que contiene algunas ciudades de Míchigan).

En la figura anterior, P1 tiene una estrategia ganadora de la siguiente manera: N1 apunta solo a los nodos N2 y N3 .

En resumen, una instancia del problema FORMULA-GAME consiste en una fórmula booleana cuantificada φ = ∃x1∀x2∃x3...Qxk(ψ) donde Q es ∃ o ∀.

El juego es jugado por dos jugadores, Pa y Pe, que alternan eligiendo valores para sucesivos xi .

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.

Cada jugador debe tomar turnos forzados, y luego P2 elige un valor para x2 .

P1 no tiene más remedio que seguir el camino hacia el lado derecho del gráfico.

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 P2 siga la conexión al nodo correspondiente en un diamante de la cadena izquierda y lo seleccione.

Sin embargo, P1 ahora no puede seleccionar ningún nodo adyacente y pierde.

Para hacer eso, solo es necesario eliminar todos los cruces de bordes del gráfico original.

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.

Fraenkel, Scheinerman y Ullman[3]​ 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.