I’ve been teaching some combinatorial game theory on the weekends to a group of Perth’s best maths students, and I recently taught them about how you can use directed graphs to visualise the winning positions in a game. An impartial game is essentially an acyclic directed graph with a unique source and sink, and I thank Grant Cairns of La Trobe University for this wonderful insight. The directed graph of a game is built in the following way. The unique source is the starting position in the game, and we combine all the finishing positions into one vertex; the sink of the graph. The vertices are the positions in the game, and we join a position to a position with a directed edge if there is a move from to .
Now comes the fun part…
The height of a position is the maximum number of moves it takes to get to the end game (the longest path in the graph). We then assign values 0 and 1 to each vertex by induction on the height: the sink has value 0, and a position has value 1 if it points to at least one position with value 0, and we give it the value 0 otherwise. After we have coloured the vertices with 0’s and 1’s, we can read off the winning positions (the 1’s) and the losing positions (the 0’s).
The picture below gives us a beautiful picture of a game of “Silver dollar — without the dollar”. The game goes like this: we start with a strip of squares which has a finite end on the left hand side, and we have some coins which each occupy one square of the strip. Each player must move a coin leftwards, any number of squares, but is not allowed to jump over another coin. The last player to move is the winner.
The picture we have below is this game where we start with coins on the second, fifth and seventh squares.