Map-coloring games

Map-coloring games

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. 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.

Contents

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

In Col there are two colors subject to the classical constraint, but Left is only allowed to color regions bLue, while Right is only allowed to color them Red. 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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • On Numbers and Games — is a mathematics book by John Horton Conway. The book is a serious mathematics book, written by a pre eminent mathematician, and is directed at other mathematicians. The material is, however, developed in a most playful and unpretentious manner… …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Educational games in the Mario series — In the early 1990s, many educational games were released in the Mario series of video games, including Mario is Missing!, a geography based game for the PC, Macintosh, Super NES and NES, I Am a Teacher: Super Mario Sweater, a Famicom Disk System… …   Wikipedia

  • Disjunctive sum — The disjunctive sum of two games is a game in which the two games are played in parallel, with each player being allowed to move in just one of the games per turn. This is extended to disjunctive sums of any number of games by associativity,… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • OptimJ — Paradigm(s) object oriented Appeared in 2006 (2006) Designed by Ateji Influenced by Java Website …   Wikipedia

  • Col (game) — Col is a pencil and paper game, specifically a map coloring game, involving the shading of areas in a line drawing according to the rules of Graph coloring. With each move, the graph must remain proper (no two areas of the same colour may touch) …   Wikipedia

  • Nightfall (video game) — Nightfall Developer(s) Altor Systems Publisher(s) Altor Systems Platform(s) …   Wikipedia

  • Dodecahedron — Regular Dodecahedron (Click here for rotating model) Type Platonic solid Elements F = 12, E = 30 V = 20 (χ = 2) Faces by sides 12{5} …   Wikipedia

  • Bone (comics) — Infobox comic book title title = Bone caption = Cover of Bone: Out From Boneville schedule = format = Maxiseries limited =Y publisher = self published date = 1991 ndash; 2004 issues = 55 main char team = past current color = background:#ff9275… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”