El juego de cambio de Shannon es un juego de conexión para dos jugadores, inventado por el matemático e ingeniero eléctrico estadounidense Claude Shannon , el "padre de la teoría de la información" en algún momento antes de 1951. [1] Dos jugadores se turnan para colorear los bordes de un gráfico arbitrario . Un jugador tiene el objetivo de conectar dos vértices distinguidos por un camino de bordes de su color. El otro jugador tiene como objetivo evitar esto usando su color en su lugar (o, de manera equivalente, borrando los bordes). El juego se juega comúnmente en una cuadrícula rectangular ; Este caso especial del juego fue inventado independientemente por el matemático estadounidense David Gale.a finales de la década de 1950 y se conoce como Gale o Bridg-It . [2] [3]
Reglas
El juego se juega en una finita gráfico con dos nodos especiales, A y B . Cada borde del gráfico se puede colorear o eliminar. Los dos jugadores se llaman Short y Cut , y movimientos alternativos. En el turno de Cut, Cut elimina del gráfico un borde sin color de su elección. En el turno de Short, Short colorea cualquier borde que aún esté en el gráfico. Si Cut logra convertir el gráfico en uno en el que A y B ya no están conectados, Cut gana. Si Short logra crear una ruta de color de A a B , Short gana. El juego siempre termina después de un número finito de movimientos, y uno de los dos jugadores tiene que ganar. Se garantiza la existencia de una estrategia ganadora en cualquier gráfico, ya sea Short, Cut o el jugador que se mueve primero. [4]
Los juegos Short y Cut son una dualidad; es decir, el juego se puede replantear de modo que ambos jugadores tengan el mismo objetivo: asegurar una cierta ventaja con ventaja distinguida e . Short intenta asegurar el conjunto de bordes que con e forma un circuito , mientras que Cut intenta asegurar un conjunto de bordes que con e forma un conjunto de cortes, el conjunto mínimo de bordes que conectan dos subgrafos .
Variantes
Las versiones del juego de cambio de Shannon que se juegan en un gráfico dirigido y un matroide orientado se han descrito con fines teóricos; [5] [6] pero no se han publicado juegos comerciales correspondientes.
Vendaval
En este juego inventado por el matemático estadounidense David Gale y descrito en la columna de Martin Gardner en Scientific American de octubre de 1958, dos cuadrículas de puntos de diferentes colores se superponen en un desplazamiento. Un jugador enlaza puntos adyacentes ortogonalmente en una cuadrícula y el otro jugador usa la otra. Un jugador intenta vincular la parte superior de su cuadrícula con la parte inferior, mientras que el otro intenta vincular su lado izquierdo con el derecho. El juego es equivalente al juego de cambio de Shannon que se juega en una cuadrícula rectangular. No puede resultar ningún empate; el primer jugador siempre puede ganar con el juego correcto.
Un juego de mesa comercial que implementa el esquema fue comercializado en 1960 por Hassenfeld Brothers con el nombre de Bridg-It. [7] El juego consistía en un tablero de plástico con dos rejillas rectangulares de pedestales de 5x6 intercaladas (una amarilla y la otra roja), dos juegos de 20 puentes de plástico rojo y amarillo, y clavijas a juego para montarlos. Los jugadores alternan colocando un puente a través de dos pedestales adyacentes del mismo color hasta que un jugador conecta los dos lados opuestos del tablero marcados con el color del jugador. En las instrucciones se describe una variante del juego: cada jugador obtiene un número limitado de puentes, digamos 10. Si ninguno de los jugadores ha ganado cuando se colocan todos los puentes, un jugador en su turno, puede reposicionar uno de sus puentes hasta que haya un ganador. resultados. El juego lleva mucho tiempo fuera de producción.
Una implementación electrónica de Game of Gale está disponible en el portal de juegos Ludii .
Relación con otros juegos
El juego de cambio de Shannon puede verse como un caso especial de un juego Maker-Breaker , en el que los patrones ganadores del Maker son caminos de conexión.
Un juego de conexión débilmente relacionado, Hex, se juega en una cuadrícula de hexágonos y tiene 6 conectividad. Hex generalizado se juega en un gráfico, al igual que el juego de Shannon, pero en lugar de colorear los bordes, en Hex los jugadores colorean los vértices. Estos juegos tienen estructuras y propiedades completamente diferentes.
Otro juego de conectividad que se juega con papel y lápiz sobre una matriz rectangular de puntos (o papel cuadriculado) es el juego infantil de " puntos y cajas ". Los jugadores se alternan dibujando en una línea vertical u horizontal que conecta dos puntos adyacentes. Cuando una línea completa un cuadrado, el jugador pone sus iniciales en el cuadrado. Después de que se hayan completado todas las líneas, el jugador que haya tomado más cuadrados es el ganador.
Tres jugadores juegan una extensión de Gale, llamada Qua, en un cubo de tablero de juego en 3D compuesto por una cuadrícula de N 3 celdas. N es un número impar igual al número de celdas a lo largo de los bordes del cubo del tablero de juego. El diseño y las reglas del tablero de juego inicial de Qua Cube se describen en su entrada Board Game Geek. [8]
Complejidad computacional
En 1964 se encontró una solución explícita para el juego de conmutación no dirigida para cualquier juego de este tipo utilizando la teoría matroide . Short debe apuntar a una posición en la que existan dos subconjuntos disjuntos de los bordes no elegidos restantes, de modo que cualquiera de los dos subconjuntos conectaría los dos vértices distinguidos. Si Short puede hacer un movimiento que resulte en una posición con esta propiedad, entonces Short puede ganar independientemente de lo que haga el otro jugador; de lo contrario, Cut puede ganar. [2]
A diferencia de otros juegos de conexión, que pueden ser difíciles para PSPACE , [9] [10] los movimientos óptimos para el juego de conmutación no dirigida se pueden encontrar en el tiempo polinomial por movimiento. Después de eliminar del gráfico los bordes elegidos por Cortar y contraer los bordes elegidos por Corto , el gráfico resultante es una menor del gráfico inicial. El problema de probar la existencia de dos árboles disjuntos, cada uno conectando los vértices distinguidos, puede representarse como un problema de partición matroide , que puede resolverse en tiempo polinomial. Alternativamente, es posible resolver el mismo problema utilizando algoritmos de flujo de red .
Ver también
- TwixT , un juego de conexión diferente y más difícil en la cuadrícula cuadrada
Referencias
- ^ Gardner, M. (1961). El segundo libro de Scientific American de acertijos matemáticos y desviaciones . Nueva York: Simon y Schuster. págs. 86-87.
- ^ a b Lehman, Alfred (1964). "Una solución del juego de cambio de Shannon". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 12 (4): 687–725. doi : 10.1137 / 0112059 . JSTOR 2946344 . Señor 0173250 .
- ^ Hayward, Ryan B .; van Rijswijck, Jack (2006). "Hex y combinatoria". Matemáticas discretas . 306 (19-20): 2515-2528. doi : 10.1016 / j.disc.2006.01.029 . Señor 2261917 .
- ^ Stephen M. Chase (1972). "Un algoritmo gráfico implementado para ganar Shannon Switching Games". Comunicaciones de la ACM . 15 (4): 253-256. doi : 10.1145 / 361284.361293 . S2CID 21110956 .
- ^ Hamidoune, Yahya Ould; Las Vergnas, Michel (1986). "Conmutación dirigida en gráficos y matroids" . Revista de teoría combinatoria . Serie B. 40 (3): 237–239. doi : 10.1016 / 0095-8956 (86) 90083-3 .
- ^ Cláudio, AP; Fonseca, S .; Sequeira, L .; Silva, IP (2015). "Juego de cambio de Shannon y variantes dirigidas". En Bourguignon, J.-P .; Jeltsch, R .; Pinto, AA; Viana, M. (eds.). Dinámica, juegos y ciencia: Conferencia internacional y escuela avanzada Planet Earth, DGS II, Portugal, 28 de agosto a 6 de septiembre de 2013 . Serie CIM en Ciencias Matemáticas. Saltador. págs. 187–199. doi : 10.1007 / 978-3-319-16118-1_10 . ISBN 978-3-319-16117-4.
- ^ Bridg-it en BoardGameGeek
- ^ "Qua" . BoardGameGeek . Consultado el 28 de agosto de 2020 .
- ^ Even, S. (octubre de 1976). "Un problema combinatorio que está completo en el espacio polinomial" . Revista de la ACM . 23 (4): 710–719. doi : 10.1145 / 321978.321989 . S2CID 8845949 .
- ^ Reisch, Stefan (1981). "Hex ist PSPACE-vollständig". Acta Informatica . 15 (2): 167-191. doi : 10.1007 / BF00288964 . Señor 0599616 . S2CID 9125259 .
enlaces externos
- Graph Game , una implementación Java del juego de conmutación de Shannon