JSON-Bag: A generic game trajectory representation

Sintesi Tecnica: JSON-Bag: Una Rappresentazione Generica delle Traiettorie di Gioco

Enunciato del Problema
Definire caratteristiche e rappresentazioni per i giochi, insieme alle relative metriche di distanza o similarità, è fondamentale per attività di analisi dei giochi come l'ottimizzazione della forza degli agenti, la modellazione degli stili di gioco umani e la progettazione automatizzata di giochi. Tradizionalmente, queste rappresentazioni si basano su caratteristiche create manualmente che richiedono una significativa conoscenza del dominio o su modelli di deep learning che necessitano di ulteriore ingegneria delle caratteristiche. Le metriche di distanza esistenti, come la distanza euclidea e la similarità del coseno, sono spesso applicate a questi vettori definiti manualmente. Gli autori propongono un metodo per rappresentare genericamente le traiettorie di gioco senza fare affidamento sull'ingegneria delle caratteristiche specifica del dominio, consentendo il confronto dei log di gioco attraverso diversi giochi da tavolo utilizzando un approccio unificato e guidato dai dati.

Metodologia
Il documento introduce il modello JSON Bag-of-Tokens (JSON-Bag). Questo metodo rappresenta le traiettorie di gioco tokenizzando le loro descrizioni JSON.

• Tokenizzazione: Una traiettoria di gioco è formata concatenando il JSON degli stati di gioco individuali. I token sono definiti come componenti atomici (valori non dizionario, non lista) identificati dal loro percorso dalla radice (ad esempio, .playerResources[0].Wood.2). Gli autori sperimentano entrambe le modalità di tokenizzazione ordinata e non ordinata a seconda delle meccaniche del gioco (ad esempio, non ordinata per le mani di carte, ordinata per le posizioni sulla griglia).
• Rappresentazione: Similmente al modello "bag-of-words" nell'Elaborazione del Linguaggio Naturale (NLP), un JSON-Bag è una collezione di coppie conteggio-occorrenza di token. Questi conteggi sono normalizzati per sommare 1, interpretando il JSON-Bag come un modello probabilistico della traiettoria di gioco, dove la frequenza del token rappresenta la probabilità di generare quel token durante il gioco.
• Metrica di Distanza: Per misurare la similarità tra questi modelli probabilistici, gli autori impiegano la Distanza Jensen-Shannon (JSD), una metrica simmetrica e limitata derivata dalla divergenza Jensen-Shannon.
• Approcci di Classificazione:
  1. Ricerca del Vicino Più Vicino basata su Prototipi (P-NNS): Un prototipo per una classe è definito come la media dei JSON-Bag di tutte le traiettorie in quella classe. La classificazione viene eseguita trovando il prototipo più vicino utilizzando la JSD.
  2. Random Forest (RF): Le singole coppie frequenza-token sono trattate come caratteristiche e inserite in un classificatore Random Forest per valutare la capacità del modello di estrarre automaticamente le caratteristiche senza selezione manuale.

Configurazione Sperimentale
L'approccio è stato valutato su sei giochi da tavolo implementati nel framework TAG: 7 Wonders, Dominion, Sea Salt and Paper, Can't Stop, Connect4 e Dots and boxes. Gli autori hanno classificato Connect4 e Dots and boxes come giochi "sparsi" a causa dei loro componenti di gioco unici limitati rispetto agli altri.
Per ogni gioco sono state eseguite tre attività di classificazione:

1. Classificazione degli Agenti: Distinzione tra agenti Random, One-step-look-ahead (OSLA) e tre varianti di agenti Monte Carlo Tree Search (MCTS).
2. Classificazione dei Parametri: Identificazione di diversi set di parametri di gioco (ad esempio, dimensioni della griglia, valori delle carte).
3. Classificazione dei Seed: Identificazione dei seed del generatore di numeri casuali utilizzati per inizializzare i giochi.

