AI: Programmare il computer perchè imapri.
Puo' una macchina imparare? E quindi fare prova d'intelligenza? Cosa significa esattamente tutto cio'? Queste sono alcune delle domande fondamentali dell'intelligenza artificiale. Ok, ma cos'è l'intelligenza artificiale? Beh, se iniziamo così, non finiremo mai :-)
Bene, volete proprio delle definizioni!? Allora, veloce, veloce:
- intelligenza artificiale = intelligenza + artificiale (?!)
- Intelligenza: troppo complicato... Nei vocabolari si trova che è la facoltà di adattarsi per sopravivere e migliorarsi (cioè sopravivere sempre meglio ;-). Questa definizione non mi piace :< (adesso non vi spiego xche).
- artificiale = non umano, in un primo tempo per noi = computer (ma ci sono tante altre possibilità...)
Eccovi serviti. Andiamo avanti.
Un esempio stupido del metodo "brute force".
Facciamo un esempio semplice, semplice, anzi addirittura stupido. Consideriamo questo (stupido) gioco ("Gioco del 4"):
- ci sono 4 caselle, numerotate da 1 a 4
- a suo turno, ogni giocatore riempie una casella libera col proprio simbolo
- vince chi ha contrassegnato due caselle adiacenti.
Un esempio di partita:
In questo caso ha vinto Human.
Analisi: Dopo un attimo di riflessione ci rendiamo conto che:
- chi gioca per primo, puo' sempre vincere
- per questo basta segnare una casella che non sia ai bordi (cioè che non sia nè 1 nè 4)
- chi gioca per secondo puo' al più pareggiare (se il primo giocatore sbaglia la prima mossa) o vincere (se il primo giocatore sbaglia sia la prima mossa che la seconda, come nell'esempio precedente).
Il primo giocatore ha 4 possibilità per la prima mossa (1,2,3,4).
Fatta la prima mossa, rimangono 3 caselle libere. Quindi per ogni prima mossa del primo giocatore, ci sono 3 possibilità per la prima mossa del secondo giocatore. Quindi 4x3=12 possibilità per la prima mossa (del primo e del secondo giocatore).
Quando sia il primo che il secondo giocatore hanno fatto la prima mossa, rimangono 2 caselle libere. Quindi per ognuna delle 12 possibilità della prima mossa "completa" (= del primo e del secondo giocatore), il primo giocatore ha 2 possibilità. Quindi 12x2=24 possibilità fino alla seconda mossa del primo giocatore.
Quando il primo giocatore ha giocato la sua seconda mossa, il gioco è finito. Infatti, a questo punto sono segnate 3 caselle, ne rimane una libera e il secondo giocatore deve per forza scegliere quella.
Morale della favola, in tutto e per tutto, ci sono
24 (=4x3x2x1) partite possibili.
NB: In matematichese il numero 1x2x3x4 = 24, si indica 4! (e si dice:
fattoriale 4).
Chiaramente per simmetria ci sono in effetti solo 12 possibilità. Per simmetria si intende che la prima giocata 1 (risp.2) è simmetrica a 4 (risp.3). Quindi se decidiamo, arbitrariamente che la prima mossa non puo' essere che 1 o 2, riduciamo le possibilità della metà.
Il problema (fare giocare Comp).
Ok, fin qui ci siamo. Adesso vogliamo programmare Comp (il computer) come primo giocatore (quindi come potenziale vincitore). Niente di più facile mi direte, basta dirgli:
- come prima mossa, segna 2 (o 3)
- come seconda mossa, segna la casella libera vicina a 2 (risp.3), cioè 3 se la prima mossa dell'avversario era 1, invece 1 se la prima mossa dell'avversario era 3 (risp. : esercizio...)
Benissimo, ma ecco noi vogliamo che queste cose Comp le scopra da solo!!!
Noi vogliamo programmare Comp per giocare a questo stupido gioco,
e perchè lui vinca, ma
non vogliamo dirgli:
gioca 2 o 3 ecc.... Mai!!
Possibile??
Sì, si puo' fare ;-)
Memoria e ricordo: database e funzione di valutazione.
Abbiamo visto che ci sono solo 24 partite possibili. Inizamo col fare un database contenenti queste 24 partite. Questo database sarà costituito da 24 entrate ("records"), ogni entrata sarà un array (array = matrice "1-dimensionale") di tre numeri (anzi 4), per esempio il primo sarà [1,2,3], con il seguente significato:
- Alla sua prima mossa, il primo giocatore (computetr) Comp ha seganto la casella 1
- Alla sua prima mossa, il secondo giocatore (umano) Hum, ha segnato la casella 2
- Alla sua seconda mossa, Comp ha segnato la casella 3
Come spiegato prima, a questo punto la partita è finita (in questo caso la partita è pari; Comp ha sbagliato sia la 1a che la 2a mossa) e possiamo assumere che il programma sia in grado di riconoscere questo dato di fatto (altrimenti fatte un array di 4 numeri con l'istruzione:
come quarta entrata, prendi l'unica casella non ancora segnata).
D'ora in poi suporemmo di avere codificato ogni partita con 3 numeri (1a mossa "completa" e 2a mossa di Comp). A questi tre numeri ne aggiungiamo un quarto: lo score (il punteggio di Comp: 0 se la partita è finita pari, -1 se Comp ha perso, 1 se Comp ha vinto). All'inizio mettiamo la quarta entrata di ogni "record" del database a 0. Quindi il nostro database inizierà così:
r1=[1,2,3,0], r2=[1,2,4,0],r3=[1,3,2,0],...
Fase di apprendimento: Iniziamo la fase di apprendimento faccendo giocare a Comp, diciamo 10 partite, "a caso":
- scegli la prima mossa a caso tra {1,2,3,4}
- per la seconda mossa, scegli, a caso, una delle due caselle rimaste libere.
Secondo la teoria delle probabilità, Comp dovrebbe vincere il 50% delle partite.
Ma facciamo un record della partita, cioè creiamo un array, currGame[], nel quale mettiamo le varie mosse della partita. Esempio:
- Comp inizia con 1: allora currGame[0] = 1; (la numerazione degli arrays parte da 0)
- l'umano gioca 2: allora currGame[1] = 2;
- Comp gioca 4 : allora currGame[2] = 4;
A questo punto la partita è finita e c'è una funzione, check(), che attribuisce il punteggio, per esempio:
//si riempie con H la casella rimasta libera (2a mossa di Human))
for(int i=0;i<4;i++){
if(currGame[i] == '-'){currGame[i] = 'H';}
}
//si guarda chi ha vinto
for(int i=0; i<3;i++){
if(currGame[i] == currGame[i+1]){ //se qualcuno ha vinto
char c = currGame[i];
switch(c){
case'H': //ha vinto Human
punt = -1;
break;
case'C': //ha vinto Comp
punt = 1;
break;
}
}
else{ punt = 0;} //altrimenti la partita è pari
}
Aggiornare il database: adesso andiamo a cercare nel database il record le cui prime tre entrate siano uguali a quelle di currGame (usare un ordinamento lessicografico; a questo punto ci accorgiamo che è preferibile mettere i records come delle matrici bidimensionali: int r[1][4] e poi:
if(punt != 0){ //altrimenti non c'è nulla da aggiornare
for(int j=0;j<24;j++){
if(currGame[0]== r[j][0]){
if(currGame[1]== r[j][1]){
if(currGame[2] == r[j][2]{ //è lui!
r[j][3] = r[j][3] + punt; //aggiornamento del punteggio di questo record
break;
}
}
}
}
Quindi con le notazioni precedenti se currGame =[1,2,4,3], check() ci dice che punt = 0: nessun aggiornamento. Se invece currGame = [1,3,2,4], check() ci dice che punt = 1 (ha vinto Comp), il record le cui prime tre entrate sono uguali a quelle di currGame è r3, quindi r3 viene aggiornato in [1,3,2,1].
Dopo 10 partite "a caso" molto probabilmente sarà stata giocata una partita vincente per Comp, il record corrispondente avrà quindi un punteggio > 0, mentre i records corrispondenti a partite pari o perdenti avranno un punteggio <= 0. Possiamo decidere che la fase di apprendimento è finita!
E vai!! adesso facciamo usare a Comp quello che ha imparato. Invece di fargli giocare la prima mossa a caso, gli diciamo: cerca nel database tutti i records con punteggio (la quarta entrata) massimo. Scegli uno di questi records e gioca la sua prima mossa. Per la seconda mossa: cerca nel database tutti i records le cui prime due entrate siano currGame[0], currGame[1]; tra questi seleziona quelli col punteggio massimo; scegli uno di questi e gioca la sua terza mossa. Da questo punto, in poi Comp dovrebbe vincere tutte le partite! (se siamo stati particolarmente sfortunati nella fase di apprendimento (per es. se Comp è decisamente ciordo!) potrebbero volerci ancora qualche partita...)
Conclusioni.
Ecco siamo riusciti a fare sì che Comp vinca tutte le partite senza mai dirgli gioca 2 o gioca 3! Mi direte much ado about nothing (molto rumore per niente): abbiamo vissuto un inferno, scritto decine di righe di codice quando bastava scriverne una e, per giunta, tutto questo per giocare a un gioco completamente stupido!!
Non siate così pessimisti! Intanto si puo' ridurre un po' la fatica: per esempio possiamo fare scrivere il database da Comp (si parte con un database vuoto, dopo ogni partita si guarda se currGame è un record del database, se non lo è, lo si aggiunge). Osservare che in questo modo non c'è bisogno di alcuna strategia, analisi ecc...
Secondo, il gioco è stupido, vero (l'avevo detto in partenza), ma lo stesso procedimento si può applicare ad altri giochi, un pò meno stupidi. Per esempio il gioco del tris (tic-tac-toe)
-Sì, ma allora lì diventa veramente pesante, ci sono tante possibilità :<
Beh, ma il database lo facciamo scrivere al computer e poi, ragazzi, questo è il metodo
brute force e la forza brutta... è brutta e anche pesante.
-Si potrebbe usare lo stesso approccio col gioco degli scacchi?
Si può fare tutto ma ho paura che la "fase di apprendimento" sarebbe decisamente molto (troppo) lunga; no qui ci vogliono altri metodi.
Per riassumere, questo stupido esempio ha messo in evidenza alcuni principi di base dell'AI:
- L'importanza dei database (per ordinare i dati e poi ripescarli; in situazioni più complesse ci vogliono degli algoritmi di "sorting" performanti)
- L'importanza delle funzioni di valutazione: ogni mossa viene "valutata" (qui con il punteggio, quarta entrata); più la valutazione è accurata e meglio è.
- La vita è dura (e anche complessa) e non tutti i problemi si possono risolvere "brutalmente" (questa, tutto sommato è una buona notizia ;-)
