Subgame Solving in Adversarial Team Games
Brian H. Zhang*, Luca Carminati*, Federico Cacciamani, Gabriele Farina, Pierriccardo Olivieri, Nicola Gatti, Tuomas Sandholm
Abstract
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.
Bibtex entry
@inproceedings{Zhang22:Subgame,
title={Subgame Solving in Adversarial Team Games},
author={Brian H. Zhang and Luca Carminati and Federico Cacciamani and Gabriele Farina and Pierriccardo Olivieri and Nicola Gatti and Tuomas Sandholm},
booktitle={Neural Information Processing Systems (NeurIPS)},
year={2022}
}