Java Tutorial - Parte 2 0.1
Un tutorial per esempi
Caricamento in corso...
Ricerca in corso...
Nessun risultato
Versione 0.5: il giocatore A.I.

Sommario

Introduzione

In questo capitolo aggiungeremo una funzionalità alla applicazione Mastermind: il giocatore Artificial Intelligence; un algoritmo piuttosto semplice che implementa una strategia per indovinare la sequenza segreta dell'avversario.

I nuovi files sorgente

In questo capitolo analizzeremo i files sorgente che implementano il giocatore A.I. rappresentato dalla classe specializzata PlayerAI, derivata da PlayerLocal. I files che fanno parte di questa nuova versione sono i seguenti:

nome file package descrizione
PlayerAI.java mastermind.player il giocatore A.I.
ClassicAI.java mastermind.player l'algortimo classico A.I.
TestAI.java mastermind.player test e statistiche dell'algoritmo
Main05.java mastermind.app classe principale versione 0.5

L'algoritmo classico

L'algoritmo classico della AI implementato in questo progetto è un algoritmo appartenente alla categoria stepwise optimal con strategia di tipo exhaustive search (=a ricerca esaustiva). Essendo un algoritmo esaustivo esso perviene sempre ad una soluzione dal momento che la elaborazione avviene per esclusione:

  1. viene dapprima generato tutto lo spazio delle possibili soluzioni e memorizzato in una tabella
  2. dalla tabella viene scelto causualmente un elemento rappresentante il primo tentativo di soluzione (la sequenza guess)
  3. se la guess è la sequenza vincente, l'algoritmo termina
  4. se la guess non è la sequenza vincente si filtra lo spazio delle soluzioni ottenuto al primo punto in modo da tenere solamente le combinazioni che sono coerenti con il risultato fornito dal tentativo
  5. da questo nuovo spazio delle possibili soluzioni si ottiene un elemento a caso e si ritorna al punto 3.

Supponiamo di avere come parametri di gioco i seguenti: n=10,k=3,repeat=false e che la nostra solution sia 456. Con l'algoritmo classico viene generata una tabella di 720 elementi che sono tutte le possibili "combinazioni" (in realtà di chiamano "disposizioni semplici") dei dieci simboli da "0" a "9" in gruppi di tre.
La formula per sapere il numero di disposizioni semplici di n elementi in base k è: Dn;k = n! / (n-k)!
Sostituendo, n=10 e k=3 otteniamo:

D10;3 = 10! / (10-3)! = 3628800 / 5040 = 720
Pertanto la tabella iniziale conterrà 720 sequenze tra le quali ci saranno le seguenti :

123 124 125 126 127 ... 451 452 453 456 457 ... 985 986 987

La AI estrarrà a caso uno dei 720 elementi della tabella, diciamo il 451 e lo invia al server di gioco il quale lo confronta con la solution 456 ea fornisce come risultato il seguente:

  • 2 punti rossi (2 reds)
  • 0 punti bianchi (0 whites)

Ora iteriamo su tutti i 720 elementi della tabella e confrontiamo ogni elemento della tabella con la guess inviata al server. Cominciamo dal primo elemento: 123. Dal confronto otteniamo:

  • 0 punti rossi (0 reds)
  • 0 punti bianchi (0 whites)

Possiamo pertanto scartare l'elemento 123 dallo spazio delle soluzioni dal momento che esso non potrà mai essere la solution: la effettiva solution può essere solo uno degli elementi che, confrontato con la guess, da il risultato di 2reds, 0whites.
Procedendo sugli elementi della tabella verranno scartati tutti quelli che non possono essere la solution: dai restanti elementi si sceglie ancora uno a caso e si ripete il confronto. A meno di non scegliere casualmente proprio la solution corretta, questo algoritmo procede, nel peggiore dei casi, fino a che nella tabella rimane un solo elemento: quello deve per forza essere la solution.