Risultati Chiave

• Prestazioni di P-NNS: JSON-Bag con JSD ha superato una baseline basata su caratteristiche create manualmente e distanza euclidea nella maggior parte delle attività. Ha distinto con successo gli agenti OSLA e Random dalle varianti MCTS nella maggior parte dei giochi. Tuttavia, le prestazioni sono peggiorate sui giochi "sparsi" (Connect4, Dots and boxes) e su attività specifiche come la classificazione dei seed di Dominion, probabilmente a causa del contenuto informativo limitato nelle descrizioni JSON sparse o dell'alto ruolo della casualità in Dominion.
• Efficienza del Campione: Negli esperimenti di classificazione N-shot, i prototipi JSON-Bag hanno dimostrato un'elevata efficienza del campione. Per attività "facili" (dove le classi presentano differenze ovvie), è stata ottenuta una classificazione accurata con soli 5 campioni per classe.
• Miglioramento di Random Forest: Quando i token JSON-Bag sono stati utilizzati come caratteristiche per un classificatore Random Forest, l'accuratezza è migliorata significativamente nelle attività in cui P-NNS ha avuto prestazioni inferiori, in particolare sui giochi sparsi e sulla classificazione complessa dei parametri. Ciò suggerisce che JSON-Bag cattura efficacemente caratteristiche che possono essere sfruttate da modelli capaci di apprendere interazioni complesse.
• Correlazione con la Distanza della Politica: La JSD tra i prototipi JSON-Bag di diverse classi di agenti è risultata altamente correlata (coefficienti di Pearson compresi tra 0,62 e 0,97) con la effettiva distanza della politica tra quegli agenti. Ciò convalida la metrica come proxy per la differenza comportamentale senza richiedere caratteristiche create manualmente.
• JSON-Char: Uno studio di ablazione che tokenizzava i singoli caratteri della stringa JSON (JSON-Char) ha prodotto risultati sorprendentemente competitivi, suggerendo che la struttura semantica del JSON stesso trasporta un segnale significativo.

Significato e Contributi
Il documento rivendica quattro contributi principali:

1. Rappresentazione Generica: Fornisce un metodo agnostico rispetto al dominio per rappresentare le traiettorie di gioco utilizzando solo descrizioni JSON, eliminando la necessità di ingegneria manuale delle caratteristiche o logica di serializzazione specifica per il gioco oltre alla conversione JSON standard.
2. Similarità Probabilistica: Dimostra che la similarità delle traiettorie di gioco può essere valutata efficacemente utilizzando l'interpretazione probabilistica dei JSON-Bag combinata con la metrica JSD basata sulla teoria dell'informazione.
3. Efficienza del Campione ed Estrazione di Caratteristiche: Mostra che i prototipi JSON-Bag sono efficienti dal punto di vista del campione per rappresentare le classi di traiettorie e che il modello possiede un'abilità intrinseca nell'estrare caratteristiche adatte ad algoritmi di machine learning come Random Forest.
4. Correlazione Comportamentale: Stabilisce una forte correlazione tra la JSD dei prototipi JSON-Bag e la effettiva distanza della politica tra gli agenti, convalidando la sua utilità per il clustering degli stili di gioco e la ricerca di novità senza fare affidamento su metriche specifiche del dominio.

Limitazioni
Gli autori riconoscono che JSON-Bag fatica con i giochi "sparsi" in cui i dati di stato serializzati mancano di componenti unici informativi o in cui le relazioni spaziali (ad esempio, coordinate della griglia) sono critiche. In tali casi, il metodo di tokenizzazione potrebbe trattare valori distinti ma semanticamente simili (come diversi conteggi di turno) come token completamente diversi, perdendo informazioni. Il documento suggerisce che il raffinamento delle strategie di tokenizzazione (ad esempio, accoppiamento di coordinate o raggruppamento di valori numerici) potrebbe affrontare queste limitazioni.