PaperlayerView exact revision on arXiv

Source-linked AI summary

General Video Game AI: a Multi-Track Framework for Evaluating Agents, Games and Content Generation Algorithms

Diego Perez-Liebana, Jialin Liu, Ahmed Khalifa, Raluca D. Gaina, Julian Togelius, Simon M. Lucas

arXiv:1802.10363v4cs.AI

TL;DR

GVGAI was created to evaluate agents that play multiple unknown games and algorithms that generate game content, addressing the overspecialization of single-game benchmarks. This survey reviews VGDL, the framework’s tracks, and their use in research and competitions, finding broad adoption alongside persistent performance and expressiveness limits.

  • Problem

    Single-game benchmarks can overspecialize agents, creating a need for a common framework that evaluates general game playing and content generation across games.

  • Method

    The paper surveys VGDL, the GVGAI framework, its competition tracks, and community approaches for agent AI and procedural content generation.

  • Results

    GVGAI has become a comprehensive framework used in international competitions to evaluate hundreds of general video game agents and algorithms for creating games and content.

  • Takeaways & Limitations

    The framework supports research across game playing, learning, multi-agent interaction, and procedural generation within a shared evaluation system.

  • Takeaways & Limitations

    VGDL’s limited expressiveness makes human-fun games and complex mechanics difficult to author, constraining the depth of challenges available to agents.

Abstract

from arXiv · show

General Video Game Playing (GVGP) aims at designing an agent that is capable of playing multiple video games with no human intervention. In 2014, The General Video Game AI (GVGAI) competition framework was created and released with the purpose of providing researchers a common open-source and easy to use platform for testing their AI methods with potentially infinity of games created using Video Game Description Language (VGDL). The framework has been expanded into several tracks during the last few years to meet the demand of different research directions. The agents are required either to play multiple unknown games with or without access to game simulations, or to design new game levels or rules. This survey paper presents the VGDL, the GVGAI framework, existing tracks, and reviews the wide use of GVGAI framework in research, education and competitions five years after its birth. A future plan of framework improvements is also described.

I. INTRODUCTION

GVGAI addresses the overspecialization of single-game benchmarks by evaluating agents on unseen games and expanding the challenge to planning, learning, and procedural content generation. The framework uses VGDL to specify games and provides standardized interfaces and tracks for agents and content generators.

  • Motivation: Single-game benchmarks can overspecialize agents to individual games, motivating tests of more general AI capabilities.The paper links this problem to overfitting in agents developed for a single game.
  • Motivation: GVGAI evaluates agents on unseen games, making game-specific engineering difficult and requiring new game sets for each competition event.Agents are developed without knowing the games they will play, and previous games cannot simply be reused.
  • Framework scope: The framework supports game-playing tracks alongside tracks for generating game levels or rules and potential game-prototyping applications.The associated software has been used for mixed-initiative design tools and other game-design research.
  • Framework scope: VGDL is a text language for specifying two-dimensional arcade games, including sprites, properties, interactions, and termination conditions.Its Sprite Set defines game objects and properties, while the Interaction Set regulates their effects.
  • Framework operation: GVGAI parses VGDL files and lets human players or bots interact with any provided VGDL game through a common controller API.Controllers implement INIT, ACT, and RESULT methods, while agents receive game-state information without the VGDL rules.
  • Framework operation: Planning tracks provide a forward model, whereas the learning setting withholds it and supplies game-state information and screen observations for episodic learning.Planning controllers operate under strict per-tick decision limits, while learning agents can also use the OpenAI Gym interface.

III. THE GVGAI COMPETITION

