Shannon cambia de juego

El juego de intercambio 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 las aristas de un grafo arbitrario . Un jugador tiene el objetivo de conectar dos vértices distintos mediante un camino de aristas de su color. El otro jugador busca impedirlo utilizando su color en su lugar (o, equivalentemente, borrando aristas). 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 desarrolla en un grafo finito con dos nodos especiales, A y B. Cada arista del grafo puede ser coloreada o eliminada. Los dos jugadores se llaman Short y Cut , y se turnan. En el turno de Cut, este elimina del grafo una arista sin color de su elección. En el turno de Short, este colorea cualquier arista que aún permanezca en el grafo. Si Cut logra transformar el grafo en uno donde A y B ya no estén conectados, gana. Si Short logra crear un camino coloreado de A a B , gana. El juego siempre termina después de un número finito de movimientos, y uno de los dos jugadores debe ganar. Tanto Short como Cut, o el jugador que mueve primero, tienen garantizada 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 reformular de manera que ambos jugadores tengan el mismo objetivo: asegurar un conjunto de aristas determinado 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 conjunto de corte, el conjunto mínimo de aristas que conectan dos subgrafos .

Se han descrito versiones del juego de conmutación de Shannon que se juegan en un grafo dirigido y en un matroide orientado 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 en octubre de 1958, se superponen dos cuadrículas de puntos de distinto color con un desfase. Un jugador une puntos adyacentes ortogonalmente en una cuadrícula, y el otro jugador usa 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 intercambio de Shannon jugado en una cuadrícula rectangular. No puede haber empate; el primer jugador siempre puede ganar con una jugada correcta.

Un juego de mesa comercial que implementaba este sistema fue comercializado en 1960 por Hassenfeld Brothers bajo el nombre de Bridg-It. ^{[ 7 ]} El juego consistía en un tablero de plástico con dos cuadrículas rectangulares intercaladas de 5x6 pedestales (un conjunto amarillo, el otro rojo), dos conjuntos de 20 puentes de plástico rojos y amarillos, y clavijas correspondientes para montarlos. Los jugadores se turnaban para colocar un puente sobre dos pedestales adyacentes del mismo color hasta que un jugador conectaba los dos lados opuestos del tablero marcados con su color. En las instrucciones se describe una variante del juego: cada jugador recibe un número limitado de puentes, por ejemplo, 10. Si ninguno de los jugadores ha ganado cuando se han colocado todos los puentes, un jugador, en su turno, puede reposicionar uno de sus puentes hasta que haya un ganador. El juego está fuera de producción desde hace mucho tiempo.

Una versión electrónica del Juego de la Tormenta está disponible en el Portal de Juegos de Ludii . Una versión interactiva de Bridg-It que muestra la estrategia ganadora de Rojo está disponible en GitHub .

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

El juego de conexión débilmente relacionado Hex se juega en una cuadrícula de hexágonos y tiene conectividad de 6. El Hex generalizado se juega en un grafo, al igual que el juego de Shannon, pero en lugar de colorear las aristas, en Hex los jugadores colorean los vértices. Estos juegos tienen estructuras y propiedades completamente diferentes.

Otro juego de conexión que se juega con papel y lápiz sobre una cuadrícula rectangular de puntos (o papel cuadriculado) es el juego infantil de " puntos y cuadrados ". 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 lo marca con sus iniciales. Una vez que se hayan completado todas las líneas, gana el jugador que haya completado más cuadrados.

Una extensión de Gale, llamada Qua, se juega entre tres jugadores en un tablero de juego cúbico tridimensional 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 cúbico. El diseño inicial del tablero de juego Qua Cube y sus reglas se describen en su entrada de Board Game Geek. ^{[ 8 ]}

En 1964 se encontró una solución explícita para el juego de conmutación no dirigido para cualquier juego de este tipo utilizando la teoría de matroides . Short debería apuntar a una posición en la que exista un conjunto de vértices.${\displaystyle S}$incluyendo los dos vértices distinguidos, así como dos subconjuntos disjuntos de los bordes restantes no elegidos soportados en${\displaystyle S}$, de tal manera que cualquiera de los dos subconjuntos (junto con los bordes ya elegidos) conectaría todos los vértices en${\displaystyle S}$. Si Short puede realizar 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 ]}

A diferencia de otros juegos de conexión, que pueden ser difíciles en PSPACE , ^{[ 10 ] [ 11 ]} los movimientos óptimos para el juego de conmutación no dirigido se pueden encontrar en tiempo polinomial por movimiento. Después de eliminar del grafo las aristas elegidas por Cut y contraer las aristas elegidas por Short , el grafo resultante es un menor del grafo 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 cuadrada.

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