Gamasutra: The Art & Business of Making Gamesspacer
Automated Testing: Building A Flexible Game Solver
View All     RSS
October 21, 2014
arrowPress Releases
October 21, 2014
PR Newswire
View All

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

Automated Testing: Building A Flexible Game Solver

October 27, 2011 Article Start Previous Page 3 of 3

Fedex quests. In some cases, we must walk through several scenes to complete an action, repeatedly. This quickly overflowed our search depth limit. This is a problem that may also affect the player, and we have solved it by using the same trick as used in the gameplay. We used the custom object "map" that is obtained in the third chapter of the game. We add the ability to shorten displacements using map's hotspots. This solution is interesting, as we show that the CPU's solving limits can be the player's limits, too.

Goals that are too far away from the current point. Sometimes it takes many actions before you can open or close a quest. The quest book gives us some goals far away from our game state. To solve this, we added the content of the inventory as mid-objectives; each inventory change becomes a goal accomplished. Since we are a point 'n' click game, gathered items are meaningful.

Inventory loop and quest loop. This problem is related to the state loop, in that unfortunately, some items can be consumed, and obtained again with very little action. Plus, some items are stackables -- up to 99 of an item.

We first tried to solve this by only using dropped items as goals. However, this will shortcut the cases where we must drop an object to continue the adventure. The solver will add it and remove it instantly (as a new short goal) in a loop.

As a solution, since only a few items of the inventory can lead to this problem, we chose to blacklist theses. In the same fashion, some quests can be reopened after being closed. A similar blacklist solution successfully removed these cases.

Another idea is to keep a full solving history through fingerprints, and stop the search if a previously explored game state is met. We didn't try it, as blacklisting proved sufficient. However, this may be an interesting development, avoiding hard coding.

Finally, here are some numbers from the game:

  • Backup (game state) size: approximately 2kb
  • Number of scenes 70
  • Number of characters 75
  • Number of Boolean variables 1272
  • Number of integer variables 49
  • Branching factor: about 3.5
  • Maximum depth search: 17 (may be quite long on a Nintendo Wii)
  • Test time: about 30 minutes to complete the adventure (with game sped up 4x) on a Nintendo Wii.


As we saw, the execution of a game solver requires the processing of game logic data. This leads to load multiple levels / scenes together (if not all), so there may be some significant changes in the game engine. Furthermore, this technique is depends of the use of the quest dictionary to search.

For another type of game, another provider for goals has to be found. This method allowed a continuous logic test of the game. This gave us a very high value at a reasonable cost. We tested continuously from early in the development phase to final test phase. The final test phase has far less bugs from this method, and reduced the time to polish.

As an extension, we added the ability to dynamically create variants of the adventure by adding random events. The solver is able to resume execution from any state of the game. A wide variety of solutions, including testing non-linear level design is now possible at low cost! It makes better use of testers: they are no longer blocked due to a crash on the critical path. So we can spare time on bug fixing.

This method can be combined with other methods like those seen in "Mario AI Competition" by Sergey Karakovskiy Togelius and Julian, to solve skill-related gameplay. A pathfinder could also be useful if some events are locked by spatial access. Many action or adventure games could use such tools to do automatic test.

To conclude, the good performance of this solver gives the possibility to use it to help the player in his quest if blocked, similar to the "super guide" that can be seen in New Super Mario Bros. Wii. The advantage is to use the player context: in an RPG, the solver will suggest different solutions if the hero is a barbarian or a magician.

Another possibility is full tree exploration. This way we can certify that no sequence of actions can lead to blocking the main quest. We can also collect some metrics, like depth from quest solving, identifying hard quests to solve.

Thanks to Wizarbox, Sébastien Duperron, Aurélien Pocheville, and Claire Roger.

Article Start Previous Page 3 of 3

Related Jobs

Treyarch / Activision
Treyarch / Activision — Santa Monica, California, United States

Senior UI Artist (temporary) Treyarch
Treyarch / Activision
Treyarch / Activision — Santa Monica, California, United States

Lead UI Artist
Infinity Ward / Activision
Infinity Ward / Activision — Woodland Hills, California, United States

Senior AI Engineer - Infinity Ward
Treyarch / Activision
Treyarch / Activision — Santa Monica, California, United States

Senior Software Engineer - Treyarch


Lior Tal
profile image
Very nice article!

I am more interested in how this scripting engine was incorporated into your game engine - i suppose you were running a custom in-house engine and not some 3rd party middleware?

What implications does it have on the engine? for example, providing all the game entity's actions as simple hooks in the game engine so that the script can bind to them.

I am interested in implementing a similar technique using Unity for automated testing.

profile image
Yes, script system was done by us to keep scripting simple (no loops, no array, simple execution control, Graymatter uses Lua who allow scripters to do awfull things), and everything was done in C++.

You have to identify available input events for entities (kill it, smash it, ...) then, try them all using save & reload. But it needs to be fast, really fast!

You can try to combine it with a heuristic in the same way A* works: for example kill as much enemies as possible.

Hanson Snitch
profile image
Being a game programmer isn't an easy thing to do, it takes time to work for it to the fullest until you hit the spot with no error