Col (juego)
Col es un juego de lápiz y papel, específicamente un juego de colorear mapas, que implica el sombreado de áreas en un dibujo lineal de acuerdo con las reglas de coloración de grafos. Con cada movimiento, el gráfico debe permanecer correcto (no se pueden tocar dos áreas del mismo color), y un jugador que no puede realizar un movimiento legal pierde. El juego fue descrito y analizado por John Conway, quien lo atribuyó a Colin Vout, en On Numbers and Games.[1]
Juego de ejemplo editar
En el siguiente juego, el primero de los dos jugadores usa el color rojo y el segundo usa azul. El último movimiento en cada imagen se muestra más brillante que las otras áreas.
El gráfico inicial:
El primer jugador puede colorear cualquiera de las áreas para comenzar. Sin embargo, la región alrededor del exterior del gráfico no se incluye como área para este juego.
Después del primer movimiento:
El segundo jugador ahora colorea una celda blanca. Como actualmente no hay áreas azules, se permite cualquier celda blanca.
Dos movimientos en:
En este punto entra en vigor el requisito de que el gráfico sea el correcto, ya que se debe realizar una zona roja que no toque la existente:
Una vez que se colorea la tercera región:
Tenga en cuenta que las áreas solo cuentan como tocantes si comparten bordes, no si solo comparten vértices, por lo que este movimiento es legal.
El juego continúa, los jugadores se mueven alternativamente, hasta que un jugador no puede hacer un movimiento. Este jugador pierde. Una posible continuación del juego es la siguiente (con cada movimiento numerado para mayor claridad):
Juego terminado:
En este resultado, el jugador azul ha perdido.
Snort editar
Snort, inventado por Simon P. Norton, usa una asignación partisana 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.
Decidir el resultado en Snort es PSPACE completo en gráficos generales.[2] Esto se prueba reduciendo el nodo partisano de Kayles, que es PSPACE-completo, a un juego de Snort.
Análisis editar
El valor de una posición Col es siempre un número o un número más una estrella.[3] Esto hace que el juego sea relativamente simple en comparación con Snort, que presenta una variedad mucho mayor de valores.
Referencias editar
- ↑ On Numbers and Games: 1
- ↑ Demaine, Erik; Hearn, Robert (2001). «Playing Games with Algorithms: Algorithmic Combinatorial Game Theory». .
- ↑ Winning Ways for your Mathematical Plays: 2
Bibliografía editar
En inglés.
- Berlekamp, Elwyn R.; John H. Conway; Richard K. Guy (1982). Winning Ways for your Mathematical Plays. Academic Press. ISBN 978-0-12-091101-1.
- Berlekamp, Elwyn R. (2004) [2001]. Winning Ways for your Mathematical Plays (2nd edición). A K Peters Ltd. ISBN 978-1-56881-130-7.
- Conway, John Horton (1976). On Numbers and Games. Academic Press. ISBN 978-0-12-186350-0.
- Conway, John Horton (2000). On Numbers and Games. A K Peters Ltd. ISBN 978-1-56881-127-7.