Juegos de colorear mapas

En la teoría de juegos combinatorios se estudian varios juegos de coloración de mapas . La idea general es que se nos da un mapa con regiones dibujadas, pero no todas coloreadas. Dos jugadores, Izquierda y Derecha, se turnan para colorear una región sin colorear por turno, sujetos a diversas restricciones, como en el problema de coloración de mapas . Las restricciones de movimiento y la condición de victoria son características de este juego en particular.

Algunos jugadores encuentran más fácil colorear los vértices del grafo dual , como en el Teorema de los Cuatro Colores . En este método de juego, las regiones se representan con pequeños círculos, y los círculos de las regiones vecinas se unen mediante segmentos de línea o curvas. Las ventajas de este método son que solo se necesita marcar un área pequeña en cada turno, y que la representación suele ocupar menos espacio en el papel o la pantalla. La primera ventaja es menos importante cuando se juega con una interfaz de computadora en lugar de lápiz y papel. También es posible jugar con fichas de Go o Damas .

Una limitación inherente a cada juego es el conjunto de colores disponibles para los jugadores en las regiones de coloración. Si Izquierda y Derecha tienen los mismos colores disponibles, el juego es imparcial ; de lo contrario, es parcial . El conjunto de colores también puede depender del estado del juego; por ejemplo, podría ser necesario que el color utilizado sea diferente al del movimiento anterior.

Las restricciones basadas en mapas para un movimiento generalmente se basan en la región a colorear y sus vecinas, mientras que en el problema de coloración de mapas , las regiones se consideran vecinas cuando se encuentran a lo largo de un límite de más de un punto. El problema clásico de coloración de mapas requiere que no se asignen dos regiones vecinas del mismo color. La restricción de movimiento clásica impone esto al prohibir colorear una región con el mismo color que una de sus vecinas. La restricción anticlásica prohíbe colorear una región con un color que difiera del color de una de sus vecinas.

Otro tipo de restricción es la implicación lógica , en la que cada movimiento posterior al primero debe colorear un vecino de la región coloreada en el movimiento anterior. La antiimplicación lógica es otra posible restricción.

Son posibles otros tipos de restricciones, como exigir que las regiones vecinas utilicen colores diferentes o idénticos. Este concepto puede considerarse aplicable a regiones con una distancia de dos en el grafo, y puede generalizarse a distancias mayores.

El ganador suele ser el último jugador en mover. Esto se conoce como la convención de juego normal . La convención de juego misère considera que el último jugador en mover pierde la partida. Existen otras condiciones posibles para ganar o perder, como contar el territorio, como en el Go .

Estos juegos, que aparecieron en (Silverman, 1971), utilizan la restricción de movimiento clásica. En el juego imparcial "Monochrome" solo hay un color disponible, por lo que cada movimiento elimina la región coloreada y sus vecinas del juego. En "Bichrome", ambos jugadores pueden elegir entre dos colores, sujetos a la condición clásica. Ambos jugadores eligen entre los mismos dos colores, por lo que el juego es imparcial . "Trichrome" extiende esto a tres colores para los jugadores. La condición puede extenderse a cualquier número fijo de colores, dando lugar a más juegos. Como menciona Silverman, aunque el teorema de los cuatro colores muestra que cualquier mapa plano puede colorearse con cuatro colores, no se aplica a mapas en los que algunos de los colores ya han sido rellenados, por lo que añadir más de cuatro colores puede tener un efecto en los juegos.

En "Col" hay dos colores sujetos a la restricción clásica, pero a la izquierda solo se le permite colorear las regiones de azul, mientras que a la derecha solo se le permite colorearlas de rojo. Por lo tanto, este es un juego partidista , ya que a la izquierda y a la derecha se les ofrecen diferentes movimientos durante el transcurso del juego.

"Snort" utiliza una asignación partidista similar de dos colores, pero con la restricción anticlásica de que las regiones vecinas no pueden tener colores diferentes. La coloración de las regiones se explica como la asignación de campos a toros y vacas, donde los campos vecinos no pueden contener ganado del sexo opuesto, para evitar que se distraigan de su pastoreo.

Estos juegos fueron presentados y analizados en (Conway, 1976) . Los nombres son mnemotécnicos para la diferencia en las restricciones ( coloración clásica de mapas frente a ruidos de animales), pero Conway también se los atribuye a sus colegas Colin Vout y Simon Norton.

El juego imparcial "Contacto" (Silverman, 1971) utiliza un solo color con la restricción de implicación: todos los movimientos posteriores al primer color deben ser vecinos de la región coloreada más recientemente. Silverman también proporciona un ejemplo de " Contacto de Misère ".

El concepto de juego de colorear mapas puede extenderse a juegos como Ángeles y Demonios , donde las reglas para colorear tienen un toque algo diferente.

• Conway, John Horton (1976). Sobre los números y los juegos . Academic Press . ISBN 0-12-186350-6.Revisado y reimpreso como
• — (2000). Sobre números y juegos . AK Peters . ISBN 1-56881-127-6.
• Silverman, David L. (1971). Tu turno . McGraw-Hill .Revisado y reimpreso como
• — (1991). Tu turno: lógica, matemáticas y acertijos de palabras para aficionados . Dover Press . ISBN 0-486-26731-8.