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

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

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]