Modellazione degli Avversari per l'Addestramento di Modelli Basati sulla Ricerca ad Albero Monte Carlo nel Gioco da Tavolo Citadels

1. Introduzione

Monte Carlo Tree Search (MCTS) si è consolidata come una tecnica efficace per il processo decisionale nei giochi da tavolo, combinando adattabilità e basso uso di conoscenze specifiche del dominio. Le sue prestazioni sono notevoli nei giochi deterministici con informazione perfetta, come Go (SILVER et al., 2016).

Tuttavia, la sua applicazione incontra limitazioni significative in ambienti con più giocatori, informazioni nascoste e vincoli di tempo, dove l'alto costo computazionale delle simulazioni e la difficoltà di adattamento compromettono la reattività e la qualità delle decisioni (POWLEY et al., 2014).

In questo contesto, approcci ibridi che integrano MCTS e Apprendimento per Rinforzo (RL) si sono dimostrati promettenti, consentendo di separare la fase di pianificazione dall'esecuzione. La costruzione di strutture decisionali persistenti, con memorizzazione preventiva della ricerca, permette la selezione istantanea delle azioni durante il gioco, riducendo la necessità di simulazioni online e preservando la profondità strategica (BROWNE, 2012; SWIECHOWSKI, 2023).

In questa ricerca, è stato testato e sviluppato un modello MCTS ibrido con tecniche di apprendimento per rinforzo offline. Il modello è stato addestrato e testato utilizzando diversi avversari in un ambiente di simulazione del gioco da tavolo Citadels (FAIDUTTI, 2016).

2. Obiettivo Generale

L'obiettivo generale di questa ricerca è sviluppare un framework ibrido MCTS-RL in grado di operare efficientemente in giochi da tavolo multiplayer con informazioni nascoste, utilizzando Citadels come caso di studio.

La proposta mira a eliminare i colli di bottiglia computazionali del MCTS tradizionale attraverso la costruzione offline di una struttura decisionale persistente, consentendo azioni rapide e robuste in fase di esecuzione.

3. Metodologia

Questa ricerca è caratterizzata come uno studio sperimentale applicato con analisi quali-quantitativa.

La prima fase ha comportato lo sviluppo e l'adattamento di un ambiente di simulazione digitale per il gioco da tavolo Citadels. A ciò è seguito lo sviluppo di cinque agenti esperti con strategie personalizzate, costruiti per imitare le strategie reali utilizzate dai giocatori umani, e lo sviluppo di un agente di base che sceglie le azioni in modo casuale. Dopo la validazione dell'ambiente e degli agenti sviluppati, è iniziato lo sviluppo del framework ibrido MCTS-RL.

Il modello MCTS è, nella sua essenza, un algoritmo di ricerca euristica che opera attraverso l'esecuzione di multiple simulazioni. Per ogni stato di gioco distinto visitato durante queste simulazioni, viene creato un nodo corrispondente in una struttura dati ad albero. Lo stato di gioco iniziale rappresenta il nodo radice di questo albero.

Tuttavia, la proposta di memorizzare l'intero albero e conservarlo per decisioni future è irrealizzabile a causa del fattore di ramificazione massiccio. Per renderlo possibile, è necessario astrarre l'albero: lo stato di gioco è suddiviso nelle sue caratteristiche fondamentali (ad esempio, oro del giocatore, numero di carte in mano) e ogni caratteristica è mappata in una tabella dati indipendente.

In questa struttura, le righe di una tabella rappresentano i possibili valori di una caratteristica dello stato, e le colonne rappresentano le possibili azioni che l'agente può intraprendere (ad esempio, guadagnare oro, pescare carte). In ogni cella sono memorizzati due valori: il numero di vittorie ottenute (n) dopo aver intrapreso quell'azione in quello stato, e il numero totale di volte in cui questa combinazione è stata esplorata (m). Queste tabelle, quando popolate attraverso simulazioni di partite di Citadels, configurano il modello appreso dall'agente.

