From Graphs to Games
In my paper with Joshua Xiong on Nim Fractals we explained how to build an evolution graph corresponding to an impartial combinatorial game. The vertices of the graph are P-positions. And two vertices are connected if the two corresponding positions are consecutive P-positions in a longest possible optimal game.
What types of graphs do we get? An evolution graph should have at least one sink: these are our terminal P-positions. Also there are no directed loops: the game is finite. In addition, the distance from a vertex to sinks is uniquely defined: the number of directed edges that is needed to move from this vertex to a sink. This number is equal to half of the number of moves in the longest game, starting from the corresponding P-position.
A natural question arises: Can we build a game from a graph? The graph needs to satisfy the properties above. But other than that, can we? We can consider the graph itself as a game. Players can start at a vertex or an edge. From an edge, they can only move to a vertex where this edge ends. From a vertex they can move to any out-edge. The corresponding evolution graph is the graph itself. Vertices correspond to P-positions and edges to N-positions.
There is an equivalent game with a more uniform description. We put a vertex in the middle of every edge in the evolution graph. The new graph becomes bipartite. Players can start at any vertex. A move is allowed from a vertex following an out-edge to the vertex, where this edge ends. Vertices that are in the same part as terminal positions are P-positions. Other vertices are N-positions.
Share:
Urban Larsson:
Hi Tanya, I think the game in the last paragraph is known as (directed) vertex geography or simply some variation of a “coin-sliding game”. Perhaps there are many other names and variations. In vertex geography you erase the vertex after your move, but this is only necessary if the undirected variation is played. In edge geography, I think we must erase the edge we moved along, but we still use vertices as positions (which is usual). I find it interesting that yo started with some positions, namely the N-positions as the edges, and that you require them to connect P-positions in a longest possible optimal way. This I have not seen before. Only UVG has polynomial complexity, the other ones are in PSPACE, if I recall correctly. Urban
25 August 2015, 5:06 pm