An online agent-based search approach in automated computer game testing with model construction

Samira Shirzadehhajimahmood, I. S. W. B. Prasetya, Frank Dignum, Mehdi Dastani

TL;DR

This paper introduces an online agent-based search approach for automated game testing that constructs a partial model of the game on-the-fly. This approach significantly improves the efficiency and effectiveness of test case generation by dynamically adapting to the game's complex environment and interactions, outperforming methods that rely on pre-built models or random exploration.

What Problem Does This Paper Address?

The increasing complexity of modern computer games, with their vast interaction spaces and intricate rules, makes automated testing a significant challenge. Traditional software testing methods often struggle with the sheer scale and dynamic nature of game environments. While model-based testing (MBT) offers a structured approach, manually creating detailed game models is prohibitively expensive and time-consuming. This paper addresses the need for an automated testing solution that can effectively navigate these complex game worlds and generate meaningful test cases without requiring a complete, pre-defined model.

Methods

The core contribution is an online agent-based search approach that integrates on-the-fly model construction. Instead of relying on a fully specified model, the agent builds a partial Extended Finite State Machine (EFSM) model of the game as it explores. This EFSM captures not only the game's logic but also its physical navigability and "zone" concepts.

Key aspects of the method include:

  • Agent-based Testing: Utilizes an agent-driven framework (iv4XR) to interact with the game, leveraging agents' reactive programming and goal-oriented behavior for abstract test programming.
  • On-the-Fly Model Construction: The EFSM model (S, T, Σ, P, α, co) is incrementally built based on the agent's observations during exploration. This includes states (S), transitions (T), zones (Σ), and interaction effects (P).
  • Online Search: The agent directly explores the game under test, accessing real-time state information. This search is guided by heuristics to select the next state to visit and to dynamically handle obstacles and interactables.
  • Hybrid EFSM: The EFSM model is extended to incorporate physical navigability and game zones, which are crucial for understanding how agents can move and interact within the game world.
  • Dynamic Goal Handling: The approach includes mechanisms to dynamically address intermediate goals, such as unblocking doors, by identifying and interacting with relevant game objects.

Datasets

The experiments were conducted using levels from the Lab Recruits (LR) game, specifically those used in the A-TEST 2021 Student Competition. These levels are described as maze-like 3D environments with varying numbers of rooms, buttons, and doors, serving as benchmarks to test the algorithm's performance under different complexity levels. No new benchmarks were introduced; existing game levels were used for evaluation.

Key Insights and Ideas

  • Model Construction is Key for Efficiency: The most striking insight is that even a partially constructed, on-the-fly model significantly boosts testing performance. The "Search" approach, which uses the model, consistently outperforms "Searchbasic," which does not. This highlights that understanding the game's structure, even partially, is crucial for efficient navigation and interaction.
  • Dynamic Obstacle Handling is Non-Trivial: The paper emphasizes that games often have elements that actively resist the player (obstacles, hazards). The proposed approach's ability to dynamically identify and interact with objects to overcome these obstacles is a core strength.
  • Exploration vs. Exploitation Trade-off: The agent must balance exploring new areas to discover game mechanics and objects with exploiting its current knowledge (the partial model) to achieve testing goals. The heuristics for selectNode() and dynamicGoal() are designed to manage this trade-off.
  • Model Accuracy vs. Task Completion: While the constructed model is not always perfectly accurate or complete (e.g., not all objects might be discovered), it's sufficient for successfully completing the defined testing tasks. This suggests that for automated testing, achieving the goal is paramount, and a perfect model isn't always a prerequisite.

Key Results

  • High Success Rate: The proposed online agent-based search approach ("Search") successfully solved testing tasks on all experimental levels, including complex ones.
  • Superior Performance: "Search" significantly outperformed "Searchbasic" (which lacked model exploitation) and a "Random" baseline. "Searchbasic" failed on some levels, indicating the necessity of the model.
  • Model Value: The model's utility was demonstrated by its ability to help the agent overcome complex situations, such as unblocking paths or dealing with previously encountered obstacles.
  • Efficiency: The total run time for the "Search" algorithm ranged from one to four minutes per level. Exploration typically accounted for 15-30% of the total time, with the remainder dedicated to solving the testing task.
  • Model Accuracy: The constructed model was found to be mostly correct and almost complete, with a high accuracy in registering button-door connections.

Limitations and Future Work

  • Limitations:
    • The current approach primarily focuses on interactables like switches and doors, and does not explicitly handle hazards or mobile objects.
  • The model construction is based on a single testing task; a more comprehensive model might require multiple tasks.
  • While the model is largely accurate, some inaccuracies in object registration were observed, though they didn't prevent task completion.
  • Future Work:
    • Improve the accuracy and completeness of the constructed model to achieve a full game model.
  • Investigate how to exploit the model in a mixed online and offline search strategy.
  • Extend the approach to handle hazards and mobile objects.

Summary updated

Abstract

The complexity of computer games is ever increasing. In this setup, guiding an automated test algorithm to find a solution to solve a testing task in a game's huge interaction space is very challenging. Having a model of a system to automatically generate test cases would have a strong impact on the effectiveness and efficiency of the algorithm. However, manually constructing a model turns out to be expensive and time-consuming. In this study, we propose an online agent-based search approach to solve common testing tasks when testing computer games that also constructs a model of the system on-the-fly based on the given task, which is then exploited to solve the task. To demonstrate the efficiency of our approach, a case study is conducted using a game called Lab Recruits.
BibTeX
@inproceedings{shirzadehhajimahmood2022online,
  author = {Samira Shirzadehhajimahmood and I. S. W. B. Prasetya and Frank Dignum and Mehdi Dastani},
  title = {{An online agent-based search approach in automated computer game testing with model construction}},
  booktitle = {A-TEST@ESEC/SIGSOFT FSE},
  year = {2022},
  url = {https://openreview.net/forum?id=bhi1Ok7a6k},
}
Figure