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?
Generalized Geography with repetitions
graph theory;time complexity;space complexity