GVGAI competitions evaluate agents across private game sets and multiple tracks, using standardized rankings for game playing and distinct procedures for learning. The learning track has included constrained training and validation phases, with later editions relaxing access and timing conditions.

  • Competition structure: GVGAI competition sets contain 10 games with five levels each, while validation and test sets remain private to participants.Public game sets support training, and submissions are evaluated repeatedly on private test levels after the deadline.
  • Competition structure: Game-playing rankings sort entries per game by victory rate, score, and game length before awarding points across the test set.The overall winner is the submission with the largest total across games.
  • Track evolution: The competition expanded from single-player planning in 2014 to two-player planning in 2016 and later included single-player learning competitions.The two-player track targets environments with more direct player interaction.
  • Learning track: In 2017, learning agents had five minutes to train on the first three levels, while validation used repeated play on levels four and five.The validation results determined competition rankings, and a naive Q-Learning implementation won the track.
  • Learning track: The 2018 learning edition used three public games, two training levels per game, three secret test levels, 100ms decisions, and unrestricted pre-submission training resources.The edition also integrated GVGAI with the OpenAI Gym API as GVGAI Gym3.
  • Learning track: In 2018, only two entries were submitted, and some sample deep-learning agents were not applied to one game because game-screen dimensions differed across levels.The comparison also included the planning agent OLETS, which had access to the forward model.

B. PCG Tracks

GVGAI combines human-evaluated procedural content generation tracks with a broad body of planning-agent research. Reported findings show trade-offs among generator playability, visual preference, search depth, and performance across games.

  • PCG Tracks: PCG competitions ask participants to generate levels or rules for supplied games or levels, with human judges comparing pairs of generated content.Judges may prefer one, both, or neither generated item.
  • Level Generation Track: Four participants entered the 2016 level-generation competition, where the cellular-automata generator Easablade won; the following year received one submission and was canceled.The 2016 entries included three simulation-based generators and one cellular-automata generator.
  • Rule Generation Track: No submissions were received for the Rule Generation track when it was introduced at CIG 2017.Three sample generators were provided and the contest ran for one month.
  • Tree Search Methods: O-MCTS branches only after macro-actions terminate, enabling deeper searches in the same time but outperforming MCTS mainly in small, sparse games.It loses against MC-DTS in the cited comparison.
  • Tree Search Methods: Multi-objective MCTS increased victory rate from 32.24% with normal MCTS to 42.38% in the tested games by jointly optimizing score and exploration.The study treated score and level exploration as simultaneous objectives.
  • Tree Search Methods: IW(1) outperformed MCTS in many games, while IW(2) performed better on puzzles; IW(1) also won the 2015 Single-Player Planning Track.Iterated Width prunes states that do not make a new tuple of at most the specified number of atoms true.
  • Tree Search Methods: Increasing MCTS’s budget by up to 30 times produced only marginal performance gains, indicating that more iterations alone did not solve the framework’s challenges.The study examined whether real-time constraints explained failures to achieve high victory rates.

C. Evolutionary Methods

Evolutionary methods in GVGAI primarily use Rolling Horizon Evolutionary Algorithms to evolve action sequences with a forward model, while studies explore parameterization and state evaluation. Results are mixed: several enhancements improve performance in some settings, but adaptive rollout control can help MCTS while harming RHEA.

  • Rolling Horizon Evolutionary Algorithms: RHEA evolves action sequences as individuals, evaluates their terminal states with the forward model, and executes the first action of the fittest sequence.The process repeats at each time step within the available decision budget.
  • Parameter studies: Higher population sizes and individual lengths produced higher victory rates across 20 representative GVGAI games.This study motivated Random Search as a sample controller equivalent to RHEA with an effectively infinite population.
  • Enhancements: A three-part RHEA-SB variant combining one-step lookahead, redundant-action avoidance, and shifted buffers achieved promising results on 20 single-player games.The tested variants applied one or both enhancements after shifting the population buffer.
  • Enhancements: State-evaluation enhancements using avatar information, spatial exploration, and gameplay knowledge significantly increased RHEA and MCTS win rates and scores on 20 games.The same evaluation enhancements were tested with both agent families.
  • Adaptive rollouts: Fitness-landscape-based adaptation of RHEA individual length harmed RHEA but improved MCTS, while simply increasing rollout length was more effective.Longer rollouts target sparse, delayed rewards; shorter rollouts target dense immediate rewards.
  • Alternative evolutionary methods: Genetic programming can map screen-derived features, including avatar and object positions, to actions through evolved horizontal, vertical, and action-use trees.The approach extracts features from game screenshots and uses arithmetic operands within the trees.

