Tic Tac Toe su Arduino con AI (algoritmo Minimax): 3 passaggi

2024 Autore: John Day | [email protected]. Ultima modifica: 2024-01-30 10:04

In questo Instructable ti mostrerò come costruire un gioco Tic Tac Toe con un'intelligenza artificiale usando un Arduino. Puoi giocare contro l'Arduino o guardare l'Arduino giocare contro se stesso.

Sto usando un algoritmo chiamato "algoritmo minimox", che può essere utilizzato non solo per costruire un'intelligenza artificiale per Tic Tac Toe, ma anche per una varietà di altri giochi come Quattro di fila, dama o persino scacchi. Giochi come gli scacchi sono molto complessi e richiedono versioni molto più raffinate dell'algoritmo. Per il nostro gioco Tic Tac Toe, possiamo usare la versione più semplice dell'algoritmo, che è comunque piuttosto impressionante. In effetti, l'intelligenza artificiale è così buona che è impossibile battere Arduino!

Il gioco è facile da costruire. Hai solo bisogno di pochi componenti e lo schizzo che ho scritto. Ho anche aggiunto una spiegazione più dettagliata dell'algoritmo, se vuoi capire come funziona.

Passaggio 1: costruisci e gioca

Per costruire il gioco Tic Tac Toe avrai bisogno dei seguenti componenti:

• Un Arduino Uno
• 9 LED RGB WS2812
• 9 pulsanti
• alcuni fili e cavi jumper

Collega i componenti come mostrato nello schizzo di Fritzing. Quindi carica il codice sul tuo Arduino.

Per impostazione predefinita, Arduino fa il primo turno. Per rendere le cose un po' più interessanti, la prima mossa viene scelta casualmente. Dopo la prima mossa, Arduino utilizza l'algoritmo minimax per determinare la migliore mossa possibile. Inizi un nuovo gioco resettando Arduino.

Puoi guardare Arduino "pensare" aprendo il monitor seriale. Per ogni possibile mossa, l'algoritmo calcola un punteggio che indica se questa mossa porterà a una vittoria (valore 10) o una perdita (valore -10) per Arduino o un pareggio (valore 0).

Puoi anche guardare Arduino giocare contro se stesso decommentando la riga "#define DEMO_MODE" all'inizio dello sketch. Se carichi lo schizzo modificato, Arduino fa la prima mossa in modo casuale e poi usa l'algoritmo minimax per determinare la mossa migliore per ogni giocatore in ogni turno.

Nota che non puoi vincere contro Arduino. Ogni partita finirà con un pareggio o perderai, se commetti un errore. Questo perché l'algoritmo sceglie sempre la migliore mossa possibile. Come forse saprai, una partita di Tic Tac Toe finirà sempre in parità se entrambi i giocatori non commettono errori. In modalità demo ogni partita finisce in parità perché, come ben sappiamo, i computer non sbagliano mai;-)

Passaggio 2: l'algoritmo Minimax

L'algoritmo è costituito da due componenti: una funzione di valutazione e una strategia di ricerca. La funzione di valutazione è una funzione che assegna un valore numerico alle posizioni della scheda. Se la posizione è una posizione finale (cioè una posizione in cui ha vinto il giocatore blu o il giocatore rosso o in cui nessuno dei due giocatori ha vinto), la funzione di valutazione è molto semplice: diciamo che Arduino suona il blu e il giocatore umano gioca il rosso. Se la posizione è vincente per il blu, la funzione assegna un valore 10 a quella posizione; se è una posizione vincente per il rosso, la funzione assegna un valore di -10 alla posizione; e se la posizione è un pareggio, la funzione assegna un valore 0.

Quando è il turno di Arduino, vuole scegliere una mossa che massimizzi il valore della funzione di valutazione, perché massimizzare il valore significa che preferirà una vittoria al pareggio (10 è maggiore di 0) e preferirà un pareggio alla sconfitta (0 è maggiore di -10). Con un ragionamento analogo, l'avversario vuole giocare in modo tale da minimizzare il valore della funzione di valutazione.

