Notes on Research Paper: Automatic Game Progression Design through Analysis of Solution Features by Butler et al.

November 19, 2019

Thesis Research

Notes on Resources

TITLE:

Automatic Game Progression Design through Analysis of Solution Features

AUTHORS:

E. Butler, E. Andersen, A. M. Smith, S. Gulwani, and Z. Popović

IEEE Citation - Zotero

[1]E. Butler, E. Andersen, A. M. Smith, S. Gulwani, and Z. Popović, “Automatic Game Progression Design through Analysis of Solution Features,” 2015, pp. 2407–2416.

ABSTRACT

- use intelligent tutoring systems and progression strategies to help with mastery of base concepts 

as well as combinations of these concepts

- System input: model of what the player needs to do to complete each level

- Expressed as either:

- Imperative procedure for producing solutions

- Representation of features common to all solutions

- System output: progression of levels that can be adjusted by changing high level parameters

INTRODUCTION

- Level Progression: "how game introduces new concepts and grows in complexity as the player progresses"

- link between level progressions and player engagement

- "Game designer Daniel Cook claims that many players derive fun from “the act of mastering 

knowledge, skills and tools,” and designs games by considering the sequence of skills that the 

player masters throughout the game [11]."

- *** Why we want to have system produce similar but varied versions of the same type 

of experience

- "Intelligent tutoring systems (ITS) [29, 22] have advanced the

teaching potential of computers through techniques that track

the knowledge of students and select the most appropriate

practice problems [8, 12]."

- "We aim to enable a different method

of game design that shifts away from manual design of levels

and level progressions, towards modeling the solution space

and tweaking high-level parameters that control pacing and

ordering of concepts"

- *** Possible major goal of my research

- "Andersen et al. [1] proposed a theory to automatically

estimate the difficulty of procedural problems by analyzing

features of how these problems are solved"

- Procedural Problems: those that can be solved by following a well-known solution procedure

- i.e. Integer division using long division

- Procedural Paths: code paths a solver would follow when executing procedure for a particular 

problem

- Use this as a measure of difficulty

- "This is mainly because Andersen’s

framework does not account for pacing. In contrast,

our system allows a designer to control the rate of increase

in complexity, the length of time spent reinforcing concepts

before introducing new ones, and the frequency and order

in which unrelated concepts are combined together to construct

composite problems"

- *** Another goal/direction for my research

RELATED WORK

- Intelligent Tutoring Systems have "several models for capturing student knowledge and selecting 

problems"

- *** Possible future work research

- "Generated levels are not useful in isolation; they must be sequenced

into some design-relevant order, called a progression"

APPLICATION

- Game called Refraction

- split lasers into number fractions that need to satisfy certain values at end

SYSTEM OVERVIEW

- Level: "any completeable chunk of content"

- Level Progression: "sequence of levels that create an entire game"

- Solution Features: "properties of the solution to a level"

- "need to be able to extract features from the levels that can

be used to create an intelligent ordering" for progression

EXTRACTING SOLUTION FEATURES

- Example of following procedural traces and n-grams within the exercise of doing hand subtraction

- Certain steps have a letter output that is recorded to see if a certain type of step 

was used and how often (i.e. Was borrowing necessary for subtraction?)

- n-grams: n-length substrings of the trace

- Example: Trace = ABABCABAB

- 1-grams: {A, B, C}

- 2-grams: {AB, BA, BC, CA}

- 3-grams: {ABA, BAB, ABC, BCA, CAB}

- 1-grams are fundamental concepts

- Compare complexity by comparing n-grams

- They used these general concepts to build their own similar, but not identical, system

- their game didn't fit this model perfectly well, so they broke their game down into 

graph objects that they thought were more representative

- they had fundamental graph objects (similar to 1-grams), that could then build into 

more complex graph objects by combining these defined fundamental graph objects

AUTOMATICALLY GENERATING LEVELS

- "We applied the level generation process described by Smith et

al. [30] to generate a large and diverse database of puzzles"

- *** Look into this for our system?

CREATING A PROGRESSION

- n-grams = graphlets (their specific type of n-gram)

- "To summarize, given two levels L1 and L2, L1 is considered conceptually simpler if, for

some positive integer n, the set of n-grams of L1 is a strict subset of the set of n-grams of L2"

- if a level contains the steps required for another level, it is more complex (has the same and 

more basically)

- Because of several issues, their approach was create a rather large library of generated levels 

to choose from, and choose a select few that represent an effective progression

- model tracks whether player has completed a problem containing each component

- also track n-grams of those components (up to very small n as values get exponentially huge)

- hard to know what to do on failure

- General Framework:

- set of problems

- domain of concepts

- player model

- These three things are what are used to generate sequence of problems for the player

- Choosing the Next Problem

- given current model state and set of problems, what is appropriate next problem?

- dynamic cost model

- cost of problem, p, is weighted sum of the n-grams in the trace of p

- weight has 2 components:

- one based on what model knows about player

- one designer-specified weight

- Player Model Cost:

"First, at each point in the progression, for a given n-gram

x, the player model assigns a cost k(x). This cost should

be high for unencountered n-grams and low for ones already

mastered, which will ensure more complex problems have a

higher cost than simpler ones with respect to the player’s history"

- Designer Added Cost:

"as expert designers, we know

(possibly from data gathered during user tests) that particular

concepts are more challenging than others or should otherwise

appear later in the progression"

- "Thus, given a library of problems P, choosing the next problem

pnext consists of finding the problem with the closest cost

to some target value T"

- "In order for this sequencing policy to be effective, it requires

a large library of levels from which to choose. The levels

should be diverse, covering the space of all interesting solution

features. Furthermore, in order to enable effective control

of pacing, this space should be dense enough that the progression

can advance without large conceptual jumps"

- *** Supports need for my thesis work