Padroneggiare Stratego, il classico gioco dell’informazione imperfetta.

'Padroneggiare Stratego, il classico gioco di informazioni imperfette.'

DeepNash impara a giocare a Stratego da zero combinando teoria dei giochi e apprendimento profondo senza modello

I sistemi di intelligenza artificiale (IA) che giocano a giochi hanno raggiunto una nuova frontiera. Stratego, il classico gioco da tavolo più complesso degli scacchi e del Go, e più astuto del poker, è stato ora padroneggiato. Pubblicato su Science, presentiamo DeepNash, un agente di intelligenza artificiale che ha imparato il gioco da zero fino a raggiungere il livello di un esperto umano giocando contro se stesso.

DeepNash utilizza un approccio innovativo, basato sulla teoria dei giochi e sull’apprendimento di rinforzo profondo senza modello. Il suo stile di gioco converge verso un equilibrio di Nash, il che significa che è molto difficile per un avversario sfruttarlo. Così difficile, infatti, che DeepNash ha raggiunto un terzo posto di tutti i tempi tra gli esperti umani sulla più grande piattaforma online di Stratego al mondo, Gravon.

I giochi da tavolo sono storicamente un indicatore di progresso nel campo dell’IA, permettendoci di studiare come gli esseri umani e le macchine sviluppano ed eseguono strategie in un ambiente controllato. A differenza degli scacchi e del Go, Stratego è un gioco di informazione imperfetta: i giocatori non possono osservare direttamente le identità delle pedine dell’avversario.

Questa complessità ha significato che altri sistemi di Stratego basati sull’IA hanno faticato a superare il livello amatoriale. Significa anche che una tecnica di IA molto efficace chiamata “ricerca nell’albero di gioco”, precedentemente utilizzata per padroneggiare molti giochi di informazione perfetta, non è sufficientemente scalabile per Stratego. Per questo motivo, DeepNash va molto oltre la ricerca nell’albero di gioco.

• Intelligenza Artificiale per il gioco da tavolo Diplomacy
• Programmazione competitiva con AlphaCode
• Annuncio di Google DeepMind

Il valore di padroneggiare Stratego va oltre il gioco. Nella nostra missione di risolvere l’intelligenza per avanzare nella scienza e beneficiare dell’umanità, dobbiamo costruire sistemi di IA avanzati che possano operare in situazioni complesse del mondo reale con informazioni limitate su altri agenti e persone. Il nostro articolo mostra come DeepNash possa essere applicato in situazioni di incertezza e bilanciare con successo gli esiti per aiutare a risolvere problemi complessi.

Conoscere Stratego

Stratego è un gioco a turni, di cattura della bandiera. È un gioco di bluff e tattiche, di raccolta di informazioni e manovre sottili. Ed è un gioco in somma zero, quindi ogni guadagno da parte di un giocatore rappresenta una perdita della stessa entità per il suo avversario.

Stratego è una sfida per l’IA, in parte perché è un gioco di informazione imperfetta. Entrambi i giocatori iniziano disponendo le loro 40 pedine nella formazione iniziale che preferiscono, inizialmente nascoste l’una all’altra all’inizio del gioco. Poiché entrambi i giocatori non hanno accesso alla stessa conoscenza, devono bilanciare tutti i possibili risultati quando prendono una decisione, fornendo un punto di riferimento impegnativo per lo studio delle interazioni strategiche. I tipi di pedine e il loro ranking sono mostrati di seguito.

L’informazione è difficile da ottenere in Stratego. L’identità di una pedina dell’avversario viene generalmente rivelata solo quando incontra l’altro giocatore sul campo di battaglia. Questo è in netto contrasto con giochi di informazione perfetta come gli scacchi o il Go, in cui la posizione e l’identità di ogni pedina sono note a entrambi i giocatori.

Gli approcci di apprendimento automatico che funzionano così bene nei giochi di informazione perfetta, come l’AlphaZero di DeepMind, non sono facilmente trasferibili a Stratego. La necessità di prendere decisioni con informazioni imperfette e la possibilità di bluffare rende Stratego più simile al poker Texas hold’em e richiede una capacità umana come quella una volta notata dallo scrittore americano Jack London: “La vita non è sempre una questione di avere buone carte, ma a volte di giocare bene una mano povera”.

Le tecniche di intelligenza artificiale che funzionano così bene nei giochi come il Texas hold’em non si trasferiscono a Stratego, tuttavia, a causa della lunghezza stessa del gioco – spesso centinaia di mosse prima che un giocatore vinca. Il ragionamento in Stratego deve essere fatto su un gran numero di azioni sequenziali senza una chiara comprensione di come ogni azione contribuisca all’esito finale.

Infine, il numero di possibili stati di gioco (espresso come “complessità dell’albero di gioco”) è fuori scala rispetto agli scacchi, al Go e al poker, rendendolo incredibilmente difficile da risolvere. Questo è ciò che ci ha entusiasmato di Stratego e perché rappresenta una sfida di decenni per la comunità dell’intelligenza artificiale.

Cercando un equilibrio

DeepNash utilizza un approccio innovativo basato su una combinazione di teoria dei giochi e apprendimento automatico basato su rinforzo profondo senza modello. “Senza modello” significa che DeepNash non cerca di modellare esplicitamente lo stato di gioco privato del suo avversario durante il gioco. Nelle prime fasi del gioco, in particolare, quando DeepNash sa poco delle pedine dell’avversario, tale modellazione sarebbe inefficace, se non impossibile.

E poiché la complessità dell’albero di gioco di Stratego è così vasta, DeepNash non può utilizzare un approccio consolidato dei giochi basato sull’intelligenza artificiale – la ricerca di alberi di Monte Carlo. La ricerca di alberi è stata un ingrediente chiave di molti traguardi significativi nell’intelligenza artificiale per giochi da tavolo meno complessi e per il poker.

