Sfida a tris il braccio robotico!

Era il 10 febbraio 1996 quando in un’anonima saletta di Philadelphia il russo Garry Kasparov, campione del mondo di scacchi, stava sfidando un avversario molto particolare: Deep Blue. Non stiamo parlando di un essere umano, bensì di un calcolatore realizzato da IBM dall’incredibile potenza computazionale. Alla sua 37ª mossa Kasparov rinunciò e concesse la vittoria al computer che, per la prima volta nella storia, aveva battuto il campione del mondo.
In quell’occasione la macchina aveva bisogno di un mediatore, un uomo che doveva fornire all’algoritmo le mosse eseguite da Kasparov, leggere i risultati del calcolo e infine muovere fisicamente il pezzo indicato sulla scacchiera; inoltre, nonostante la prima sconfitta, il russo vinse tre incontri successivi e ne pareggiò due; fu comunque un’impresa straordinaria in un momento storico in cui Google non esisteva e il Wi-Fi non era ancora nato.
L’idea così affascinante di quella che il New York Times dell’epoca definì come «un’inattesa vittoria della macchina sull’uomo» è stata lo stimolo che ci ha spinti a creare questo progetto: un braccio robotico RoboArm che sfida l’uomo a Tris. Rispetto all’impresa di Deep Blue il coefficiente di difficoltà è, in questo caso, notevolmente inferiore: il tris, a differenza degli scacchi, ha un’infinità di combinazioni in meno. Abbiamo quindi approfittato di questo vantaggio rendendo il braccio robotico completamente invincibile, il peggior risultato che potrà ottenere è un pareggio e, al contempo, cercherà di vincere in tutti i casi in cui è possibile scegliendo la mossa migliore ad ogni azione. Inoltre, a differenza di Deep Blue, l’effetto “uomo contro macchina” è qui accentuato, infatti è proprio il robot a muoversi autonomamente per spostare le pedine e, al termine dello scontro, se richiesto, rimetterle a posto senza bisogno di mediatori.

Come funziona

Il campo da gioco, realizzato in plexiglass, è composto dal tipico schema del tris costituito da nove caselle disposte in un quadrato 3×3; ai lati troviamo le pedine (anch’esse in plexiglass) che riproducono “X” e “O” attribuite rispettivamente al robot e allo sfidante.
L’input da parte del giocatore avviene tramite un tastierino a matrice 4×3 in cui nove tasti riproducono il campo da gioco del tris in miniatura, a ciascun pulsante corrisponde una casella. Troviamo il pulsante “termina partita”, che, se premuto durante il proprio turno, comunica al robot che non si vuole più continuare; “nuova partita”, invece, può essere premuto al termine della sfida per iniziarne una nuova e infine con “riordina pedine” il robot si muoverà autonomamente recuperando dal campo le pedine utilizzate per rimetterle negli appositi spazi laterali. In Fig. 1 possiamo vedere un’immagine del tastierino con la copertura in plexiglass incisa a laser. Analizziamo ora una partita tipo.
Il robot sceglie casualmente chi dovrà effettuare la prima mossa; nel caso in cui sia lui il fortunato estratto, si muove autonomamente, prende la prima pedina a croce e la posiziona sul campo in base alla decisione dell’algoritmo. Attende quindi che il giocatore prema un pulsante sul tastierino e, quando questo avviene, recupera la pedina avversaria e la posiziona dove indicato. Nel caso in cui venga estratto il giocatore come primo, il robot attende semplicemente l’input. La partita continua fino alla vittoria del robot o a un pareggio; a quel punto attenderà che lo sfidante prema eventualmente il tasto “riordina pedine” e “nuova partita”.

Fig. 1

L’hardware

