Home About EIS →

From Breakout to Space Invaders, All Over Again

In the past, I’ve written about game design as a new domain for automated discovery, in which one might build discovery systems which uncovered new and interesting knowledge in game design. However, unless you are already familiar with discovery systems, all this might sound too blue-sky to even visualize. So what does it even mean for machine to discover something about game design?

In the prehistory of discovery systems for mathematics and science it wasn’t clear either. It took the development of working systems to give a clear idea of what automated discovery would look like in those domains, and the first hint was in rediscovery of existing knowledge. AM (the “Automated Mathematician”) rediscovered Goldbach’s conjecture about prime numbers through open-ended tinkering with small integers. BACON rediscovered Kepler’s Third Law governing the motion of planets around the Sun by exploring a space of symbolic expressions in relation to a fixed data set (a very early success in what is now popularized as data mining).

If rediscovery provides the first clear evidence of automated discovery in some domain, what would you dare a system to rediscover in game design? We don’t have any sort of “Miyamoto’s Second Law of Platformer Jumping Mechanics” (though it would be pretty neat to see it if it existed). We’ve got the 400 Project and Koster’s Laws of Online World Design, but these are more like wisdom, an intangible step above the kind of solid knowledge we might one day bake into bad-ass design tools. The Game Ontology Project is closer, but what’s something really obvious?

Ok, System, let’s see you rediscover Space Invaders after I feed you Breakout as input.

Here’s a story of a hypothetical system doing exactly that. I wrote this for an earlier project proposal, but I had to cut it out before the final version.

To show how our system would work in the context of known games, let’s look at how it might recreate the development of Space Invaders given Breakout as inspiration, a well-known, historical innovation that took place in the 1970s. We briefly review the core mechanics of both games first.

In Space Invaders, the player controls a laser cannon which can move horizontally across the bottom of the screen, firing bolts upward at a moving, rectangular grid of aliens. Aliens are removed from play when touched by a bolt. As the aliens progress down the screen, bouncing (as a group), defeat is triggered if aliens touch the row of the screen that holds the laser cannon and victory is triggered if all aliens are removed.

The mechanics of Breakout, the earlier game, involved a player-controlled paddle that moved horizontally across the bottom of the screen. A single ball bounces off of walls, the paddle, and a fixed, rectangular grid of bricks. When bricks are touched they are removed. If the ball reaches the row of the screen that holds the paddle and the paddle is not present, defeat is triggered. Likewise, when all bricks are removed victory is triggered. Clearly, Space Invaders drew on patterns set in Breakout (just as many of the mechanics of Breakout are found even earlier in the game Pong).

Consider the scenario where our system is given a logically-encoded version of Breakout as inspiration. We assume the system has a basic design theory already in its working memory (consisting of some small to medium scale design patterns and a fairly loose set of recombination rules) and knowledge of other games such as a logical version of Pong.

Because the system would like to produce design knowledge, it finds a sequence of tasks that it thinks (on the basis of a task decomposition) will lead to the ability to concisely explain how the unfamiliar artifact, Breakout, was produced. The first such task is to apply the design decompilation tool to explain Breakout’s construction using the current design theory. This will produce one such construction plan, but it will likely be quite long. Noticing regularities with the construction path determined for Pong, the system proposes the general pattern of having defeat triggered when a movable object is on the bottom row of the screen. Likewise, it will have already proposed patterns for objects that move with constant velocity and bounce off of walls. Adding these defeat conditions as a new design pattern, the system can now explain how to construct Breakout in fewer steps than it did originally.

