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.
