[python] Semplice esercizio su TensorFlow e il riconoscimento delle immagini nel gioco del Tris (Machine Learning)

Vogliamo realizzare un semplice programma in Python che sfrutti il riconoscimento delle immagini mediante TensorFlow e machine learning.

Il programma consentirà all’utente di pescare il risultato di una partita a Tris, da una cartella di immagini come la seguente:

Selezionando una partita il programma ci dirà chi ritiene che sia il vincitore e mostrerà lo schema della partita che ha dedotto a partire dall’immagine che gli abbiamo passato, nella maniera seguente:

1. Configurazione iniziale e librerie utilizzate

Per affrontare l’esercizio in questione abbiamo bisogno di alcune librerie. Il progetto verrà sviluppato in Python 3.7.

Possiamo installare le opportune librerie utilizzando PIP, nel caso specifico avremo bisogno delle seguenti installazioni:

Creiamo un file elaboratore.py nel quale svilupperemo l’intero programma. All’inizio inseriamo le seguenti istruzioni di importazione:

Faccio notare che la prima istruzione from __future__ import absolute_import, division, print_function, unicode_literals deve trovarsi all’inizio e non è una vera e propria importazione. Si tratta di una configurazione sul funzionamento di Python, che importa “funzionalità future” dal modulo fittizio __future__. E’ un modo per rendere disponibili, nella versione attuale, funzionalità previste in versioni successive, ma che ancora non sono state ufficialmente implementate.

Nel nostro caso specifico questa importazione non è essenziale (stiamo già lavorando in Python 3.7 e la funzione print non è più uno statement, bensì una funzione appunto, ecc), ma la possiamo lasciare per rendere compatibile il programma anche con versioni precedenti.

Detto questo procediamo allo sviluppo del necessario.

2. Dati iniziali

Per sviluppare il gioco utilizzeremo i seguenti set di dati (qui l’allegato da cui scaricarli):

  1. Set delle immagini per l’addestramento del modello, ricaveremo le immagini da un’unica grande immagine originale chiamata training.jpg (questa è un’immagine contenente 144 disegni, metà sono O e l’altra metà sono X, disegnate a mano sul computer, ciascun elemento è grande 100×100 px, per un totale di 1200×1200 px, ovvero 12 righe x 12 colonne)

  2. Piccolo set di immagini di test nel file test.jpg (solita dimensione 100×100 px per ciascuna immagine, per un totale di 4×4 = 16 elementi)
  3. Archivio con 10 partite giocate a Tris di cui conosciamo il risultato e vogliamo farlo riconoscere al computer

3. Struttura del programma

Vogliamo creare 3 classi che si occuperanno di diversi aspetti del programma:

  1. ElaboraImmagini – con questa classe elaboreremo le immagini di test, di addestramento e delle singole partite. In tutti e tre i casi si tratta di suddividere un’immagine originale in immagini più piccole; nei primi due casi, quello di test e addestramento, salveremo le immagini in una cartella da cui leggerle successivamente, mentre nel terzo caso, quello delle immagini che compongono una partita, salveremo il risultato in un vettore
  2. CreaDBImmagini – con questa classe vogliamo elaborare le immagini di test e di addestramento salvate nelle rispettive cartelle, ottenendo dei vettori contenenti le immagini medesime e un elenco di output (o etichette) associati a ciascuna immagine
  3. GiocoTris – la vera e propria classe che si occuperà dello sviluppo del gioco, preparando il modello di apprendimento, salvandolo e valutando il punteggio su ciascuna partita che verrà passata dal giocatore

Infine metteremo tutto in un semplice ciclo while che permetterà all’utente di scegliere un’immagine dall’elenco di quelle disponibili e farla analizzare.

4. Elaboriamo le immagini di addestramento e test

Creiamo una classe nella maniera seguente (nel codice ho inserito il commento sui singoli passaggi):

Il metodo ritaglia(s, coor, i) accetta coordinate in (x,y) sull’immagine, le x rappresentano le “colonne”, mentre le y rappresentano le “righe”, nella maniera seguente:

La prima immagine verrà ritagliata con coordinate (0, 0, 100, 100), la seconda con (100, 0, 200, 100) ecc.