D. Hybrids

Hybrid GVGAI agents combine multiple planning or evolutionary techniques within one algorithm. Reported benefits depend strongly on game and parameter conditions, with several enhancements improving selected settings but others producing marginal or negative gains.

  • Definition: Hybrid methods are defined as algorithms that mix more than one approach within a single agent.The survey distinguishes these from agents whose predominant technique merely includes minor enhancements.
  • Evolutionary hybrids: Seeding RHEA populations with one-step lookahead or MCTS sequences increased victory rates when population size and individual length were small, but benefits vanished at larger values.The seeding methods dedicate part of the decision budget to initializing promising sequences.
  • Evolutionary hybrids: RHEA with rollouts improved performance in many games, whereas additional variants involving MCTS alternatives, sequence planning, occlusion detection, or NPC attitude checks performed worse than sample agents.These results came from comparisons across multiple RHEA variants.
  • MCTS hybrids: Modifications to KB-MCTS produced only marginal improvements, likely due to adding path-finding rather than changing the evolutionary approach.The modifications replaced Euclidean distance with A* path-finding and altered weight aggregation and action selection.
  • MCTS hybrids: Replacing KB-MCTS’s evolutionary weighting with Q-Learning and a grid view improved victory rates across several game sets and achieved the highest average victory rate among compared algorithms.The Q-Learning approach updates rollout-biasing weights at each rollout step.
  • MCTS hybrids: Evolving MCTS tree policies showed that tree policy matters substantially, although most evolved policies performed poorly in the five-game study.A separate policy was evolved for each game to exploit game-specific characteristics.
  • Adaptive hybrids: Self-adaptive MCTS parameter tuning improved performance where vanilla MCTS performed poorly while maintaining similar victory rates where it already performed well.The tuned parameters included play-out depth and exploration factor.

E. Hyper-heuristics / Algorithm Selection

Hyper-heuristic approaches select or switch among algorithms according to game characteristics or observed play. The reviewed work uses game classification and classifiers to adapt agent choice, with several competition-winning or promising results.

  • Definition: Hyper-heuristics use a higher-level decision process to determine which algorithm should act at each time.This separates algorithm selection from combining methods inside a single agent.
  • Algorithm combinations: A* with Enforced Hill Climbing can guide high-level navigation before switching to MCTS for local maneuvering near a goal.The approach performed well in some tested games, while path computation was difficult under short time budgets.
  • Algorithm combinations: YOLOBOT combines heuristic Best First Search for deterministic environments with MCTS for stochastic games and won several GVGAI competition editions.The controller switches methods after assessing game conditions or reaching search thresholds.
  • Algorithm selection: Return42 first classifies a game as deterministic or stochastic, then uses A* for deterministic navigation and random walks otherwise.The selection is based on the game type detected at runtime.
  • Game classification: K-means clustering grouped games and algorithms into four difficulty-related clusters based on VGDL sprite features and agent win rates.The resulting clusters appeared to correspond to different rates of successful play.
  • Algorithm selection: Portfolio selection using classifiers such as SVM and J48 achieved higher victory rates than the compared individual-agent choices.The classifiers were trained with game-based features to select an agent for each game.
  • Algorithm selection: Agent-log classifiers trained across 80 games used player-experience features to predict whether a game would be won at early, middle, and late stages.The features describe how search was conducted rather than relying on potentially human-biased game features.

A. Tree Search methods

