Scenario-Driven Neuroevolution: Using Models to Guide Test Generation for Games

1 Introduction

• Fixed input sequences can become flaky in non-deterministic games because they cannot adapt to changes in program behaviour.Neatest instead uses neural networks that generate inputs dynamically from the current program state, making them robust to program randomisation.Source: §1 · p. 2
• Neatest’s branch- or statement-based goals can cause scalability problems and deceptive fitness landscapes, such as getting stuck when obstacles block a direct route to an exit.The approach also treats code locations as equally important, without distinguishing critical from less important code.Source: §1 · pp. 2–3
• Model-guided testing requires human effort to build models, but these can be small, high-level, reusable, and linked to requirements for more actionable failure triage.Using a model as a hyperparameter also gives testers a more understandable way to adjust search direction and performance.Source: §1 · p. 3
• The proposed black-box approach guides Neatest toward model states representing desired scenarios, rather than optimising for every branch or statement.Models can define ordered waypoints to help agents navigate around deceptive fitness landscapes.Source: §1 · pp. 2–3
• The paper introduces two game-agnostic modelling strategies to improve evolutionary search.The proposed approach is implemented as an extension to Neatest in the Whisker testing framework.Source: §1 · p. 3
• The model-guided approach improves branch coverage by 7% over the white-box approach while optimising agents to perform specified testing scenarios.The evaluation uses 13 Scratch games across varying genres.Source: §1 · pp. 3–4

2.1 The Scratch Programming Environment

• Scratch scripts control sprites on a 2D canvas, but logical flaws remain possible, and conventional search-based testing struggles to reach advanced game states or adapt to game randomisation.Whisker supports Scratch testing, including manual tests and automatically generated tests.Source: §2.1 · p. 4

2.2 Neuroevolution-based Testing of Games

• Neatest uses neuroevolution to optimise neural-network agents for reaching code statements or branches, then checks that successful agents remain reliable across random seeds.Its iterative process selects a coverage objective, scores networks by approach level and branch distance, and evolves network weights and topology.Source: §2.2 · p. 5

2.3 Model-Based Testing

• Game models are extended finite-state machines: abstract states are connected by guarded transitions evaluated against selected aspects of program state.For Scratch, the model can observe runtime details such as sprite positions, variables, costumes, and events.Source: §2.3 · pp. 5–6
• Rather than one general-purpose model, testers can create small models for particular test purposes; edge effects can also serve as test oracles.The paper focuses on input generation and does not use edge effects in that role.Source: §2.3 · p. 6

3 Inferring Actions from Game Models through Neuroevolution

• Model-guided Neatest derives coverage targets from game-model states and uses execution traces to score how close an agent comes to reaching its target.Approach level counts intervening model states; branch distance measures progress toward satisfying the guard on an edge leading closer to the target.Source: §3 · pp. 6–7
• For a target at the second level, an agent that has reached the first waypoint has approach level 1, with branch distance determined by the guard linking the waypoints.This example illustrates how model progress and edge conditions contribute separately to fitness.Source: §3 · p. 7
• Guard distance uses player-to-target distance for location or contact checks, absolute value differences for variables or time, and binary values for guards without a measurable proximity.Distances for conjunctive conditions are summed; when multiple edges reach a target, the shortest-path edge is used, with lowest branch distance breaking ties.Source: §3 · p. 7
• The paper focuses on test input generation; after execution, it measures code and model coverage, while a separate test oracle is needed for pass/fail verdicts.Whisker supports several oracle options.Source: §3 · p. 7

4.1 Dataset

• The dataset combines 13 Scratch games that vary in genre and complexity and require meaningful gameplay to win.Successful gameplay strategies can complete each game in under a minute of non-accelerated play.Source: §4.1 · pp. 7–8

4.2 Experimental Setup

• Experiments compare model-state coverage with branch coverage and wins, repeat each experiment 30 times, and use a five-hour search budget.An objective counts as covered only when an agent solves it in 10 randomized game executions.Source: §4.2 · p. 9

4.3 Threats to Validity

• The evaluation cannot guarantee that results generalise beyond its small dataset, despite its varied game genres and controls.The authors also identify randomness in games and neuroevolution as a source of variation across reruns.Source: §4.3 · p. 11

4.4 RQ1 (Simple Models)

• Across 13 games, simple-model Neatest averages 80% branch coverage versus 85% for code-guided Neatest, with significantly higher coverage in five games and lower coverage in seven.The simple models focus on finishing games and can ignore easy-to-reach side branches that are not needed to win.Source: §4.4 · p. 11, Table 3 · p. 12

4.5 RQ2 (Specialised Models)

• Specialised models raise average branch coverage from 76% to 89% on the selected games, and outperform code-guided Neatest by playing the games better.The RQ2 average uses only the best model for each game.Source: §4.5 · p. 12, Table 4 · p. 13
• Curriculum Learning’s stepwise progression can improve coverage and favour reliable progress under randomized behaviour, while simple models can win slightly more often.For CreateYourWorld, intermediate waypoints raise branch coverage from 74% to 77%, and side-goal waypoints raise it from 77% to 79%.Source: §4.5 · p. 13
• In CreateYourWorld, sink states let the search stop futile runs early, increasing evaluations from 1,800 to 14,000 and generations from 12 to 93 within five hours.An agent enters a sink state when it misses the next goal within a customizable time limit.Source: §4.5 · pp. 13–14
• Model-guided tests achieve higher state coverage with lower variance for Pong and WhackAMole, and better express HackAttack’s desired no-life-loss playstyle.In Dragons, 100% model coverage can coexist with low branch coverage, showing that a model task need not align with branch-coverage-maximizing gameplay.Source: §4.4 · p. 12, §4.5 · p. 14

• Neatest has been extended with many-objective search, novelty search, and gradient-guided network-weight optimisation using player traces.These extensions can be combined with any fitness function, but were excluded here to compare code-guided and model-guided searches.Source: §5 · p. 15
• Earlier model-based testing targeted platform games, MMORPG quests, stealth levels, and Android games, but was limited to specific genres or scenarios.Source: §5 · p. 15
• Prior work uses Q-Learning to test games based on a model with high-level input actions requiring a navigation map, simplifying search but adding manual overhead and possibly diverging from player behavior.Source: §5 · p. 15
• To the authors’ knowledge, no existing framework lets testers define scenarios for any game and realise them with agents robust to program randomisation.Source: §5 · p. 15

• Model-guided Neatest evolves one agent per model state rather than per branch, which can scale better because scenarios usually have fewer model states than program branches.Testers define scenarios with abstract models, and the agents replicate the desired gameplay behaviour.Source: §6 · p. 15
• Small, high-level models keep modelling effort low, while simple specialisation techniques can increase achieved coverage.Source: §6 · p. 15
• Future work includes combining model-guided Neatest with other extensions, using neuroevolution for hard-to-reach states or reachability-driven test oracles, and applying it to autonomous driving or robot control.Source: §6 · p. 15