Software:Map-coloring games

Short description: Games in game theory

A trichrome map-coloring game in progress, on a map of the United States. On their turn, a player may choose any of the three colors to shade an unshaded state, so long as it would not share a color with a bordering state. Three states have become unshadeable, being surrounded by all three colors.

Several map-coloring games are studied in combinatorial game theory. The general idea is that we are given a map with regions drawn in but with not all the regions colored. Two players, Left and Right, take turns coloring in one uncolored region per turn, subject to various constraints, as in the map-coloring problem. The move constraints and the winning condition are features of the particular game.

Some players find it easier to color vertices of the dual graph, as in the Four color theorem. In this method of play, the regions are represented by small circles, and the circles for neighboring regions are linked by line segments or curves. The advantages of this method are that only a small area need be marked on a turn, and that the representation usually takes up less space on the paper or screen. The first advantage is less important when playing with a computer interface instead of pencil and paper. It is also possible to play with Go stones or Checkers.

Move constraints

An inherent constraint in each game is the set of colors available to the players in coloring regions. If Left and Right have the same colors available to them, the game is impartial; otherwise the game is partisan. The set of colors could also depend on the state of the game; for instance it could be required that the color used be different from the color used on the previous move.

The map-based constraints on a move are usually based on the region to be colored and its neighbors, whereas in the map-coloring problem, regions are considered to be neighbors when they meet along a boundary longer than a single point. The classical map-coloring problem requires that no two neighboring regions be given the same color. The classical move constraint enforces this by prohibiting coloring a region with the same color as one of its neighbor. The anticlassical constraint prohibits coloring a region with a color that differs from the color of one of its neighbors.

Another kind of constraint is entailment, in which each move after the first must color a neighbor of the region colored on the previous move. Anti-entailment is another possible constraint.

Other sorts of constraints are possible, such as requiring regions that are neighbors of neighbors to use different or identical colors. This concept can be considered as applying to regions at graph distance two, and can be generalized to greater distances.

Winning conditions

The winner is usually the last player to move. This is called the normal play convention. The misère play convention considers the last player to move to lose the game. There are other possible winning and losing conditions possible, such as counting territory, as in Go.

Monochrome and variants

These games, which appeared in (Silverman, 1971), all use the classical move constraint. In the impartial game "Monochrome" there is only one color available, so every move removes the colored region and its neighbors from play. In "Bichrome" both players have a choice of two colors, subject to the classical condition. Both players choose from the same two colors, so the game is impartial. "Trichrome" extends this to three colors to the players. The condition can be extended to any fixed number of colors, yielding further games. As Silverman mentions, although the Four color theorem shows that any planar map can be colored with four colors, it does not apply to maps in which some of the colors have been filled in, so adding more than four colors may have an effect on the games.

Col and Snort

A game of Col

In "Col" there are two colors subject to the classical constraint, but Left is only allowed to color regions B"l"ue, while Right is only allowed to color them "R"ed. Thus this is a partisan game, because different moves become available to Left and Right in the course of play.

"Snort" uses a similar partisan assignment of two colors, but with the anticlassical constraint: neighboring regions are not allowed to be given different colors. Coloring the regions is explained as assigning fields to bulls and cows, where neighboring fields may not contain cattle of the opposite sex, lest they be distracted from their grazing.

These games were presented and analyzed in (Conway, 1976). The names are mnemonic for the difference in constraints (classical map coloring versus animal noises), but Conway also attributes them to his colleagues Colin Vout and Simon Norton.

Other games

The impartial game "Contact" (Silverman, 1971) uses a single color with the entailment constraint: all moves after the first color a neighbor of the most recently colored region. Silverman also provides an example of "Misère Contact".

The concept of a map-coloring game may be extended to cover games such as Angels and Devils, where the rules for coloring are somewhat different in flavor.

References

• Conway, John Horton (1976). On numbers and games. Academic Press. ISBN 0-12-186350-6.  Revised and reprinted as
• — (2000). On numbers and games. A K Peters. ISBN 1-56881-127-6. 
• Silverman, David L. (1971). Your Move. McGraw-Hill.  Revised and reprinted as
• — (1991). Your Move: logic, math and word puzzles for enthusiasts. Dover Press. ISBN 0-486-26731-8.