Tic Tac Toe a Arduino amb AI (algorisme Minimax): 3 passos

2024 Autora: John Day | [email protected]. Última modificació: 2024-01-30 08:15

En aquest instructiu us mostraré com construir un joc Tic Tac Toe amb una IA mitjançant un Arduino. Podeu jugar contra l'Arduino o veure com l'Arduino juga contra si mateix.

Estic fent servir un algorisme anomenat "algoritme minimax", que es pot utilitzar no només per construir una IA per a Tic Tac Toe, sinó també per a una varietat d'altres jocs com Quatre en fila, dames o fins i tot escacs. Jocs com els escacs són molt complexos i requereixen versions de l’algorisme molt més refinades. Per al nostre joc Tic Tac Toe, podem utilitzar la versió més senzilla de l'algorisme, que no obstant això és bastant impressionant. De fet, la IA és tan bona que és impossible guanyar l’Arduino.

El joc és fàcil de construir. Només necessiteu uns quants components i l’esbós que he escrit. També he afegit una explicació més detallada de l'algorisme, si voleu entendre com funciona.

Pas 1: Construeix i juga

Per construir el joc Tic Tac Toe necessitareu els components següents:

• Un Arduino Uno
• 9 LED RGB WS2812
• 9 polsadors
• alguns cables de cable i pont

Connecteu els components tal com es mostra a l'esbós de Fritzing. A continuació, pengeu el codi al vostre Arduino.

Per defecte, l’Arduino pren el primer torn. Per fer les coses una mica més interessants, es tria el primer moviment a l'atzar. Després del primer moviment, l'Arduino utilitza l'algorisme minimax per determinar el millor moviment possible. Comenceu un joc nou restablint l’Arduino.

Podeu veure com "Arduino" pensa obrint el monitor de sèrie. Per a cada moviment possible, l'algorisme calcula una qualificació que indica si aquest moviment comportarà una victòria (valor de 10) o una pèrdua (valor de -10) per a l'Arduino o un empat (valor de 0).

També podeu veure com Arduino juga contra si mateix descomentant la línia "#define DEMO_MODE" al principi de l'esbós. Si pengeu l’esbós modificat, l’Arduino fa el primer moviment a l’atzar i, a continuació, utilitza l’algorisme minimax per determinar el millor moviment per a cada jugador en cada torn.

Tingueu en compte que no podeu guanyar contra l'Arduino. Cada partit acabarà en empat o perdrà si comet un error. Això es deu al fet que l'algoritme sempre tria el millor moviment possible. Com sabreu, un joc de Tic Tac Toe sempre acabarà en empat si els dos jugadors no s’equivoquen. En mode de demostració, tots els jocs acaben en empat perquè, com tots sabem, els ordinadors mai no cometen errors;-)

Pas 2: l'algorisme Minimax

L’algorisme consta de dos components: una funció d’avaluació i una estratègia de cerca. La funció d'avaluació és una funció que assigna un valor numèric a les posicions del tauler. Si la posició és una posició final (és a dir, una posició en què ha guanyat el jugador blau o el jugador vermell o on cap dels dos no ha guanyat), la funció d'avaluació és molt senzilla: diguem que l'Arduino juga en blau i que el jugador humà juga en vermell.. Si la posició és una posició guanyadora per al blau, la funció assigna un valor de 10 a aquesta posició; si és una posició guanyadora per al vermell, la funció assigna un valor de -10 a la posició; i si la posició és un sorteig, la funció assigna un valor de 0.

Quan li toca el torn a l’Arduino, vol triar un moviment que maximitzi el valor de la funció d’avaluació, perquè maximitzar el valor significa que preferirà guanyar per empat (10 és més que 0) i diferir un empat per perdre (0 és superior a -10). Per un argument anàleg, l'oponent vol jugar de manera que minimitzi el valor de la funció d'avaluació.