La descrizione completa del braccio robotico e della sua elettronica sono state presentate in questo post: “Roboarm” è realizzato in plexiglass (le parti sono tagliate a laser) e ha quattro gradi di libertà con la possibilità di montare una pinza (sia in verticale che in orizzontale) per afferrare oggetti. La mobilità è affidata a tre servo RC analogici con ingranaggi in metallo da 13kg*cm e due mini servo da 1,2 kg*cm; i primi permettono il movimento della base, della spalla e del gomito, mentre gli altri controllano la pinza (rotazione e apertura/chiusura).
Al posto della pinza è possibile installare un sistema “Pick and Place”, appositamente studiato per “Roboarm”, che consente di sollevare degli oggetti grazie alla sua ventosa e alla pompa a vuoto di cui è dotato.
Più nel dettaglio un’elettrovalvola a tre vie permette la commutazione tra pompa e sfiato in modo da poter controllare l’aspirazione e il rilascio tramite Arduino. Sostituendo la pinza con il sistema di aspirazione non utilizzeremo un servomotore poiché non è in questo caso necessario ruotare gli oggetti presi, possiamo evitare di controllare anche il servomotore del polso (che sarà però fisicamente presente in quanto parte integrante del polso stesso). Controlleremo quindi solo i tre servomotori da 13kg*cm.
Abbiamo utilizzato l’apposito shield (presentato nel numero 228) compatibile con Arduino/Fishino UNO che permette di gestire i servo e il sistema di Pick and place fornendo la corrente necessaria.
Poiché, come affermato in precedenza, utilizzeremo solo alcuni dei servomotori disponibili, nella Tabella 1 vediamo l’assegnazione dei componenti e degli output con i relativi pin Arduino (solo quelli usati in questo progetto).
Il dispositivo di input è una tastiera composta da 12 pulsanti collegati a matrice (4 righe x 3 colonne) con 7 pin. Nella Fig. 2 possiamo vedere lo schema generale del progetto.
Per connettere la tastiera ad Arduino tramite lo shield abbiamo sfruttato i pin dei servomotori non utilizzati e i pin di feedback facendo riferimento allo schema elettrico dello shield. Alcuni di questi sono analogici (utilizziamo da A1 ad A5), nel codice li abbiamo però dichiarati come digitali denominandoli rispettivamente da 15 a 19.

Fig. 2

Tabella 1

Programmazione

Prima di parlare dell’algoritmo vincente vero e proprio abbiamo la necessità di registrare le posizioni del robot nel campo da gioco in funzione degli angoli dei tre servomotori.
Nel complesso le posizioni saranno: le nove del tris, cinque laterali per le pedine “X” e cinque laterali per le pedine “O”. Ci sono vari modi per ottenere i tre angoli (le posizioni dei tre motori), in questo caso abbiamo pensato di sfruttare il tastierino già a disposizione e scrivere un codice che permette di controllare il robot tramite i pulsanti. In particolare le prime tre righe della tastiera (vista in verticale con il connettore verso il basso) controllano i tre servo; per ciascuna riga il primo pulsante aumenta l’angolo e l’ultimo lo diminuisce. Quando premiamo un pulsante il servo corrispondente si muove, tenendolo premuto continuerà il movimento.
Una volta portato il braccio nella posizione desiderata utilizziamo la quarta riga come debug: premendo ciascuno dei tre pulsanti mostreremo a monitor seriale l’ultima posizione data in input ai rispettivi tre servomotori. Utilizziamo questo procedimento per trovare tutte le diciannove posizioni che ci serviranno nel codice del tris vero e proprio.
Nel Listato 1 troviamo la funzione “tastierino” che, in base al pulsante premuto, stampa i valori degli angoli oppure chiama la funzione “movimento”.
I valori trovati saranno organizzati nel nuovo codice in array bidimensionali in cui le righe rappresentano le diverse posizioni e le colonne i valori degli angoli dei tre servomotori.
Ora dobbiamo scrivere il codice vero e proprio.
Per fare in modo che il robot vinca sempre abbiamo due possibilità: o utilizzare l’intelligenza artificiale e quindi “insegnargli” a giocare a tris, oppure scrivere tutte le possibili combinazioni di mosse manualmente. Noi abbiamo optato per la seconda.

Ad una prima occhiata sembra una pazzia, in effetti facendo qualche calcolo otteniamo che le combinazioni possibili in una partita sono ben 255.168! E quindi come abbiamo fatto a scriverle tutte?
In realtà quel numero enorme non tiene conto delle simmetrie nello schema del tris, inoltre, ci sono delle situazioni in cui la vittoria non è possibile per nessuna delle due parti e non è quindi necessario considerare l’evoluzione della partita. Con queste ipotesi le combinazioni si riducono notevolmente e possono essere scritte in un codice, ma come approfittiamo delle simmetrie? Tutte le mosse saranno divise in due macro gruppi: quando il robot parte per primo (e quindi “attacca”) e quando invece “difende”, ovvero è il giocatore a partire.
Il campo da gioco del tris è rappresentato nel codice da un array bidimensionale 3×3, in cui quando non ci sono pedine ciascuna casella vale 1, quando viene posizionata una pedina “X” la casella vale 3 e per la pedina “O” del giocatore il valore è 5. In questo modo possiamo tenere sotto controllo tutta la partita ed effettuare rapidi calcoli numerici per controllare, per esempio, se in una riga, colonna o diagonale qualcuno ha fatto tris.


