💻 computer science

Offline Nash Solvers Meet Online Tree Search in Multi-Agent Games on Graphs

Questo articolo introduce la Primitive-Guided Tree Search (PGTS), un framework ibrido che combina computazioni offline dell'equilibrio di Nash esatto su sottogiocochi trattabili con la ricerca ad albero online per risolvere efficacemente giochi di Inseguimento-Fuga multi-agente su grafi, superando significativamente i baseline esistenti basati su apprendimento ed euristiche.

Autori originali: Mukesh Kumar, Yue Guan, Panagiotis Tsiotras

Pubblicato 2026-07-13

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Mukesh Kumar, Yue Guan, Panagiotis Tsiotras

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina una partita di tag ad alta tensione giocata su una mappa gigante di strade cittadine. Hai una squadra di "Tagger" (la squadra Rossa) che cerca di catturare una squadra di "Runner" (la squadra Blu) prima che raggiungano un'uscita segreta. Il problema? Man mano che aggiungi giocatori sul campo, il numero di mosse possibili esplode. È come cercare di prevedere ogni singola mossa in una partita a scacchi, ma con un milione di pezzi in movimento contemporaneamente. Se provi a calcolare la mossa perfetta per ogni singolo giocatore nello stesso momento, il tuo cervello (o il tuo computer) va in crash per il puro sovraccarico matematico.

Per molto tempo, i ricercatori hanno cercato di risolvere questo problema in due modi principali, e entrambi presentavano grandi difetti. Il primo modo era pre-calcolare la strategia perfetta per ogni possibile situazione prima ancora che la partita iniziasse. Ma questo è come memorizzare ogni possibile percorso in un labirinto prima di entrarvi; se il labirinto cambia anche solo di poco, o se gli altri giocatori fanno qualcosa di strano che non ti aspettavi, la tua mappa memorizzata diventa inutile. Il secondo modo era pensare in corsa durante la partita, simulando milioni di scenari futuri per scegliere la mossa migliore. Ma con così tanti giocatori, il numero di rami da esplorare è così enorme che il computer rimane incastrato tra le erbacce e non riesce a trovare il percorso migliore in tempo.

Ecco l'eroe della storia: Primitive-Guided Tree Search (PGTS). Pensa al PGTS come a un coach intelligente che combina il meglio dei due mondi.

L'arma segreta del Coach: La libreria di "Mini-Giochi"

Invece di cercare di risolvere l'intero enorme gioco in una volta sola, il coach del PGTS va in biblioteca prima della partita e risolve un sacco di versioni piccole e semplici del gioco. Questi sono chiamati "primitive sub-team games" (giochi di sottoteam primitivi).

Immagina di risolvere un gioco di tag 1 contro 1.
Poi di risolvere un gioco 2 contro 1 (due tagger contro un runner).

Il coach risolve questi piccoli giochi perfettamente e scrive le risposte in un "foglio di trucchi" (una cache di policy e valori). Questa è la parte offline. È veloce perché i giochi sono piccoli.

Il Giorno della Partita: Ricerca ad Albero Intelligente

Quando la vera partita inizia, il coach non tira a indovinare, né si affida solo al vecchio foglio di trucchi. Utilizza una Ricerca ad Albero (Tree Search), che è come guardare lungo un bivio per vedere dove conduce. Ma ecco la magia:

