Hosted Pages



Pathfinding Benchmarks



Grid-Based Path Planning Competition



AAAI 2017 Job Fair


AAAI 2017 Workshop on what's next for AI in games


Archived Pages


AAAI16 Student Activities

AAAI15 Student Activities

MAPF 2012 Workshop

AIIDE 2011

GIGA 2011

SoCS 2010

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:

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.

  • 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.