AAMAS 2018 Tutorial
From Game Theory to AI in Games
Agents are core entities existent in all games; from game theoretical abstract games to fully fledged complex digital games. How do these agents play these games? How can we model their play? How do we view their interactions with opponents (albeit they are friends or foes, humans or AIs)?
To address the above questions, in this tutorial we use the principles of agent modeling and machine learning as overarching elements for connecting Game Theory to AI in digital games. The relationship between game theory and gameplay is strong but far from being explored extensively. On the one hand, game theory studies mathematical models of rational decision makers within abstract games, for the analysis of economic or social behavior in adversarial or cooperative settings. More specifically, game theory focuses on characterizing or predicting the actions of rational or bounded-rational agents, and studies the related emerging “game solution concepts” such as the celebrated Nash equilibrium. On the other hand, popular board games such as Go and complex digital games such as StarCraft offer unique opportunities for the study of agent modeling, machine learning and artificial intelligence at large.
In this tutorial we attempt to incorporate foundational ideas and concepts from game theory and multiagent systems research in the game AI field. Particular game AI areas such as gameplaying and player (or opponent) modeling could benefit from theoretical models of game-playing and empirical implementations of agent-based systems. Similarly, we argue that game AI research and practice can only help in advancing work on theoretical game theory and multiagent systems.
Interweaving these fields properly with the current stream of game AI research is a non-trivial exercise, given the different focus and paths these fields have taken. Further, there are limits to the degrees theoretical models can capture the complexity of games covered in game AI. These are the gaps our tutorial attempts to bridge by bringing successful examples of their interrelationship forward. Some instances of Game Theory that found successful applications in game AI include the various implementations of theoretical models for playing abstract, card and board games.
The structure of the tutorial covers the following topics:
Part I: From Game Theory...
- Game Theory: providing the cornerstones of rationality
- From rational choice theory to game theory
- Basic game-theoretic solution concepts: Nash equilibria, Pareto efficiency, the Core
- Testing Game-Theoretic concepts in Multi-Player Game Environments
- Multi-agent competitions
- Lessons learned
- Learning in Games
- Converging to Equilibria
- Fictitious play and evolutionary models
- Beyond Playing Equilibria
- Reinforcement learning and multiagent reinforcement learning
- Alternative machine learning paradigms for learning in games
- Converging to Equilibria
Part II: ...to AI in Games
- Taxonomy of play in digital games
- Characteristics of games and their design
- Design considerations for AI algorithms that play games
- Popular AI methods for playing Games
- Monte Carlo tree search, reinforcement learning, supervised learning, Chimeric methods
- AI across game genres
- Board, card, arcade, strategy, casual, shooter, fighting, and serious games
- Procedural personas
- Agents as means for procedurally generating game content
- Humans as agents in games
- Modeling behavior and playing experience
The potential target audience includes: (a) young graduate or PhD-level researchers in the areas of Game Theory, Learning, and Artificial Intelligence in Games; and (b) senior researchers in oneof these areas who wish to strengthen their ability to do work on the intersection of these fields. The main topic of the tutorial is expected to be appealing to a larger audience interested in the research crossroads of theoretical game theory and its practical application to digital games.
The tutorial assumes participants have a basic background knowledge on game theory, machine learning and optimization.
You can download the presentation slides through the following link:From Game Theory to AI in Games
Why This Tutorial Is of Interest to AAMAS
The tutorial spans topics relating to Game Theory and Learning, two major AAMAS areas. Moreover, it links those to topics relating to AI for Digital Games, an area that has attracted much interest (in terms of research and practical applications) in recent years. As such, we believe that the tutorial can help the cross-fertilization of ideas originating in these traditionally AAMAS and non-AAMAS research areas
In particular, topics of interest include (but are not limited to) the following topics listed in the AAMAS-2018 call for papers:
- Agent Cooperation (e.g., Biologically-inspired methods, teamwork, team formation)
- Humans and Agents (e.g., Human-agent interaction, Multi-user-agent interaction, Agents competing against humans)
- Learning and Adaptation (e.g., Reward structures for learning, Evolutionary algorithms, Multi-agent learning, Deep learning, Adversarial machine learning, Learning agent capabilities, Learning agent-to-agent interactions)
- Economic Paradigms (e.g., Bargaining and negotiation, Cooperative games: theory & analysis, Cooperative games: computation, Non-cooperative games: theory & analysis, Game theory for practical applications)
The tutorial presenters are recognized experts in their fields of academic interest. In particular, Chalkiadakis, a regular AAMAS attendee, is a co-author (along with Michael Wooldridge and Edith Elkind) of the graduate level textbook Computational Aspects of Cooperative Game Theory. Yannakakis, on the other hand, is a recognised figure within the AI and Games research community and the co-author of the recent AI and Games textbook.
Georgios Chalkiadakis is an Associate Professor at the School of Electical and Computer Engineering, Technical University of Crete (TUC). His research interests are in the areas of multiagent systems, algorithmic game theory, and learning; and more specifically, in coalition formation, decision making under uncertainty, and reinforcement learning in multiagent domains. His PhD thesis (University of Toronto, 2007) was nominated for the IFAAMAS-2007 Victor Lesser Distinguished Dissertation Award. Before joining TUC, he was a Research Fellow at the School of Electronics and Computer Science, University of Southampton, UK; and has also worked as a software engineer at the Institute of Computer Science of the Foundation for Research and Technology - Hellas, and as a teacher of informatics in Greek high schools. Georgios has served in the Organizing Committee of several workshops in top AI and MAS international conferences; and has organised and chaired two AI/MAS summer schools. Georgios has been teaching multiagent systems and AI courses (undergraduate and graduate level) at TUC since 2011. Moreover, he has presented or co-presented tutorials on cooperative game theory at AAMAS-09, AAMAS-10, AAAI-10, AAMAS-2011, IJCAI-2011, AAMAS-2012, SETN-2016, EASSS-2017. More details on Georgios Chalkiadakis can be found at his web page: intelligence.tuc.gr/~gehalk
Georgios N. Yannakakis is a Professor and Director of the Institute of Digital Games, University of Malta. He is a leading expert of the game artificial intelligence research field with core theoretical contributions in machine learning, evolutionary computation, affective computing and player modelling, computational creativity and procedural content generation. He has published more than 200 papers and his work has been cited broadly. He has attracted funding from several EU (mainly FP7, H2020) and national research projects and received multiple awards for published work in top-tier journals and conferences. His work has been featured in New Scientist, Science Magazine, The Guardian, Le Monde and other venues. He is regularly invited to give keynote talks and tutorials in the most recognised conferences in his areas of research activity and has organized a few of the most respected conferences in the areas of game AI and game research. He is an Associate Editor of IEEE Transactions on Games and was an Associate Editor of the IEEE Transactions on Affective Computing (2009–2016) and the IEEE Transactions on Computational Intelligence and AI in Games (2009-2017). He has presented tutorials in IEEE CIG (in 2008, 2011 and 2014), ACII (2009), IEEE GIC (2009) conferences and at the recent DeepLearn Summer School (2017). More details on Georgios N. Yannakakis can be found at his web page: yannakakis.net