What is Col?

Col is a fascinating two-player pencil-and-paper game rooted in the mathematical field of graph theory. It's often described as a map-coloring game, where players take turns coloring different regions within a line drawing. The game was first described and analyzed by the renowned mathematician John Conway, who credited its invention to Colin Vout.

The core idea of Col revolves around the rules of graph coloring. In simple terms, this means that when you color a region, it must not touch any other region that already has the same color. This rule ensures the "properness" of the coloring throughout the game. Players use their own distinct colors, and the game continues until one player finds themselves unable to make a legal move, at which point they lose.

How to Play Col

To play Col, you start with a line drawing that divides a space into several distinct regions, much like a simplified map. The area outside the drawing is usually not considered a region for gameplay. Let's imagine two players, one using red and the other using blue.

The first player begins by choosing any uncolored region and coloring it with their color (e.g., red). There are no restrictions on this first move. The second player then takes their turn, choosing another uncolored region and coloring it with their color (e.g., blue). At this point, since no red regions are touching, and no blue regions are touching, any choice is still legal.

The game becomes more strategic as more regions are colored. When it's your turn, you must select an uncolored region and color it with your designated color. The critical rule is that the region you choose to color cannot share an edge with any other region that is already colored with your same color. It's perfectly fine for your newly colored region to touch regions colored by your opponent. It's important to remember that "touching" means sharing a common boundary line, not just meeting at a single point or vertex.

Players continue to alternate turns, following this rule. The game ends when a player is faced with a situation where every remaining uncolored region either touches one of their own already-colored regions or touches multiple regions in such a way that no legal move can be made. The player who cannot make a legal move is declared the loser.

Why Col is Interesting

Col is more than just a simple coloring game; it's a prime example of a combinatorial game, a type of game studied in mathematics where players take turns making moves, and there's no hidden information or element of chance. Specifically, Col is a partisan game, meaning each player has their own distinct pieces or colors and different objectives.

One of the reasons Col is so interesting to mathematicians is its relative simplicity in analysis. According to John Conway's work in "On Numbers and Games," the "value" of any position in Col can always be expressed as a "number or a number plus star." This mathematical property makes it more straightforward to determine optimal strategies and outcomes compared to many other complex games.

This simplicity stands in contrast to a related game called Snort, invented by Simon P. Norton. While Snort also involves two players coloring regions with two different colors, its core rule is almost the opposite of Col's: neighboring regions are *not allowed* to be given *different* colors. This seemingly small change makes Snort much more complex to analyze; deciding its outcome is considered PSPACE-complete on general graphs, meaning it's computationally very difficult. Col, with its elegant proper coloring rule, offers a more accessible entry point into the fascinating world of mathematical game theory.

Col Game