Simulare giochi e prevedere i risultati.
Non è sorprendente che tutto ciò di cui hai bisogno per eccellere in un gioco informativo perfetto sia visibile a tutti nelle regole del gioco?
Sfortunatamente, per i comuni mortali come me, leggere le regole di un nuovo gioco è solo una piccola frazione del viaggio per imparare a giocare a un gioco complesso. Trascorriamo la maggior parte del tempo giocando, idealmente contro un giocatore di forza paragonabile (o un giocatore migliore che sia abbastanza paziente da aiutarci a mettere in luce le nostre debolezze). Perdere spesso e, si spera, vincere a volte fornisce punizioni e ricompense psicologiche che ci spingono a giocare sempre meglio.
Forse, in un futuro non troppo lontano, un modello linguistico saprà leggere le regole di un gioco complesso come gli scacchi e, fin dall’inizio, giocarlo al massimo livello possibile. Nel frattempo, propongo una sfida più modesta: imparare giocando da soli.
In questo progetto formeremo un agente affinché impari a farlo gioca con informazioni perfette, giochi per due giocatori osservando i risultati delle partite giocate dalle versioni precedenti di se stesso. L’agente approssimerà un valore (il risultato previsto del gioco) per qualsiasi stato del gioco. Come ulteriore sfida, al nostro agente non sarà consentito mantenere una tabella di ricerca dello spazio degli stati, poiché questo approccio non sarebbe gestibile per giochi complessi.
Il gioco
Il gioco di cui parleremo è SumTo100. L’obiettivo del gioco è raggiungere la somma di 100 sommando numeri compresi tra 1 e 10. Ecco le regole:
- Inizializza somma = 0.
- Scegli un primo giocatore. I due giocatori si alternano.
- Mentre la somma < 100:
- Il giocatore sceglie un numero compreso tra 1 e 10 inclusi. Il numero selezionato viene aggiunto alla somma senza superare 100.
- Se la somma < 100, gioca l'altro giocatore (cioè si torna all'inizio del punto 3).
4. Vince il giocatore che ha aggiunto l’ultimo numero (raggiungendo 100).
Iniziare con un gioco così semplice presenta numerosi vantaggi:
- Lo spazio degli stati ha solo 101 valori possibili.
- Gli stati possono essere tracciati su una griglia 1D. Questa peculiarità ci consentirà di rappresentare la funzione valore di stato appresa dall’agente come un grafico a barre 1D.
- La strategia ottimale è nota:
– Raggiungere la somma di 11n + 1, dove n ∈ {0, 1, 2, …, 9}
Possiamo visualizzare il valore dello stato della strategia ottimale:
Lo stato del gioco è la somma dopo che un agente ha completato il suo turno. Un valore di 1,0 significa che l’agente vincerà sicuramente (o ha vinto), mentre un valore di -1,0 significa che l’agente perderà sicuramente (supponendo che l’avversario giochi in modo ottimale). Un valore intermedio rappresenta il rendimento stimato. Ad esempio, un valore di stato pari a 0,2 indica uno stato leggermente positivo, mentre un valore di stato pari a -0,8 rappresenta una probabile perdita.
Se vuoi immergerti nel codice, lo script che esegue l’intera procedura di addestramento è learn_sumTo100.sh, in questo deposito. Altrimenti, abbi pazienza mentre esamineremo una descrizione di alto livello di come il nostro agente impara giocando da solo.
Generazione di giochi giocati da giocatori casuali
Vogliamo che il nostro agente impari dai giochi giocati dalle versioni precedenti di se stesso, ma nella prima iterazione, poiché l’agente non ha ancora imparato nulla, dovremo simulare i giochi giocati da giocatori casuali. Ad ogni turno, i giocatori riceveranno l’elenco delle mosse legali dall’autorità del gioco (la classe che codifica le regole del gioco), dato lo stato attuale del gioco. I giocatori casuali selezioneranno una mossa a caso da questo elenco.
La Figura 2 è un esempio di un gioco giocato da due giocatori casuali:
In questo caso, il secondo giocatore ha vinto la partita raggiungendo la somma di 100.
Implementeremo un agente che ha accesso a una rete neurale che prende come input lo stato del gioco (dopo che l’agente ha giocato) e restituisce in output il rendimento atteso di questo gioco. Per ogni dato stato (prima che l’agente abbia giocato), l’agente ottiene l’elenco delle azioni legali e dei corrispondenti stati candidati (consideriamo solo i giochi con transizioni deterministiche).
La Figura 3 mostra le interazioni tra l’agente, l’avversario (il cui meccanismo di selezione delle mosse è sconosciuto) e l’autorità del gioco:
In questo contesto, l’agente fa affidamento sulla sua rete neurale di regressione per prevedere il ritorno atteso degli stati del gioco. Quanto meglio la rete neurale riesce a prevedere quale mossa candidata produce il rendimento più elevato, tanto meglio giocherà l’agente.
Il nostro elenco di partite giocate casualmente ci fornirà il set di dati per il nostro primo passaggio di allenamento. Prendendo il gioco di esempio della Figura 2, vogliamo punire le mosse effettuate dal giocatore 1 poiché il suo comportamento ha portato ad una perdita. Lo stato risultante dall’ultima azione assume un valore di -1,0 poiché ha permesso all’avversario di vincere. Agli altri stati vengono scontati valori negativi di un fattore γᵈ , dove d è la distanza rispetto all’ultimo stato raggiunto dall’agente. γ (gamma) è il fattore di sconto, un numero ∈ (0, 1), che esprime l’incertezza nell’evoluzione di un gioco: non vogliamo punire le decisioni iniziali tanto duramente quanto le ultime decisioni. La Figura 4 mostra i valori di stato associati alle decisioni prese dal giocatore 1:
I giochi casuali generano stati con il rendimento atteso target. Ad esempio, raggiungere una somma pari a 97 ha un rendimento atteso target di -1,0, mentre una somma pari a 73 ha un rendimento atteso target di -γ³. Metà degli stati adotta il punto di vista del giocatore 1, mentre l’altra metà assume il punto di vista del giocatore 2 (anche se nel caso del gioco SumTo100 questo non ha importanza). Quando una partita termina con una vittoria per l’agente, gli stati corrispondenti ottengono valori positivi scontati in modo simile.
Formare un agente per prevedere il ritorno delle partite
Abbiamo tutto ciò che ci serve per iniziare il nostro addestramento: una rete neurale (useremo un perceptron a due strati) e un set di dati di coppie (stato, rendimento atteso). Vediamo come evolve la perdita sul rendimento atteso previsto:
Non dovremmo sorprenderci che la rete neurale non mostri molto potere di previsione sull’esito dei giochi giocati da giocatori casuali.
La rete neurale ha imparato qualcosa?
Fortunatamente, poiché gli stati possono essere rappresentati come una griglia 1D di numeri compresi tra 0 e 100, possiamo tracciare i rendimenti previsti della rete neurale dopo il primo ciclo di addestramento e confrontarli con i valori dello stato ottimale della Figura 1:
A quanto pare, attraverso il caos dei giochi casuali, la rete neurale ha imparato due cose:
- Se riesci a raggiungere la somma di 100, fallo. Buono a sapersi, visto che è l’obiettivo del gioco.
- Se raggiungi la somma di 99, perderai sicuramente. In questa situazione, infatti, l’opponente ha una sola azione legale e tale azione comporta una perdita per l’agente.
La rete neurale ha imparato essenzialmente a finire il gioco.
Per imparare a giocare un po’ meglio, dobbiamo ricostruire il set di dati simulando partite giocate tra copie dell’agente con la loro rete neurale appena addestrata. Per evitare di generare partite identiche, i giocatori giocano in modo un po’ casuale. Un approccio che funziona bene è scegliere le mosse con l’algoritmo epsilon-greedy, utilizzando ε = 0,5 per la prima mossa di ogni giocatore, quindi ε = 0,1 per il resto della partita.
Ripetendo il ciclo di allenamento con giocatori sempre migliori
Poiché entrambi i giocatori ora sanno che devono raggiungere 100, raggiungere una somma compresa tra 90 e 99 dovrebbe essere punito, perché l’avversario coglierebbe al volo l’opportunità di vincere la partita. Questo fenomeno è visibile nei valori dello stato previsto dopo il secondo ciclo di allenamento:
Vediamo emergere uno schema. Il primo ciclo di addestramento informa la rete neurale sull’ultima azione; il secondo turno di allenamento informa sulla penultima azione e così via. Dobbiamo ripetere il ciclo di generazione dei giochi e di allenamento sul pronostico almeno tante volte quante sono le azioni del gioco.
L’animazione seguente mostra l’evoluzione dei valori di stato previsti dopo 25 cicli di allenamento:
L’inviluppo dei rendimenti previsti decade in modo esponenziale, man mano che si va dalla fine verso l’inizio del gioco. È un problema?
Due fattori contribuiscono a questo fenomeno:
- γ smorza direttamente i rendimenti attesi target, man mano che ci allontaniamo dalla fine del gioco.
- L’algoritmo epsilon-greedy inietta casualità nei comportamenti dei giocatori, rendendo i risultati più difficili da prevedere. Esiste un incentivo a prevedere un valore vicino allo zero per proteggersi da casi di perdite estremamente elevate. Tuttavia, la casualità è auspicabile perché non vogliamo che la rete neurale impari una singola linea di gioco. Vogliamo che la rete neurale sia testimone di errori e mosse buone inaspettate, sia da parte dell’agente che dell’avversario.
In pratica, non dovrebbe essere un problema perché in ogni situazione confronteremo i valori tra le mosse legali in un dato stato, che condividono scale comparabili, almeno per il gioco SumTo100. La scala dei valori non ha importanza quando scegliamo la mossa avida.
Ci siamo sfidati a creare un agente che possa imparare a padroneggiare un gioco di informazione perfetta che coinvolge due giocatori, con transizioni deterministiche da uno stato a quello successivo, data un’azione. Non erano consentite strategie o tattiche codificate manualmente: tutto doveva essere appreso giocando da soli.
Potremmo risolvere il semplice gioco di SumTo100 eseguendo più round lanciando copie dell’agente l’una contro l’altra e addestrando una rete neurale di regressione per prevedere il rendimento atteso dei giochi generati.
L’intuizione acquisita ci prepara bene per la prossima scala nella complessità del gioco, ma sarà per il mio prossimo post! 😊
Grazie per il tuo tempo.
