Juego de cambio de Shannon

De Wikipedia, la enciclopedia libre

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" antes de 1951.[1]​ Dos jugadores se turnan para colorear los bordes de un grafo 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[editar]

El jugador Cut tomó 3 turnos (bordes punteados), el jugador Short tomó 4 turnos (bordes verdes).

El juego se juega en un grafo finito con dos nodos especiales, A y B. Cada borde del grafo se puede colorear o eliminar. Los dos jugadores se llaman Short y Cut, y movimientos alternativos. En el turno de Cut, elimina del grafo un borde no coloreado de su elección. En el turno de Short, colorea cualquier borde que quede en el grafo. Si Cut logra convertir el grafo en uno en el que A y B ya no están conectados, gana. Si Short logra crear un camino coloreado de A a B, él gana. El juego siempre termina después de un número finito de movimientos y uno de los dos jugadores tiene que ganar. Ya sea Short, Cut o el jugador se mueve primero se garantiza la existencia de una estrategia ganadora en cualquier grafo dado.[4]​

Los juegos Short y Cut son una dualidad; es decir, el juego se puede replantear para 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[editar]

Las versiones del juego de cambio de Shannon que se juegan en un grafo dirigido y un matroide orientado se han descrito con fines teóricos;[5]​[6]​ pero no se han publicado juegos comerciales correspondientes.

Gale[editar]

Una victoria para el rojo en Gale.

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 la colocación de un puente sobre 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 ningún jugador ha ganado cuando se colocan todos los puentes, un jugador en su turno, puede reposicionar uno de sus puentes hasta un ganador resultados. El juego lleva mucho tiempo fuera de producción.

Una implementación electrónica de Gale está disponible en Ludii Games Portal.

Relación con otros juegos[editar]

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 grafo, 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 una estructura 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.

Una extensión de Gale para tres jugadores, llamada Qua, se juega en un cubo de tablero de juego 3D compuesto por una cuadrícula de N3 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 iniciales del tablero de juego Qua Cube se describen en su entrada en BoardGameGeek.[8]​

Complejidad computacional[editar]

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 de matroides. 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, 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 PSPACE-complejos,[9]​[10]​ los movimientos óptimos para el juego no dirigido 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.

Véase también[editar]

Referencias[editar]

  1. ↑ Gardner, M. (1961). The Second Scientific American Book of Mathematical Puzzles and Diversions. NY: Simon and Schuster. pp. 86–87. 
  2. ↑ a b Lehman, Alfred (1964). «A solution of the Shannon switching game». Journal of the Society for Industrial and Applied Mathematics 12 (4): 687-725. JSTOR 2946344. MR 0173250. doi:10.1137/0112059. 
  3. ↑ Hayward, Ryan B.; van Rijswijck, Jack (2006). «Hex and combinatorics». Discrete Mathematics 306 (19–20): 2515-2528. MR 2261917. doi:10.1016/j.disc.2006.01.029. 
  4. ↑ Chase, Stephen M. (1 de abril de 1972). «An implemented graph algorithm for winning Shannon Switching Games». Communications of the ACM 15 (4): 253-256. ISSN 0001-0782. doi:10.1145/361284.361293. Consultado el 10 de febrero de 2021. 
  5. ↑ Hamidoune, Yahya Ould; Las Vergnas, Michel (1 de junio de 1986). «Directed Switching Games on graphs and matroids». Journal of Combinatorial Theory, Series B (en inglés) 40 (3): 237-269. ISSN 0095-8956. doi:10.1016/0095-8956(86)90083-3. Consultado el 10 de febrero de 2021. 
  6. ↑ Cláudio, A. P.; Fonseca, S.; Sequeira, L.; Silva, I. P. (2015). «Shannon switching game and directed variants». En Bourguignon, J.-P.; Jeltsch, R.; Pinto, A.A. et al., eds. Dynamic, Games and Science: International Conference and Advanced School Planet Earth, DGS II, Portugal, August 28–September 6, 2013. CIM Series in Mathematical Sciences. Springer. pp. 187-199. ISBN 978-3-319-16117-4. doi:10.1007/978-3-319-16118-1_10. 
  7. ↑ «BRIDG-IT». BoardGameGeek (en inglés estadounidense). Consultado el 31 de enero de 2021. 
  8. ↑ «Qua». BoardGameGeek (en inglés estadounidense). Consultado el 28 de agosto de 2020. 
  9. ↑ Even, S.; Tarjan, R. E. (1 de octubre de 1976). «A Combinatorial Problem Which Is Complete in Polynomial Space». Journal of the ACM 23 (4): 710-719. ISSN 0004-5411. doi:10.1145/321978.321989. Consultado el 10 de febrero de 2021. 
  10. ↑ Reisch, Stefan (1 de junio de 1981). «Hex ist PSPACE-vollständig». Acta Informatica (en alemán) 15 (2): 167-191. ISSN 1432-0525. doi:10.1007/BF00288964. Consultado el 10 de febrero de 2021. 

Enlaces externos[editar]

Obtenido de «https://es.wikipedia.org/w/index.php?title=Juego_de_cambio_de_Shannon&oldid=159221882»