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]