Generalized geography

In computational complexity theory, generalized geography is a well-known PSPACE-complete problem.

Geography is a children's game, where players take turns naming cities from anywhere in the world. Each city chosen must begin with the same letter that ended the previous city name. Repetition is not allowed. The game begins with an arbitrary starting city and ends when a player loses because he or she is unable to continue.

To visualize the game, a directed graph can be constructed whose nodes are each cities of the world. An arrow is added from node N₁ to node N₂ if and only if the city labeling N₂ starts with the letter that ending the name of the city labeling node N₁. In other words, we draw an arrow from one city to another if the first can lead to the second according to the game rules. Each alternate edge in the directed graph corresponds to each player (for a two player game). The first player unable to extend the path loses. An illustration of the game (containing some cities in Michigan) is shown in the figure below.

In a generalized geography (GG) game, we replace the graph of city names with an arbitrary directed graph. The following graph is an example of a generalized geography game.

We define P₁ as the player moving first and P₂ as the player moving second and name the nodes N₁ to N_n. In the above figure, P₁ has a winning strategy as follows: N₁ points only to nodes N₂ and N₃. Thus P₁'s first move must be one of these two choices. P₁ chooses N₂ (if P₁ chooses N₃, then P₂ will choose N₉ as that is the only option and P₁ will lose). Next P₂ chooses N₄ because it is the only remaining choice. P₁ now chooses N₅ and P₂ subsequently chooses N₃ or N₇. Regardless of P₂'s choice, P₁ chooses N₉ and P₂ has no remaining choices and loses the game.

The problem of determining which player has a winning strategy in a generalized geography game is PSPACE-complete.

Let GG = { ⟨G, b⟩ | P₁ has a winning strategy for the generalized geography game played on graph G starting at node b }; to show that GG ∈ PSPACE, we present a polynomial-space recursive algorithm determining which player has a winning strategy. Given an instance of GG, ⟨G, n_start⟩ where G is a directed graph and n_start is the designated start node, the algorithm M proceeds as follows:

On M(⟨G, n_start⟩):

1. Measure the out-degree of node n_start. If this degree is 0, then return reject, because there are no moves available for player one.
2. Construct a list of all nodes reachable from n_start by one edge: n₁, n₂, ..., n_i.
3. Remove n_start and all edges connected to it from G to form G₁.
4. For each node n_j in the list n₁, ..., n_i, call M(⟨G₁, n_j⟩).
5. If all of these calls return accept, then no matter which decision P₁ makes, P₂ has a strategy to win, so return reject. Otherwise (if one of the calls returns reject) P₁ has a choice that will deny any successful strategies for P₂, so return accept.

The algorithm M clearly decides GG. It is in PSPACE because the only non-obvious polynomial workspace consumed is in the recursion stack. The space consumed by the recursion stack is polynomial because each level of recursion adds a single node to the stack, and there are at most n levels, where n is the number of nodes in G. This is essentially equivalent to a depth-first search.

The following proof is due to David Lichtenstein and Michael Sipser.^[1]

To establish the PSPACE-hardness of GG, we can reduce the FORMULA-GAME problem (which is known to be PSPACE-hard) to GG in polynomial time (P). In brief, an instance of the FORMULA-GAME problem consists of a quantified Boolean formula φ = ∃x₁ ∀x₂ ∃x₃ ...Qx_k(ψ) where Q is either ∃ or ∀. The game is played by two players, P_a and P_e, who alternate choosing values for successive x_i. P_e wins the game if the formula ψ ends up true, and P_a wins if ψ ends up false. The formula ψ is assumed to be in conjunctive normal form.

In this proof, we assume that the quantifier list starts and ends with the existential qualifier, ∃, for simplicity. Note that any expression can be converted to this form by adding dummy variables that do not appear in ψ.

By constructing a graph G like the one shown above, we will show any instance of FORMULA-GAME can be reduced to an instance of Generalized Geography, where the optimal strategy for P₁ is equivalent to that of P_e, and the optimal strategy for P₂ is equivalent to that of P_a.

