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