Generalized geography
In computational complexity theory, generalized geography is a well-known PSPACE-complete problem.
Geography is a children's game, 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.
To visualize the game, a directed graph 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.
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.
The problem of determining which player has a winning strategy in a generalized geography game is PSPACE-complete.
...
Wikipedia