Tree-search methods in GVGAI are dominated by MCTS, with entries adding search, rollout, value-map, and learning mechanisms. Performance varies by game structure, while competition results and two-player settings expose the importance of opponent modeling and generalization.

  • Competition evidence: Most early two-player competition entries used MCTS, and the 2016 winner also won in 2018, underscoring the challenge of multi-player generalization.The survey identifies greater research focus on multi-player games as needed for faster progress.
  • MCTS variants: Open-loop MCTS stores node statistics instead of game states, while some agents switch to Breadth-First Search in deterministic games to avoid simulation cost.The method choice depends on an initial assessment of game type.
  • MCTS enhancements: MCTS enhancements include value maps and dynamic rollout lengths that direct exploration toward promising positions or higher-level targets.Value maps can encode physical locations or heuristic concepts such as novelty and target proximity.
  • Learning: Online learning is common across agents, but only adrienctx also used offline learning to tune stochastic-gradient-descent parameters on training data.The offline-tuned parameters were learning rate and mini-batch size.
  • Evolutionary alternatives: Number27 used a genetic algorithm with fixed-length action sequences and an event-updated value heat-map, winning the CIG 2016 leg and placing fourth overall.The heat-map encourages exploration toward interesting level regions using object frequency and influence ranges.
  • Evolutionary alternatives: CatLinux used RHEA with a shift buffer that retained and shifted the evolved population between game ticks, placing fifth overall in the 2016 Championship.Each sequence drops its previous action and receives a new random action at the end.
  • Learning: No offline learning was used by the EA agents, leaving parameter tuning as a possible improvement direction.The survey explicitly identifies both offline and online tuning as potential avenues.
  • Opponent modeling: Two-player GVGAI agents mostly use random opponent models, while later work evaluates alternatives including minimax-style, average, fallible, mirror, and buffer-based models.The framework’s sample One Step Lookahead model selects random non-losing opponent actions.

1) Random agent:

GVGAI learning agents use diverse state representations, reinforcement-learning methods, and learning budgets to play unknown games. Results vary substantially with learning time, feedback, and competition constraints.

  • Approximately 40% of decisions by DontUnderestimateUchiha were random because its exploration probability stayed between 0.5 and 0.3 for the first 2,000 ticks.
  • kkunan won the first 2017 learning track despite using a simple Q-learning design with manually selected parameters.
  • Learning agents differed in state input, training time, algorithms, tested games, and sometimes maximum game length.
  • Agents using screen capture were absent from the 2017 classic-GVGAI learning competition submissions, although later work evaluated screen-based learning.
  • Sarsa-based agents performed poorly, likely because of arbitrary parameters and only five minutes to learn three training levels before testing three harder levels.
  • None of three tested DRL algorithms outperformed planning agents on six of eight games, but A2C nearly doubled the best planning-agent score on stochastic Seaquest.

VII. METHODS FOR LEVEL GENERATION

GVGAI level-generation methods range from fast constructive procedures based on general design knowledge to learned, pattern-based, and cellular-automata approaches. These methods differ in how much structure they impose before generating content.

  • Constructive generators: Constructive generators place level elements using general knowledge such as separating enemies from the avatar and avoiding walls that partition the world.
  • Constructive generators: The sample random generator adds a solid border, places one instance of each mapped character randomly, then adds further random sprites.
  • Constructive generators: A knowledge-based generator labels sprites by type and interaction, builds obstacles, places the avatar, and locates harmful sprites far from it.
  • Constructive generators: The competition-winning Easablade generator used cellular automata across multiple layers for obstacles, exits, avatars, goals, harmful sprites, and other elements.
  • Constructive generators: An n-gram generator records player actions and uses action sequences with predefined rules and constraints to shape generated levels.
  • Constructive generators: A pattern-based constructive generator analyzed 97 games with 3x3 windows and discovered 12,941 unique patterns for level construction.

B. Search-based methods

