2019

The Hanabi Challenge: A New Frontier for AI Research

Bard, Nolan, Foerster, Jakob N., Chandar, Sarath et al.

Understand

From the early days of computing, games have been important testbeds for studying how well machines can do sophisticated decision making.

In recent years, machine learning has made dramatic advances with artificial agents reaching superhuman performance in challenge domains like Go, Atari, and some variants of poker.
As with their predecessors of chess, checkers, and backgammon, these game domains have driven research by providing sophisticated yet well-defined challenges for artificial intelligence practitioners.
We continue this tradition by proposing the game of Hanabi as a new challenge domain with novel problems that arise from its combination of purely cooperative gameplay with two to five players and imperfect information.

Built on

arXiv:1902.06075
Original
J. Goodman, Re-determinizing information set monte carlo tree search in hanabi , CoRR abs/1902.06075 · 1902
Earlier work this paper cites.
V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. P. Lillicrap, T. Harley, D. Silver, K. Kavukcuoglu, Asynchronous methods for deep reinforcement learning, in: Proceedings of the 33rd International Conference on Machine Learning (ICML), 2016, pp. 1928–1937
1937
Earlier work this paper cites.
J. Veness, D. Silver, A. Blair, W. Uther, Bootstrapping from game tree search, in: Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, A. Culotta (Eds.), Advances in Neural Information Processing Systems 22, Curran Associates, Inc., 2009, pp. 1937–1945
1945
Earlier work this paper cites.
H. P. Grice, Logic and conversation, in: P. Cole, J. L. Morgan (Eds.), Syntax and semantics, Vol. 3, New York: Academic Press, 1975
1975
Earlier work this paper cites.
D. Premack, G. Woodruff, Does the chimpanzee have a theory of mind?, Behavioral and Brain Sciences 1 (1978) 515–526
1978
Earlier work this paper cites.
V. P. Crawford, J. Sobel, Strategic information transmission , Econometrica 50 (6) (1982) 1431–1451. URL http://www.jstor.org/stable/1913390
1982
Earlier work this paper cites.
D. C. Dennett, The Intentional Stance, The MIT Press, Cambridge, MA, 1987
1987
Earlier work this paper cites.
M. L. Littman, Markov games as a framework for multi-agent reinforcement learning, in: In Proceedings of the Eleventh International Conference on Machine Learning, Morgan Kaufmann, 1994, pp. 157–163
1994
Earlier work this paper cites.
G. Tesauro, Temporal difference learning and TD-Gammon, Communications of the ACM 38 (3) (1995) 58–68
1995
Earlier work this paper cites.
J. Schaeffer, R. Lake, P. Lu, M. Bryant, Chinook the world man-machine checkers champion, AI Magazine 17 (1) (1996) 21
1996
Earlier work this paper cites.
J. Baxter, A. Tridgell, L. Weaver, Knightcap: a chess program that learns by combining TD(lambda) with game-tree search, in: Proceedings of the 15th International Conference on Machine Learning, Morgan Kaufmann, 1998, pp. 28–36
1998
Earlier work this paper cites.
M. Campbell, A. J. Hoane Jr, F.-h. Hsu, Deep blue, Artificial intelligence 134 (1-2) (2002) 57–83
2002
Earlier work this paper cites.
doi:10.1287/moor.27.4.819.297
D. S. Bernstein, R. Givan, N. Immerman, S. Zilberstein, The complexity of decentralized control of markov decision processes , Math. Oper. Res. 27 (4) (2002) 819–840 · 2002
Earlier work this paper cites.
M. Bowling, M. Veloso, Simultaneous adversarial multi-robot learning, in: IJCAI, Vol. 3, 2003, pp. 699–704
2003
Earlier work this paper cites.
doi:10.1007/s10458-005-2631-2
L. Panait, S. Luke, Cooperative multi-agent learning: The state of the art , Autonomous Agents and Multi-Agent Systems 11 (3) (2005) 387–434 · 2005
Earlier work this paper cites.
L. Kocsis, C. Szepesvári, Bandit based Monte-Carlo planning, 2006, pp. 282–293
2006
Earlier work this paper cites.
D. Lewis, Convention: A philosophical study, John Wiley & Sons, 2008
2008
Earlier work this paper cites.
L. Busoniu, R. Babuska, B. D. Schutter, A comprehensive survey of multiagent reinforcement learning, IEEE Transaction on Systems, Man, and Cybernetics, Part C: Applications and Reviews 38 (2) (2008) 156–172
2008
Earlier work this paper cites.
M. Zinkevich, M. Johanson, M. Bowling, C. Piccione, Regret minimization in games with incomplete information, in: Advances in Neural Information Processing Systems 20 (NIPS 2007), 2008
2008
Earlier work this paper cites.
W. Yoshida, R. J. Dolan, K. J. Friston, Game theory of mind, PLOS Computational Biology 4 (12) (2008) 1–14
2008
Earlier work this paper cites.
Y. Shoham, K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009
2009
Earlier work this paper cites.
doi:https://doi.org/10.1016/j.cognition.2011.10.004
S. T. Piantadosi, H. Tily, E. Gibson, The communicative function of ambiguity in language , Cognition 122 (3) (2012) 280 – 291 · 2011
Earlier work this paper cites.
P. I. Cowling, E. J. Powley, D. Whitehouse, Information set Monte Carlo tree search, IEEE Transactions on Computational Intelligence and AI in Games 4 (2012) 120–143
2012
Earlier work this paper cites.
L. Matignon, G. J. Laurent, N. L. Fort-Piat, Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems, The Knowledge Engineering Review 27 (01) (2012) 1–31
2012
Earlier work this paper cites.
A. Nowé, P. Vrancx, Y.-M. D. Hauwere, Game theory and multi-agent reinforcement learning, in: Reinforcement Learning: State-of-the-Art, Springer, 2012, Ch. 14, pp. 441–470
2012
Earlier work this paper cites.

