Juego de cambio de Shannon , 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]​

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.

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.

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.

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 N³ 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]​

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.

• TwixT

• Wikimedia Commons alberga una categoría multimedia sobre Juego de cambio de Shannon.
• Graph Game, implementación del juego en Java