il Tris

Il Filetto 3x3 o Tic-Tac-Toe o, più semplicemente, Tris, è un gioco antichissimo, con numerose varianti, da giocare su un campo 3 per 3, con pedine di due colori o con carta e penna, con i simboli X e O.
Nella più variante semplice ciascuno dei due giocatori inserisce a turno una pedina del proprio colore sul tavolo di gioco, fino a formare un Tris o Filetto, ovvero una fila di tre pedine dello stesso colore, in orizzontale, in verticale o in diagonale: vince chi realizza per primo un tris; riempito il campo senza alcun tris, la partita è Pari.

Nella terminologia della teoria dei giochi, il filetto è un gioco a due persone, "finito" (cioè con un risultato determinato), senza elementi dovuti al caso e giocato con "informazione perfetta", in quanto tutte le mosse sono note ad entrambi i giocatori.

Il numero delle sequenze di mosse possibili sembra grandissimo, 362880 = 9! = 9x8x7x6x5x4x3x2x1, ma in realtà vi sono solo pochi schemi fondamentali e chiunque può diventare un giocatore imbattibile con venti minuti di analisi del gioco: si scopre ben presto che giocando "razionalmente", senza distrazioni, non ci sono mai vincitori e il gioco finisce sempre Pari.
Per trovare questo risultato il supercomputer di Wargame, il film di John Badham, impegna tutte le sue risorse e alla fine, saggiamente, abbandona il progetto di guerra totale che aveva avviato. Evidentemente gli autori del film non avevano mai visto un computer perché anche un Commodore 64 scopre in pochi minuti la parità del gioco, analizzando tutte le sequenze possibili; su un Athlon 2600 il tempo non è quantificabile !

X		O		O	O	X	O
	O		X			O
		O		O		O
Apertura d'Angolo		Apertura Centrale			Apertura Laterale

Strategia di Gioco

La sola possibilità di vincere è nel far cadere un avversario inesperto in una trappola che permetta di completare una fila alla mossa successiva in due modi, uno solo dei quali può essere bloccato. Per ciascuna delle tre possibili aperture, esiste una risposta che porti al pareggio e altre perdenti, ma, superata questa trappola, è difficile perdere:

apertura di X	contromossa di O
Angolo	occupare il centro
Centrale	occupare un angolo
Laterale	sulla riga o colonna della mossa

Struttura dati


	1	2	3	4	5	6	7	8	9

La tavola di gioco (una Matrice 3x3) viene allocata in un vettore di 9 elementi; ogni casella della Tavola vale 0 se vuota, 1 se occupata dal giocatore X, 2 se occupata dal giocatore O.

int Giocatori	0 : Umano - Umano; 1 : Computer - Umano 2 : Umano - Computer
int Who	giocatore che deve muovere: 1(primo) o 2
int Tavola[10]	scacchiera di gioco
int Nvuote	numero delle caselle vuote (cioè con valore 0)
int DoveGioco	mossa da fare da parte di Who
int QuantoVale	valore della mossa (vista da Who)

Algoritmo

La valutazione della mossa migliore in ogni fase del gioco viene affidata ad una funzione ricorsiva, che deve essere in grado di valutare la mossa perfetta. Una mossa vale 0 se porta alla parità, 1 o più se vincente, -1 o meno se perdente; la mossa vincente vale di più se fatta più presto.
La funzione ValutaMossa( ) esamina il campo di gioco e prova tutte le mosse legali (quelle nelle caselle vuote) in modo da cercare quella con punteggio più alto:

se la mossa crea un Tris, assegna un punteggio positivo, pari al numero di caselle vuote, in modo da far preferire la mossa che chiude prima il gioco vincendo o che ritarda la sconfitta;
viceversa se non vi sono altre caselle vuote, la partita è pari e assegna 0 alla mossa;
viceversa chiede la valutazione dell'avversario chiamando ricorsivamente la stessa funzione ValutaMossa(); il punteggio restituito (punto di vista dell'avversario) verrà cambiato di segno (metodo Neg-Max).

Codice Sorgente in C

Il programma sorgente è per Borland C/C++, ma può essere rapidamente adattato ad altri compilatori; è possibile scaricare l'eseguibile di 11 Kb.

Considerazioni finali

Il programma consente tre modalità di gioco:

F1 : Umano - Umano
F2 : Computer - Umano
F3 : Umano - Computer

Il giocatore inserisce le mosse con il tastierino numerico da 1 a 9 e, al suo turno, può chiedere aiuto con il tasto F5. In questo gioco non è possibile battere il Computer, ma solo pareggiare.