Similar

arXiv:http://science.sciencemag.org/content/336/6084/998.full.pdf
M. C. Frank, N. D. Goodman, Predicting pragmatic reasoning in language games , Science 336 (6084) (2012) 998–998 · 2012
Cited alongside, same era.
M. G. Bellemare, Y. Naddaf, J. Veness, M. Bowling, The Arcade Learning Environment: An evaluation platform for general agents, Journal of Artificial Intelligence Research 47 (2013) 253–279
2013
Cited alongside, same era.
N. Burch, M. Johanson, M. Bowling, Solving imperfect information games using decomposition , in: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014, pp. 602–608. URL http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8407
2014
Cited alongside, same era.
B. Wymann, C. Dimitrakakis, A. Sumner, E. Espié, C. Guionneau, Torcs : The open racing car simulator (2015)
2015
Cited alongside, same era.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., Human-level control through deep reinforcement learning, Nature 518 (7540) (2015) 529–533
2015
Cited alongside, same era.
C. Cox, J. D. Silva, P. Deorsey, F. H. J. Kenter, T. Retter, J. Tobin, How to make the perfect fireworks display: Two strategies for Hanabi, Mathematics Magazine 88 (5) (2015) 323–336
2015
Cited alongside, same era.
H. Osawa, Solving Hanabi: Estimating hands by opponent’s actions in cooperative game with incomplete information, in: Proceedings on the 2015 AAAI Workshop on Computer Poker and Imperfect Information, 2015, pp. 37–43
2015
Cited alongside, same era.
D. Bloembergen, K. Tuyls, D. Hennes, M. Kaisers, Evolutionary dynamics of multi-agent learning: A survey, J. Artif. Intell. Res. (JAIR) 53 (2015) 659–697
2015
Cited alongside, same era.
M. Bowling, N. Burch, M. Johanson, O. Tammelin, Heads-up Limit Hold’em Poker is solved, Science 347 (6218) (2015) 145–149
2015
Cited alongside, same era.
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, D. Hassabis, Mastering the game of Go with deep neural networks and tree search, Nature 529 (7587) (2016) 484–489
2016
Cited alongside, same era.
T. Schaul, J. Quan, I. Antonoglou, D. Silver, Prioritized experience replay, in: International Conference on Learning Representations, 2016
2016
Cited alongside, same era.
M. J. H. van den Bergh, A. Hommelberg, W. A. Kosters, F. M. Spieksma, Aspects of the cooperative card game Hanabi, in: BNAIC 2016: Artificial Intelligence. 28th Benelux Conference on Artificial Intelligence, Vol. 765 of CCIS, Springer, Cham, 2016, pp. 93–105
2016
Cited alongside, same era.

Then

