Moving AI Lab

Using Large Scale Search for Game Design

AIIDE 2014 Playable Experience Submission

Main Idea

When contraints exist that will help someone solve a puzzle, the puzzles should be selected to maximize the gain acquired by the user from understanding the constraints. We use search (AI) tools to build levels for a game which maximizes this gain.

Background

There is wide interest in the general idea of procedural content generation, particuarly for generation of maps and natural structures. We are interested in a slightly different problem of procedurally assisted design -- tools that will help designers create interesting experiences, but where the designer still has a strong role in the creation process. The design role is just assisted by the strengths of the computer - the ability to efficiently perform significant brute-force computations.

Designer Jonathan Blow has often talked about his process of discovering the puzzles that exist when a set of mechanics are created for a game. In a sense, our goal is to automate parts of this process so that the mechanics can be explored and understood more quickly and thoroughly.

Project Goals

This specific project arose from an analysis of the game Fling!, a popular mobile game. In our previous analysis (http://web.cs.du.edu/~sturtevant/papers/BFS-design.pdf) we looked at this game from the perspective of the number of reachable states in each puzzle (we refer to a single puzzle as a "board"). There are 35 levels of difficulty in the game which are presumably of increasing difficulty. While there is a correlation between reachable states and the level of a board, there is also tremendous variation.

The game also has constraints -- in particular that there is only one solution for every board. This means that there is exactly one move in each board configuation that will lead to a solution. Looking at the reachable states in the reduced state space (eliminating moves that would require the solution to violate the above constraint) we still found the same trends. In particular, that there wasn't a strong correlation between the size of the search space and the difficulty of a level. There can be an order of magnitude difference in the number of states reachable by a breadth-first search on the same level. The breadth-first size tracks the levels well as the number of pieces on the board increases. Once the number of pieces on the board plateau's, so does the number of states in the breadth-first search.

We hypothesize that there is a correlation between the size of the search tree and the difficulty of a problem - this is one possible measure of the difficulty of a problem. (Although it isn't difficult to design puzzles for which this rule will not hold, such problems often contain many unnecessary elements which can easily be abstracted away.) Futhermore, we believe that one mark of a good puzzle is that it is relatively easy for experts, but difficult for novices. This suggests further than an expert that deeply understands the constraints in a puzzle should be able to solve it quickly (a small search tree), where a novice that doesn't understand these constraints should have a difficult time (a large search tree). So, the ratio of the brute-force tree size to the constraint-reduced tree size is a second measure that we believe is interesting for level design.

(Clearly if this ratio is 1 then there is no gain from understanding the constraint and using to help solve boards.)

Creating a Playable Experience

The goal of the game Fling! is to push (or fling) all objects off of the playing area until only a single piece remains. We build a similar game with penguins on an ice sheet. Each action must push a penguin into a non-adjacent pengiun. Pieces cannot be pushed directly off of the board, but must first collide with another piece. Collisions are elastic, so each action pushes a single piece off of the board. Here is a sample board that has two legal moves. (The penguins are drawn as black squares.)

Moving either of the pieces in the 6th row to the left/right will cause the other piece to leave the board, and will leave the pushed piece in the middle of the original configuration. Taking either of these actions results in the following board:

At this point either piece can be moved up or down to complete the puzzle.

Because there are two legal moves that both lead to the same solution, the original board did not have a unique solution. But, the original board is interesting because there is no way to lose - all actions lead to a winning configuration. (Note that when there are two peices left on the board there are always either 2 or 0 legal moves. So, our definition of unique solutions only applies to boards with 3 or more pieces.)

The original game of Fling! has a unique solution constraint but it isn't always helpful. We used large-scale search to enumerate and filter levels in order to automatically build the most interesting problems which meet the single-solution constraint.

We began the process of creating interesting levels by enumerating all levels which were both solvable and uniquely solvable using retrograde analysis. A board is solvable if it contains a move which moves to a board which is solvable. A board is uniquely solvable if it contains a single move which leads to another board which is uniquely solvable and no other moves can reach solvable states. The number of boards in each of these categories is shown below.

No significantly complex approaches are needed to solve boards with up to 11 pieces, although we have built software that can scale to larger boards. (With 11 pieces there are 56!/11!45! = 148.9 billion possible boards.) Of all of these 11-piece boards, only 13.7 millions boards are unique solvable.

Given these 13.7 million boards we first remove as many symmetries as possible by converting to a canonical representation. Then, we solve each board using a regular breadth-first search and also using a breadth-first search which only generates moves according to the uniqueness constraints. We compute the ratio of these sizes for each board, and then choose top 50 boards by a secondary sort on the size of the brute-force tree. These boards were then placed in our playable experience.

We also did this for boards with 7 pieces, 8 pieces, and 11 pieces; we could easily do this with other board sizes. The resulting levels are placed in the playable experience: Penguin Push. For constrast, we placed two other sets of levels in the game. The first set are those for which all legal actions lead to a solution. The second set are those with a ratio of 1: knowing the single-solution constraint gives no guidance on finding the solution.

Below we describe some of the things that users should take note of when playing this experience.

Play Notes

Some important notes with playing the experience:

• In our experience the provided levels are challenging, but rewarding, as they can be difficult to solve. It seems that humans do a better job on levels where the same penguin moves repeatedly. We are considering incorporating this into the selection algorithm.
• We have labeled each level with the number of states in the reduced breadth-first search in brackets. Thus, the level marked "Level 3:1 [22]" is the first level in the third (medium) pack. There are only 22 legal states when taking the uniquess constraint into account. (There are 145 otherwise.)

  With 7 pieces on the board the maximum reduction factor due to understanding the uniqueness constraint is 4.6. With 8 pieces the reduction increases to 8.2. With 11 pieces this increases further to 26.7. An expert should be able to ignore moves which don't meet this constraint, while a novice will not be able to.

• The levels work as follows:
  • Intro: All moves lead to a solution.
  • Easy: Levels with 7 pieces. (Only a single move leads to the solution at each step.)
  • Medium: Levels with 8 pieces. (Only a single move leads to the solution at each step.)
  • Hard: Levels with 11 pieces. (Only a single move leads to the solution at each step.)
  • Bad: Levels with 8 pieces. (Nothing can be inferred from knowing the uniqueness constraint.)
• The key to understanding this playable experience is to understand the uniqueness constraint. Some may understand the implications of this constraint immediately, but we provide several examples to help explain this:
• Here is an easy example to understand the uniqueness constraint.

  While this board is solvable, it is not unique solvable. There are several possible first moves, one of which results in this state:

  A similar move could be made at the bottom of the board before solving the level, but these two moves can be made in any order. Hence, there is more than possible move at each step.

  The uniquesness constrain means that you will never make parallel moves like this. If you could make two moves in any order to reach the solution, there must be more than one legal move that leads to a solution.

• Here is a more complex example to help understand the uniqueness constraint. Consider the first board in the medium difficulty (pack 3) set:

  Knowing the unique solution constraint, we can eliminate moving the piece in the upper-left corner as the first move. The only legal move for this piece would result in the board:

  After making this move, there are no additional moves that can be made with this piece, and there are no moves which couldn't have been made in the previous step. Thus, no new moves are enabled by this action and this can't be the first step in a unique solution. The opposite move, however, results in this board:

  This board allows two new moves: either the piece in the top row is moved down or the piece in the bottom row is moved up. In fact, this is the only initial move which allows additional moves, and one of these two moves will lead to the solution.

• We chose to put the raw levels into the playable experience even though in practice these should be curated by a designer, and further constraints might be used to select interesting levels. This illustrates what the final output of our process looks like and how much additional work might be needed for further refinement. While we did remove levels that had a Hamming distance less than 2, we still ended up with very similar levels. The fewer the pieces on the board, the more often this occurs. Consider medium difficulty levels 3:5 and 3:7.

  From a solution perspective these levels are identical. Yet, it is also the case that small changes to a board can complete alter the solution. Thus, it is an open question of how to detect boards which are close enough to be uninteresting versus boards which are similar, but unique. (One possible approach is to correlate the moves used in the solution for each board.)

  See the Shigi video in the links below for a picture of how the interactive design process might work.

  There are several other examples of similar levels with the playable experience.

• Players might notice themes emerging across sets of levels. For instance, the solutions to the first few medium levels often use a mechanic of putting two pieces next to each other. This process was completely emergent.
• We apologize for not putting the game onto the App Store. While the game is fully functional, the number of small details which need to be refined to make the game accessible to the general public was a bit too large to complete for this years playable experience deadline. (Jeff Orkin will decide how to handle this and will handle this submission independently.)

Download

You can now download the current version of Penguin Push (working title). The build runs on iPad and iPhone but is currently only provisioned for the AIIDE playable experience reviewers devices.