Rolling Horizon Evolutionary Algorithms for General Video Game Playing

• URL: http://arxiv.org/abs/2003.12331v2
• Date: Mon, 24 Aug 2020 14:03:28 GMT
• Title: Rolling Horizon Evolutionary Algorithms for General Video Game Playing
• Authors: Raluca D. Gaina, Sam Devlin, Simon M. Lucas, Diego Perez-Liebana
• Abstract summary: Rolling Horizon Evolutionary Algorithms have recently managed to beat the state of the art in win rate across many video games. This paper presents the state of the art in Rolling Horizon Evolutionary Algorithms, combining all modifications described in literature, as well as new ones, for a large hybrid. We then use a parameter optimiser, the N-Tuple Bandit Evolutionary Algorithm, to find the best combination of parameters in 20 games from the General Video Game AI Framework.
• Score: 4.560263516804932
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Game-playing Evolutionary Algorithms, specifically Rolling Horizon Evolutionary Algorithms, have recently managed to beat the state of the art in win rate across many video games. However, the best results in a game are highly dependent on the specific configuration of modifications and hybrids introduced over several papers, each adding additional parameters to the core algorithm. Further, the best previously published parameters have been found from only a few human-picked combinations, as the possibility space has grown beyond exhaustive search. This paper presents the state of the art in Rolling Horizon Evolutionary Algorithms, combining all modifications described in literature, as well as new ones, for a large resultant hybrid. We then use a parameter optimiser, the N-Tuple Bandit Evolutionary Algorithm, to find the best combination of parameters in 20 games from the General Video Game AI Framework. Further, we analyse the algorithm's parameters and some interesting combinations revealed through the optimisation process. Lastly, we find new state of the art solutions on several games by automatically exploring the large parameter space of RHEA.

Related papers

• Runtime analysis of a coevolutionary algorithm on impartial combinatorial games [1.104960878651584]
  Coevolutionary algorithms (CoEAs) evolve a population of individuals by iteratively selecting the strongest based on their interactions against contemporaries, and using those selected as parents for the following generation. However, the successful application of CoEAs for game playing is difficult due to pathological behaviours such as cycling, an issue especially critical for games with in runtime payoff landscapes. In this paper, we push the scope of analysis to discover an optimal strategy for an impartial game. This result applies to any impartial game, and for many games the implied bound is or quasipolynomial as a function of the number of
  arXiv  Detail & Related papers  (2024-09-06T10:39:17Z)
• Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics [9.044970217182117]
  We show that a biased random-key genetic algorithm (BRKGA) with two simple modifications obtains significantly better results. We then add a natural greedy, namely to repeatedly discard small-degree vertices that are not necessary for reaching the whole graph. The resulting algorithm consistently outperforms all of the state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2024-04-05T11:02:02Z)
• 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)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence [81.3266426402464]
  We show that the state-wise average policy of this algorithm converges to an approximate Nash equilibrium (NE) of the game. We extend this algorithm to multi-player general Markov Games and show a $mathcalwidetildeO(T-1/2)$ convergence rate to Correlated Equilibria (CCE)
  arXiv  Detail & Related papers  (2022-06-06T14:23:13Z)
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation [78.48747645545944]
  We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games. We introduce a new algorithm for computing optimal equilibria in all three notions.
  arXiv  Detail & Related papers  (2022-03-14T15:21:18Z)
• Battle royale optimizer with a new movement strategy [0.0]
  This paper proposes a modified BRO (M-BRO) in order to improve balance between exploration and exploitation. The complexity of this modified algorithm is the same as the original one. The results show that BRO with additional movement operator performs well to solve complex numerical optimization problems.
  arXiv  Detail & Related papers  (2022-01-19T16:36:13Z)
• Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
  This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. Provably efficient algorithms for both decoupled and coordinated settings are developed.
  arXiv  Detail & Related papers  (2021-07-30T15:25:13Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  We study last-iterate convergence of optimistic algorithms in sequential games. We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
  arXiv  Detail & Related papers  (2021-06-27T22:02:26Z)
• Portfolio Search and Optimization for General Strategy Game-Playing [58.896302717975445]
  We propose a new algorithm for optimization and action-selection based on the Rolling Horizon Evolutionary Algorithm. For the optimization of the agents' parameters and portfolio sets we study the use of the N-tuple Bandit Evolutionary Algorithm. An analysis of the agents' performance shows that the proposed algorithm generalizes well to all game-modes and is able to outperform other portfolio methods.
  arXiv  Detail & Related papers  (2021-04-21T09:28:28Z)
• Generating and Blending Game Levels via Quality-Diversity in the Latent Space of a Variational Autoencoder [7.919213739992465]
  We present a level generation and game blending approach that combines the use of VAEs and QD algorithms. Specifically, we train VAEs on game levels and then run the MAP-Elites QD algorithm using the learned latent space of the VAE as the search space.
  arXiv  Detail & Related papers  (2021-02-24T18:44:23Z)
• Rolling Horizon NEAT for General Video Game Playing [1.160208922584163]
  This paper presents a new Statistical Forward Planning (SFP) method, Rolling Horizon NeuroEvolution of Augmenting Topologies (rhNEAT) Unlike traditional Rolling Horizon Evolution, rhNEAT evolves weights and connections of a neural network in real-time, planning several steps ahead before returning an action to execute in the game.
  arXiv  Detail & Related papers  (2020-05-14T07:25:23Z)

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.