Finding Friend and Foe in Multi-Agent Games

Abstract

Recent breakthroughs in AI for multi-agent games like Go, Poker, and Dota, have seen great strides in recent years. Yet none of these games address the real-life challenge of cooperation in the presence of unknown and uncertain teammates. This challenge is a key game mechanism in hidden role games. Here we develop the DeepRole algorithm, a multi-agent reinforcement learning agent that we test on The Resistance: Avalon, the most popular hidden role game. DeepRole combines counterfactual regret minimization (CFR) with deep value networks trained through self-play. Our algorithm integrates deductive reasoning into vector-form CFR to reason about joint beliefs and deduce partially observable actions. We augment deep value networks with constraints that yield interpretable representations of win probabilities. These innovations enable DeepRole to scale to the full Avalon game. Empirical game-theoretic methods show that DeepRole outperforms other hand-crafted and learned agents in five-player Avalon. DeepRole played with and against human players on the web in hybrid human-agent teams. We find that DeepRole outperforms human players as both a cooperator and a competitor.

arXiv commentJack Serrino and Max Kleiman-Weiner contributed equally

References in corpus (6)

• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• Human-level performance in first-person multiplayer games with population-based deep reinforcement learning
• Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems
• Maintaining cooperation in complex social dilemmas using deep reinforcement learning
• Learning to Share and Hide Intentions using Information Regularization
• Deep Counterfactual Regret Minimization

Cited by in corpus (11)

• Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
• The Emergence of Adversarial Communication in Multi-Agent Reinforcement Learning
• Multi-Agent Collaboration via Reward Attribution Decomposition
• Learning to Play No-Press Diplomacy with Best Response Policy Iteration
• Joint Policy Search for Multi-agent Collaboration with Imperfect Information
• Learning to Deceive in Multi-Agent Hidden Role Games
• No-regret Learning in Cournot Games
• Search in Imperfect Information Games
• Competing in a Complex Hidden Role Game with Information Set Monte Carlo Tree Search
• Polymatrix Competitive Gradient Descent
• A Game Generative Network Framework with its Application to Relationship Inference