E. Pacuit, O. Roy, Epistemic foundations of game theory, in: E. N. Zalta (Ed.), The Stanford Encyclopedia of Philosophy, summer 2017 Edition, Metaphysics Research Lab, Stanford University, 2017
2017
Later among the works it cites.
D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, T. H. Arthur Guez, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, T. Graepel, D. Hassabis, Mastering the game of Go without human knowledge, Nature 550 (2017) 354–359
2017
Later among the works it cites.
H. de Vries, F. Strub, S. Chandar, O. Pietquin, H. Larochelle, A. Courville, Guesswhat?! visual object discovery through multi-modal dialogue, in: IEEE Conference on Computer Vision and Pattern Recognition, 2017
2017
Later among the works it cites.
J. R. Wright, K. Leyton-Brown, Predicting human behavior in unrepeated, simultaneous-move games, Games and Economic Behavior 106 (2017) 16–37
2017
Later among the works it cites.
M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Perolat, D. Silver, T. Graepel, A unified game-theoretic approach to multiagent reinforcement learning, in: Advances in Neural Information Processing Systems, 2017
2017
Later among the works it cites.
N. C. Rabinowitz, F. Perbet, H. F. Song, C. Zhang, S. M. A. Eslami, M. Botvinick, Machine theory of mind , in: Proceedings of the 35th International Conference on Machine Learning (ICML), 2018, pp. 4215–4224. URL http://proceedings.mlr.press/v80/rabinowitz18a.html
2018
Later among the works it cites.
Board Game Arena, Board game arena: Play board games online!, https://en.boardgamearena.com/#!gamepanel?game=hanabi , [Online; accessed 5-December-2018] (2018)
2018
Later among the works it cites.
N. Brown, T. Sandholm, Superhuman AI for heads-up no-limit poker: Libratus beats top professionals, Science 359 (6374) (2018) 418–424
2018
Later among the works it cites.
A. Iraci, Conventions for hanabi, http://hanabi.pythonanywhere.com/static/Hanabi.pdf , [Online; accessed 17-October-2019] (2018)
2018
Later among the works it cites.
J. Nesta, Github - zamiell/hanabi-conventions: Hanabi conventions for the hyphen-ated group, https://github.com/Zamiell/hanabi-conventions , [Online; accessed 5-December-2018] (2018)
2018
Later among the works it cites.
M. C. Machado, M. G. Bellemare, E. Talvitie, J. Veness, M. Hausknecht, M. Bowling, Revisiting the Arcade Learning Environment: Evaluation protocols and open problems for general agents, Journal of Artificial Intelligence Research 61 (2018) 523–562
2018
Later among the works it cites.
E. T. Gottwald, M. Eger, C. Martens, I see what you see: Integrating eye tracking into hanabi playing agents , in: Joint Proceedings of the AIIDE 2018 Workshops co-located with 14th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2018), 2018. URL http://ceur-ws.org/Vol-2282/EXAG_112.pdf
2018
Later among the works it cites.
A. O’Dwyer, Github - quuxplusone/hanabi: Framework for writing bots that play hanabi, https://github.com/Quuxplusone/Hanabi , [Online; accessed 19-September-2018] (2018)
2018
Later among the works it cites.
J. Wu, Github - wuthefwasthat/hanabi.rs: Hanabi simulation in rust, https://github.com/WuTheFWasThat/hanabi.rs , [Online; accessed 29-November-2018] (2018)
2018
Later among the works it cites.
D. Wu, Github - lightvector/fireflower: A rewrite of hanabi-bot in scala, https://github.com/lightvector/fireflower , [Online; accessed 3-December-2018] (2018)
2018
Later among the works it cites.
J. Walton-Rivers, P. Williams, CIG 2018 Hanabi fireworks competition, http://hanabi.aiclash.com/ , https://project.dke.maastrichtuniversity.nl/cig2018/competitions/ , retrieved Sept. 27th, 2018 (2018)
2018
Later among the works it cites.
R. Canaan, H. Shen, R. R. Torrado, J. Togelius, A. Nealen, S. Menzel, Evolving agents for the hanabi 2018 CIG competition, in: IEEE Conference on Computational Intelligence and Games (CIG), 2018, pp. 1–8
2018
Later among the works it cites.
R. Sutton, A. Barto, Reinforcement Learning: An Introduction, 2nd Edition, MIT Press, 2018
2018
Later among the works it cites.
doi:10.1126/science.aar6404
D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, D. Hassabis, A general reinforcement learning algorithm that masters chess, shogi, and go through self-play , Science 362 (6419) (2018) 1140–1144 · 2018
Later among the works it cites.
S. V. Albrecht, P. Stone, Autonomous agents modelling other agents: A comprehensive survey and open problems, Artificial Intelligence 258 (2018) 66–95
2018
Later among the works it cites.
A. Grover, M. Al-Shedivat, J. K. Gupta, Y. Burda, H. Edwards, Learning policy representations in multiagent systems, in: Proceedings of the International Conference on Machine Learning (ICML), 2018
2018
Later among the works it cites.
The Hanabi Learning Environment, https://github.com/deepmind/hanabi-learning-environment , [Online; accessed 1-February-2019] (2019)
2019
Closest in time.
doi:10.1126/science.aau6249
M. Jaderberg, W. M. Czarnecki, I. Dunning, L. Marris, G. Lever, A. G. Castañeda, C. Beattie, N. C. Rabinowitz, A. S. Morcos, A. Ruderman, N. Sonnerat, T. Green, L. Deason, J. Z. Leibo, D. Silver, D. Hassabis, K. Kavukcuoglu, T. Graepel, Human-level performance in 3d multiplayer games with population-based reinforcement learning , Science 364 (6443) (2019) 859–865 · 2019
Closest in time.
doi:10.1145/3290605.3300325
C. Liang, J. Proft, E. Andersen, R. A. Knepper, Implicit communication of actionable information in human-ai teams , in: Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems, 2019 · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…