Il processo di addestramento include una componente di apprendimento per rinforzo: dopo ogni partita simulata, i risultati aggiornano le tabelle decisionali, influenzando le scelte future. Le vittorie agiscono come ricompense e rafforzano le azioni efficaci, aumentando la loro probabilità di essere scelte di nuovo, mentre le sconfitte riducono questa possibilità. Così, attraverso molte simulazioni, il modello si adatta continuamente, bilanciando l'esplorazione di nuove alternative e lo sfruttamento di strategie comprovate, convergendo gradualmente verso comportamenti più efficaci.

4. Risultati e Discussione

Per valutare le prestazioni del modello MCTS proposto, è stato cruciale comprendere le dinamiche di potere tra le strategie di base (agenti esperti e agente casuale). Per raggiungere questo obiettivo, ciascuna è stata sottoposta a un round di 10.000 partite contro quattro avversari identici.

La mappa di calore presentata nella Figura 1 illustra le prestazioni di ciascuna strategia (asse Y) contro i diversi avversari (asse X). Le strategie possiedono punti di forza e debolezze distinti: gli Esperti 1, 2 e 3 si dimostrano competenti nella maggior parte degli scenari, mentre gli Esperti 4 e 5 sono considerevolmente meno efficaci. Come previsto, la strategia completamente casuale mostra prestazioni molto basse contro qualsiasi avversario minimamente strutturato.

Figura 1: Confronto tra le strategie.

Il passo successivo è stato valutare il modello MCTS-RL. Sono state condotte diverse sessioni di addestramento, ciascuna incentrata su uno degli avversari, per un totale di 100.000 partite di addestramento per ogni versione del modello. Quindi, le prestazioni di ciascun modello addestrato sono state misurate contro tutti i tipi di avversari seguendo lo stesso modello di test precedente, e contro avversari variati estratti casualmente.

La mappa di calore mostrata nella Figura 2 presenta il tasso di vittoria consolidato di ciascun modello. Il risultato più significativo è stato quello del modello addestrato nell'ambiente variato, che ha ottenuto prestazioni costanti, superando le altre versioni del modello in quasi tutti gli scenari di test. Ciò suggerisce che l'esposizione a una diversità di strategie durante l'addestramento è stata fondamentale per sviluppare una capacità di gioco più robusta e generalista.

Figura 2: Confronto tra modelli addestrati.

I modelli addestrati contro gli Esperti 4 e 5, considerati gli avversari più deboli, sono diventati agenti sorprendentemente efficaci. Al contrario, l'addestramento contro gli Esperti 1 e 3, considerati avversari forti, ha prodotto modelli con prestazioni complessive molto scadenti.

Una possibile spiegazione per questo contrasto è che le strategie esperte avanzate tendono ad essere altamente specializzate, mentre il modello MCTS-RL, all'inizio dell'addestramento, si avvicina a un comportamento casuale. Contro avversari forti, anche azioni potenzialmente vantaggiose potrebbero non portare a vittorie sufficienti affinché il modello riconosca schemi di successo; mentre contro avversari meno specializzati, le vittorie si verificano più frequentemente, favorendo l'apprendimento. Tuttavia, questa rimane un'ipotesi che richiede conferma.

5. Conclusione

Questo studio ha dimostrato la fattibilità dell'approccio proposto, che utilizza un'astrazione dell'albero MCTS per preservare la conoscenza acquisita tra le mosse. I risultati hanno confermato che il modello è in grado di sviluppare strategie robuste per l'ambiente.

Le prestazioni superiori dell'agente addestrato nell'ambiente variato mostrano che l'esposizione a molteplici tattiche è fondamentale per costruire un modello generalista. Inoltre, la ricerca indica che la qualità dell'agente finale dipende più dalla diversità che dall'apparente forza degli avversari di addestramento.

Come studi futuri, sarebbe interessante esplorare più precisamente le reali ragioni per cui strategie meno specializzate hanno prodotto modelli più efficienti rispetto a strategie più forti. Inoltre, un confronto del modello proposto con altri modelli MCTS aiuterebbe anche a ottenere una valutazione più accurata dell'approccio.