## 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: