Gioco di Shannon
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[modifica | modifica wikitesto]
Il 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[modifica | modifica wikitesto]
Il 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 | modifica wikitesto]
- ^ (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 | modifica wikitesto]
- (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 | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su Gioco di Shannon
Collegamenti esterni[modifica | modifica wikitesto]
- Graph Game, implementazione in Java del gioco di Shannon