Possiamo subito elaborare le immagini di addestramento e di test aggiungendo le seguenti due righe di codice:

5. Preleviamo le immagini di addestramento e test, associandoci gli opportuni output

Adesso vogliamo creare la classe che ci consentirà di prelevare le immagini, inserendole in un vettore, ed associare a ciascuna immagine nel vettore l’opportuno output.

Ogni immagine può rappresentare o una O oppure un X, a queste due “etichette” vogliamo associare un valore numerico, che nel mio caso sarà 0 per la O e 1 per la X.

Il comportamento che ci aspettiamo sarà il seguente: train_img, train_desc = CreaDBImmagini(...).get()

train_img conterrà i valori RGB per ciascuna immagine, in una lista di immagini così codificate. Ciascuna immagine è una griglia di pixel, per esempio un’immagine di 3×3 px diventerebbe una matrice di questo tipo [[1,2,3],[4,5,6],[7,8,9]]. I pixel in realtà non sono numerati in questo modo, ma ciascun pixel ha un valore RGB da 0 a 255, per ciascun colore. Quindi se il primo pixel fosse completamente nero al posto dell’1 avremmo [0,0,0], una lista con 3 zeri. Se fosse completamente bianco avremmo [255,255,255], se fosse rosso avremmo [255,0,0] ecc. Questo significa che l’immagine del nostro esempio avrebbe una rappresentazione tridimensionale 3x3x3 diventando così per esempio: [[[0,0,0],[0,0,0],[0,0,0]],[[0,0,0],[255,255,255],[0,0,0]],[[0,0,0],[0,0,0],[0,0,0]]]. In questo caso il pixel centrale, quello che abbiamo numerato come 5, sarebbe bianco e gli altri tutti neri. Se avessimo 100 di queste immagini, avremmo un oggetto di dimensione 100x3x3x3. Ovvero una lista di 100 elementi, di cui ciascun elemento è questa lista, di liste di liste, rappresentante la singola immagine.

train_desc è invece una semplice lista monodimensionale, se avessimo 100 immagini questa sarebbe una lista di 100 elementi. Ogni elemento descrive l’immagine, nel nostro caso se l’immagine corrispondente in train_img fosse una O allora avremo uno 0, nel caso di una X avremo un 1. Sarà quindi una lista tipo [0,1,1,0,0,....]. In questo esempio vorrebbe dire che le immagini in train_img rappresentano in ordine: O, X, X, O, O, ecc.

Tutti gli altri commenti sono nel codice:

6. Sviluppiamo la classe di gioco

A questo punto sviluppiamo la classe di gioco integrando le precedenti classi.

Anche su questo facciamo un paio di appunti. Quando calcoliamo le previsioni con previsione = s.__modello.predict(gioco) otteniamo una lista di liste di probabilità. Ogni sub-lista contiene tante probabilità quanti sono i neuroni (o nodi) impostati nell’ultimo layer del modello. Nel nostro caso all’istruzione keras.layers.Dense(2, activation='softmax') abbiamo impostato 2 neuroni, quindi il vettore di previsione conterrà un elenco di liste del tipo [p1, p2], dove p1 e p2 sono le probabilità dell’output 0 e dell’output 1 (che ricordiamoci corrispondono a O e a X, rispettivamente). Il risultato di previsione sarà qualcosa del tipo [[1. 0.],[0.51 0.49], [0. 1.]]. Nel caso specifico vorrebbe dire che secondo il ML la prima immagina è una O, poi uno spazio vuoto, poi una X. Per quanto riguarda l’uso di softmax e relu fare riferimento a questa pagina.

Per i dettagli sull’optimizer Adam fare riferimento a questa pagina.

Il calcolo della griglia di vittoria è molto semplice, perché abbiamo un vettore lineare e non una matrice (o griglia vera e propria). In questo caso una partita come quella del gioco_1.jpg sarà rappresentata da una lista di 0, 1 e 2, in questo modo (dove 0 = vuoto, 1 = O, 2 = X): [2, 2, 1, 2, 1, 0, 2, 1, 1]

Quando il primo valore è diverso da 0, quindi da vuoto, basta controllare che a distanza di 3 siano uguali, come qui: [2, 2, 1, 2, 1, 0, 2, 1, 1]