E se non rimane alcun elemento in tabella? Cioè se tutti gli elementi vengono scartati?
Questa è una eventualità che non dovrebbe mai accadere: dico non dovrebbe (il condizionale è d'obbligo) perchè esiste, in verità, una situazione in cui la AI rimane senza soluzioni in tabella e quindi non sà più che pesci pigliare. Questa situazione accade quando l'umano "bara": mi spiego meglio con un esempio. Supponiamo di aver stabilito le regole del gioco come:

    n=10, k=3, repeat=false

e l'umano sceglie (barando) la solution 112 che non è valida poichè contiene un simbolo ripetuto. Ebbene, questa soluzione non apparirà mai nella tabella iniziale dello spazio di tutte le soluzioni possibili dal momento che la AI non prende nemmeno in considerazione una sequenza che contiene simboli ripetuti poichà repeat=false.
Ecco perchè dopo un certo numero di iterazioni, tutte le possibili soluzioni in tabella saranno scartate e la tabella rimarrà vuota.

Ovviamente sto descrivendo una situazione disonesta non contemplata dalla AI ma che dobbiamo prevedere noi programmatori impedendo al giocatore umano di barare. Ecco perchè è stato implementato il metodo Sequence.isValid che verifica la validità di una sequenza in base a determinati parametri di gioco (vedi La classe Sequence).

L'implementazione del algoritmo

Sebbene l'algoritmo possa essere implementato direttamente nella classe PlayerAI ho deciso di separare le due implementazioni in due classi distinte in modo che sia più facile utilizzare un nuovo algoritmo quando e se ne sarà sviluppato uno più veloce o più efficiente.
L'algoritmo viene istanziato quando comincia una nuova partita quindi il momento giusto per creare l'istanza dell'algoritmo è quando il giocatore AI riceve la notifica della avvenuta creazione di una nuova partita:

// File: PlayerAI.java
@Override
public void notifyNewGame( InputListener l, Params params )
{
super.notifyNewGame( l, params );
ai = new ClassicAI( params.getN(), params.getK(), params.getRepeat());
}

Per il resto, un qualsiasi algoritmo alternativo a ClassicAI deve implementare due soli metodi che vengono richiamati dalla classe PlayerAI:

  • getGuess: che restituisce la ipotesi di soluzione
  • notify: che notifica all'algoritmo i risultati del confronto

Il costruttore

L'algoritmo classico viene costruito con i parametri di gioco; essi sono indispensabili per allocare correttamente la tabella di tutte le possibili soluzioni (guessTable)

public ClassicAI( int n, int k, boolean repeat )
{
... omissis ...
if ( repeat ) {
expectedSize = (int) Math.pow( this.n, this.k );
}
else {
expectedSize = factorial( this.n ) / factorial( this.n - this.k );
}
logger.fine( "guessTable expected size=" + expectedSize );
init();
}

Oltre a memorizzare i parametri al costruttore nei membri dati interni, il costruttore determina la dimensione prevista della tabella di tutte le possibili soluzioni che è data dalla formula già vista in L'algoritmo classico.
Perchè determinare la dimensione esatta della tabella? Conosco già la vostra risposta ma è sbagliata! Poichè la tabella è una array di stringhe e poichè la dimensione di una array deve essere determinata nel momento stesso della sua allocazione, questo valore è cruciale; senza di esso non potremmo mai allocare la array:

String[] guessTable = new String[expectedSize];

Questa è la risposta più ovvia ma, come scritto in precedenza, è la risposta sbagliata! Se avete dato una occhiata al listato sorgente di ClassicAI avrete sicuramente notato che la tabella delle possibili soluzioni (guessTable) non è affatto una array ma un vettore, la cui dimensione non ha alcun bisogno di essere conosciuta a priori dal momento che può espandersi dinamicamente mano a mano che gli elementi vengono aggiunti ad esso:

public class ClassicAI
{
... omissis ...
private Vector<String> guessTable;

Ma allora perchè? La risposta nelle prossime sezioni.

La tabella delle guess

La tabella di tutte le possibili soluzioni viene elaborata nel metodo privato init, richiamato dal costruttore:

private void init()
{
logger.finer( "init() - expected size:" + expectedSize );
guessTable = new Vector<String>(expectedSize);
... omissis ...
logger.finer( "init() guessTable size=" + guessTable.size());
assert expectedSize == guessTable.size() : "ClassicAI.init() guessTable size: " + guessTable.size()
+ " must be equal to expected size: " + expectedSize;
}

Il metodo comincia con la allocazione della tabella che è una istanza della classe Vector che può essere paragonata ad una array ma con importanti features prima tra tutte la possibilità di espandersi dinamicamente.
Come potete osservare, il vettore viene costruito passandovi la dimensione prevista della tabella: questo aumenta l'efficienza del vettore poichè se la dimensione del vettore è conosciuta (anche approssimativa) si possono evitare i ridimensionamenti che sono, notoriamente, operazioni time-consuming (=consumano tempo).

Il metodo prosegue con la elaborazione delle sequenze che rappresentano tutte le possibili soluzioni ed infine, rispondo alla domanda di cui sopra (vedi Il costruttore); la dimensione prevista della guessTable viene confrontata con la dimensione effettiva della guessTable: i due valori devono coincidere.
Il confronto avviene tramite una assert. Questo è il classico esempio di uso di una istruzione assert: è impossibile che la dimensione della guessTable sia diversa dalla dimensione calcolata con la formula matematica; se questo evento si verifica abbiamo commesso un errore nella elaborazione delle sequenze aggiunte alla guessTable ed a questo punto è inutile continuare il programma.

Elaborare una guess

Il metodo getGuess ritorna una ipotesi di soluzione dalla tabella delle soluzioni possibili. La strategia per estrarre una guess dalla tabella è la seguente:

  • se il numero di elementi in guessTable è ZERO ritorna null: questo è un caso che non dovrebbe mai accadere dal momento che questo algoritmo classico è di tipo exaustive search (= a ricerca esaustiva, deve sempre pervenire ad una soluzione)
  • se il numero di elementi in guessTable è 1 viene restituito l'unico elemento rimasto in tabella: questa dovrebbe per forza essere la soluzione corretta
  • se il numero di elementi in guessTable è maggiore di 1 si ottiene un indice casuale, che chiameremo i, tra ZERO ed il numero di elementi nella guessTable meno uno: la sequenza ritornata è l'elemento ad indice i

Scartare le guess impossibili

Dopo che è stata restituita una guess, il codificatore notifica all'algoritmo il risultato del confronto tra la guess e la sequenza segreta; il metodo da richiamare per la notifica dei risultati è il notify.
Come già descritto in L'algoritmo classico, la strategia dell'algoritmo ClassicAI è quella di usare i risultati del confronto per scartare dalla guessTable tutte quelle sequenze che non sono compatibili con i risultati ottenuti. Questa operazione viene eseguita dal metodo deleteElements il quale itera su tutti gli elementi di guessTable (che vengono usati come solution) e la guess appena restituita: se i risultati del confronto non coincidono con quelli notificati dal codificatore, l'elemento viene cancellato dalla guessTable.

E qui avrete la risposta alla seconda domanda che vi siete posti in Il costruttore. Perchè usare una istanza di Vector anzichè una semplice array per memorizzare la tabella delle possibili soluzioni visto e considerato che sappiamo a priori la sua dimensione?
La risposta è piuttosto banale: perchè la array è, per così dire, statica mentre un vettore è dinamico. Non solo il vettore si espande dinamicamente mano a mano che gli elementi vengono aggiunti ad esso, ma può anche ridursi automaticamente mano a mano che gli elementi vengono rimossi da esso!

Pensateci bene: abbiamo una array di 10 elementi che contengono i numeri da 0 a 9:

int[] intArray = {0,1,2,3,4,5,6,7,8,9};

Ora devo rimuovere il quinto elemento (il valore 4): come faccio? Anche se non sembra a prima vista, questa operazione non è banale: non c'è altra scelta che allocare una nuova array di 10-1 elementi e copiarvi tutti gli elementi di intArray ad eccezione dell'elemento ad indice 4.
Ma se utilizziamo un vettore, invece, è tutta una altra musica:

Iterator<String> iter = guessTable.iterator();
while ( iter.hasNext() ) {
String item = iter.next();
... omissis ...
iter.remove();
}
  • per prima cosa otteniamo un iteratore sul vettore che vogliamo analizzare richiamando il metodo iterator della classe Vector
  • in un ciclo while mettiamo come condizione che l'iteratore contenga ancora almeno un elemento: questo si ottiene con il metodo Iterator.hasNext
  • preleviamo l'elemento dall'iteratore con il metodo Iterator.next
  • facciamo le elaborazioni del caso sull'elemento appena ottenuto: nel nostro caso confrontiamo l'elemento con guess e analizziamo i risultati con confronto
  • se la verifica del confronto è negativa rimuoviamo l'elemento dal vettore con il metodo Iterator.remove

Vi è anche da osservare che l'uso degli iteratori nelle classi container di Java è da considerarsi fail-fast: una qualsiasi modifica della struttura del container successiva alla creazione dell'iteratore invalida l'iteratore stesso e ne causa il sollevamento di eccezioni.
In questo contesto, l'uso del metodo remove per rimuovere elementi da una classe container come Vector è da considerarsi sicuro.

Efficenza dell'algoritmo

Quanto è furbo l'algoritmo? Essendo un algoritmo piuttosto semplice non possiamo certo aspettarci miracoli ma la domanda rimane: in quanti tentativi questo semplice algoritmo riesce ad indovinare la sequenza segreta? Dipende dalla fortuna, come sempre: poichè la guess è scelta a caso dalla tabella delle possibili soluzioni esiste sempre la possibilità che la prima guess estratta a caso sia proprio la solution cercata.
Quindi la domanda deve essere posta in altri termini: in quanti tentativi, in media ed al massimo, l'algoritmo classico riesce a indovinare la sequenza segreta?

Per rispondere a questa domanda non abbiamo altra scelta che provarlo. Scriviamo una piccola app CLI che risponda a queste domande. Trovate il listato sorgente di questa app in TestAI nel package mastermind.player. La app ha la seguente sintassi:

\V05>java -ea mastermind.player.TestAI [OPTIONS] [NUM-LOOPS]

where OPTIONS is:
   -h      display help
   -r      allow repetition, default=FALSE
   -kINT   sequence length (3,4), default=3
   -nINT   number of symbols (6..10), default=10
   -sSTRING set a fixed segret sequence (the solution)

and NUM-LOOPS is the number of loops to execute (default: 10)

La app crea un numero variabile di sequenze segrete casuali e usa l'algoritmo classico per indovinarle. Il numero di solution create è determinato dal argomento NUM_LOOPS il cui default è 10. La app registra il numero di tentativi occorsi per indovinare la solution e alla fine della elaborazione calcola:

  • il numero medio di tentativi
  • il numero massimo di tentativi
  • il numero minimo di tentativi
  • il numero di fail ossia quante volte l'algoritmo non è riuscito a pervenire ad una soluzione; questo valore dovrebbe essere ZERO.

Eseguita con NUM_LOOPS uguale a 1.000, la app di test dà i seguenti risultati:

TEST AI results (n=10 k=3 r=false)
  number of loops   : 1000
  minimum tries     : 2
  maximum tries     : 9
  total tries       : 5286
  total fails       : 0
  averageo tries    : 5.286

Quindi, in media, l'algoritmo impiega 5,2 tentativi per indovinare la sequenza segreta (è più efficiente di un umano) con un minimo di 2 ed un massimo di 9. Come previsto, il numero di fails è pari a ZERO, ma questo francamente ce lo aspettavamo essendo questo algoritmo di tipo exhaustive search quindi deve sempre arrivare ad una soluzione.
Possiamo quindi affermare che gli algoritmi di tipo esaustivo sono efficienti? Assolutamente no! Per il Mastermind lo è sicuramente ma solo perchè il numero di tutte le possibili soluzioni è piccolo. In fondo, con i parametri più estesi abbiamo un potenziale di soli 10.000 possibili soluzioni. Infatti, se poniamo n=10, k=4, repeat=true:
D(n,k) = nk = 104 = 10000

Problemi più complessi potrebbero avere centinaia di miliardi di possibili soluzioni e sarebbe di fatto impossibile creare una tabella di simili dimensioni.

Il giocatore A.I.

La classe PlayerAI rappresenta il giocatore AI. Il codice non è particolarmente complesso anzi, è piuttosto semplice da comprendere. Mi limito a commentare velocemente i metodi implementati:

  • il costruttore non fà altro che richiamare il costruttore della classe base
  • getType: ritorna Player.Type.AI
  • getSolution: ritorna una sequenza generata casualmente
  • notifyNewGame: istanzia l'algoritmo della Intelligenza Artificiale; al momento è stato implementato solo il ClassicAI (vedi L'algoritmo classico)
  • getGuess: nel proprio turno il giocatore AI richiede una guess al algoritmo istanziato al punto precedente: se l'algoritmo ritorna null la guess ritornata è "resign"
  • notifyHaveResults: notifica all'algoritmo i risultati del confronto tra la solution dell'avversaio e la guess ottenuta al punto precedente

La classe principale

Per finire, scriviamo la nuova classe principale Main05. Essendo derivata da Main04, la quale implementa tutte le interfacce e funzionalità, la nuova classe che rappresenta la nuova versione è piuttosto scarsa di codice: non sono necessari nuovi membri dati e per quanto riguarda i metodi, è sufficente sovrascriverne davvero pochi:

  • getVersion: che deve restituire la versione 0.5
  • overrideDefaultProperties: che imposta come avversario di default il tipo "AI"
  • createPlayer: che istanzia un oggetto di tipo PlayerAI in risposta alla proprietà "opponentType=AI" anzichè sollevare una eccezione come nella versione precedente

Giochiamo alcune partite

Ora che abbiamo un avversario intelligente possiamo provare a giocare qualche partita. Ricordatevi di specificare nella command-line il tipo di avversario AI altrimenti giocherete ancora con il giocatore di TEST (quello stupido):

>java -ea mastermind.game.Main opponentType=AI

Su cinque partite che ho giocato contro la AI ne ho vinte due, perse due e una pareggiata: devo anche riconoscere che nelle due partite che ho vinto ho avuto una discreta fortuna; al primo turno ho avuto un punteggio di ZERO rossi e ZERO bianchi: potrebbe sembrare un pessimo risultato ma invece è un colpo di fortuna poichè un tale risultato elimina tre simboli da tutte le sequenza.

AI contro giocatore di test

Solo per curiosità, cosa succede se la AI gioca contro il giocatore di TEST? Il risultato di una simile prova è piuttosto scontato: la AI vince sempre. Ed infatti è proprio così!

>java -ea mastermind.game.Main playerType=TEST

Avrete anche notato che la partita finisce in un attimo, quasi non si riesce a vederne lo svolgimento. Questo è perfettamente normale dal momento che le elaborazioni sia della AI che del giocatore di TEST sono velocissime.

AI contro se stessa

Anche questo è un test piuttosto interessante. In teoria, se la AI gioca contro se stessa la partita dovrebbe sempre finire patta, no?

>java -ea mastermind.game.Main playerType=AI opponentType=AI

E invece no. Su dieci partite provate, 2 sono finite patta mentre le altre sono state vinte in equal misura (4 a 4) dai due giocatori AI. Questo risultato è perfettamente prevedibile dal momento che anche la AI possiede il fattore fortuna: non dimentichiamo che le guess sono scelte casualmente dalla tabella delle soluzioni possibili.

Il log della solution

Benchè abbiamo preso diverse precauzioni per evitare che il giocatore umano possa "barare", vi è un evidente bug (=errore logico) nella applicazione che permette al giocatore umano di vincere sempre e vincere facile contro la A.I.: il log della solution da parte del server di gioco.

ago 14 1:15:08 PM mastermind.game.MasterMindServer haveSolution
INFO: haveSolution() id=1, solution=708, gui=false

Il log è uno strumento utilissimo per il debug ma non possiamo lasciare questo assurdo messaggio nel log. Questo è un avvertimento per i futuri programmatori: MAI e dico PROPRIO MAI inserire nel log dati sensibili come per esempio le password; questo è solo un gioco e non ci sono conseguenze gravi ma in un ambiente di produzione ed in una applicazione importante un errore come questo potrebbe avere conseguenze catastrofiche.
Lascio al lettore la risoluzione di questo problema.

Ulteriore documentazione

La documentazione completa del package descritto in questo capitolo può essere visualizzata clikkando il seguente link che riporta alla documentazione Javadoc della versione 0.5 del progetto: The MasterMind Project Version 0.5

Argomento precedente - Argomento successivo - Indice Generale

Generato da doxygen 1.12.0