Per a una posició no final, l'algorisme calcula el valor de la funció d'avaluació mitjançant una estratègia de cerca recursiva. A partir de la posició actual, simula alternativament tots els moviments que poden fer el jugador blau i el jugador vermell. Això es pot visualitzar com un arbre, com al diagrama. Quan arriba a una posició final, comença a retrocedir, portant el valor de la funció d’avaluació des del nivell de recursió inferior fins al nivell de recursió més alt. Assigna el màxim (si en el pas de recursió corresponent és el torn del jugador blau) o el mínim (si en el pas de recursió corresponent és el torn del jugador vermell) dels valors de la funció d’avaluació des del nivell de recursió inferior fins a la posició al nivell de recursió més alt. Finalment, quan l'algorisme ha acabat de retrocedir i ha arribat a la posició actual de nou, es necessita aquest moviment (o un dels moviments) que té el valor màxim de la funció d'avaluació.

Pot semblar una mica abstracte, però en realitat no és tan difícil. Penseu en la posició que es mostra a la part superior del diagrama. Al primer pas de recursió, hi ha tres moviments diferents que pot fer el blau. El blau intenta maximitzar el valor de la funció d'avaluació. Per a cadascun dels moviments que pot fer el blau, hi ha dos moviments que pot fer el vermell. El vermell intenta minimitzar el valor de la funció d'avaluació. Penseu en el moviment en què juga el blau a l'extrem superior dret. Si el vermell juga al quadre central, el vermell ha guanyat (-10). Si, en canvi, el vermell juga al quadre inferior central, el blau guanyarà en el següent moviment (10). Per tant, si el blau juga a la cantonada superior dreta, el vermell es jugarà al quadre central, ja que això minimitza el valor de la funció d’avaluació. De la mateixa manera, si el blau juga al quadre inferior central, el vermell tornarà a jugar al quadre central perquè això minimitza la funció d'avaluació. Si, en canvi, el blau juga al quadre central, no importa el moviment que faci el vermell, el blau sempre guanyarà (10). Com que el blau vol maximitzar la funció d'avaluació, es jugarà al quadre central, ja que aquesta posició dóna com a resultat un valor més gran de la funció d'avaluació (10) que els altres dos moviments (-10).

Pas 3: resolució de problemes i altres passos

Si premeu un botó i s’encén un LED diferent del que correspon al botó, és probable que tingueu els cables dels pins A0-A2 o 4-6 barrejats o bé connecteu els LED en un ordre equivocat.

Tingueu en compte també que l'algorisme no sempre tria un moviment que permetrà guanyar l'Arduino el més ràpid possible. De fet, vaig passar un temps depurant l'algoritme perquè l'Arduino no va triar cap moviment que hagués estat un moviment guanyador. Vaig passar un temps fins que em vaig adonar que, en canvi, havia triat una jugada que garantís que guanyaria una jugada més tard. Si voleu, podeu provar de modificar l'algoritme de manera que sempre preferirà una jugada guanyadora a una victòria posterior.

Una possible extensió d’aquest projecte seria utilitzar l’algorisme per construir una IA per a un 4x4 o fins i tot un Tic Tac Toe de 5x5. Tanmateix, tingueu en compte que el nombre de posicions que ha d’examinar l’algorisme creix molt ràpidament. Haureu de trobar maneres de fer la funció d’avaluació més intel·ligent associant valors a posicions que no siguin finals, segons la probabilitat que la posició sigui bona o dolenta per al jugador en qüestió. També podeu provar de fer la cerca més intel·ligent aturant la recursió aviat si un moviment resulta menys digne d’exploració que els moviments alternatius.

Arduino probablement no és la millor plataforma per a aquestes extensions a causa de la seva memòria limitada. La recursió permet que la pila creixi durant l'execució del programa i, si la pila creix massa, pot danyar la memòria del programa, provocant bloquejos o comportaments erràtics. Vaig triar l'Arduino per a aquest projecte principalment perquè volia veure si es podia fer i amb finalitats educatives, no perquè fos la millor opció per a aquest tipus de problemes.