In questo modo stiamo controllando le colonne.

Per controllare le righe basta verificare le triplette, così: [2, 2, 1, 2, 1, 0, 2, 1, 1]

7. Chiudiamo il programma

Infine costruiamo il ciclo while per poter far usare il programma:

Per completezza riporto di seguito l’intero codice di programmazione:

 

Vedi articolo

[python] Esercizio su funzioni ricorsive e calcolo tratte dei treni

Facciamo un piccolo programma in Python che ci permetta di gestire le distanze da percorrere tra due stazioni, di partenza ed arrivo.

Abbiamo le seguenti tratte:

Stazione A Stazione B Distanza
Firenze Bologna 100km
Firenze Roma 250km
Roma Napoli 200km
Bologna Milano 220km
Bologna Venezia 150km

Ogni tratta è percorribile sia in andata che in ritorno. Quello che vogliamo è che il programma ci permetta di inserire due città e calcolare la distanza minima da percorrere e le stazioni da attraversare.

Anzitutto vediamo come sono disposti i nodi dell’intero percorso:

Notiamo che in questa configurazione elementare solo Bologna ha 3 rami, mentre tutte le altre città hanno solo 2 rami ciascuna.

Potremmo affrontare l’esercizio lavorando sui nodi oppure sulle tratte. In questa soluzione lavorerò sulle tratte.

Cominciamo quindi creando anzitutto una classe che ci permetta di descrivere ogni tratta come abbiamo visto nel mandato dell’esercizio.

In questo modo dichiariamo 3 variabili private per registrare le due città della tratta e la rispettiva distanza.

Adesso registriamo tutte le tratte in una lista, nel modo seguente:

Ora cominciamo a pensare all’algoritmo che potrebbe permetterci di calcolare il percorso.

Immaginiamo anzitutto la soluzione più semplice, dove io penso di andare da Firenze a Napoli. Su questa tratta non ci sono diramazione e sostanzialmente il percorso che dovrà venire fuori sarà Firenze – Roma – Napoli.

Fase 1:

Faccio un ciclo su ogni elemento della lista tratte[] e cerco anzitutto dove è presente la città di partenza. Siccome la città può essere sia in A che in B, per ogni oggetto Tratta dovrò implementare un metodo all’interno dell’oggetto stesso che mi permetta di valutare se la città sia presente in modo comodo. Implementiamo quindi la classe nel modo seguente:

Il metodo presente(citta) mi permette di valutare se la città sia presente nella tratta.

Fase 2:

Se trovo la città di partenza su una tratta allora controllo se l’altra città della tratta sia quella di arrivo. Allo stesso tempo registro la città di partenza all’interno di una lista percorso[] in modo da metterla come partenza del percorso complessivo.

Quindi se l’altra città è quella di arrivo posso chiudere il percorso, altrimenti passo il controllo sull’altra città.

Quando mi trovo nella riga 10 capisco anche che ho trovato la fine del percorso, quindi posso salvare l’intero percorso da qualche parte. Siccome potrei avere molteplici percorsi possibili decido di salvare il percorso in una lista globale chiamata percorsi = []

Modifichiamo quindi il codice nel modo seguente:

Adesso analizziamo due aspetti dell’ultima istruzione, quella dove richiamo la funzione.

Anzitutto voglio tirare fuori dalla tratta l’altra città, rispetto alla città di partenza. Per farlo implemento la classe principale nel modo seguente:

In questo modo quando mi trovo per esempio sulla tratta Firenze – Roma posso passare all’oggetto tratta Firenze, che conosco essendo il punto di partenza e chiedergli di darmi l’altra città della tratta, in questo caso Roma.

Il secondo aspetto che voglio evidenziare è che passo la lista percorso[] alla funzione medesima in partenza dall’altra città, per farlo utilizzo l’istruzione []+percorso, in caso contrario percorso passerebbe per riferimento e qualora fosse passato su più rami verrebbe elaborato contemporaneamente da più rami. Io invece voglio che resti un oggetto singolo e lineare per ogni percorso.

