Geography Playground · Thobias Høivik

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.

A played game of Undirected Edge Geography

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 (for details on what exactly this means you can see my page on introductory complexity theory), so one should not expect an efficient solver for arbitrary large graphs.

Taking a step back, we can think of Edge Geography as something like Chess, Go or Tic Tac Toe. We play against one another (or against a computer) and we try to get the oponent into a position such that they will end up with no legal continuation.

Below is a demo where you can try to play against an optimal opponent (optimal meaning it will always win if you make a mistake, but if you get a winning position it will just pick the first possible move).

Play first

Can you beat perfect play?

Your turn

Move the token along an edge. The edge disappears after you use it. If it is your turn and there is nowhere left to move, you lose.

The computer is not using a heuristic. These graphs are small enough that it can recursively solve the remaining game and choose a winning move whenever one exists.

A polynomial space algorithm for Edge Geography

A natural computational question is whether we can efficiently determine the winner, given some position. We can come up with a very simple algorithm, very similar to the backbone of algorithms used in Chess!

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 then essentially the
current position and set of remaining moves.

Intutively, we look at, for every move I can play, what can the oponent do, then ask how I can respond to those. This is exponential, but the recursion depth has manageable dependence on the number of moves so we say that this procedure gives us a “PSPACE” (polynomial space) upper bound on the problem.

More precisely

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}.

Vertex mode: left-click empty space to add a vertex, left-click a vertex to choose the start, drag vertices to move them, and right-click a vertex to remove it. Edge mode: left-click two vertices to add or toggle an edge; right-click an edge to remove it.

Directed Edge Geography is PSPACE-complete

To show that the problem is PSPACE-complete (polynomial space complete) we do a polynomial time reduction, which is basically just an algorithm, from another PSPACE-complete problem.

We use this to conclude that if our problem was solvable “quickly”, we could turn an instance of the hard problem into ours quickly and then run our algorithm quickly to solve the starting problem.

Basically, we show that Edge Geography is just as hard as the hardest problem solvable with polynomial space.

That problem is the Quantified Boolean Formula (QBF) problem, the canonical PSPACE-complete problem!

The Quantified Boolean Formula problem asks if a a quantified boolean formula, which is a formula where the variables can take on true or false values and those variables are quantified, is true.

For instance the formula $\forall x \exists y : x \land y$ is a formula saying: “for every $x$ there exists a $y$ such that $x$ and $y$ ”.

This formula is not true because if $x$ is false the expression $x$ and $y$ is automatically false.

We create a game of (Directed) Edge Geography where Player $1$ gets to choose true or false for all the variables which are existentially quantified ( $\exists$ ), while Player $2$ gets to choose values for the universally quantified variables ( $\forall$ ).

Then Player 2 gets to choose a collection of these variables so that if those variables are false, Player $1$ loses.

Otherwise Player $2$ will lose.

Semi-rigorous reduction procedure

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

\Phi = Q_1 x_1 \; Q_2 x_2 \; \cdots \; Q_n x_n \; \varphi(x_1,\ldots,x_n),

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,

\exists x \, \Psi(x)

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

\forall x \, \Psi(x)

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

The decision problem QBF is:

\text{QBF} = \{\Phi : \Phi \text{ is a true fully quantified Boolean formula}\}.

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.

Directed Edge Geography reduction

QBF → directed Edge Geography

The formula creates a directed graph. Variable choices consume edges, Player 2 challenges a clause, and Player 1 must point back to an already-consumed assignment branch.

Winning position

(x ∨ y ∨ ¬z)(¬x ∨ z)(¬y ∨ z)

Step 1 / 18 · P1 to move

Start

Player 1 starts at the beginning of the generated directed Edge Geography instance.

Formula builder

Toggle quantifiers above. Click a table cell to cycle through absent, positive, and negative literals.

Clause	x	y	z
C1
C2
C3

Current assignment

∃x–

∀y–

∃z–

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.

[FSU93] A. S. Fraenkel, E. R. Scheinerman, and D. Ullman, “Undirected edge geography,” Theoretical Computer Science 112(2):371–381, 1993. DOI: 10.1016/0304-3975(93)90026-P.