Using Large Scale Search for Game Design
AIIDE 2014 Playable Experience Submission
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.
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
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
(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
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
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
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.
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 "
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
- 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 corer 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
- 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
- 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
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.
The about screen in the game is no longer in sync with this web page.
A rare bug in the code that checked for duplicate states was fixed that
has changed the levels slightly.
If you are having trouble with the game, we suggest downloading
Fling! Free to get a better tutorial and other sample levels.
Note that we use slightly different single-solution constraints.
Fling! allows two moves which lead to exactly the same state in a
solution while we do not:
Moving the bottom pieces together would be allowed as part of the structure of a large puzzle in Fling!
but not in Penguin Push (except for first level which doesn't use the single solution constraint).
Related Resources / Links
© Nathan Sturtevant, All rights reserved.