In aggiunta all’array tabella della partita “reale” creiamo un altro array bidimensionale 3×3, ma che rappresenta un tris “fittizio” in cui tutte le situazioni sono riportate a uno dei casi base che abbiamo studiato. La prima mossa è decisiva (sia nel caso in cui inizi il robot, sia viceversa), è la prima pedina infatti a decretare il tipo di simmetria.
Facendo riferimento alla Fig. 3 (in cui possiamo vedere il procedimento algoritmico), abbiamo scritto i casi possibili solo quando la prima pedina viene messa in una delle tre posizioni evidenziate.
Quando questo non accade viene chiamata la funzione “Ruota()” il cui scopo è prendere il tris “reale” e ruotarlo di 0°, 90°, 180° o 270° in modo da portare la pedina in una delle tre posizioni base; nel Listato 2 vediamo come esempio le funzioni “Ruota90()”, “Ruota180()” e “Ruota270()” che vengono chiamate da “Ruota()” in base alla situazione e che creano effettivamente il tris fittizio (dichiarato come pos1[3][3]).

Su questo nuovo array bidimensionale lavorerà l’algoritmo che, dopo aver capito la mossa migliore da fare, tramite la funzione “Riruota()”, convertirà la posizione fittizia in una posizione sul tris reale in base alla rotazione di partenza. Ogni volta che verrà posizionata una nuova pedina, sarà applicata la stessa rotazione, verrà quindi calcolato l’output e infine riconvertito in una posizione reale. Oltre alle mosse valutate, come abbiamo già detto, ci sono dei casi in cui la partita non può essere vinta da nessuno dei due contendenti, in questa situazione la funzione “Random()” semplicemente posiziona la pedina in una casella libera.
Abbiamo notato che basta scrivere le possibilità per le prime tre mosse sia in attacco che in difesa, oltre la terza o il gioco termina perché qualcuno può chiudere un tris, oppure finisce in pareggio.
Ad ogni ciclo vengono chiamate le funzioni “chiudiMioTris()”, “chiudiSuoTris()”, “controllavittoria()” e “controllapareggio()”.
La funzione “chiudiMioTris()” è visibile nel Listato 3, in particolare possiamo vedere il controllo di righe, colonne e diagonali tramite cicli for in cui la condizione è numerica (poiché le pedine vengono considerate come numeri).
Potrebbe essere interessante spiegare la funzione “primaMossa()” che viene chiamata quando è il robot a dover scegliere dove posizionare la prima pedina. Abbiamo analizzato i vari casi e abbiamo concluso che la probabilità di vittoria è maggiore con la prima mossa al centro; mettendo invece la pedina negli angoli è leggermente inferiore; le rimanenti posizioni hanno una probabilità molto bassa di vittoria.
Abbiamo quindi strutturato la funzione in modo da estrarre dove posizionare la pedina tenendo conto delle varie probabilità sopra citate.
Per quanto riguarda la parte di codice che controlla il movimento del robot, abbiamo inizialmente utilizzato la libreria “Braccio.h” a disposizione, tuttavia questa creava dei problemi nel prendere e rilasciare la pedina. Andando ad analizzare il funzionamento della libreria troviamo un ciclo while in cui, ad ogni iterazione, per ciascun servomotore, viene incrementato/diminuito l’angolo, il ciclo termina quando tutti i servomotori sono arrivati in posizione.
Poiché nel nostro caso la ventosa deve arrivare a toccare il terreno, se usiamo questo codice c’è la possibilità che quando la punta sta toccando terra, la base deve terminare il movimento e quindi trascina per il campo la ventosa.
Per ovviare a questo problema abbiamo scritto una funzione interamente dedicata prendendo spunto dalla libreria stessa, ma che esegue i tre movimenti separatamente; nel caso in cui il robot stia prendendo la pedina, l’ultimo movimento che farà sarà la discesa della punta (quindi il controllo del servo gomito) mentre in caso di rilascio della pedina il primo movimento sarà alzare la punta.
La funzione “sistemaTutto()” permette di rimettere tutto a posto a lato del campo, nel Listato 4 possiamo vederne il contenuto.
Viene letto l’array bidimensionale che corrisponde al tris “reale” alla ricerca di pedine, quando ne viene trovata una inizia la sequenza di movimento, le variabili “numXprese” e “numOprese” tengono il conto di quante pedine ho già posizionato in modo da metterle in fila ai lati del campo.

Conclusioni

Con questo progetto abbiamo quindi convertito una sfida di programmazione (rendere un macchina invincibile a tris) in un qualcosa di pratico, grazie al braccio robotico e al sistema di pick and place. Possiamo effettivamente vedere delle azioni meccaniche e non solamente la restituzione di un risultato a schermo.
Un possibile miglioramento futuro potrebbe essere l’eliminazione del tastierino e l’implementazione di un sistema di rilevazione dell’input ancora più automatico magari con una telecamera; oppure semplicemente cambiare gioco e chissà se un giorno anche il nostro robot potrà competere con un campione del mondo di scacchi!

Download

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.

Menu