Algoritmo mossa vincente e nuova rappresentazione

Nell'algoritmo della mossa vincente il computer gioca una partita di filetto (tris). Prima di ogni mossa verifica per ogni riga, colonna e diagonale la possibilità di vittoria per sé e per il suo avversario. Ciò vuol dire che prima di ogni mossa compie 8 controlli per cercare l'eventuale mossa vincente per sé (3 righe + 3 colonne + 2 diagonali) e altrettanti 8 controlli per stabilire se il proprio avversario può vincere la partita nella successiva mossa. Complessivamente l'algoritmo gira 16 volte in ogni turno con conseguente consumo di risorse del processore e rallentamento del processo decisionale.

Nuova rappresentazione

L'efficienza dell'algoritmo della mossa vincente può essere migliorato modificando la rappresentazione del problema. Ad esempio, introducendo un quadrato la cui somma orizzontale, verticale e diagonale dia sempre 15.

In questa nuova rappresentazione l'algoritmo limita il numero dei controlli (loop) alle coppie di simboli già scritti dai giocatori. Per ciascuna coppia di simboli viene sottratto da 15 la somma dei relativi numeri delle posizioni sul quadrato. Il risultato maggiore di zero e minore di dieci individua la "mossa vincente" se è vuota la posizione che completa l'allineamento tra le due posizioni. Ciò vuol dire che il computer non effettua alcun controllo al 1° turno del gioco, effettua 1 controllo per sé e uno per l'avversario al 2° turno del gioco, 3 controlli per sé e 3 per l'avversario al 3° turno di gioco, ecc.

In conclusione, questa variante dell'algoritmo consente di ridurre il numero dei controlli in tre turni di gioco da 48 (16x3) a 8. L'esempio dimostra l'importanza della rappresentazione quando si affronta un problema di intelligenza artificiale. Per il resto non risolve gran parte degli altri handicap dell'algoritmo della mossa vincente. In particolar modo l'algoritmo non è generalizzabile in quanto non può essere applicato per la soluzione di problemi simili (tris tridimensionale) a quello per cui è stato progettato (tris bidimensionale).