Se estudian varios juegos de colorear mapas en la teoría de juegos combinatorios . La idea general es que se nos da un mapa con las regiones dibujadas, pero no todas las regiones coloreadas. Dos jugadores, izquierda y derecha , se turnan para colorear en una región sin colorear por turno, sujeto a varias restricciones. Las restricciones de movimiento y la condición ganadora son características del juego en particular.
A algunos jugadores les resulta más fácil colorear los vértices del gráfico dual , como en el teorema de los cuatro colores . En este método de juego, las regiones están representadas por pequeños círculos y los círculos de las regiones vecinas están vinculados por segmentos de línea o curvas. Las ventajas de este método son que solo es necesario marcar un área pequeña en un 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 Go piedras o Damas .
Mover restricciones
Una restricción inherente en 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, el juego es partidista . El conjunto de colores también podría depender del estado del juego; por ejemplo, podría ser necesario que el color utilizado sea diferente del color utilizado en el movimiento anterior.
Las restricciones basadas en mapas en un movimiento generalmente se basan en la región que se va a colorear y sus vecinos, mientras que en el problema de colorear el mapa , las regiones se consideran vecinas cuando se encuentran a lo largo de un límite más largo que un solo punto. El problema clásico de colorear mapas requiere que no se asigne el mismo color a dos regiones vecinas. 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 uno de sus vecinos.
Otro tipo de restricción es la vinculación , en la que cada movimiento después del primero debe colorear a un vecino de la región coloreada en el movimiento anterior. La anti-vinculación es otra posible limitación.
Son posibles otros tipos de restricciones, como requerir que las regiones vecinas a las vecinas utilicen colores diferentes o idénticos. Se puede considerar que este concepto se aplica a regiones a una distancia de gráfico dos y se puede generalizar a distancias mayores.
Condiciones ganadoras
El ganador suele ser el último jugador en moverse. A esto se le llama la convención de juego normal . La convención de juego misère considera que el último jugador en moverse pierde el juego. Hay otras posibles condiciones para ganar y perder, como contar territorio, como en Go .
Monocromo y variantes
Todos 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 vecinos del juego. En Bichrome, ambos jugadores pueden elegir entre dos colores, sujeto 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 se puede extender 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 se puede colorear con cuatro colores, no se aplica a los mapas en los que se han rellenado algunos de los colores, por lo que agregar más de cuatro colores puede tener un efecto en el juegos.
Col y Snort
En Col hay dos colores sujeto a la restricción clásica, pero la izquierda sólo está permitido a las regiones de color B l ue, mientras que la derecha sólo se permite a los colores R ed. Por lo tanto, este es un juego partidista , porque diferentes movimientos están disponibles para Izquierda y Derecha en el transcurso del juego.
Snort usa una asignación partidista similar de dos colores, pero con la restricción anticlásica: las regiones vecinas no pueden recibir 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 que no se distraigan de su pastoreo.
Estos juegos fueron presentados y analizados en (Conway, 1976) . Los nombres son nemotécnicos para la diferencia en las restricciones ( colores de mapas clásicos versus ruidos de animales), pero Conway también los atribuye a sus colegas Colin Vout y Simon Norton.
Otros juegos
El juego imparcial Contact (Silverman, 1971) utiliza un solo color con la restricción de vinculación: todos los movimientos después del primer color, un vecino de la región coloreada más recientemente. Silverman también proporciona un ejemplo de Misère Contact .
El concepto de un juego de colorear mapas puede extenderse para cubrir juegos como Ángeles y Diablos , donde las reglas para colorear tienen un sabor algo diferente.
Referencias
- Conway, John Horton (1976). Sobre números y juegos . Prensa académica . ISBN 0-12-186350-6. Revisado y reimpreso como
- --- (2000). Sobre números y juegos . AK Peters . ISBN 1-56881-127-6.CS1 maint: nombres numéricos: lista de autores ( enlace )
- Silverman, David L. (1971). Tu movimiento . McGraw-Hill . Revisado y reimpreso como
- --- (1991). Your Move: acertijos de lógica, matemáticas y palabras para entusiastas . Prensa de Dover . ISBN 0-486-26731-8.CS1 maint: nombres numéricos: lista de autores ( enlace )