Thursday, June 15, 2017

Game Description: Cutthroat and Impartial Cutthroat

A long time back, while going through Lessons in Play, I got hung up on the definition of Impartial Cutthroat in section 2.2.  I completely forgot about this until recently, when a student asked me to explain what was going on.  Today, I had a look back at Cutthroat and Impartial Cutthroat and confirmed my understanding with Richard Nowakowski.  In this post, I'll try to clarify both games.

Cutthroat is a partisan game played on a graph where each vertex is colored Blue or Red.  In addition, each connected component of the graph must include vertices of both colors.  Each turn a player chooses one of the vertices of their color and removes it from the board, including all incident edges.  Then, remove any connected component that includes only vertices of one color.

Here's a whiteboard sketch of a Cutthroat game tree I made today:

Notice that Red has an immediate move to zero by choosing the lower red vertex.  (The remaining two connected components are both mono-colored, so they are immediately removed.)

I've added this as it's own entry in the ruleset table.

Impartial Cutthroat is a bit different.  On one hand, it's the same game if you assume that players can choose vertices of any color AND all vertices are given a unique color.  

Another way to explain it is that a position is an uncolored graph where each vertex must have at least one neighbor.  On a player's turn, they choose a vertex and remove it and all incident edges.  Afterwards, all vertices with no neighbors are also removed.

Yet another way to explain Impartial Cutthroat is by considering it as a variant of Node Kayles.  In Kayles, a player chooses a vertex, then removes that vertex and all of its direct neighbors.  Here, there are two differences:
  • The player must choose a vertex that has at least one neighbor.
  • Only the chosen vertex is removed, not any of the neighbors.
Because of this similarity, I've included it in the ruleset table as a variant of Node Kayles, instead of a standalone game or a variant of Cutthroat.


  1. I was under the impression that Cutthroat is supposed to be related to Clobber. In Clobber, if you have a connected component of a single color, then there are no moves left. It isn't exactly the same, and there's probably no way of making them the same, but it has a very similar sort of feel. Also, they're both all-small games.

    1. Those are really good points. I definitely didn't think of that!