Juego de cambio de Shannon

El juego de conmutación 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", algún tiempo 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 utilizando su color en su lugar (o, equivalentemente, 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 fines de la década de 1950 y se conoce como Gale o Bridg-It . ^{[2] [3]}

El juego se desarrolla en un gráfico finito con dos nodos especiales, A y B . Cada borde del gráfico puede colorearse o eliminarse. Los dos jugadores se llaman Short y Cut , y se alternan movimientos. En el turno de Cut, Cut elimina del gráfico un borde no coloreado 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 donde A y B ya no estén conectados, Cut gana. Si Short logra crear un camino coloreado 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. Tanto Short, Cut o el jugador que mueve primero tienen garantizada la existencia de una estrategia ganadora en cualquier gráfico dado. ^[4]

Los juegos Short y Cut son una dualidad, es decir, el juego puede ser replanteado de modo que ambos jugadores tengan el mismo objetivo: asegurar un determinado conjunto de aristas con arista distinguida e . Short intenta asegurar el conjunto de aristas que con e forma un circuito , mientras que Cut intenta asegurar un conjunto de aristas que con e forma un cutset, el conjunto mínimo de aristas que conectan dos subgrafos .

Se han descrito versiones del juego de conmutación de Shannon que se juega en un gráfico dirigido y un matroide orientado con fines teóricos; ^{[5] [6]} pero no se han publicado juegos comerciales correspondientes.

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, se superponen dos cuadrículas de puntos de diferentes colores en un desfase. Un jugador une puntos adyacentes ortogonalmente en una cuadrícula y el otro jugador utiliza la otra. Un jugador intenta unir la parte superior de su cuadrícula con la inferior, mientras que el otro intenta unir 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 haber empate; el primer jugador siempre puede ganar si juega correctamente.

En 1960, Hassenfeld Brothers comercializó un juego de mesa que implementaba este esquema bajo el nombre de Bridg-It. ^[7] El juego consistía en un tablero de plástico con dos cuadrículas rectangulares de pedestales intercaladas de 5x6 (un conjunto amarillo, el otro rojo), dos conjuntos de 20 puentes de plástico rojos y amarillos cada uno, y clavijas a juego para montarlos. Los jugadores se alternan colocando 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 que resulte un ganador. El juego dejó de producirse hace tiempo.

Una implementación electrónica del Juego de Gale está disponible en el Portal de Juegos Ludii.

El juego de cambio de Shannon puede verse como un caso especial de un juego de Creador-Destructor , en el que los patrones ganadores para el Creador son caminos de conexión.

Hex es un juego de conexión débilmente relacionado que se juega en una cuadrícula de hexágonos y tiene conectividad 6. 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 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 casillas ". Los jugadores se turnan para dibujar una línea vertical u horizontal que conecte dos puntos adyacentes. Cuando una línea completa un cuadrado, el jugador escribe sus iniciales en el cuadrado. Una vez que se han completado todas las líneas, el jugador que ha tomado la mayor cantidad de casillas es el ganador.

Una extensión de Gale, llamada Qua, se juega con tres jugadores en un tablero de juego en forma de cubo 3D compuesto por una cuadrícula de N ³ celdas. N es un número impar igual al número de celdas a lo largo de los bordes del tablero de juego en forma de cubo. El diseño y las reglas iniciales del tablero de juego Qua Cube se describen en su entrada en Board Game Geek. ^[8]

En 1964 se encontró una solución explícita para el juego de cambio no dirigido para cualquier juego de este tipo que utilice la teoría de matroides . Short debería apuntar a una posición en la que exista un conjunto de vértices que incluya los dos vértices distinguidos, así como dos subconjuntos disjuntos de los bordes no elegidos restantes apoyados en , de modo que cualquiera de los dos subconjuntos (junto con los bordes ya elegidos) conecte todos los vértices en . 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] [9]}${\estilo de visualización S}$${\estilo de visualización S}$${\estilo de visualización S}$

A diferencia de otros juegos de conexión, que pueden ser difíciles para PSPACE , ^{[10] [11]} los movimientos óptimos para el juego de cambio no dirigido se pueden encontrar en tiempo polinomial por movimiento. Después de eliminar del gráfico los bordes elegidos por Cut y contraer los bordes elegidos por Short , el gráfico resultante es un menor del gráfico inicial. El problema de probar la existencia de dos árboles disjuntos, cada uno conectando los vértices distinguidos, se puede representar como un problema de partición de matroides , que se puede resolver en tiempo polinomial. Alternativamente, es posible resolver el mismo problema utilizando algoritmos de flujo de red .

• TwixT , un juego de conexión diferente y más difícil en la cuadrícula

Wikimedia Commons alberga una categoría multimedia sobre El cambio de juego de Shannon .

• Graph Game, una implementación en Java del juego de conmutación de Shannon