Consider the \"Generalized Geography\" game: on directed graph G with selected s
ID: 652909 • Letter: C
Question
Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to move wins.
GG = { : G is a directed graph, b is a node in G, and the next player to play has a winning strategy for generalized geography from start node b, i.e., there are moves for the next player to win no matter how opponent plays }
This problem is well-known to be in PSPACE and EXPTIME-hard. My question is: If we allow repetitions in GG, it still belongs to EXPTIME-hard?
Explanation / Answer
If repetitions are allowed, the problem is in P, as the (immediate) losing nodes are the ones with no outgoing edges, first find these, then declare the nodes winning from which you can reach such a node, if you can reach only winning ones, its a losing node, and so on, rest are drawing.