Arrivati a questo punto del codice la situazione è la seguente:

  1. Prendo in input partenza DA = Firenze e A = Napoli
  2. Aggiungo DA (Firenze) al percorso[]
  3. Passo a setaccio la lista delle tratte[]
  4. In posizione 0 trovo la tratta Firenze – Bologna a cui DA appartiene
  5. Controllo se A (Napoli) appartiene alla tratta
  6. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Bologna e la passo come nuovo DA alla funzione medesima
  7. La funzione ricomincia e aggiungendo DA (Bologna) al percorso[]
  8. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  9. Trovo che DA nella posizione 0 sulla tratta Firenze – Bologna
  10. LOOP INFINITO!

Fase 3:

Devo evitare il loop infinito in cui il percorso possa tornare indietro. Per farlo modifico la mia funzione aggiungendo il seguente controllo all’inizio:

In questo modo controllo che il punto di partenza DA non sia già presente nel percorso[].

Adesso ricomincio a controllare il mio algoritmo da capo:

  1. Prendo in input partenza DA = Firenze e A = Napoli
  2. Aggiungo DA (Firenze) al percorso[]
  3. Passo a setaccio la lista delle tratte[]
  4. In posizione 0 trovo la tratta Firenze – Bologna a cui DA appartiene
  5. Controllo se A (Napoli) appartiene alla tratta
  6. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Bologna e la passo come nuovo DA alla funzione medesima
  7. La funzione ricomincia e aggiungendo DA (Bologna) al percorso[]
  8. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  9. Trovo che DA nella posizione 0 sulla tratta Firenze – Bologna
  10. L’altra città (Firenze) è uguale ad A? No, quindi ripasso l’altra città come nuovo DA alla funzione medesima
  11. La funzione si interrompe, perché DA (Firenze) è già presente in percorso[]
  12. Torno al punto 9
  13. In posizione 3 trovo Bologna – Milano dentro tratte[] dove appartiene il mio DA
  14. Questo pezzo di codice adesso si ripete uguale a quello tra 10 e 12 fino a chiudersi su Milano e Venezia che terminano il percorso
  15. Trono al punto 3
  16. In posizione 1 trovo la tratta Firenze – Roma a cui DA (Firenze) appartiene
  17. Controllo se A (Napoli) appartiene alla tratta
  18. Dal momento che non appartiene, prendo l’altra città della tratta, ovvero Roma e la passo come nuovo DA alla funzione medesima
  19. La funzione ricomincia e aggiungendo DA (Roma) al percorso[]
  20. Scorro la lista delle tratte[] in cerca di DA (Bologna)
  21. Trovo che DA nella posizione 1 sulla tratta Firenze – Roma
  22. L’altra città (Firenze) è uguale ad A? No, quindi ripasso l’altra città come nuovo DA alla funzione medesima
  23. La funzione si interrompe, perché DA (Firenze) è già presente in percorso[]
  24. Torno al punto 20
  25. Trovo che DA nella posizione 2 sulla tratta Roma – Napoli
  26. Controllo se A (Napoli) appartiene alla tratta
  27. Napoli appartiene alla tratta nel pezzo di codice if t.presente(a)
  28. A questo punto aggiungo A (Napoli) alla fine di percorso[]
  29. Aggiungo il percorso[] ai percorsi[] con l’istruzione percorsi.append(percorso)

Fase 4:

Apporto ancora un paio di correzioni tecniche alla mia funzione per evitare inutili duplicati.

A questo punto posso scrivere la parte principale del mio programma con:

Per stampare il percorso faccio una join su ogni percorso che trovo dentro a percorsi[]

Fase 5:

Aggiungo soltanto un metodo per calcolare le distanze. Potrei farlo anche in modi più ottimizzato, ma per le finalità di questo esercizio ci accontentiamo di percorrere tutte le stazioni, esclusa l’ultima, e di calcolare la distanza tra la stazione corrente e la successiva sommandole tutte insieme.

A tale proposito aggiunto un metodo che mi permetta di valutare se 2 città appartengono entrambe alla tratta ed un getter per la distanza.

La funzione quindi sarà:

Fatto tutto questo posso completare il mio programma nella sua versione finale nel modo seguente:

Se volessimo complicare un po’ lo schema potremmo aggiungere altre tratte:

Ed ottenere una versione finale del programma in questo modo:

Il nostro nuovo programma genererà un output come questo:

Vedi articolo