Gioco di Shannon

Da Wikipedia, l'enciclopedia libera.

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]

  1. ^ (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.
  2. ^ Frederic Maire, The Solution of Shannon Game [collegamento interrotto], 2004

Bibliografia[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  • Graph Game, implementazione in Java del gioco di Shannon