Evolving playable content for Cut the Rope through a simulation-based approach

In order to automatically generate high-quality game levels, one needs to be able to automatically verify that the levels are playable. The simulation-based approach to playability testing uses an artificial agent to play through the level, but building such an agent is not always an easy task and such an agent is not always readily available. We discuss this problem in the context of the physics-based puzzle game Cut the Rope, which features continuous time and state space, making several approaches such as exhaustive search and reactive agents inefficient. We show that a deliberative Prolog-based agent can be used to suggest all sensible moves at each state, which allows us to restrict the search space so that depth-first search for solutions become viable. This agent is successfully used to test playability in Ropossum, a level generator based on grammatical evolution. The method proposed in this paper is likely to be useful for a large variety of games with similar characteristics. Copyright c 2013, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.