il Filetto

Chiamato anche Tris, Tria, Tela o Tavola Mulino, è un gioco antichissimo.
Ancor prima dei Romani, che lo chiamavano Triodo, veniva giocato in Asia Minore centinaia d'anni prima di Cristo. Tavolieri simili a quelli del moderno Filetto e anche più complessi, sono stati trovati, insieme ad altri giochi, in templi Egizi.

Si gioca in due (Bianco e Nero) con un campo di gioco sul quale sono disegnati 3 quadrati concentrici, collegati a metà di ogni lato da una linea retta.
Esistono numerose varianti del gioco: nella versione analizzata le pedine sono poste (alternativamente dai due giocatori) sulle intersezioni delle linee che formano i quadrati, cercando di realizzare un Tris o Filetto, ovvero una fila di tre pedine dello stesso colore, in orizzontale o in verticale; vince chi realizza per primo un tris (non si fa filetto se le pedine sono in fila, ma in diagonale)

Terminate le 12 pedine a testa senza alcun tris, la partita è Pari, ma, come vedremo, ciò non accade mai (se il primo giocatore gioca bene)

Strategia di Gioco

Per vincere occorre costruire una situazione tale da avere più di una possibilità di tris contemporaneamente, in modo che l'avversario non possa bloccarle.
Per scegliere la mossa migliore possiamo assegnare un punteggio ad ogni casella vuota, in base alla situazione delle pedine sulle due linee adiacenti, inserendo tutte le possibili combinazioni in una tabella: risulta più conveniente giocare in una casella che massimizza la somma dei due punteggi così calcolati

Come dimostrato dal programma, chi gioca per primo ha una strategia vincente; il gioco quindi NON è equo. La variante più diffusa del gioco utilizza solo nove pedine a testa, per poi spostarle sul campo da gioco fino a formare un tris; ad ogni tris formato si toglie una pedina all'avversario fino a ridurlo nell'impossibilità di giocare. In questo caso il programma dimostra che chi gioca per primo fa sicuramente il primo tris con le prime nove pedine (il seguito della partita ad un altro programma).

Struttura dati

int Tavola[24] La tavola di gioco ( 24 nodi) viene allocata in un vettore di interi; ogni casella vale 0 se vuota, 1 se occupata dal giocatore 1, 2 se occupata dal giocatore 2.
int Nvuote Numero delle caselle vuote a disposizione
int Who Giocatore che deve muovere: 1(primo) o 2(secondo)
int DoveGioco mossa da fare da parte di Who (casella da 0 a 23)
int QuantoVale valore della mossa da fare (vista da Who):
-1 = sconfitta, 0 = pareggio, +1 = vittoria
int Giocatori Giocatori selezionati: 
0 = Umano-Umano, 1 = Computer-Umano, 2 = Umano-Computer

Algoritmo

Il programma accetta le mosse da tastiera, oppure le sceglie tramite una funzione ricorsiva di Valutazione Esatta.
La funzione innanzi tutto elenca tutte le mosse possibili (le caselle vuote) assegnando a ciascuna un valore euristico (tramite la tabella PuntiMossa[ ])
L'elenco delle mosse viene ordinato in base al valore, e si comincia a provare ad una ad una tutte le mosse partendo da quella con punteggio maggiore.

  • Se la mossa è vincente, decreta la mossa come Mossa Migliore e interrompe la valutazione, assegnando +1 alla posizione attuale;

  • altrimenti, se non ci sono altre caselle libere, assegna 0 alla posizione attuale;

  • altrimenti, chiama ricorsivamente la funzione di valutazione sulla tavola creata con la mossa: il punteggio ottenuto (valutazione dell'avversario) verrà cambiato di segno (algoritmo Neg-Max). 

Il metodo usato per l'ordinamento delle mossa è irrilevante ai fini del tempo complessivo.

Per migliorare le prestazioni, a sei mosse dalla fine viene abbandonata la funzione ricorsiva, per utilizzare funzioni particolari:

  • sei caselle vuote: la routine elenca le caselle vuote, cercando una mossa vincente; se non la trova, prova ad una ad una tutte le mosse, chiamando la funzione di valutazione a 5 vuote, cui passa l'elenco delle caselle vuote.

  • cinque caselle vuote: la routine prova le 5 mosse, chiamando la funzione di valutazione a 4 vuote, cui passa l'elenco delle caselle vuote.

  • quattro caselle vuote: la routine prova le 4 mosse, chiamando la funzione di valutazione a 3 vuote, cui passa l'elenco delle caselle vuote.

  • tre caselle vuote: dapprima cerca, tra le mosse possibili, quella vincente; se non ne trova, riprova ogni mossa con le contromosse; se la mossa crea  una contromossa vincente per l'avversario, è considerata perdente; se l'avversario non ha la mossa vincente, non l'avrà dopo la mossa di Who.
    Who occupa la prima casella M1; la scacchiera cambia per Who che potrebbe ora avere una mossa vincente, se l'avversario non la blocca: la scacchiera è quindi vincente solo se si sono formate due mosse vincenti. Viceversa la mossa è pari. Se non trova la vittoria, Who riprova con M2 e M3.

Alfa-Beta

Il numero dei percorsi possibili nel Filetto è proporzionale a 24! = 1023 (circa); considerando che molti rami si interrompono per strada, il numero dei percorsi si riduce a "solo" 1013, ovvero alcuni mesi di calcolo sul mio PC.

Per ridurre i tempi di valutazione, diventa indispensabile l'adozione del taglio Alfa-Beta, che riduce drasticamente il numero dei rami di valutazione possibili ed è tanto più efficace quanto migliore è la valutazione euristica preliminare: il numero dei rami è diventato dell'ordine di 107, ovvero 30 secondi di calcolo al massimo.

Codice Sorgente in C

Per la codifica ho utilizzato il linguaggio C: il codice riportato è per Borland BC 3.1 su DOS, ma è facilmente adattabile ad un qualsiasi compilatore per altri S.O. (eliminare i riferimenti alla longword 0x046C del timer e le funzioni gotoxy()).
Potete scaricare direttamente l'eseguibile di solo 21 Kb.
L'interfaccia utente è davvero spartana, e non usa né mouse né tasti cursore: volendo può essere arricchita (o, meglio, rifatta) da qualche volenteroso programmatore.
Per ora, l'unico scopo del programma è di verificare la parità del gioco.

Considerazioni finali

Il programma consente tre modalità di gioco:

  • F1 : Umano - Umano

  • F2 : Computer - Umano

  • F3 : Umano - Computer

Il giocatore inserisce le mosse con le lettere dell'alfabeto da A a X (maiuscolo o minuscolo) e, al suo turno, può chiedere aiuto con il tasto F5.

Il programma è stato testato su un Athlon XP 2600 (2083 Mhz) e indica come vincente qualsiasi prima mossa in meno di 30 secondi.
Dopo le prime tre mosse la risposta del computer è praticamente istantanea e porta alla vittoria del primo giocatore in meno di 18 mosse.
Se il computer gioca per secondo, riconosce subito di essere perdente ma è pronto ad approfittare di un'eventuale distrazione dell'umano.
Provando il programma su altri computer (fino a un Pentium 133), si evince che l'unico parametro influente sul tempo di calcolo è la frequenza di clock del processore

Software didattico