Real World Games Look Like Spinning Tops

• URL: http://arxiv.org/abs/2004.09468v2
• Date: Wed, 17 Jun 2020 15:41:23 GMT
• Title: Real World Games Look Like Spinning Tops
• Authors: Wojciech Marian Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafiei, David Balduzzi, Max Jaderberg
• Abstract summary: This paper investigates the geometrical properties of real world games (e.g. Tic-Tac-Toe, Go, StarCraft II) We hypothesise that their geometrical structure resemble a spinning top. We prove the existence of this geometry for a wide class of real world games, exposing their temporal nature. We show that this unique structure also has consequences for learning - it clarifies why populations of strategies are necessary for training of agents, and how population size relates to the structure of the game.
• Score: 27.182163984605193
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper investigates the geometrical properties of real world games (e.g. Tic-Tac-Toe, Go, StarCraft II). We hypothesise that their geometrical structure resemble a spinning top, with the upright axis representing transitive strength, and the radial axis, which corresponds to the number of cycles that exist at a particular transitive strength, representing the non-transitive dimension. We prove the existence of this geometry for a wide class of real world games, exposing their temporal nature. Additionally, we show that this unique structure also has consequences for learning - it clarifies why populations of strategies are necessary for training of agents, and how population size relates to the structure of the game. Finally, we empirically validate these claims by using a selection of nine real world two-player zero-sum symmetric games, showing 1) the spinning top structure is revealed and can be easily re-constructed by using a new method of Nash clustering to measure the interaction between transitive and cyclical strategy behaviour, and 2) the effect that population size has on the convergence in these games.

Related papers

• Sink equilibria and the attractors of learning in games [0.0]
  Characterizing the limit behavior -- that is, the attractors -- of learning dynamics is one of the most fundamental open questions in game theory. We show through a topological construction that the one-to-one conjecture is false. Second, we make progress on the attractor characterization problem for two-player games by establishing that the one-to-one conjecture is true.
  arXiv  Detail & Related papers  (2025-02-11T21:40:11Z)
• Representation Learning of Geometric Trees [9.280083998326285]
  We introduce a new representation learning framework tailored for geometric trees. It first features a unique message passing neural network, which is both provably geometrical structure-recoverable and rotation-translation invariant. We validate our method's effectiveness on eight real-world datasets, demonstrating its capability to represent geometric trees.
  arXiv  Detail & Related papers  (2024-08-16T15:16:35Z)
• Communication Complexity of Graph Isomorphism, Coloring, and Distance Games [0.0]
  We show that perfect non-signalling strategies collapse communication complexity under favorable conditions. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies.
  arXiv  Detail & Related papers  (2024-06-04T10:53:16Z)
• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• Ordinal Potential-based Player Rating [6.454304238638547]
  We show that Elo ratings do preserve transitivity when computed in the right space. We introduce a new game decomposition that prioritises capturing the sign pattern of the game. We link our approach to the known concept of sign-rank, and evaluate our methodology using both toy examples and empirical data from real-world games.
  arXiv  Detail & Related papers  (2023-06-08T17:08:52Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Neural Convolutional Surfaces [59.172308741945336]
  This work is concerned with a representation of shapes that disentangles fine, local and possibly repeating geometry, from global, coarse structures. We show that this approach achieves better neural shape compression than the state of the art, as well as enabling manipulation and transfer of shape details.
  arXiv  Detail & Related papers  (2022-04-05T15:40:11Z)
• Navigating the Landscape of Multiplayer Games [20.483315340460127]
  We show how network measures applied to response graphs of large-scale games enable the creation of a landscape of games. We illustrate our findings in domains ranging from canonical games to complex empirical games capturing the performance of trained agents pitted against one another.
  arXiv  Detail & Related papers  (2020-05-04T16:58:17Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  We show how adapting the reward can give strong convergence guarantees in monotone games. We also show how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium.
  arXiv  Detail & Related papers  (2020-02-19T21:36:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.