Strategy refinement in adversarial team games

While strategy refinement in two players zero-sum (2p0s) games has been widely investigated in the literature, no work deals with adversarial team games. Recent algorithms, such as Libratus [Brown and Sandholm, 2017a] and Pluribus [Brown and Sandholm, 2019], achieved superhuman skills in sequential decision-making problems, with imperfect information (e.g. Poker No-Limit Texas Hold’em). Their approach consists in the offline computation of a blueprint strategy, on a more compact version of the game, and in its online improvement by using techniques of subgame solving while playing. The same algorithms cannot be applied directly to team games due to the presence of asymmetric information available to teammates. To solve these problems, we propose a new pipeline for strategy refinement. Our approach allows the computation of the blueprint strategy and applies subgame solving, combining reach solving [Brown and Sandholm, 2017b] and depth-limited solving [Brown et al., 2018b], working directly on the team tree [Zhang et al., 2022]. Moreover, for the evaluation and benchmarking purposes, a game simulator and two team games have been implemented: Bridge and a Search Game. Thanks to this work, team games with an arbitrary number of players can be solved exploiting the benefits of the abstraction and strategy refinement, laying the foundation for future works such as the design of abstraction algorithms at team level to participate in a Bridge computer competition.

Mentre il perfezionamento di una strategia in giochi a somma zero a due giocatori è stato studiato in letteratura, lo stesso non si può affermare per giochi a squadre avversarie. Algoritmi recenti, come Libratus [Brown and Sandholm, 2017a] e Pluribus [Brown and Sandholm, 2019], hanno raggiunto abilità sovrumane in problemi sequenziali, ad informazioni imperfette (per esempio: Poker No-Limit Texas Hold’em). Il loro approccio consiste nel calcolo di una strategia grezza, ottenuta da una versione astratta del gioco, e nel suo perfezionamento attraverso l’applicazione di tecniche di risoluzione di sotto-giochi. Gli stessi algoritmi non possono essere applicati direttamente nei giochi a squadre a causa della presenza di informazioni asimmetriche tra i vari compagni di squadra. Per risolvere tali problemi, proponiamo una nuova pipeline per il miglioramento di una strategia. Il nostro approccio consente il calcolo della strategia grezza e il suo perfezionamento utilizzando tecniche di risoluzione dei sotto-giochi, combinando reach solving [Brown and Sandholm, 2017b] e depth-limited solving [Brown et al., 2018b], lavorando direttamente su un albero di gioco costruito dal punto di vista della squadra. Inoltre, per eseguire gli esperimenti conclusivi, è stato implementato un simulatore e due giochi a squadre: Bridge e un Search Game. Grazie a questo lavoro, giochi a squadre, con un arbitrario numero di giocatori, possono essere risolti con tutti i vantaggi derivanti dall’astrazione e dal rifinimento di una strategia. Oltretutto, getta le basi per lavori futuri quali, ad esempio, la progettazione di algoritmi di astrazione dal punto di vista di una squadra per partecipare a competizioni di Bridge tra computer.