Another version of Geography Game

Question

The classic definition of normal “Geography Game” is the following:

Each player on her turn choose a word such that starts with the last letter of the previously choosen word by another player. (Called “Generalized Geography” in Sipser Chapter 8 and called “The Game of Geography” in papadimitiou Chapter 19. This version is a classic problem in Space Complexity which you probably already know it).

There is another version of the game, in this version player $I$ and player $II$ are restricted to the words that choosed by themeselves. e.g. If player $I$’s last word is Alaska and player $II$’s last word is Kansas then player $I$ next word must start with A not S. The game has a structure like Tron , to be more percise players attempt to block each other ways in the graph. We want to decide if player $I$ has a winning strategy.

This game is also PSPACE-complete. But i don’t know it’s name so i could not find any information about that.

I am looking for the paper which introduced this problem and prove this problem is also PSPACE-complete with reduction from classic version of Geography Game.

Answer 1

At first let me describe "The Game of Geography"; i borrow the definition from this article: On the complexity of some two-person perfect-information games

Input is a pair $\langle G, s \rangle$, where $G$ is a directed graph and $s$ is a node of $G$. A marker is initially placed on node $s$. A move consists of moving the marker along a directed arc to an adjacent node. Each directed arc can be used once only. The first player unable to move loses.

In Sipser ToC 3rd edt. (2012), Chapter 8 (Space complexity), Theorem 8.14 (p. 345), this Problem called $GG$:

$GG=\{\langle G,s \rangle |$Player $I$ has a winning strategy for the generalized geography played on graph $G$ starting at node $s\}$

Now consider this problem which introduced by Simonson (February 5, 1986 SIGART/Issue 96 ):

The game is played on an $N\times N$ board. Two players alternately put markers down and the first player who puts his marker on and edge of boards loses. The main rule is that each player must place his marker only on squares which are adjacent to the last marker he placed down.

This explain the similarity between altered version of $GG$ and Tron game. now we can describe the altered $GG$. This variation as Hendrik Jan has mentioned in comments, called $PG$ or Partizan Geography. I borrow the definition from this paper: Theor. Comput. Sci. 110 (Mathematical Games):

There are two specified vertices $s_1$ and $s_2$. The players alternately chooses arcs. The first arc chosen by the two players, must have its tail, respectively, at $s_1$ and $s_2$; and each subsequently chosen arc must have its tail at the vertex that was the head of the arc previously chosen by that player.

Now we can define altered $GG$ in order to describe this variant:

$PG=\{\langle G,s_1,s_2 \rangle |$Player $I$ has a winning strategy for the partizan geography played on graph $G$ starting at nodes $s_1$ and $s_2\}$

As i mention, This variant is also PSPACE-complete, in fact $PG$ is proved to be PSPACE-complete under the name $TRON$ (Theor. Comput. Sci. 110 (1993) 215-245 (Mathematical Games))

What Hendrik Jan in comments mentioned, is more interesting. Because before now i did not know there are different restrictions that we can apply to the game which when they applied, the game still stay PSPACE-complete. This article: On the Computational Complexities of Various Geography Variants examine four different rule variants.