Although automated test generation is common in many programming domains, games still challenge test generators due to their heavy randomisation and hard-to-reach program states. Neuroevolution combined with search-based software testing principles has been shown to be a promising approach for testing games, but the co-evolutionary search for optimal network topologies and weights involves unreasonably long search durations. Humans, on the other hand, tend to be quick in picking up basic gameplay. In this article, we therefore aim to improve the evolutionary search for game input generators by integrating knowledge about human gameplay behaviour. To this end, we propose a novel way of systematically recording human gameplay traces, and integrating these traces into the evolutionary search for networks using traditional gradient descent as a mutation operator. Experiments conducted on 10 diverse Scratch games demonstrate that the proposed approach reduces the average search time from 5 hours down to only 97 minutes and helps the test generator achieve higher program coverage by reaching the winning states of games more often.

Games are designed to challenge human players, but this also makes it challenging to generate software tests for computer games automatically. Neural networks have therefore been proposed to serve as dynamic test cases trained to reach statements in the underlying code, similar to how static test cases consisting of event sequences would do in traditional software. The Neatest approach combines search-based software testing principles with neuroevolution to generate such dynamic test cases. However, it may take long or even be impossible to evolve a network that can cover individual program statements, and since Neatest is a single-objective algorithm, it will have to be sequentially invoked for a potentially large number of coverage goals. In this paper, we therefore propose to treat the neuroevolution of dynamic test cases as a many-objective search problem. By targeting all coverage goals at the same time, easy goals are covered quickly, and the search can focus on more challenging ones. We extend the state-of-the-art many-objective test generation algorithms MIO and MOSA as well as the state-of-the-art many-objective neuroevolution algorithm NEWS/D to generate dynamic test cases. Experiments on 20 Scratch games show that targeting several objectives simultaneously increases Neatest's average branch coverage from 75.88% to 81.33% while reducing the search time by 93.28%.

Although automated test generation is common in many programming domains, games still challenge test generators due to their heavy randomisation and hard-to-reach program states. Neuroevolution combined with search-based software testing principles has been shown to be a promising approach for testing games, but the co-evolutionary search for optimal network topologies and weights involves unreasonably long search durations. In this paper, we aim to improve the evolutionary search for game input generators by integrating knowledge about human gameplay behaviour. To this end, we propose a novel way of systematically recording human gameplay traces, and integrating these traces into the evolutionary search for networks using traditional gradient descent as a mutation operator. Experiments conducted on eight diverse Scratch games demonstrate that the proposed approach reduces the required search time from five hours down to only 52 minutes.

The video gaming industry thrives with an expected record revenue of $365.60 billion in 2023 and an annual growth rate of 6.52% from 2023 to 2027 [1] . To gain a foothold in this emerging market, developers have to ensure the best gaming experience possible, which can only be achieved via extensive testing procedures. However, most video games are created incrementally; some are even developed indefinitely, resulting in many program increments that have to be tested over and over again. Even though fully automated testing of games could relieve developers from this tedious task, a look at current industry practices reveals a dire need for more research, as most companies still test manually [2] , [3] . Besides entertaining the player, video games are also increasingly used for programming education because games keep the students motivated while demonstrating crucial programming concepts [4] – [6] . Although even experienced programmers rely on integrated development tools, students are left off with a lack of tools to assist them during their learning journey. Thus, more work on automated game testing is required such that students and practitioners cannot only validate the correctness of programs but also use generated inputs for dynamic program analysis.

Abstract The importance of programming education has led to dedicated educational programming environments, where users visually arrange block-based programming constructs that typically control graphical, interactive game-like programs. TheScratchprogramming environment is particularly popular, with more than 90 million registered users at the time of this writing. While the block-based nature ofScratchhelps learners by preventing syntactical mistakes, there nevertheless remains a need to provide feedback and support in order to implement desired functionality. To support individual learning and classroom settings, this feedback and support should ideally be provided in an automated fashion, which requires tests to enable dynamic program analysis. In prior work we introducedWhisker, a framework that enables automated testing ofScratchprograms. However, creating these automated tests forScratchprograms is challenging. In this paper, we therefore investigate how to automatically generateWhiskertests. Generating tests forScratchraises important challenges: First, game-like programs are typically randomised, leading to flaky tests. Second,Scratchprograms usually consist of animations and interactions with long delays, inhibiting the application of classical test generation approaches. Thus, the new application domain raises the question of which test generation technique is best suited to produce high coverage tests capable of detecting faulty behaviour. We investigate these questions using an extension of theWhiskertest framework for automated test generation. Evaluation on common programming exercises, a random sample of 1000Scratchuser programs, and the 1000 most popularScratchprograms demonstrates that our approach enablesWhiskerto reliably accelerate test executions, and even though manyScratchprograms are small and easy to cover, there are many unique challenges for which advanced search-based test generation using many-objective algorithms is needed in order to achieve high coverage.

Learners are often introduced to programming via dedicated languages such as SCRATCH, where block-based commands are assembled visually in order to control the interactions of graphical sprites. Automated testing of such programs is an important prerequisite for supporting debugging, providing hints, or assessing learning outcomes. However, writing tests for SCRATCH programs can be challenging: The game-like and randomised nature of typical SCRATCH programs makes it difficult to identify specific timed input sequences used to control the programs. Furthermore, precise test assertions to check the resulting program states are incompatible with the fundamental principle of creative freedom in programming in SCRATCH, where correct program behaviour may be implemented with deviations in the graphical appearance or timing of the program. The event-driven and actor-oriented nature of SCRATCH programs, however, makes them a natural fit for describing program behaviour using finite state machines. In this paper, we introduce a model-based testing approach by extending WHISKER, an automated testing framework for SCRATCH programs. The model-based extension describes expected program behaviour in terms of state machines, which makes it feasible to check the abstract behaviour of a program independent of exact timing and pixel-precise graphical details, and to automatically derive test inputs testing even challenging programs. A video demonstrating model-based testing with WHISKER is available at the following URL: https://youtu.be/edgCNbGSGEY

Game-like programs have become increasingly popular in many software engineering domains such as mobile apps, web applications, or programming education. However, creating tests for programs that have the purpose of challenging human players is a daunting task for automatic test generators. Even if test generation succeeds in finding a relevant sequence of events to exercise a program, the randomized nature of games means that it may neither be possible to reproduce the exact program behavior underlying this sequence, nor to create test assertions checking if observed randomized game behavior is correct. To overcome these problems, we propose Neatest, a novel test generator based on the NeuroEvolution of Augmenting Topologies (NEAT) algorithm. Neatest systematically explores a program’s statements, and creates neural networks that operate the program in order to reliably reach each statement—that is, Neatest learns to play the game in a way to reliably cover different parts of the code. As the networks learn the actual game behavior, they can also serve as test oracles by evaluating how surprising the observed behavior of a program under test is compared to a supposedly correct version of the program. We evaluate this approach in the context of Scratch, an educational programming environment. Our empirical study on 25 non-trivial Scratch games demonstrates that our approach can successfully train neural networks that are not only far more resilient to random influences than traditional test suites consisting of static input sequences, but are also highly effective with an average mutation score of more than 65%.