Generalized Geography
Encyclopedia
In computational complexity theory
, generalized geography is a problem that can be proven to be PSPACE-complete
.
, which is good for a long car trip, 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.
can be constructed whose nodes are each cities of the world. An arrow is added from node N1 to node N2 if and only if the city labeling N2 starts with the letter that ending the name of the city labeling node N1. 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.
. Let
GG = { | P1 has a winning strategy for the generalized geography game played on graph G starting at node b }.
, we present a polynomial-space recursive algorithm determining which player has a winning strategy. Given an instance of GG,start> where G is a directed graph and nstart is the designated start node, the algorithm M proceeds as follows:
On M(start>):
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.
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
φ = ∃x1 ∀x2 ∃x3 ...Qxk(ψ) where Q is either ∃ or ∀. The game is played by two players, Pa and Pe, who alternate choosing values for successive xi. Pe wins the game if the formula ψ ends up true, and Pa wins if ψ ends up false.
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 P1 is equivalent to that of Pe, and the optimal strategy for P2 is equivalent to that of Pa.
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, P1 goes first, selecting the left node if x1 is true and the right node if x1 is false. Each player must then take forced turns, and then P2 chooses a value for x2. These alternating assignments continue down the left side. After both players pass through all the diamonds, it is again P1 's turn, because we assumed that the last quantifier is existential. P1 has no choice but to follow the path to the right side of the graph. Then it is P2 '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, Pe wins if ψ is true, while Pa wins if ψ is false. The right side of the graph guarantees that P1 wins if and only if Pe wins, and that P2 wins if and only if Pa wins.
First we show that P2 always wins when Pa wins. If Pa wins, ψ is false. If ψ is false, there exists an unsatisfying clause. P2 will choose an unsatisfying clause to win. Then when it is P1's turn he must choose a literal in that clause chosen by P2. Since all the literals in the clause are false, they do not connect to previously visited nodes in the left vertical chain. This allows P2 to follow the connection to the corresponding node in a diamond of the left chain and select it. However, P1 is now unable to select any adjacent nodes and loses.
Now we show that P1 always wins when Pe wins. If Pe wins, ψ is true. If ψ is true, every clause in the right side of the graph contains a true literal. P2 can choose any clause. Then P1 chooses the literal that is true. And because it is true, its adjacent node in the left vertical node has already been selected, so P2 has no moves to make and loses.
, 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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, generalized geography is a problem that can be proven to be PSPACE-complete
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
.
Introduction
Geography is a children's gameGame
A game is structured playing, usually undertaken for enjoyment and sometimes used as an educational tool. Games are distinct from work, which is usually carried out for remuneration, and from art, which is more often an expression of aesthetic or ideological elements...
, which is good for a long car trip, where players take turns naming cities
City
A city is a relatively large and permanent settlement. Although there is no agreement on how a city is distinguished from a town within general English language meanings, many cities have a particular administrative, legal, or historical status based on local law.For example, in the U.S...
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.
Graph model
To visualize the game, a directed graphDirected graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
can be constructed whose nodes are each cities of the world. An arrow is added from node N1 to node N2 if and only if the city labeling N2 starts with the letter that ending the name of the city labeling node N1. 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.
Playing the game
We define P1 as the player moving first and P2 as the player moving second and name the nodes N1 to Nn. In the above figure, P1 has a winning strategy as follows: N1 points only to nodes N2 and N3. Thus P1's first move must be one of these two choices. P1 chooses N2 (if P1 chooses N3, then P2 will choose N9 as that is the only option and P1 will lose). Next P2 chooses N4 because it is the only remaining choice. P1 now chooses N5 and P2 subsequently chooses N3 or N7. Regardless of P2's choice, P1 chooses N9 and P2 has no remaining choices and loses the game.Problem statement
The problem of determining which player has a winning strategy in a generalized geography game is PSPACE-completePSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
. Let
GG = {
Generalized geography is in PSPACE
To show that GG ∈ PSPACEPSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
, we present a polynomial-space recursive algorithm determining which player has a winning strategy. Given an instance of GG,
On M(
- Measure the out-degree of node nstart. If this degree is 0, then return reject, because there are no moves available for player one.
- Construct a list of all nodes reachable from nstart by one edge: n1, n2, ..., ni.
- Remove nstart and all edges connected to it from G to form G1.
- For each node nj in the list n1, ..., ni, call M(
- If all of these calls return accept, then no matter which decision P1 makes, P2 has a strategy to win, so return reject. Otherwise (if one of the calls returns reject) P1 has a choice that will deny any successful strategies for P2, so return accept.
The algorithm M clearly decides GG. It is in PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
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.
Generalized geography is PSPACE-hard
To establish the PSPACE-hardness of GG, we can reduce the FORMULA-GAMEFormula game
A formula game is an artificial game represented by a fully quantified Boolean formula. Players' turns alternate and the space of possible moves is denoted by bound variables. If a variable is universally quantified, the formula following it has the same truth value as the formula beginning with...
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
True quantified Boolean formula
In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified , using either existential or universal quantifiers, at the...
φ = ∃x1 ∀x2 ∃x3 ...Qxk(ψ) where Q is either ∃ or ∀. The game is played by two players, Pa and Pe, who alternate choosing values for successive xi. Pe wins the game if the formula ψ ends up true, and Pa wins if ψ ends up false.
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 P1 is equivalent to that of Pe, and the optimal strategy for P2 is equivalent to that of Pa.
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, P1 goes first, selecting the left node if x1 is true and the right node if x1 is false. Each player must then take forced turns, and then P2 chooses a value for x2. These alternating assignments continue down the left side. After both players pass through all the diamonds, it is again P1 's turn, because we assumed that the last quantifier is existential. P1 has no choice but to follow the path to the right side of the graph. Then it is P2 '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, Pe wins if ψ is true, while Pa wins if ψ is false. The right side of the graph guarantees that P1 wins if and only if Pe wins, and that P2 wins if and only if Pa wins.
First we show that P2 always wins when Pa wins. If Pa wins, ψ is false. If ψ is false, there exists an unsatisfying clause. P2 will choose an unsatisfying clause to win. Then when it is P1's turn he must choose a literal in that clause chosen by P2. Since all the literals in the clause are false, they do not connect to previously visited nodes in the left vertical chain. This allows P2 to follow the connection to the corresponding node in a diamond of the left chain and select it. However, P1 is now unable to select any adjacent nodes and loses.
Now we show that P1 always wins when Pe wins. If Pe wins, ψ is true. If ψ is true, every clause in the right side of the graph contains a true literal. P2 can choose any clause. Then P1 chooses the literal that is true. And because it is true, its adjacent node in the left vertical node has already been selected, so P2 has no moves to make and loses.
Consequences
Given that GG is PSPACE-completePSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
, no polynomial time algorithm exists for optimal play in GG unless P = PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
. However, it may not be as easy to prove the complexity of other games because certain games (such as chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
) contain a finite number of game positions — making it hard (or impossible) to formulate a mapping to a PSPACE-complete
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
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
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
, as a corollary of the proof of the completeness of GG.