Geography Playground

What is Geography?

Geography is a two-player game played on a graph. A token starts on some vertex. On your turn, you move the token along an available edge. In Edge Geography, the traversed edge is deleted. If it is your turn and there is no legal edge to take, you lose.

This playground focuses on Edge Geography, the version studied in my first research paper. Both Directed Edge Geography and Undirected Edge Geography are PSPACE-complete in general, so one should not expect an efficient solver for arbitrary large graphs.

A polynomial space algorithm for Edge Geography

The solver is deliberately naive. It recursively evaluates positions by minimax:

• a position is losing if there are no legal moves;
• a position is winning if at least one legal move leads to a losing position;
• otherwise, it is losing.

The state is essentially:

current vertex + set of remaining edges

So the brute-force search has exponential dependence on the number of edges. Up to polynomial factors, this is about $O(2^m)$, where $m = |E(G)|$. For a simple undirected graph, $m \leq \binom{n}{2}$, so in terms of vertices this is bounded by roughly $O(2^{n^2})$. The recursion depth of this algorithm is $O(|E|)$ which is polynomial in the input size so $\text{Undirected Edge Geography}, \ \text{Directed Edge Geography} \in \text{PSPACE}$.

Directed Edge Geography is PSPACE-complete

Since we have membership in PSPACE for Directed Edge Geography we must show hardness for the class to get completeness. This is done by constructing a polynomial time reduction from a known PSPACE-complete problem. The canonical PSPACE-complete problem is Quantified Boolean Formula (QBF), which is defined as follows:

A quantified Boolean formula is a Boolean formula in which every variable is bound by a quantifier. Formally, an instance consists of a formula

where each $Q_i \in \{\exists,\forall\}$, each $x_i$ is a Boolean variable, and $\varphi$ is a propositional Boolean formula over the variables $x_1,\ldots,x_n$, for example a formula in conjunctive normal form, as is the usual convention.

The truth value of $\Phi$ is defined recursively as follows. If there are no quantifiers, then $\Phi$ is true exactly when the propositional formula $\varphi$ evaluates to true under the current assignment. Otherwise,

is true if and only if at least one of $\Psi(\text{true})$ or $\Psi(\text{false})$ is true, while

is true if and only if both $\Psi(\text{true})$ and $\Psi(\text{false})$ are true.

The decision problem QBF is:

The reduction works by turning choices of truth values into choices of graph moves. After the variables have been chosen, the graph enters a clause-checking phase. A satisfied literal gives an escape route; an unsatisfied clause traps the player.

Rigorously proving that this works and that the reduction can be constructed in polynomial time gives PSPACE-hardness of the problem.

Undirected Edge Geography is PSPACE-complete

Now that we know that Directed Edge Geography is PSPACE-complete we can replace any directed instance with an undirected instance by using a small clever gadget which simulates a directed edge such that Player 1 wins the directed instance if and only if they win the undirected instance. For details on how this is done see Fraenkel, Scheinerman, and Ullman’s 1993 paper on Undirected Edge Geography [FSU93]. Since replacing each edge can be done in polynomial time we have that Undirected Edge Geography is PSPACE-hard and thus complete.