The Saturday Paper - Tower of Gamebel

Header image: Atlas Shrank, a PuzzleScript game.

One of the aims of The Saturday Papers is to introduce people to new academic research that I think might inspire, help or just excite them. It's also a great way to link up academics with developers who are interested in putting new techniques or wild experimental ideas into practice in their own projects. Occasionally, though, there are unusual overlaps between the work of developers and researchers that are just too perfect not to point out. This week on The Saturday Papers, we're looking at game description languages.

We're reading A Video Game Description Language for Model-based or Interactive Learning by Tom Schaul, but we're also learning about PuzzleScript by Stephen Lavelle. I'll be shortening Tom Schaul's work to PyVGDL for most of the column. Both projects define languages which people can use to describe games and both have open-source engines which interpret and run these game descriptions as playable games. They've also got really interesting backstories and aims, and I think communities that are interested in one should definitely benefit from learning more about the other. Let's go take a look!

PyVGDL came out of discussions at a Daghstuhl seminar on AI and games held in 2012. These seminars are week-long invitational events that include a healthy dose of future work discussions about a chosen area of research. They publish the results of the seminars online for those interested, so if you want to see what things were discussed you can have a read here. The section that talks about what would become PyVGDL starts off referencing general game playing and Stanford's Game Description Language, but PyVGDL is designed for more than this alone. The discussion also touched on the potential for procedural content generation and automated game design to both benefit from a concise, expressive language for describing games.

Whenever I read discussions about languages, I always get antsy until someone shows me an example, so let's cut to the chase with a snippet of PyVGDL. Here's a definition for a simple Sokoban-like (I've simplified a little bit of the syntax):

There's four major categories of instruction here. The SpriteSet section defines objects in the game world. The syntax is fairly readable - name on the left hand side, followed by an arrow, and then any extra data like colours, movement styles, and the like. All of these special keywords are defined elsewhere. The LevelMapping section defines a legend relating symbols to objects defined in the SpriteSet - this keeps the level designs as compact, comma-separated arrays. InteractionSet defines the rules, based on the collision of two objects (on the left hand side of the arrow), and applies an effect to the first object in the rules. In the example above, if a box collides with a hole, then the box is destroyed. Finally, the TerminationSet defines how the game can end, both failures and success. In this case we can only end the game in one way - by having zero boxes left in the game world, we win. 

Before we go on to talk about PyVGDL's aims, PuzzleScript deserves a similar overview. PuzzleScript was developed by Stephen Lavelle, better known as the prolific indie game developer increpare. Stephen's experience as a designer seems to have paid into PuzzleScript's design as a language, as well as the editor which can be used to design PuzzleScript games in a web browser. PuzzleScript is focused on grid-based, turn-based puzzle games (although other games are certainly possible, including real-time games with some tweaking).

To match our PyVGDL example above, here's Sokoban as seen by PuzzleScript. As with PyVGDL, I've snipped a few things out to focus on the core of the language:

You can probably already see some similarities here. OBJECTS defines the entities that can exist in the game world, while LEGEND gives them symbols for the game's level descriptions. RULES define the game's interactions, although unlike PyVGDL they aren't limited to collisions. I'll talk about PuzzleScript's rules in a second. Finally, WINCONDITIONS describes how a game can be won. Here, the syntax lets us express that all Target objects have a Crate on top of them (the Target here is equivalent to PyVGDL's Hole object).

PuzzleScript's rules are more delicate than PyVGDL's and can interpret things like relative positioning and movement. There are also some very subtle modifiers that can be added to rules too - in fact, PuzzleScript can do things like scripted sequences and has been shown to be Turing Complete. There's a nice tutorial on PuzzleScript's website, but I'll briefly explain how the single rule of Sokoban works here. PuzzleScript's rules work by pattern matching on the left-hand side of the "->" implication in a given rule. The left hand side is a pattern showing a player next to a crate, and moving in the direction of the crate (the ">" symbol indicates relative movement). The right hand side, which is what happens when the game detects the pattern on the left, simply says that the player and the crate both move in the same direction. In simple terms: the player pushes crates by moving into them.

Both engines have very interesting tricks up their sleeves that set them apart from each other, and their domains are somewhat different too - PuzzleScript is very focused on grid-based games, and excels and turn-based ones although real-time seems quite possible. Meanwhile, PyVGDL wants a broader scope, with implementations of Pac-Man and Super Mario alongside the likes of Boulderdash and Sokoban. Which is not to say one is better than the other - simply that they have different objectives. The two share a common foundation in terms of their formalisms, however, and even their rules and interactions are reconcilable (although PuzzleScript seems capable of more complex behaviours, PyVGDL could be extended to accommodate these).

But more than the technical and formal foundations, I also feel like the philosophies and aims of these two projects fit really well with one another. PuzzleScript is about empowering people to make small games efficiently and without much programming knowledge. It has a wonderful interface, easy distribution and storage of games via the web, and has a suite of extra tools that lets users design artwork and sound effects for their games on top of the core game itself. Meanwhile, PyVGDL aims to produce a language that is clear and unambiguous enough for a machine to interpret, write, evaluate or analyse it. If it can achieve this, then we can build software to design games, play games, even review games written in PyVGDL.

PyVGDL gained a lot of interest among researchers, and the paper was nominated for Best Paper at CIG 2013. Meanwhile, PuzzleScript has resulted in hundreds of games being made, both by veteran game designers and those making their first ever games. The success of both of these projects in their own respective fields makes me excited, because it's rare to see the interests of developers and researchers align quite so perfectly. Getting researchers and designers to work together on the same tools and codebases would mean exciting things for both parties: for researchers, an opportunity to test out their systems with real users, and real game designers of all skill levels; and for developers, a tool that's being extended and improved with experimental and awesome technology that can offer opportunities to build new kinds of games in new ways.

Plans are afoot to host a number of game jam-style events next year specifically for researchers to get involved with, something I'm very excited about. Lots of these events may bring together game developers and academics to create projects together and foster collaboration. If this takes off, we might see the next generation of PuzzleScripts and PyVGDLs being collaborations between the two communities - and that's great news, no matter what you're looking to achieve.

Where To Find More

Tom Schaul is finishing up working at NYU, and will soon be making a move to DeepMind technologies, a company headed up by none other than Demis Hassabis, who gave a talk at Imperial's GaME event not so long ago about some fascinating work DeepMind are doing on artificial intelligence. He can still be contacted by the work if you have questions, and you can also find the entire project open-sourced on GitHub here. Stephen Lavelle has recently moved to Berlin where he's continuing to develop wonderful games and projects like PuzzleScript. Stephen is also on Twitter if you want to keep up with his latest work!