Invece, DeepNash è alimentato da una nuova idea algoritmica basata sulla teoria dei giochi che chiamiamo “Regularised Nash Dynamics” (R-NaD). Lavorando a una scala senza precedenti, R-NaD guida il comportamento di apprendimento di DeepNash verso ciò che è noto come un equilibrio di Nash (approfondisci i dettagli tecnici nel nostro articolo).

Un comportamento di gioco che porta a un equilibrio di Nash è inespugnabile nel tempo. Se una persona o una macchina giocasse in modo perfettamente inespugnabile a Stratego, il peggior tasso di vittoria che potrebbe ottenere sarebbe del 50%, e solo se si confrontasse con un avversario altrettanto perfetto.

In incontri contro i migliori bot di Stratego – compresi diversi vincitori del Campionato Mondiale di Stratego per Computer – il tasso di vittoria di DeepNash ha superato il 97% ed è stato frequentemente del 100%. Contro i migliori giocatori umani esperti sulla piattaforma di giochi Gravon, DeepNash ha ottenuto un tasso di vittoria dell’84%, guadagnandosi un posto tra i primi tre di tutti i tempi.

Aspettatevi l’imprevedibile

Per ottenere questi risultati, DeepNash ha dimostrato alcuni comportamenti notevoli sia durante la fase iniziale di dispiegamento delle pedine che durante la fase di gioco. Per diventare difficile da sfruttare, DeepNash ha sviluppato una strategia imprevedibile. Ciò significa creare dispiegamenti iniziali sufficientemente diversi per impedire all’avversario di individuare schemi in una serie di partite. E durante la fase di gioco, DeepNash randomizza tra azioni apparentemente equivalenti per evitare tendenze sfruttabili.

I giocatori di Stratego cercano di essere imprevedibili, quindi c’è valore nel mantenere nascoste le informazioni. DeepNash dimostra come valorizza le informazioni in modo piuttosto sorprendente. Nell’esempio seguente, contro un giocatore umano, DeepNash (blu) ha sacrificato, tra le altre pedine, un 7 (Maggiore) e un 8 (Colonnello) all’inizio del gioco e di conseguenza è stato in grado di individuare il 10 (Maresciallo), il 9 (Generale), un 8 e due 7 dell’avversario.

Tutti questi sforzi hanno lasciato DeepNash in una significativa svantaggio materiale; ha perso un 7 e un 8 mentre il suo avversario umano ha preservato tutte le sue pedine classificate 7 e oltre. Tuttavia, avendo informazioni solide sui pezzi migliori del suo avversario, DeepNash ha valutato le sue possibilità di vittoria al 70% – e ha vinto.

L’arte del bluff

Come nel poker, un bravo giocatore di Stratego deve a volte rappresentare forza, anche quando è debole. DeepNash ha imparato diverse tattiche di bluff del genere. Nell’esempio qui sotto, DeepNash usa un 2 (uno Scout debole, sconosciuto al suo avversario) come se fosse un pezzo di rango alto, inseguendo l’8 conosciuto del suo avversario. L’avversario umano decide che il cacciatore è molto probabilmente un 10 e cerca quindi di attirarlo in un’imboscata con la loro Spia. Questa tattica di DeepNash, rischiando solo un pezzo minore, riesce a smascherare ed eliminare la Spia del suo avversario, un pezzo critico.

Vedi di più guardando questi quattro video di partite complete giocate da DeepNash contro esperti umani (anonimizzati): Partita 1, Partita 2, Partita 3, Partita 4.

“Il livello di gioco di DeepNash mi ha sorpreso. Non avevo mai sentito parlare di un giocatore artificiale di Stratego che si avvicinasse al livello necessario per vincere una partita contro un giocatore umano esperto. Ma dopo aver giocato contro DeepNash, non sono rimasto sorpreso dal suo successivo piazzamento nei primi 3 posti sulla piattaforma Gravon. Mi aspetto che se gli fosse permesso di partecipare ai Campionati Mondiali umani avrebbe ottenuto ottimi risultati.” – Vincent de Boer, co-autore del documento e ex Campione Mondiale di Stratego

Prospettive future

Mentre abbiamo sviluppato DeepNash per il mondo altamente definito dello Stratego, il nostro nuovo metodo R-NaD può essere applicato direttamente ad altri giochi a due giocatori con somma zero, sia con informazioni perfette che imperfette. R-NaD ha il potenziale per generalizzarsi ben oltre i contesti di gioco a due giocatori per affrontare problemi del mondo reale su larga scala, spesso caratterizzati da informazioni imperfette e spazi di stato astronomici.

Speriamo anche che R-NaD possa contribuire a sbloccare nuove applicazioni di intelligenza artificiale in settori in cui sono presenti un gran numero di partecipanti umani o AI con obiettivi diversi che potrebbero non avere informazioni sulle intenzioni degli altri o su ciò che sta accadendo nell’ambiente, come nell’ottimizzazione su larga scala della gestione del traffico per ridurre i tempi di percorrenza dei conducenti e le emissioni dei veicoli associate.

Creando un sistema di intelligenza artificiale generalizzabile che sia robusto di fronte all’incertezza, speriamo di portare le capacità di risoluzione dei problemi dell’IA ancora più avanti nel nostro mondo intrinsecamente imprevedibile.

‍

Scopri di più su DeepNash leggendo il nostro articolo su Science.

Per i ricercatori interessati a provare R-NaD o a lavorare con il nostro metodo appena proposto, abbiamo reso il nostro codice open source.