Espansione Guidata: Inveza di guardare ogni possibile mossa (il che richiederebbe un tempo infinito), il coach utilizza il foglio di trucchi per guardare solo le mosse che sembrano promettenti sulla base di quei piccoli giochi 1 contro 1 e 2 contro 1. È come se il coach dicesse: "Ehi, in una situazione di 2 contro 1, i tagger di solito fanno questo, quindi concentriamoci lì".
Stima del Valore delle Foglie: Quando il coach raggiunge la fine di un percorso di pensiero (una "foglia" sull'albero), non ha bisogno di simulare l'intero gioco fino alla fine. Gli basta guardare le posizioni attuali, scomporre il grande team di nuovo in quei piccoli gruppi 1 contro 1 e 2 contro 1, e usare il foglio di trucchi pre-calcolato per indovinare il punteggio finale.

Questo permette alla squadra di coordinarsi perfettamente come gruppo, pur utilizzando la velocità dei piccoli giochi pre-risolti.

Cosa Dice il Paper (e Cosa Non Dice)

Gli autori hanno testato questo nuovo coach su diverse mappe, incluse una griglia 7x7, una complessa mappa di "Scotland Yard" e una mappa reale di Atlanta con 151 nodi. Hanno eseguito simulazioni in cui il gioco durava 6 step temporali sulle griglie e 9 step temporali sulle mappe più grandi.

I risultati sono stati impressionanti. In queste simulazioni, la squadra PGTS (utilizzando uno stile decisionale "Regret Matching" o "Decoupled UCT") ha costantemente superato i migliori metodi esistenti.

Sulla complicata mappa "Grid 2", i vecchi metodi hanno ottenuto un'utilità nel caso peggiore di circa 0,25 - 0,37, mentre il PGTS ha ottenuto 0,40 - 0,46.
Sulla mappa di Scotland Yard, la differenza è stata enorme: i vecchi metodi hanno ottenuto punteggi bassi come 0,00 o 0,05, mentre il PGTS ha ottenuto 0,68 - 0,73.
Anche contro un runner "intelligente" che non correva solo in linea retta, il PGTS ha mantenuto la sua posizione, mentre gli altri metodi (che erano stati addestrati su runner semplici) sono crollati.

Il paper argomenta esplicitamente contro l'idea di affidarsi solo ai mini-giochi pre-calcolati (decomposizione) senza la ricerca ad albero. Hanno scoperto che, sebbene i mini-giochi siano utili, falliscono nel catturare come l'intero team debba lavorare insieme. Se usi solo i mini-giochi, la coordinazione del team si rompe e le prestazioni calano significativamente. La ricerca ad albero è la colla che tiene insieme la coordinazione del team.

Il Verdetto

Questa non è una bacchetta magica che risolve ogni problema dell'universo, ma nel mondo di queste specifiche simulazioni, è un punto di svolta. Gli autori dimostrano che, scomponendo un problema gigante e spaventoso in pezzi piccoli e risolvibili e usando poi quei pezzi per guidare una ricerca intelligente, è possibile battere le migliori strategie attuali. Lo hanno provato attraverso estese simulazioni al computer su varie topologie di grafi, mostrando che il loro metodo è robusto anche quando l'altra squadra cerca di essere furba.

Il paper suggerisce che questo approccio potrebbe essere esteso ad altri tipi di giochi multi-agente e persino a situazioni in cui non si può vedere tutto (osservabilità parziale), ma per ora lo hanno dimostrato solo in queste specifiche simulazioni di inseguimento-evasione. È un trucco astuto che trasforma un incubo matematico in un puzzle gestibile, dimostrando che a volte, il modo migliore per vincere la grande partita è padroneggiare prima i piccoli giochi.

Sintesi Tecnica: Ricerca ad Albero Guidata da Primitive in Giochi di Inseguimento-Evasione Multi-Agente

1. Formulazione del Problema

Il documento affronta la sfida di calcolare le politiche di equilibrio di Nash in giochi di Inseguimento-Evasione (Pursuit-Evasion Games, PEG) multi-agente su grafi. In questi giochi, un team di Inseguitori (Rossi) tenta di catturare un team di Evasori (Blu) prima che gli Evasori raggiungano nodi di uscita designati. La difficoltà principale risiede nella crescita esponenziale degli spazi di stato e di azione congiunti all'aumentare del numero di agenti.

Gli approcci esistenti affrontano un compromesso:

Metodi offline (es. PSRO, MAPPO) addestrano le politiche offline ma spesso mancano di adattabilità rispetto a comportamenti avversari non visti durante l'addestramento e soffrono di un'elevata complessità di addestramento.
Metodi di pianificazione online (es. MCTS) si adattano agli stati correnti ma faticano con i massicci fattori di ramificazione inerenti ai giochi simultanei multi-agente, rendendo la ricerca profonda computazionalmente impraticabile.
Metodi ibridi (es. varianti di AlphaZero) spesso si affidano all'apprendimento di approssimazioni accurate di valore/politica richiedendo dati estesi, o sono limitati a contesti a due giocatori.

L'obiettivo è sviluppare un framework scalabile e robusto che combini la profondità strategica del calcolo dell'equilibrio offline con l'adattabilità della ricerca online.

2. Metodologia: Ricerca ad Albero Guidata da Primitive (PGTS)

Gli autori propongono la Ricerca ad Albero Guidata da Primitive (Primitive-Guided Tree Search, PGTS), un framework ibrido che decompone il complesso gioco multi-agente in sub-giochi trattabili offline e integra queste soluzioni in una ricerca Monte Carlo ad Albero Simultanea (SM-MCTS) online.

2.1 Fase Offline: Sub-Giochi di Team Primitive

Invece di risolvere direttamente il gioco completo, PGTS pre-calcola gli equilibri di Nash esatti per piccoli e rappresentativi sub-giochi "primitive" che coinvolgono sottoinsiemi di agenti:

1v1: Un Inseguitore contro un Evasore.
2v1: Due Inseguitori contro un Evasore.
Questi vengono risolti utilizzando l'iterazione del valore di Shapley sugli spazi di stato ristretti ( $V \times V$ e $V^2 \times V$ ). L'output include le politiche miste ottimali ( $\pi^*$ ) e le funzioni di valore ( $V^*$ ) per queste primitive, che vengono memorizzate per l'uso durante l'esecuzione.

2.2 Fase Online: Ricerca ad Albero

Ad ogni passo temporale, PGTS esegue una ricerca ad albero a partire dallo stato congiunto corrente. L'algoritmo modifica la standard SM-MCTS in due modi critici:

Espansione Guidata da Primitive:
Per mitigare l'esponenziale fattore di ramificazione, l'algoritmo non espande tutte le possibili azioni congiunte. Inve invece, utilizza le politiche primitive offline per guidare la ricerca:
- Per ogni Evasore, l'algoritmo identifica i suoi $k_r$ Inseguitori più vicini.
- Campiona azioni congiunte per interazioni locali (gruppi 1v1 e 2v1) basandosi sulle politiche di Nash pre-calcolate ( $\pi^*_{1v1}, \pi^*_{2v1}$ ).
- Questi campioni formano un insieme di azioni candidate ristretto, aumentato con azioni euristiche di percorso minimo (shortest-path) ed esplorazione casuale per evitare un impegno eccessivo sui priori.
Stima del Valore Foglia tramite Surrogati di Sub-team:
Invece di eseguire costose simulazioni (rollout) Monte Carlo fino all'orizzonte, l'algoritmo stima il valore dei nodi foglia utilizzando le funzioni di valore delle primitive offline.
- L'algoritmo approssima il valore del gioco completo scomponendo lo stato corrente in un insieme di sub-team primitive.
- Impiega una strategia di matching sequenziale: prima, associa greedymente gli agenti per formare interazioni 2v1 (catturando una coordinazione di ordine superiore come l'intrappolamento congiunto) utilizzando l'algoritmo di Hungarian sulla matrice di valore 2v1.
- Gli agenti rimanenti vengono associati in interazioni 1v1.
- Il valore foglia è la somma aggregata di questi valori delle primitive, permettendo alla ricerca di terminare a profondità minori mantenendo stime accurate degli esiti.

2.3 Selezione delle Azioni

Il framework supporta due operatori di selezione per attraversare l'albero:

Regret Matching (RM): Applica il regret matching al gioco a matrice stimato in ogni nodo per calcolare le politiche miste.
Decoupled UCT (DUCT): Applica i limiti superiori di confidenza (Upper Confidence Bounds) indipendentemente ai valori marginali delle azioni di ciascun team.

3. Contributi Chiave

Framework Ibrido: L'introduzione di PGTS, che integra in modo unico le soluzioni esatte di Nash di piccoli sub-giochi in una ricerca ad albero online per la coordinazione multi-agente.
Espansione Strutturata: Un meccanismo per ridurre i fattori di ramificazione campionando le azioni basandosi su priori strategici derivati dai calcoli di equilibrio offline piuttosto che su un campionamento casuale o puramente euristico.
Valutazione Foglia Scalabile: Un metodo di stima del valore surrogato che sfrutta le funzioni di valore delle primitive offline e un algoritmo di matching sequenziale (priorità al 2v1 rispetto al 1v1) per valutare i nodi foglia senza deep rollout.
Preservazione della Coordinazione: A differenza dei semplici metodi di decomposizione che trattano i sub-team indipendentemente, PGTS mantiene la coordinazione a livello di team eseguendo rollout di azioni congiunte nello spazio delle azioni completo, guidati dalle primitive.

4. Risultati Sperimentali

Gli autori hanno valutato PGTS su quattro topologie di grafi: due griglie 7x7 (Easy/Hard), un grafo Scotland Yard di 200 nodi e un grafo reale di Atlanta di 151 nodi. Il team degli Inseguitori è stato testato contro vari comportamenti degli Evasori.

Baseline:

MT-PSRO: Multi-Task Policy Space Response Oracles (basato su apprendimento).
NSGZero: MCTS guidato da reti neurali per la sicurezza di rete.
Decomposition: Una baseline che utilizza solo la decomposizione dei sub-team senza ricerca ad albero.
Intercepting: Una baseline euristica basata sul percorso minimo.

Risultati:

Robustezza: PGTS (sia le varianti RM che DUCT) ha ottenuto costantemente l'utilità nel caso peggiore (Worst-Case Utility, WCU) più elevata in tutte le topologie, superando significativamente le baseline basate sull'apprendimento (MT-PSRO, NSGZero) che mostravano segni di overfitting verso Evasori che seguono il percorso minimo.
Coordinazione: PGTS ha superato la baseline di pura "Decomposition", dimostrando che la componente di ricerca ad albero cattura efficacemente la coordinazione a livello di team che la decomposizione statica manca.
Ablazione: Rimuovere l'espansione guidata da primitive o le primitive 2v1 ha causato cali significativi di prestazioni, particolarmente su grafi più grandi e complessi (Scotland Yard, Atlanta), confermando la necessità di entrambi i componenti per un'efficace esplorazione e stima del valore.

5. Significato e Rivendicazioni

Il documento sostiene che PGTS offra una soluzione scalabile alla "maledizione della dimensionalità" nei PEG multi-agente. Sfruttando le soluzioni esatte di piccole interazioni locali ricorrenti (primitive) per guidare una ricerca globale, il metodo raggiunge:

Trattabilità Computazionale: Gestisce efficacemente il fattore di ramificazione e la profondità di ricerca.
Adattabilità: Mantiene la capacità di ragionare su politiche coordinate nello spazio delle azioni congiunte completo, diversamente dalla decomposizione statica.
Robustezza: Funziona bene contro diverse strategie avversarie, incluse quelle non viste durante qualsiasi fase di addestramento, poiché si basa su principi di teoria dei giochi piuttosto che su distribuzioni apprese.

Gli autori concludono che questo approccio colma il divario tra l'ottimalità teorica del calcolo dell'equilibrio offline e l'adattabilità pratica della pianificazione online, fornendo un framework robusto per il decision-making multi-agente in ambienti avversariali. Si suggerisce come lavoro futuro l'estensione a osservabilità parziale e classi di giochi multi-agente più ampie.