Timezone: »

 
Poster
Subgame Solving in Adversarial Team Games
Brian Zhang · Luca Carminati · Federico Cacciamani · Gabriele Farina · Pierriccardo Olivieri · Nicola Gatti · Tuomas Sandholm

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #532
in Poster Session 2 »

In adversarial team games, a team of players sequentially faces a team of adversaries. These games are the simplest setting with multiple players where cooperation and competition coexist, and it is known that the information asymmetry among the team members makes equilibrium approximation computationally hard. Although much effort has been spent designing scalable algorithms, the problem of solving large game instances is open. In this paper, we extend the successful approach of solving huge two-player zero-sum games, where a blueprint strategy is computed offline by using an abstract version of the game and then it is refined online, that is, during a playthrough. In particular, to the best of our knowledge, our paper provides the first method for online strategy refinement via subgame solving in adversarial team games. Our method, based on the team belief DAG, generates a gadget game and then refine the blueprint strategy by using column-generation approaches in anytime fashion. If the blueprint is sparse, then our whole algorithm runs end-to-end in polynomial time given a best-response oracle; in particular, it avoids expanding the whole team belief DAG, which has exponential worst-case size. We apply our method to a standard test suite, and we empirically show the performance improvement of the strategies thanks to subgame solving.

Author Information

Brian Zhang (Carnegie Mellon University)
Luca Carminati (Politecnico di Milano)
Federico Cacciamani (Politecnico di Milano)
Gabriele Farina (Meta AI; Carnegie Mellon University)
Pierriccardo Olivieri
Nicola Gatti (Politecnico di Milano)
Tuomas Sandholm (CMU, Strategic Machine, Strategy Robot, Optimized Markets)

More from the Same Authors