skip to main content

Title: Estimates for the Branching Factors of Atari Games
The branching factor of a game is the average number of new states reachable from a given state. It is a widely used metric in AI research on board games, but less often computed or discussed for videogames. This paper provides estimates for the branching factors of 103 Atari 2600 games, as implemented in the Arcade Learning Environment (ALE). Depending on the game, ALE exposes between 3 and 18 available actions per frame of gameplay, which is an upper bound on branching factor. This paper shows, based on an enumeration of the first 1 million distinct states reachable in each game, that the average branching factor is usually much lower, in many games barely above 1. In addition to reporting the branching factors, this paper aims to clarify what constitutes a distinct state in ALE.  more » « less
Award ID(s):
Author(s) / Creator(s):
Date Published:
Journal Name:
Proceedings of the 2021 IEEE Conference on Games
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer’s (or, in another version Kakutani’s) fixed point theorem, the most sophisticated result in his era’s topology—in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept—this notion of “the outcome of the game”—every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games. 
    more » « less
  2. null (Ed.)
    This paper considers a class of linear-quadratic-Gaussian (LQG) mean-field games (MFGs) with partial observation structure for individual agents. Unlike other literature, there are some special features in our formulation. First, the individual state is driven by some common-noise due to the external factor and the state-average thus becomes a random process instead of a deterministic quantity. Second, the sensor function of individual observation depends on state-average thus the agents are coupled in triple manner: not only in their states and cost functionals, but also through their observation mechanism. The decentralized strategies for individual agents are derived by the Kalman filtering and separation principle. The consistency condition is obtained which is equivalent to the wellposedness of some forward-backward stochastic differential equation (FBSDE) driven by common noise. Finally, the related ϵ-Nash equilibrium property is verified. 
    more » « less
  3. In the classical discrete Colonel Blotto game—introducedby Borel in 1921—two colonels simultaneously distributetheir troops across multiple battlefields. The winner of eachbattlefield is determined by a winner-take-all rule, independentlyof other battlefields. In the original formulation, eachcolonel’s goal is to win as many battlefields as possible. TheBlotto game and its extensions have been used in a widerange of applications from political campaign—exemplifiedby the U.S presidential election—to marketing campaign,from (innovative) technology competition to sports competition.Despite persistent efforts, efficient methods for findingthe optimal strategies in Blotto games have been elusivefor almost a century—due to exponential explosion inthe organic solution space—until Ahmadinejad, Dehghani,Hajiaghayi, Lucier, Mahini, and Seddighin developed thefirst polynomial-time algorithm for this fundamental gametheoreticalproblem in 2016. However, that breakthroughpolynomial-time solution has some structural limitation. Itapplies only to the case where troops are homogeneous withrespect to battlegruounds, as in Borel’s original formulation:For each battleground, the only factor that matters to the winner’spayoff is how many troops as opposed to which sets oftroops are opposing one another in that battleground.In this paper, we consider a more general setting of thetwo-player-multi-battleground game, in which multifacetedresources (troops) may have different contributions to differentbattlegrounds. In the case of U.S presidential campaign,for example, one may interpret this as different typesof resources—human, financial, political—that teams can investin each state. We provide a complexity-theoretical evidencethat, in contrast to Borel’s homogeneous setting, findingoptimal strategies in multifaceted Colonel Blotto gamesis intractable. We complement this complexity result witha polynomial-time algorithm that finds approximately optimalstrategies with provable guarantees. We also study a furthergeneralization when two competitors do not have zerosum/constant-sum payoffs. We show that optimal strategiesin these two-player-multi-battleground games are as hard tocompute and approximate as Nash equilibria in general noncooperative games and economic equilibria in exchange markets. 
    more » « less
  4. Abstract

    We consider 3XOR games with perfect commuting operator strategies. Given any 3XOR game, we show existence of a perfect commuting operator strategy for the game can be decided in polynomial time. Previously this problem was not known to be decidable. Our proof leads to a construction, showing a 3XOR game has a perfect commuting operator strategy iff it has a perfect tensor product strategy using a 3 qubit (8 dimensional) GHZ state. This shows that for perfect 3XOR games the advantage of a quantum strategy over a classical strategy (defined by the quantum-classical bias ratio) is bounded. This is in contrast to the general 3XOR case where the optimal quantum strategies can require high dimensional states and there is no bound on the quantum advantage. To prove these results, we first show equivalence between deciding the value of an XOR game and solving an instance of the subgroup membership problem on a class of right angled Coxeter groups. We then show, in a proof that consumes most of this paper, that the instances of this problem corresponding to 3XOR games can be solved in polynomial time.

    more » « less
  5. Creating engaging interactive story-based experiences dynamically responding to individual player choices poses significant challenges for narrative-centered games. Recent advances in pre-trained large language models (LLMs) have the potential to revolutionize procedural content generation for narrative-centered games. Historically, interactive narrative generation has specified pivotal events in the storyline, often utilizing planning-based approaches toward achieving narrative coherence and maintaining the story arc. However, manual authorship is typically used to create detail and variety in non-player character (NPC) interaction to specify and instantiate plot events. This paper proposes SCENECRAFT, a narrative scene generation framework that automates NPC interaction crucial to unfolding plot events. SCENECRAFT interprets natural language instructions about scene objectives, NPC traits, location, and narrative variations. It then employs large language models to generate game scenes aligned with authorial intent. It generates branching conversation paths that adapt to player choices while adhering to the author’s interaction goals. LLMs generate interaction scripts, semantically extract character emotions and gestures to align with the script, and convert dialogues into a game scripting language. The generated script can then be played utilizing an existing narrative-centered game framework. Through empirical evaluation using automated and human assessments, we demonstrate SCENECRAFT’s effectiveness in creating narrative experiences based on creativity, adaptability, and alignment with intended author instructions.

    more » « less