Una nuova rappresentazione dell'algoritmo della mossa vincente

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. Complessivamente l'algoritmo esegue 16 cicli in ogni turno con conseguente consumo di risorse del processore e rallentamento del processo decisionale.

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.

L'efficienza dell'algoritmo può essere migliorato modificando la rappresentazione del problema.

La nuova rappresentazione del problema

Nella rappresentazione alternativa del problema, si utilizza una matrice quadrata in cui la somma orizzontale, verticale e diagonale è sempre uguale a 15.

Esempio. Quando tutte le celle sono vuote, la somma della prima riga 8+3+4 è uguale a 15. La somma della prima colonna 8+1+6 è uguale a 15. E così via.

In ogni turno l'algoritmo sottrae da 15 la somma dei numeri in cui si trovano due coppie di simboli uguali.

Il risultato maggiore di zero e minore di dieci individua la "mossa vincente" ( o bloccante ), se è vuota la posizione che completa l'allineamento tra le due posizioni.

Esempio. Nella situazione precedente, la sottrazione 15-4-2 della terza colonna è uguale a 9. L'algoritmo trova una mossa vincente ( o bloccante se i simboli X sono dell'avversario ). Facendo riferimento alla tabella a sinistra, la prima X vale 4, mentre la seconda X vale 2.

In questa nuova rappresentazione l'algoritmo controlla soltanto le righe, colonne e diagonali con due simboli.

Quindi, riduce il numero dei controlli (loop) alle sole coppie di simboli già scritti dai giocatori.

Un esempio pratico

• 1° turno di gioco. Non effettua alcun controllo perché le celle sono tutte vuote.
  
• 2° turno di gioco. Effettua un solo controllo per sé e uno per l'avversario.
  
• 3° turno di gioco. Compie tre controlli per sé e tre per l'avversario. E così via.
  

Pro e contro della nuova rappresentazione

Vantaggi

Questa variante dell'algoritmo riduce il numero dei controlli rispetto alla versione originale dell'algoritmo.

Esempio. Al 3° turno di gioco l'algoritmo ha compiuto 2+6=8 controlli. Nell'algoritmo della mossa vincente, invece, sono necessari 48 controlli (16x3).

L'esempio dimostra l'importanza della rappresentazione quando si affronta un problema di intelligenza artificiale.

Svantaggi

La variante non risolve gli altri handicap dell'algoritmo della mossa vincente.

In particolar modo l'algoritmo non è generalizzabile.

Esempio. Non può essere usato per risolvere problemi simili (tris tridimensionale) a quello per cui è stato progettato (tris bidimensionale).