Prior AI successes in complex games have largely focused on settings with at most hundreds of actions at each decision point.In contrast, Diplomacy is a game with more than 10^20 possible actions per turn. Previous attempts to address games with large branching factor, such as Diplomacy, StarCraft and Dota, used human data to bootstrap the policy or used handcrafted reward shaping. In this paper we describe an algorithm for action exploration and equilibrium approximation in games with combinato…