Per una posizione non finale, l'algoritmo calcola il valore della funzione di valutazione mediante una strategia di ricerca ricorsiva. Partendo dalla posizione attuale, simula alternativamente tutte le mosse che possono eseguire il giocatore blu e il giocatore rosso. Questo può essere visualizzato come un albero, come nel diagramma. Quando arriva in una posizione finale, inizia a fare un passo indietro, portando il valore della funzione di valutazione dal livello di ricorsione inferiore al livello di ricorsione superiore. Assegna il massimo (se nella corrispondente fase di ricorsione è il turno del giocatore blu) o il minimo (se nella corrispondente fase di ricorsione è il turno del giocatore rosso) dei valori della funzione di valutazione dal livello di ricorsione inferiore alla posizione sul livello di ricorsione più elevato. Infine, quando l'algoritmo ha finito di fare un passo indietro ed è arrivato di nuovo alla posizione corrente, esegue quella mossa (o una delle mosse) che ha il valore massimo della funzione di valutazione.

Può sembrare un po' astratto, ma in realtà non è così difficile. Considera la posizione mostrata nella parte superiore del diagramma. Nella prima fase di ricorsione, ci sono tre diverse mosse che il blu può fare. Il blu cerca di massimizzare il valore della funzione di valutazione. Per ciascuna delle mosse che il blu può fare, ci sono due mosse che può fare il rosso. Il rosso cerca di minimizzare il valore della funzione di valutazione. Considera la mossa in cui il blu gioca nell'angolo in alto a destra. Se il rosso gioca nel riquadro centrale, il rosso ha vinto (-10). Se invece il rosso gioca nel riquadro in basso al centro, il blu vincerà nella mossa successiva (10). Quindi, se il blu viene riprodotto nell'angolo in alto a destra, il rosso giocherà nel riquadro centrale, poiché ciò riduce al minimo il valore della funzione di valutazione. Analogamente, se il blu gioca nel riquadro in basso al centro, il rosso giocherà di nuovo nel riquadro centrale perché ciò riduce al minimo la funzione di valutazione. Se invece il blu gioca nel riquadro centrale, non importa quale mossa fa il rosso, il blu vincerà sempre (10). Poiché il blu vuole massimizzare la funzione di valutazione, giocherà nella casella centrale, poiché quella posizione determina un valore maggiore della funzione di valutazione (10) rispetto alle altre due mosse (-10).

Passaggio 3: risoluzione dei problemi e ulteriori passaggi

Se si preme un pulsante e si accende un LED diverso da quello corrispondente al pulsante, probabilmente si sono scambiati i fili sui pin A0-A2 o 4-6 o si sono collegati i LED nell'ordine sbagliato.

Si noti inoltre che l'algoritmo non sceglie necessariamente sempre una mossa che consentirà all'Arduino di vincere il più velocemente possibile. In effetti, ho passato un po' di tempo a eseguire il debug dell'algoritmo perché Arduino non ha scelto una mossa che sarebbe stata una mossa vincente. Mi ci è voluto del tempo prima che mi rendessi conto che invece aveva scelto una mossa che garantiva che avrebbe vinto una mossa dopo. Se lo desideri, puoi provare a modificare l'algoritmo in modo che preferisca sempre una mossa vincente a una vittoria successiva.

Una possibile estensione di questo progetto sarebbe quella di utilizzare l'algoritmo per costruire un'intelligenza artificiale per un 4x4 o anche un 5x5 Tic Tac Toe. Tuttavia, si noti che il numero di posizioni che l'algoritmo deve esaminare cresce molto rapidamente. Dovrai trovare modi per rendere più intelligente la funzione di valutazione assegnando valori a posizioni non definitive, in base alla probabilità che la posizione sia buona o cattiva per il giocatore in questione. Potresti anche provare a rendere la ricerca più intelligente interrompendo la ricorsione in anticipo se una mossa risulta essere meno degna di ulteriori esplorazioni rispetto alle mosse alternative.

L'Arduino non è probabilmente la migliore piattaforma per tali estensioni a causa della sua memoria limitata. La ricorsione consente allo stack di crescere durante l'esecuzione del programma e, se lo stack cresce troppo, può danneggiare la memoria del programma, causando arresti anomali o comportamenti irregolari. Ho scelto Arduino per questo progetto principalmente perché volevo vedere se si poteva fare e per scopi didattici, non perché fosse la scelta migliore per questo tipo di problema.