Lezione 9 MCTS Flashcards
Quali caratteristiche di Go ci mostrano quali difetti dell’Alpha-Beta search?
Il branching factor, che a inizio partita è 361, e quindi permetterebbe solo 4 o 5 mosse. Poi il fatto che non esistono funzioni euristiche molto efficaci identificare il valore di uno stato.
Cosa usa il Monte Carlo Tree Search al posto della funzione euristica per valutare il vantaggio in uno stato?
Usa una simulazione o rollout/playout per generare molte possibili sequenze di mosse che portano dallo stato che stiamo studiando ad uno terminale, e poi fa la media delle utilità che si possono ottenere. In questo modo otteniamo l’utilità media dello stato.
Cosa ci serve per poter effettuare delle simulazioni efficaci nel Monte Carlo Tree Search?
Potremmo accontentarci di fare mosse a caso, ma nella vita reale la maggior parte dei giocatori non gioca completamente a caso, perciò dobbiamo adottare delle politiche di playout (playout policies), per far si che le mosse effettuate siano in qualche modo realistiche e ci permettano di ottenere risultati verosimili.
In cosa consiste il Pure Monte Carlo Tree Search? In cosa è limitato?
Consiste nello svolgere semplicemente N simulazioni, tenere traccia dei risultati e capire quali mosse portano a più vittorie. E’ limitato perchè richiede troppe risorse e non ha una direzione nel modo in cui effettua le simulazioni.
In cosa consiste il passo di selezione nel Montecarlo Tree Search? Quali sono le politiche che si applicano in quello step?
Consiste nello scegliere quali nodi già generati dell’albero vogliamo percorrere, l’obiettivo è partire dalla radice e arrivare ad una foglia. Per selezionare i nodi da seguire usa politiche di exploitation (scegliere stati che hanno già una buona percentuale di simulazioni a buon fine) e di exploration (scegliere stati che non sono stati scelti molte volte e che quindi non hanno ancora dimostrato il loro potenziale).
In cosa consiste il passo di espansione nel Montecarlo Tree Search?
Una volta raggiunta una foglia nel passo di selezione, espandiamo l’albero di ricerca creando uno o più stati figli, per ora senza alcun risultato di simulazione
In cosa consiste il passo di simulazione nel Montecarlo Tree Search?
Una volta espanso l’albero dobbiamo svolgere delle simulazioni per valutare la qualità dei nodi espansi.
In cosa consiste il passo di back-propagation nel Montecarlo Tree Search?
Consiste nell’aggiornare retroattivamente i risultati delle simulazioni svolte in precedenza aggiungendo quelli delle simulazioni svolte sugli ultimi nodi espansi.
Qual’è la formula della politica di selezione UCB1 “upper confidence bound formula”?
UCB1(n)=U(n)/N(n)
+ C*sqrt(log(N(Parent(n)))/N(n))
U(n) è l’utilità totale dello stato, N(n) è il numero di simulazioni effettuate, quindi il primo termine rappresenta l’utilità media dello stato, detto coefficiente di exploitation. Il secondo termine, moltiplicato da una costante che serve a pesare i due coefficienti (tipicamente uguale a sqrt2), è il coefficiente di exploration, ed è inversamente proporzionale al numero di simulazioni svolte nel nodo figlio.
Come capiamo quando fermarci con il MCTS? Cosa restituisce la sua esecuzione?
Noi possiamo applicare il MCTS in qualsiasi punto del nostro albero, possiamo darci come limite una quantità di tempo o di simulazioni, e alla fine l’algoritmo restituirà la mossa che ha avuto più simulazioni (non necessariamente quella con più utilità media). Questo perchè se sono state applicate politiche di selezione intelligenti la mossa con più simulazioni dovrebbe anche essere una con una buona utilità media.