The left vertical chain of nodes is designed to mimic the procedure of choosing values for variables in FORMULA-GAME. Each diamond structure corresponds to a quantified variable. Players take turns deciding paths at each branching node. Because we assumed the first quantifier would be existential, P₁ goes first, selecting the left node if x₁ is true and the right node if x₁ is false. Each player must then take forced turns, and then P₂ chooses a value for x₂. These alternating assignments continue down the left side. After both players pass through all the diamonds, it is again P₁ 's turn, because we assumed that the last quantifier is existential. P₁ has no choice but to follow the path to the right side of the graph. Then it is P₂ 's turn to make a move.

When the play gets to the right side of the graph, it is similar to the end of play in the formula game. Recall that in the formula game, P_e wins if ψ is true, while P_a wins if ψ is false. The right side of the graph guarantees that P₁ wins if and only if P_e wins, and that P₂ wins if and only if P_a wins.

First we show that P₂ always wins when P_a wins. If P_a wins, ψ is false. If ψ is false, there exists an unsatisfying clause. P₂ will choose an unsatisfying clause to win. Then when it is P₁'s turn he must choose a literal in that clause chosen by P₂. Since all the literals in the clause are false, they do not connect to previously visited nodes in the left vertical chain. This allows P₂ to follow the connection to the corresponding node in a diamond of the left chain and select it. However, P₁ is now unable to select any adjacent nodes and loses.

Now we show that P₁ always wins when P_e wins. If P_e wins, ψ is true. If ψ is true, every clause in the right side of the graph contains a true literal. P₂ can choose any clause. Then P₁ chooses the literal that is true. And because it is true, its adjacent node in the left vertical node has already been selected, so P₂ has no moves to make and loses.

Generalized geography is PSPACE-complete, even when played on planar graphs. The following proof is from theorem 3 of.^[1]

Since planar GG is a special case of GG, and GG is in PSPACE, so planar GG is in PSPACE. It remains to show that planar GG is PSPACE-hard. This can be proved by showing how to convert an arbitrary graph into a planar graph, such that a game of GG played on this graph will have the same outcome as on the original graph.

In order to do that, it's only necessary to eliminate all the edge crossings of the original graph. We draw the graph such that no three edges intersect at a point, and no pair of crossing edges can both be used in the same game. This is not possible in general, but is always possible for the graph constructed from a FORMULA-GAME instance; for example we could have only the edges from clause vertices involved in crossings. Now we replace each crossing with this construction:

The result is a planar graph, and the same player can force a win as in the original graph: if a player chooses to move "up" from V in the transformed game, then both players must continuing moving "up" to W or lose immediately. So moving "up" from V in the transformed game simulates the move V→W in the original game. If V→W is a winning move, then moving "up" from V in the transformed game is also a winning move, and vice versa.

Thus, the game of GG played on the transformed graph will have the same outcome as on the original graph. This transformation takes time that is a constant multiple to the number of edge intersections in the original graph, thus it takes polynomial time.

Thus planar GG is PSPACE-complete.

GG played on planar bipartite graphs with maximum degree 3 is still PSPACE-complete, by replacing the vertices of degree higher than 3 with a chain of vertices with degree at most 3. Proof is in.^[1] and uses the following construction:

If one player uses any of the entrances to this construction, the other player chooses which exit will be used. Also the construction can only be traversed once, because the central vertex is always visited. Hence this construction is equivalent to the original vertex.

A variant of GG is called edge geography, where after each move, the edge that the player went through is erased. This is in contrast to the original GG, where after each move, the vertex that the player used to be on is erased. In this view, the original GG can be called Vertex Geography.

Edge geography is PSPACE-complete. This can be proved used the same construction that was used for vertex geography.^[2]

One may also consider playing either Geography game on an undirected graph (that is, the edges can be traversed in both directions). Fraenkel, Scheinerman, and Ullman^[3] show that undirected vertex geography can be solved in polynomial time, whereas undirected edge geography is PSPACE-complete, even for planar graphs with maximum degree 3. If the graph is bipartite, then Undirected Edge Geography is solvable in polynomial time.

Given that GG is PSPACE-complete, no polynomial time algorithm exists for optimal play in GG unless P = PSPACE. However, it may not be as easy to prove the complexity of other games because certain games (such as chess) contain a finite number of game positions — making it hard (or impossible) to formulate a mapping to a PSPACE-complete problem. In spite of this, the complexity of certain games can still be analyzed by generalization (e.g., to an n × n board). See the references for a proof for generalized Go, as a corollary of the proof of the completeness of GG.

• Michael Sipser, Introduction to the Theory of Computation, PWS, 1997.