Un algoritmo per… il Go!

Lo scopo di questo articolo è quello di presentare un algoritmo utile per giocare 1vs1 a Go. Non parleremo dunque dei metodi utilizzati dai calcolatori per trovare la mossa vincente data una posizione, ma ci “limiteremo” (se così si può dire!) a descrivere il gioco usando i diagrammi di flusso. Prima, però, occorre introdurre alcuni concetti basilari della teoria dei grafi, una branca della matematica molto utilizzata in informatica (e non solo).

Una premessa riguardante la teoria dei grafi

Chiamiamo grafo un insieme di punti (detti nodi) collegati da linee (dette archi). Lo studio dei grafi trova svariate applicazioni non solo in informatica (come già citato prima), ma anche in fisica, medicina, linguistica, logistica e teoria dei giochi (questo articolo ne è la prova).

Colorare un grafo significa associare un colore a ciascun nodo o arco (o ad entrambi). Nel caso del go, studieremo le 3-colorazioni sui nodi, ovvero le colorazioni sui nodi che fanno uso di una palette con 3 colori. (Siccome l’articolo riguarda il go, useremo il nero, il bianco e il marrone. La scelta del marrone è dovuta al colore che assume solitamente il nodo vuoto di un goban).

Se disegnassimo un grafo su un foglio e colorassimo ciascun nodo di nero, bianco o marrone, vedremmo da lontano una figura (il grafo appunto) pezzato con delle macchie monocromatiche. Chiamiamo gruppo ciascuna di queste macchie.

Un arco che collega un nodo colorato (ad es. nero) ad un nodo vuoto è una libertà per quel nodo. Chiamiamo libertà di un gruppo l’unione delle libertà di tutti i nodi del gruppo. Un gruppo senza libertà è detto morto mentre un gruppo con almeno una libertà è detto vivo.

Descrizione del gioco

Ora che abbiamo introdotto gli aspetti fondanti della teoria dei grafi applicata al go, possiamo descrivere tutti gli aspetti del gioco usando i grafi. In particolare, ci occuperemo di:

• Materiale di gioco
• Meccanica di gioco
• Meccanica della cattura
• Vincoli sulla legalità delle mosse
• Fine partita e calcolo del punteggio

Materiale di gioco

Il goban è un grafo con N² nodi disposti in modo da formare un quadrato con N nodi per lato. (Solitamente N = 19, per cui segue N² = 361). Gli archi del grafo sono le connessioni tra i nodi. Due nodi (i,j) e (k,l) del goban si dicono connessi se

|i-k|=1 oppure |j-l l=1

Le pietre del goban possono essere di due colori: nero oppure bianco. Posizionare una pietra equivale a colorare un nodo del goban. Le pietre posizionate all’interno del goban non possono essere spostate ma solo catturate (si veda più avanti per i dettagli).

Meccanica di gioco

All’inizio della partita tutti i nodi del goban sono senza colorazione. Il primo turno spetta al giocatore che ha il nero.

Ad ogni turno un giocatore (ad es. il nero) sceglie un nodo vuoto e lo colora con il suo colore. In alternativa, il giocatore può decidere di abbandonare la partita oppure di passare il turno. (I meccanismi di cattura e i vincoli sulla legalità delle mosse sono descritti nelle sezioni successive).

Meccanica della cattura

Se una mossa (ad es. del nero) è tale da uccidere un gruppo avversario, allora il gruppo avversario viene rimosso dal goban e le pietre che lo componevano si aggiungono ai prigionieri del giocatore che ha effettuato la mossa (in questo caso il nero).

Vincoli sulla legalità delle mosse

Nel go sono solamente due le regole che rendono una mossa illegale:

• Regola del Ko. Una stessa colorazione del goban non può ripresentarsi due volte all’interno della partita a meno che la ripetizione non sia dovuta ad un “passo”.

• Regola del suicidio. Un nodo vuoto connesso a pietre tutte bianche non può essere colorato di nero. (La stessa regola vale se si invertono i colori). Questa regola decade se le quattro pietre bianche vengono catturate a seguito del posizionamento della pietra nera nel nodo vuoto.

Fine partita e calcolo del punteggio

Se uno dei due giocatori abbandona o se entrambi i giocatori passano il turno, la partita termina e si procede con il calcolo del punteggio. Parleremo della matematica legata al calcolo del punteggio in un altro articolo sempre dedicato al go.

Descrizione di un algoritmo per giocare 1vs1 a go

Passiamo ora all’ ultima parte del nostro articolo, ovvero quella dedicata alla progettazione di un algoritmo per giocare 1vs1 a go.

L’algoritmo principale è chiamato main() e si compone di tre parti:

1. una prima parte dedicata al caricamento delle impostazioni (ad es. komi = 6.5) e alla creazione di un goban vuoto
2. una seconda parte ripetuta ciclicamente ogni volta che viene posata una pietra sul goban o uno dei due giocatori passa
3. una terza parte per la rimozione delle pietre morte dal goban e per il calcolo del punteggio.

