More Like this

1. Playing to Wait: A Taxonomy of Idle Games

   https://doi.org/10.1145/3173574.3174195  

   Alharthi, Sultan A.; Alsaedi, Olaa; Toups Dugas, Phoebe O.; Tanenbaum, Theresa Jean; Hammer, Jessica (January 2018, Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems)

   Idle games are a recent minimalist gaming phenomenon in which the game is left running with little player interaction. We deepen understanding of idle games and their characteristics by developing a taxonomy and identifying game features. This paper examines 66 idle games using a grounded theory approach to analyze play, game mechanics, rewards, interactivity, progress rate, and user interface. To establish a clearly bounded definition of idle games, we analyzed 10 non-idle games with the same approach. We discuss how idle games move players from playing to planning, how they question dominant assumptions about gameplay, and their unusual use of resources such as player attention and computer cycles. Our work illuminates opportunities for the design of idle games, suggests design implications, and provides a framework for researchers to clearly articulate questions about this genre. 

   more » « less
2. Instance-dependent Sample Complexity Bounds for Zero-sum Matrix Games

   Maiti, Arnab; Jamieson, Kevin; Ratliff, Lillian J. (January 2023, Proceedings of Machine Learning Research)

   Francisco Ruiz, Jennifer Dy (Ed.)

   We study the sample complexity of identifying an approximate equilibrium for two-player zero-sum n × 2 matrix games. That is, in a sequence of repeated game plays, how many rounds must the two players play before reaching an approximate equilibrium (e.g., Nash)? We derive instance-dependent bounds that define an ordering over game matrices that captures the intuition that the dynamics of some games converge faster than others. Specifically, we consider a stochastic observation model such that when the two players choose actions i and j, respectively, they both observe each other’s played actions and a stochastic observation Xij such that E [Xij ] = Aij . To our knowledge, our work is the first case of instance-dependent lower bounds on the number of rounds the players must play before reaching an approximate equilibrium in the sense that the number of rounds depends on the specific properties of the game matrix A as well as the desired accuracy. We also prove a converse statement: there exist player strategies that achieve this lower bound. 

   more » « less
3. “Press Space To Fire”: Automatic Video Game Tutorial Generation

   Green, Michael Cerny; Khalifa, Ahmed; Barros, Gabriella A.; Togelius, Julian (January 2017, Workshop on Experimental AI in Games)

   We propose the problem of tutorial generation for games, i.e. to generate tutorials which can teach players to play games, as an AI problem. This problem can be approached in several ways, including generating natural language descriptions of game rules, generating instructive game levels, and generating demonstrations of how to play a game using agents that play in a human-like manner. We further argue that the General Video Game AI framework provides a useful testbed for addressing this problem. 

   more » « less
4. Simple Uncoupled No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium

   Farina, G.; Celli, A.; Marchesi, A.; Gatti, N. (January 2021, ArXivorg)

   null (Ed.)

   The existence of simple uncoupled no-regret learning dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form games generalize normal-form games by modeling both sequential and simultaneous moves, as well as imperfect information. Because of the sequential nature and presence of private information in the game, correlation in extensive-form games possesses significantly different properties than its counterpart in normal-form games, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to the classical notion of correlated equilibrium in normal-form games. Compared to the latter, the constraints that define the set of EFCEs are significantly more complex, as the correlation device must keep into account the evolution of beliefs of each player as they make observations throughout the game. Due to that significant added complexity, the existence of uncoupled learning dynamics leading to an EFCE has remained a challenging open research question for a long time. In this article, we settle that question by giving the first uncoupled no-regret dynamics that converge to the set of EFCEs in n-player general-sum extensive-form games with perfect recall. We show that each iterate can be computed in time polynomial in the size of the game tree, and that, when all players play repeatedly according to our learning dynamics, the empirical frequency of play is proven to be a O(T^-0.5)-approximate EFCE with high probability after T game repetitions, and an EFCE almost surely in the limit. 

   more » « less
5. Paper to Pixels: A Chronicle of Map Interfaces in Games

   https://doi.org/10.1145/3357236.3395502  

   Toups Dugas, Phoebe O.; LaLone, Nicolas; Spiel, Katta; Hamilton, Bill (July 2020, Proceedings of the 2020 ACM Designing Interactive Systems Conference)

   Game map interfaces provide an alternative perspective on the worlds players inhabit.compared to navigation applications popular in day-to-day life, game maps have different affordances to match players' situated goals. To contextualize and understand these differences and how they developed, we present a historical chronicle of game map interfaces. Starting from how games came to involve maps, we trace how maps are first separate from the game, becoming more and more integrated into play until converging in smartphone-style interfaces. We synthesize several game history texts with critical engagement with 123 key games to develop this map-focused chronicle, from which we highlight trends and opportunities for future map designs. Our work contributes a record of trends in game map interfaces that can serve as a source of reference and inspiration to game designers, digital physical-world map designers, and game scholars. 

   more » « less