In this week’s post, Dan and Andrew’s Game Place debuts a new game based on graph coloring: the Grundy Game. The game is played on a graph, like the one above. The players take turns writing positive whole numbers in the circles (only one number can go in a circle). Here are the rules:
- Decide randomly which player goes first.
- A player moves by writing a positive whole number, 1, 2, 3, 4, and so on, in an empty vertex. These are the circles in the example board.
- You may not use a number that is already written in a vertex adjacent to the one you are filling. In the board above, adjacency is shown by a line between the two vertices.
- The number a player writes is added to their score.
- The game continues until all the vertices have a number in them.
- The player with the lowest score wins.
What does this have to do with coloring graphs?
Our sister blog, Occupy Math, has a post on graph coloring in case you want the whole scoop. In the Grundy game, the numbers are serving as surrogates for colors. A graph is properly colored if we put a color on each vertex in a manner so that no color is adjacent to itself along the edges of the graph. The Occupy Math post shows how this is useful for conflict resolution, but in the Grundy game it actually creates the tension that causes the game to have nontrivial strategy.
By carefully choosing where you move, you can force the other player to write a larger number than he might otherwise be able to. The Grundy game board, shown above in two states, is much too simple — except possibly for explaining the rules — but it illustrates this strategic point. The board on the left shows the smallest possible numbers and also shows that, if these numbers appear, the first player will always win by four to five. The second version of the board shows the first player’s first two moves in black and the second player’s first two moves in red. These moves force both players to write a three!
Other ways of representing boards
The alternate way of presenting a board is as a Voronoi tiling. Numbers are written in the “countries” of the “map” inside the circle. Two countries are adjacent if they share a border. If several countries meet at a corner they are not considered to be adjacent (we tried to avoid this in our example boards). While this way of presenting a board for the Grundy game looks very different, the game can still be played with the same rules. Example boards are available in a PDF.
Strategy notes
The number of neighbours a vertex has tells you the largest number that a player can be forced to write on that vertex — and that only happens if all the neighbours are all different from one another. In the example using the hexagon as a board, since every vertex has two neighbours, the biggest number you will ever have to write is three.
Groups of neighbours that are all joined to one another must all have different numbers on them. This means that graphs with longer cycles in them probably make for more difficult strategy when they are used as boards in the Grundy game. Similarly, having several neighbours per vertex creates the room to force your opponent to write a large number. These strategic concerns informed the choice of graph in the boards that are explicitly given as systems of vertices and edges, like the one at the top of the post. The Voronoi-map boards were generated at random and then we chose boards that follow these strategic guidelines.
We are currently researching what makes a good Grundy board, beyond the rules of thumb given in this post, by seeing how simple AIs play the Grundy game. If we find anything interesting, we will make another post. If you have any thoughts, please let up know in the comments!
This is Dan of Dan and Andrew’s Game Place. Also comment if you like (or hate) the game!
Dan and Andrew's Game Place 