Tra la prima e la seconda parte è inoltre presente una parte intermedia che permette di controllare se nei due turni precedenti è stato effettuato oppure no un doppio passo. (Se infatti entrambi i giocatori passano allora la partita termina e si passa al conteggio dei punti).

Esamineremo ora ciascuna parte più nel dettaglio.

Parte 1) (Programma GoSettings). Questa parte è la più semplice delle tre e non merita molte osservazioni. Può essere migliorata aggiungendo la possibilità di variare la dimensione del goban, di giocare con handicap (e in quel caso il komi diventa necessariamente zero), di modificare il komi o di scegliere tra regole cinesi e regole giapponesi per il calcolo del punteggio.

Parte 2) (Programma Mossa). In primis, viene controllato che la mossa, scelta dal giocatore che ha il turno sia legale. Questo controllo viene effettuato dal programma IsMossaIllegale(). Nel caso in cui la mossa scelta sia legale, il programma distingue due casi. Se il giocatore ha deciso di passare, questa informazione viene memorizzata in una variabile (Neropassa o Biancopassa, a seconda di chi muove). Se invece il giocatore ha scelto un nodo (i,j) del goban, il programma colora il nodo (i,j) con il colore che esegue la mossa e cattura i gruppi che nella nuova configurazione del goban risultano morti. (Questa ultima operazione viene effettuata dal programma Cattura). Infine viene incrementato il contatore del turno e si torna al controllo sul doppio passo.

Programma IsMossaIllegale). Nel go una mossa è illegale se è un ko oppure un suicidio. Il controllo sul ko viene effettuato dal programma Ko(). Dato che ogni colorazione del goban è memorizzata in una lista (detta ListaGoban), per scongiurare il ko basta controllare che ogni nuova colorazione non sia già presente in ListaGoban. Il controllo sul suicidio viene invece effettuato combinando il programma IsCattura() (che restituisce true se la mossa che si vuole effettuare provoca la cattura di un gruppo) e il programma Liberta(i,j) (che invece calcola le libertà del gruppo a cui appartiene una pietra posata in (i,j).

Parte 3) (Programma PostPartita). Dopo che entrambi i giocatori hanno passato, i gruppi morti vengono rimossi dal goban e si procede al calcolo del territorio per ciascuno giocatore. Infine, si calcolano i punteggi secondo le regole giapponesi o cinesi. Questa parte è la più complicata delle tre e merita certamente una trattazione a sè in uno dei prossimi articoli.

E ora…generalizziamo!

A pensarci bene, il gioco del go obbedisce a cinque regole:

• Il gioco avviene su una griglia o una scacchiera.
• All’inizio della partita la griglia di gioco (ovvero il goban) è vuoto.
• Tutti gli aspetti del gioco (meccanica dei turni, cattura, vincoli di legalità e punteggio) dipendono dalla colorazione dei nodi del grafo
• Ogni nodo della griglia di gioco può ospitare al massimo un colore (o simbolo)
• Un giocatore non può effettuare consecutivamente due turni

Un altro gioco che obbedisce alle cinque regole del go è il tris. Il fatto notevole è che tutti i giochi che rispettano le cinque regole possono essere analizzati con la teoria dei grafi in maniera del tutto simile a quanto visto con il go. Ad esempio:

Gioco: TRIS

Materiale di gioco: scacchiera/grafo 3×3. Tre caselle (i,j), (k,l) e (m,n) si dicono connesse se almeno una delle condizioni seguenti è vera:

• stanno tutte sulla stessa riga, ovvero i = k = m.
• stanno tutte sulla stessa colonna, ovvero j = l = n.
• stanno tutte sulla diagonale principale, ovvero (i = j = 1) e (k = l = 2) e (m = n = 3).
• stanno tutte sull’anti-diagonale principale, ovvero (i + j) = (k + l) = (m + n) = 4.

In questo caso la proprietà di connessione è definita su una terna di nodi anziché su una coppia. Il concetto di arco assume quindi un significato più astratto rispetto a quello del goban perché non può essere visualizzato come un “ponte” tra due nodi. (Dal punto di vista dell’algoritmo è sufficiente modificare da definizione di arco rendendola una proprietà su tre nodi anziché su due e tutto torna alla normalità. L’unico prezzo da pagare è la maggiore astrazione).

Meccanica dei turni. Ad ogni turno un giocatore disegna un cerchio o un triangolo su un nodo. (Notare che se al posto dei cerchi e dei triangoli usassimo il bianco e il nero la meccanica dei turni rimarrebbe la stessa).

Meccanica di cattura. Non presente (il che semplifica il gioco!)

Vincoli di legalità delle mosse. Non presenti

Fine partita. La partita termina quando uno dei due giocatori colora tre nodi connessi usando il suo colore. Il giocatore che raggiunge questo obiettivo è il vincitore della partita.

Punteggio. Non presente.

Per la descrizione degli altri giochi “simili al go” (ovvero tali da rispettare le 5 regole) e per tutti gli altri giochi rimanete sintonizzati con il nostro blog!