Il gioco di Shannon è un gioco di strategia astratto per due giocatori, inventato contemporaneamente e indipendentemente da Claude Shannon e David Gale; è infatti conosciuto anche come Gale, Bridg-It e Bird Cage.
Regole
modificaIl gioco si svolge su un grafo finito costituito da due nodi speciali, A e B. Ogni connessione del grafo può essere colorata o rimossa. I due giocatori si chiamano Short e Cut, e muovono alternatamente. Il giocatore Cut, durante il suo turno, può cancellare dal grafo una connessione a sua scelta, purché non sia già colorata. A questo punto il gioco passa in mano al giocatore Short, che durante il suo turno può colorare una qualsiasi connessione ancora presente sul grafo. Se Cut riesce a creare un grafo dove A e B non sono più connessi, vince. Se Short riesce a creare un percorso colorato da A a B, vince.
Ci sono anche versioni alternative di questo gioco, svolte su un grafo con connessioni direzionali e una matrice orientata. È stata trovata una soluzione di gioco per ognuna di queste varianti utilizzando la teoria delle matrice, diversamente ad altri giochi come Hex.
Algoritmi di vittoria
modificaIl gioco termina dopo un numero finito di mosse, e necessariamente uno dei due giocatori avrà la vittoria. A prescindere da quale giocatore inizi, questo avrà sempre garantita l'esistenza di una strategia di vittoria su ogni possibile grafo.[1]
Il gioco di Short e Cut sono un dualismo, ed in qualche maniera hanno lo stesso obiettivo: assicurarsi una determinata connessione tramite un'altra determinata connessione. Ad esempio: Short cerca di assicurarsi un gruppo di connessioni che formino un circuito, mentre Cut cerca di assicurarsi un gruppo di connessioni che creino un'interruzione; entrambi, composti del minor numero di connessioni possibile per connettere i due sottografi.[2]
Note
modifica- ^ (EN) Stephen M. Chase, An implemented graph algorithm for winning Shannon Switching Games, in Communications of the ACM, vol. 15, n. 4, 1972, pp. 253-256, DOI:10.1145/361284.361293.
- ^ Frederic Maire, The Solution of Shannon Game (archiviato), 2004
Bibliografia
modifica- (EN) Martin Gardner, Recreational Topology, in The Second Scientific American Book of Mathematical Puzzles and Diversions, 1987, pp. 78-88, ISBN 0-226-28253-8.
- (EN) Martin Gardner, Bridg-it and Other Games, in New Mathematical Diversions, 1995, pp. 210-218, ISBN 0-88385-517-8.
Altri progetti
modifica
Wikimedia Commons contiene immagini o altri file su Gioco di Shannon
Collegamenti esterni
modifica- Graph Game, implementazione in Java del gioco di Shannon
