Enhancing the Monte Carlo Tree Search Algorithm for Video Game Testing

Date

2020-03-01

Author

Arıyürek, Sinan
Betin Can, Aysu
Sürer, Elif

Metadata

Show full item record

Item Usage Stats

225
views

0
downloads

In this paper, we study the effects of several Monte Carlo Tree Search (MCTS) modifications for video game testing. Although MCTS modifications are highly studied in game playing, their impacts on finding bugs are blank. We focused on bug finding in our previous study where we introduced synthetic and human-like test goals and we used these test goals in Sarsa and MCTS agents to find bugs. In this study, we extend the MCTS agent with several modifications for game testing purposes. Furthermore, we present a novel tree reuse strategy. We experiment with these modifications by testing them on three testbed games, four levels each, that contain 45 bugs in total. We use the General Video Game Artificial Intelligence (GVG-AI) framework to create the testbed games and collect 427 human tester trajectories using the GVG-AI framework. We analyze the proposed modifications in three parts: we evaluate their effects on bug finding performances of agents, we measure their success under two different computational budgets, and we assess their effects on human-likeness of the human-like agent. Our results show that MCTS modifications improve the bug finding performance of the agents.

Subject Keywords

Game Testing, Monte Carlo Tree Search

URI

https://arxiv.org/abs/2003.07813
https://hdl.handle.net/11511/84724

Journal

IEEE

DOI

https://doi.org/10.1109/CoG47356.2020.9231670

Collections

Graduate School of Informatics, Article

Suggestions

OpenMETU
Core

AUTOMATED VIDEO GAME TESTING USING REINFORCEMENT LEARNING AGENTS Arıyürek, Sinan; Sürer, Elif; Betin Can, Aysu; Department of Bioinformatics (2022-9-21) In this thesis, several methodologies are introduced to automate and improve video game playtesting. These methods are based on Reinforcement Learning (RL) agents. First, synthetic and human-like tester agents are proposed to automate video game testing. The synthetic agent uses test goals generated from game scenarios, and the human-like agent uses test goals extracted from tester trajectories. Tester agents are derived from Sarsa and Monte Carlo Tree Search (MCTS) but focus on finding defects, while tradi...
Verifying maze-like game levels with model checker SPIN Tekik, Onur; Betin Can, Aysu; Sürer, Elif; Department of Information Systems (2021-11-5) In this thesis, we present a new methodology that includes procedural generation and verification of maze-like game levels. The methodology employs a model checker, called SPIN, to both produce a winning sequence of actions and to formally verify custom game design properties. To verify a game level, we propose automated tailoring on template game models, considering the level-in-test, specifically designed according to the game rules. By leveraging the counterexample generation feature of SPIN, we find one...
Rigorous Analysis of Deformed Nanowires Using the Multilevel Fast Multipole Algorithm Karaosmanoglu, Bariscan; Yilmaz, Akif; Ergül, Özgür Salih (2015-05-17) We present accurate full-wave analysis of deformed nanowires using a rigorous simulation environment based on the multilevel fast multipole algorithm. Single nanowires as well as their arrays are deformed randomly in order to understand the effects of deformations to scattering characteristics of these structures. Results of hundreds of simulations are considered for statistically meaningful analysis of deformation effects. We show that deformations significantly enhance the forward-scattering abilities of ...
Automated Video Game Testing Using Synthetic and Human-Like Agents Arıyürek, Sinan; Betin Can, Aysu; Sürer, Elif (2019-06-01) In this paper, we present a new methodology that employs tester agents to automate video game testing. We introduce two types of agents -synthetic and human-like- and two distinct approaches to create them. Our agents are derived from Reinforcement Learning (RL) and Monte Carlo Tree Search (MCTS) agents, but focus on finding defects. The synthetic agent uses test goals generated from game scenarios, and these goals are further modified to examine the effects of unintended game transitions. The human-like ag...
Improved Nano-optical Traps for Single-particle Sensing Applications Isiklar, G.; Algun, M.; Ergül, Özgür Salih (2019-01-01) We present numerical design and simulations of nano-optical traps for single-particle sensing applications. While commonly used nano-holes with circular shapes are suitable for physically trapping nanoparticles to be detected and identified, they generate relatively weak signals in the far zone, especially when nanoparticles are small. We show that optical sensitivity of nano-holes can be enhanced significantly by using well-designed tip geometries such that metallic and dielectric nanoparticles can be dete...

Citation Formats

S. Arıyürek, A. Betin Can, and E. Sürer, “Enhancing the Monte Carlo Tree Search Algorithm for Video Game Testing,” IEEE, 2020, Accessed: 00, 2021. [Online]. Available: https://arxiv.org/abs/2003.07813.