By imagining gameplay traces from Breakout, the system can induce that players (who are headed towards victory) always reflect the ball up from their paddle towards the grid of blocks for removal. To produce a demonstration of this player modeling rule in a new game, the system sets out to build a new game for which the requirements of that rule are present (that the game have a single moving element that removes other elements from a fixed grid when touched and the moving element rises up from the player-control “paddle” at the bottom of the screen) but some other mechanics have changed. To build such a game, the system follows almost all of the same steps as in the abduced construction of Breakout, modifying a few steps at the end to produce a new game. In this Space Invaders producing modification, the wall-bouncing mechanic is transferred to the grid of bricks (now with alien-art by chance) and the ball itself is now created on the player’s command (partially recycling the serving mechanic of Pong that was retained in Breakout).

Having designed a new game, it continues its experimental plan to verify its proposed player modeling rule. It invokes the design compiling tool to build a testable version of the game. Next, it invokes the trace generation tool, specifying the previous player modeling rule and looks to see that there are traces in which the victory event happens (that the imagined Breakout player can occasionally beat Space Invaders by applying the same heuristics). If the rule is verified, the system saves this evidence back into its working memory.

By the end of this process the system has not only designed a new game but invented and experimentally verified that a new player choice predicting rule can be applied to more than the game it was inspired by. While the real Space Invaders actually drew on contemporary cultural influences such as Star Wars for its thematic inspiration, we have an explanation of how such a game might have been invented on the basis of purely-curious motivations (curiosity about design knowledge). It is interesting to note that the real Space Invaders also only allowed one bolt on the screen at a time, suggesting an even closer link to Breakout’s mechanics than might be expected. The general notion of projectiles (or even a multi-ball version of Breakout) had not yet been developed.

Ok, Spacewar had projectiles in 1961, but it certainly wasn’t a distinguishable pattern across games yet. 1979’s Galaxian had a fixed number of projectiles while it seemed that 1980’s Defender did not have this limitation… What’s more interesting here is where the story above makes reference to a few things that don’t really exist yet.

There’s a “task decomposition” of game design that tells the system how to go about doing the smaller processes of game design (making code changes, proposing a design pattern, compiling a prototype, getting a playtester to try the game, etc.) in a way that leads to new design insights. It would be fantastic if we could just look up all of the processes of game design in a book, but this isn’t something you can find. Part of building a discovery system in game design would be proposing and trying out different task decompositions, seeing which lead to coherent behavior, and seeing what tricks a human designer might steal from the system. What’s the main loop of game design? What are the steps? Even approximate answers here would give us fresh perspective.

There’s a design decompiler that turns foreign game designs into a sequence of instructions for rebuilding it from familiar parts. Now there’s something I’d like for my birthday! Decompilers aren’t unheard of, but the trick is getting them to decompile a game into the language of game design pattern. The problem here is that what we call “design patterns” aren’t currently formal enough for use in this kind of tool. In fact, it might even take some hands-on experience with an automated system before we can really say what makes good, code-level design patterns for game design – like software design patterns, but with hooks for understanding interactive play. Most game programming tools are all about cramming your design into code, but with a nice design decompiler you could get a handle on the emergent design you get when you make those inevitable programming mistakes.

Finally, the story has us feeding classic games into a computer and expecting it to understand them. We aren’t talking about talking about stuffing arcade cabinets into a wood chipper. Instead this refers to making a reasonably faithful model of these games in a formal language which the system can already process. This one isn’t even that crazy, we can do it now. My “logical game engine”, Ludocore, has already been used to produce prototype-quality game models that are both human playable and machine analyzable (example game here). Getting this technology to talk to a design decompiler will enable us to implement a few of the small steps in the larger task decomposition of game design.

It might be a while before we see any automated system rediscovering Space Invaders, but at least we now have a story of what it might be like and why the system would do it in the first place.

post scriptum: If you want a picture to help you visualize one possible architecture for a game design discovery system, have a look at this:

About the author:  Adam is a PhD student, research scientist, software engineer, musician, artist, and hacker. He has a very special kind of respect for those elegant weapons like lisp (pronounced "scheme") and prolog, for a more civilized age. Read more from this author

This entry was posted in Academics and tagged , , , , , . Bookmark the permalink. Both comments and trackbacks are currently closed.