Search-based level generators use simulation, evolutionary search, constraints, or patterns to produce playable or targeted content. They trade generation time against beatability, challenge, similarity, and human preference.

  • Search-based methods: Search-based generators use simulations to evaluate whether generated levels are playable and better than random object placement.
  • Search-based methods: FI2Pop evolves feasible and infeasible populations separately, rewarding agent-performance differences while reducing violations such as early avatar death.
  • Search-based methods: A suspense-driven generator adjusts levels toward three approximately 50% suspense peaks while favoring winnable games.
  • Search-based methods: A genetic generator combines normalized score differences between MCTS and One Step Look Ahead with constraints in its fitness function.
  • Discussion: Constructive generators are fastest but do not guarantee beatability, whereas search-based and constraint-based generators take longer and produce challenging beatable levels.
  • Discussion: Easablade received 78.4% of preferences, but most of its generated levels were either unbeatable or easier than competing generators.

VIII. METHODS FOR RULE GENERATION

Rule-generation methods construct VGDL games directly or search for rule sets satisfying constraints and performance criteria. The surveyed approaches range from validity-focused random generation to structured and evolutionary designs.

  • Constructive methods: Constructive rule generators produce rules in one pass without playing the game, often incorporating game-design knowledge.
  • Constructive methods: The simplest generator randomly selects sprites and interactions, retaining only rules that compile without errors.
  • Constructive methods: A more complex generator classifies sprites by roles, creates interactions using VGDL and level-design knowledge, and generates winning and losing termination conditions.
  • Search-based methods: Search-based rule generation uses algorithms to identify games satisfying criteria beyond randomly selected interactions.
  • Search-based methods: FI2Pop evolves feasible and infeasible games while enforcing constraints such as limiting bad frames and preventing avatar death during the first 40 frames.
  • Search-based methods: An evolutionary-strategy generator mutates and recombines complete games to maximize performance differences between algorithms.

C. Discussion

GVGAI research spans game generation, agent evaluation, human-like play, tutorials, deception, and game-design support. Across these efforts, generator speed, output features, evaluation criteria, and agent behavior shape what can be compared or produced.

  • Game generation: Constructive generators are faster but do not guarantee distinct or playable games, whereas search-based generators spend longer seeking playability.Thorbjorn uniquely generates complete games, including interaction rules and termination conditions, complicating comparisons.
  • Game generation: The constructive sample generator was preferred in 76.38% of user-study comparisons, ahead of genetic at 44.73% and random at 24.07%.The genetic generator’s fitness constraint favored games that considerably limited sprite movement.
  • Broader uses: GVGAI supports research beyond playing agents, including recommender systems, AI-assisted design and debugging, tutorial generation, deceptive games, and behavior-oriented game evaluation.These applications use VGDL descriptions, agent behavior, or gameplay data to support design and analysis.
  • Evaluation: GVGAI studies also model human-like action distributions, evolve game parameters for target score trends, and investigate agents’ robustness to altered environments.These directions broaden evaluation from winning performance to play style, experience, and environmental sensitivity.
  • Evaluation: Relative Algorithm Performance Profiles evaluate whether games distinguish stronger from weaker agents across repeated playings.Related work extends evaluation by comparing scores and win rates against random agents or by evolving games against selected opponent strengths.

D. Robustness testing

