CoChat
Sign Up
PreprintCited by 33Artificial Intelligence in GamesReinforcement Learning in RoboticsGame Theory and Applications

Finding Friend and Foe in Multi-Agent Games

Open access
Serrino, Jack, Kleiman-Weiner, Max, Parkes, David C., Tenenbaum, Joshua B.·2019·arXiv
DOI 10.48550/arxiv.1906.02330arXiv 1906.02330
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1906.02330

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 36

  1. [1][1] Stefano V Albrecht and Peter Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. arXiv preprint arXiv:1709.08071 , 2017. - · arXiv
  2. [4][4] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold'em poker is solved. Science , 347(6218):145-149, 2015. -
  3. [5][5] Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret minimization. arXiv preprint arXiv:1811.00164 , 2018. - · arXiv
  4. [7][7] Colin Camerer. Behavioral game theory: Experiments in strategic interaction . Princeton University Press, 2003. -
  5. [8][8] Colin F Camerer, Teck-Hua Ho, and Juin-Kuan Chong. A cognitive hierarchy model of games. The Quarterly Journal of Economics , pages 861-898, 2004. -
  6. [9][9] Rodrigo Canaan, Christoph Salge, Julian Togelius, and Andy Nealen. Leveling the playing field-fairness in ai versus human game benchmarks. arXiv preprint arXiv:1903.07008 , 2019. - · arXiv
  7. [10][10] Gokul Chittaranjan and Hayley Hung. Are you a werewolf? detecting deceptive roles and outcomes in a conversational role-playing game. In 2010 IEEE International Conference on Acoustics, Speech and Signal Processing , pages 5334-5337. IEEE, 2010. -
  8. [11][11] Peter I Cowling, Edward J Powley, and Daniel Whitehouse. Information set Monte Carlo tree search. IEEE Transactions on Computational Intelligence and AI in Games , 4(2):120-143, 2012. -
  9. [12][12] Peter I Cowling, Daniel Whitehouse, and Edward J Powley. Emergent bluffing and inference with Monte Carlo tree search. In 2015 IEEE Conference on Computational Intelligence and Games (CIG) , pages 114-121. IEEE, 2015. -
  10. [14][14] Joseph Farrell and Matthew Rabin. Cheap talk. Journal of Economic perspectives , 10(3):103-118, 1996. -
  11. [16][16] Joseph Henrich. The secret of our success: how culture is driving human evolution, domesticating our species, and making us smarter . Princeton University Press, 2015. -
  12. [17][17] Max Jaderberg, Wojciech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human-level performance in first-person multiplayer games with population-based deep reinforcement learning. arXiv preprint arXiv:1807.01281 , 2018. - · arXiv
  13. [18][18] Michael Johanson. Measuring the size of large no-limit poker games. arXiv preprint arXiv:1302.7008 , 2013. - · arXiv
  14. [19][19] Michael Johanson, Nolan Bard, Marc Lanctot, Richard Gibson, and Michael Bowling. Efficient nash equilibrium approximation through monte carlo counterfactual regret minimization. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 2 , pages 837-846. International Foundation for Autonomous Agents and Multiagent Systems, 2012. -
  15. [20][20] Michael Johanson, Kevin Waugh, Michael Bowling, and Martin Zinkevich. Accelerating best response calculation in large extensive games. In Twenty-Second International Joint Conference on Artificial Intelligence , 2011. -
  16. [21][21] Max Kleiman-Weiner, Mark K Ho, Joseph L Austerweil, Michael L Littman, and Joshua B Tenenbaum. Coordinate to cooperate or compete: abstract goals and joint intentions in social interaction. In Proceedings of the 38th Annual Conference of the Cognitive Science Society , 2016. -
  17. [22][22] Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization in extensive games. In Advances in neural information processing systems , pages 1078-1086, 2009. -
  18. [23][23] Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Julien Perolat, David Silver, Thore Graepel, et al. A unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems , pages 4193-4206, 2017. -
  19. [24][24] Joel Z Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems , pages 464-473. International Foundation for Autonomous Agents and Multiagent Systems, 2017. -
  20. [26][26] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In ICML , volume 94, pages 157-163, 1994. -
  21. [27][27] Matej Moravˇ cík, Martin Schmid, Neil Burch, Viliam Lis` y, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science , 356(6337):508-513, 2017. -
  22. [28][28] Martin A Nowak. Five rules for the evolution of cooperation. Science , 314(5805):1560-1563, 2006. -
  23. [31][31] David G Rand and Martin A Nowak. Human cooperation. Trends in cognitive sciences , 17(8):413, 2013. -
  24. [32][32] Michael Shum, Max Kleiman-Weiner, Michael L Littman, and Joshua B Tenenbaum. Theory of minds: Understanding behavior in groups through inverse planning. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19) , 2019. -
  25. [33][33] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature , 529(7587):484-489, 2016. -
  26. [35][35] David Silver and Joel Veness. Monte-carlo planning in large pomdps. In Advances in neural information processing systems , pages 2164-2172, 2010. -
  27. [36][36] DJ Strouse, Max Kleiman-Weiner, Josh Tenenbaum, Matt Botvinick, and David J Schwab. Learning to share and hide intentions using information regularization. In Advances in Neural Information Processing Systems , pages 10270-10281, 2018. -
  28. [37][37] Duane Szafron, Richard Gibson, and Nathan Sturtevant. A parameterized family of equilibrium profiles for three-player kuhn poker. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems , pages 247-254. International Foundation for Autonomous Agents and Multiagent Systems, 2013. -
  29. [38][38] Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit texas hold'em. In Twenty-Fourth International Joint Conference on Artificial Intelligence , 2015. -
  30. [39][39] Michael Tomasello. A natural history of human thinking . Harvard University Press, 2014. -
  31. [40][40] Karl Tuyls, Julien Perolat, Marc Lanctot, Joel Z Leibo, and Thore Graepel. A generalised method for empirical game theoretic analysis. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems , pages 77-85. International Foundation for Autonomous Agents and Multiagent Systems, 2018. -
  32. [41][41] Tomer Ullman, Chris Baker, Owen Macindoe, Owain Evans, Noah Goodman, and Joshua B Tenenbaum. Help or hinder: Bayesian models of social goal inference. In Advances in neural information processing systems , pages 1874-1882, 2009. -
  33. [42][42] Michael P Wellman. Methods for empirical game-theoretic analysis. In AAAI , pages 1552-1556, 2006. -
  34. [43][43] Daniel Whitehouse. Monte Carlo tree search for games with hidden information and uncertainty . PhD thesis, University of York, 2014. -
  35. [44][44] Michael Wunder, Michael Kaisers, John Robert Yaros, and Michael Littman. Using iterated reasoning to predict opponent strategies. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 2 , pages 593-600. International Foundation for Autonomous Agents and Multiagent Systems, 2011. -
  36. [45][45] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in neural information processing systems , pages 1729-1736, 2008.

Cited by

Sorted by citations

Authors
Serrino, J., Kleiman-Weiner, M., Parkes, D. C., & Tenenbaum, J. B.
Affiliations
  • Massachusetts Institute of Technology (US)
  • Harvard University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
32
Pages
1249-1259
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1906.02330
arXiv
1906.02330
OpenAlex
W2948847269
Cited by
33
References
3
Citations by year
2025: 1 · 2024: 5 · 2023: 4 · 2022: 4 · 2021: 7 · 2020: 9 · 2019: 3
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion)
  • arXiv (Cornell University)
  • neural information processing systems
Funders
  • National Science Foundation (1231216)
  • Future of Life Institute
  • Templeton World Charity Foundation
  • Defense Advanced Research Projects Agency
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
Keywords
multi-agent reinforcement learning, counterfactual regret minimization, self-play, deductive reasoning, human-agent teams, game-theoretic analysis

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review