Map-coloring games
Encyclopedia
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.
; 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.
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 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.
, 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.
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.
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
. 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
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
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 impartialImpartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
; otherwise the game is partisan
Partisan game
In combinatorial game theory, a game is partisan or partizan if it is not impartial. That is, some moves are available to one player and not to the other.Most games are partisan; for example, in chess, only one player can move the white pieces....
. 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 playMisère game
Misere or misère is a bid in various card games, and the player who bids misere undertakes to win no tricks or as few as possible, usually at no trump, in the round to be played...
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
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
.
Monochrome and variants
These games, which appeared in (Silverman, 1971), all use the classical move constraint. In the impartial gameImpartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
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
Impartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
. 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
Four color theorem
In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color...
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 gamePartisan game
In combinatorial game theory, a game is partisan or partizan if it is not impartial. That is, some moves are available to one player and not to the other.Most games are partisan; for example, in chess, only one player can move the white pieces....
, 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)
On Numbers and Games
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 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 gameImpartial game
In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric...
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
Angel problem
The angel problem is a question in game theory proposed by John Horton Conway. The game is commonly referred to as the Angels and Devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard...
, where the rules for coloring are somewhat different in flavor.