Robustness studies show that altered conditions can reorder agent rankings, while current improvements often remain game- or configuration-specific. The survey identifies time allocation, general features, macro-actions, game classification, and opponent modeling as open challenges.

  • Robustness testing: When environmental conditions change, sample agents can rise to the top while strong controllers perform worse; MCTS is more robust than several alternatives.Best-first and A* agents handled noise particularly badly, while some controllers remained better than others across conditions.
  • Open problems: Approximately 50% is the highest victory rate rarely surpassed by leading approaches, while many single-player games remain below 25%.The survey identifies improving performance across a large proportion of games as the central challenge.
  • Open problems: Existing enhancements usually improve only subsets of games or algorithm configurations rather than achieving performance across the board.The survey links this limitation to the difficulty of designing truly general approaches for unseen games.
  • Open problems: More sophisticated sprite-distance features can outperform Euclidean distances, but computing them consumes a substantial part of the decision-time budget.This creates a trade-off between feature quality and time available for choosing difficult actions.
  • Open problems: Macro-actions can improve some games, leave others unchanged, or reduce performance, and high-level planning remains unsolved.Future work may adapt repetition lengths dynamically and support more complex planning structures.
  • Open problems: Future research includes more accurate game classification, portfolios of adaptive algorithms, and richer opponent models that distinguish collaboration from competition.These challenges apply to both single- and two-player settings, with opponents adding further complexity.

XI. EDUCATIONAL USE OF GVGAI

GVGAI is used in teaching, assignments, dissertations, and competitions that develop both agents and games. Its educational use extends from applying GVGAI concepts to creating novel VGDL games and exploring research tracks.

  • Educational uses: GVGAI supports taught-module assignments and many MSc dissertations, although educational examples are not exhaustive.The single-player planning track receives most dissertation attention because it was developed first and provides sample agents.
  • Taught modules: Students commonly learn GVGAI concepts and write agents whose league performance contributes substantially to assessment.Several institutions have organized private leagues for these assignments.
  • Taught modules: Students can instead learn VGDL by developing novel games, including puzzle games later used in planning-track training and validation sets.A similar AI-assisted game-design assignment also produced planning-track games.
  • Dissertations: MSc projects have extended sample agents, including MCTS with options, which significantly outperformed sample MCTS on most studied games.Options are action sequences designed for specific subgoals.
  • Dissertations: Student and research projects also apply ASP or genetic algorithms to level generation, learn from screen capture, and extend the framework with new tracks.These examples span content generation, learning, and framework development.
  • Future directions: GVGAI’s continuing development creates opportunities for new competition tracks and varied research and educational activities.Proposed directions include game generation and multi-agent or multiplayer settings.

3) Turing Test GVGAI:

The survey presents GVGAI as a broad platform for evaluating agents and generating games and content, with extensibility as a central strength. It also identifies difficult content-generation tasks and limitations in VGDL expressiveness as priorities for future development.

  • Future tracks: A proposed Turing Test track would evaluate agents that play like humans across arbitrary games.The paper notes the problem’s difficulty and significant research interest.
  • Framework extensions: GVGAI’s growing game library could integrate automatically designed games, while interoperability with Gym, ALE, or Malmo could add games and enable 3D support.A common API would allow GVGAI agents to play tasks from these systems.
  • Framework extensions: Wider action spaces could allow simultaneous actions or continuous controls, increasing legal action combinations at each decision step.This is presented as a possible agent-interface improvement.
  • Framework extensions: Improved logging and visualization could expose score changes, action entropy, explored positions, replays, and gameplay metrics.The envisioned website would support richer analysis and real-time visualization in browser-based play.
  • Conclusions: GVGAI evaluates playing agents and content-generation algorithms across planning, learning, game, and level-creation challenges.The framework has supported international competitions and evaluation of hundreds of agents.
  • Conclusions: GVGAI is easier to extend than ALE through rapid creation of VGDL games, levels, generators, and variations, though ALE offers higher-quality commercial games.The paper notes that ALE-trained agents risk overfitting to their training games and levels.
  • Conclusions: Content tracks require generating rules or levels for unseen games, making general evaluation measures and agent-based play-testing especially important.The survey describes these tracks as an extremely hard challenge.
  • Conclusions: VGDL enables rapid, concise game specification but limits human-oriented fun and complex mechanics, motivating compatible games authored in other languages.Alternative languages must conform to the GVGAI API for track compatibility.
Loading 1802.10363v4…