Encoding and Generating
IEEE Computational Intelligence and Games 2012
Mark J. Nelson
Encoding? Generating? Mechanics?
- Encoding: a representation of a game
- Generating: producing new games (or game variants)
- Game mechanics: roughly, a game's logic
Game generation versus PCG
As in regular game development, what constitutes an asset can have gray areas.
- Procedural content generation focuses on assets: levels, items, terrain, etc.
- Game generation focuses on... non-assets.
- Core of the game in some sense
This tutorial's approach
- A "correct" approach to explain isn't settled yet
- Survey of systems and papers
- End with some proposals for future work and connections
I'll be pulling up a few of the papers during the talk. To follow along:
(If you're reading this online after my talk, that link is a better summary
than reading these slides!)
First cluster of systems: board games
A significant chunk of work, including the earliest.
- Board games have nice formal structure
- Discrete, turn-based
- Established culture of inventing formal variants
- Defines a generative space of games more general than chess
- "Symmetric, chess-like games"
- Motivation: worry that chess-playing AI had delved too deeply into special-case code, away from fundamental advances in intelligence
B. Pell, "METAGAME in symmetric chess-like games." In Heuristic Programming in Artificial Intelligence 3 – The Third Computer Olympiad. Ellis Horwood, 1992.
- Ontology: board, spaces, pieces with movement, capture, and promotion rules
- Goals: stalemate, eradicate, or arrival
- Symmetric by construction
- "...a tradeoff between generality, where we prefer classes which can
describe the widest variety of games, and structure, where we prefer a class
where the individual games appear to have similar underlying
(See example on p. 14)
Probabilistic grammar, which is possible due to the encoding.
- Roughly balanced by symmetric construction
- The defined space of games is dense in playable games (though still needs some checks)
- Modularity-breaking references mix logic among the generated branches
- (Some) high-level controllability
Metagame control knobs
- Rule complexity
- Decision complexity
- Indirect: search complexity
- Indirect: locality
Balanced board games
- Metagame aims for rough balance by construction.
- We could explicitly check for balance by simulation
- Proposal: A game is balanced if a general gameplaying engine playing itself gets roughly equal win rates on each side
Significantly smaller representation space than Metagame, in a subset of Zillions of Games ZRF format.
Space searched with a genetic algorithm.
V. Hom & J. Marks, "Automatic design of balanced board games", AIIDE 2007.
Evolutionary game design
Ludi proposes a much more ambitious framework:
- Criteria other than balance, e.g. aesthetics
- Search a much larger space, via recombination of game elements
- Distinguish variants from new games (game distance)
C. Browne & F. Maire, "Evolutionary game design", TCIAIG 2(1), 2010.
Second cluster of systems: graphical logics
Vaguely an old-school arcade style:
- 2d objects that might move
- Of several kinds
- Player typically controls one (often single-player)
- Collisions might happen and have effects
- Some kind of goal
Designing graphical-logic games
What makes an interesting graphical-logic game?
- Compared to board games, less existing formal structure and theory for evaluation
- Concepts of "balance" and "strategies" in 1-player games are different
Evolving graphical-logic games
Proposal: "a game is fun if it is learnable but not trivial"
- Related to theories of fun and curiosity (1-player balance?)
- Implementation: A game is good if a controller can be learned to beat it, but not a very trivial controller
- Evolve rules and evolve controllers
J. Togelius & J. Schmidhuber, "An experiment in automatic game design", CIG 2008.
Sculpting game spaces
Proposal: declaratively specify the boundaries/contents of a game space
- Flexibility: less fixed up-front ontology of elements
- Constraint-based: include or exclude games based on written criteria
- Aim is generative-space sculpting rather than optimization
- Implementation: answer-set programming
A.M. Smith & M. Mateas, "Variations Forever: Flexibly generating rulesets from a sculptable design space of mini-games", CIG 2010.
Proposal: Integrate PCG concerns such as level and NPC generation into the rule-generation system
- Possible synergy as elements play off each other
- Larger search space (unless further constrained)
- Internal and external criteria
- Interest in modularity, possibly in mixed-initiative design
M. Cook & S. Colton, "Multi-faceted evolution of simple arcade games", CIG 2011.
Could we generate something like this?
Factoring game design
Four design-knowledge areas:
- Abstract mechanics: order-fulfillment
- Concrete representations: sliding beer, customer position
- May have their own mechanics, e.g. collision-detection
- Input mappings: control bartender, hold/release button
- Thematic elements: in a bar, serving customers
M.J. Nelson & M. Mateas, "Towards automated game design", AI*IA 2007.
What do game-generation systems generate?
- So far, mechanics at some level
- Some more abstract, some more concrete, usually not strongly separated
- Generate concrete representations for abstract games (a few exist)
- Generate thematic mappings (a few exist)
- Generate input mappings (open research topic?)
Generating concrete representations
Given an abstract game, can we assign audiovisual elements and layout to its abstract state/events, and make it playable?
- So far, "game compiler" systems
- Specified ontology, rule-based compilation
- Ties into code-generation, automatic programming
J. Orwant, "EGGG: Automated programming for game generation", IBM Systems Journal 39(3-4), 2000.
Generating thematic mappings
Proposal: an auto-skinning system
- What is the relationship between mechanics and the skin?
- Mechanics define nouns and verbs
- Constraints on mapping skins to those nouns/verbs
M.J. Nelson & M. Mateas, "Towards automated game design", AI*IA 2007.
M.J. Nelson & M. Mateas, "An interactive game-design assistant", IUI 2008.
Generating rhetorical games
Can the mapping be more than just "making sense"?
- User supplies a concept map they want a game about
- Codify rhetorical strategies in simple games
- Devise appropriate mappings
M. Treanor, B. Blackford, M. Mateas, I. Bogost, "Game-O-Matic: Generating videogames that represent ideas", PCG 2012.
M. Treanor, B. Schweizer, I. Bogost, M. Mateas, "The micro-rhetorics of Game-O-Matic", FDG 2012.
Connections to other areas
- Game-mechanic encodings as game ontology
- Formalized game mechanics for design support and verification
Game-mechanic encodings are formal specifications about what games "are" and "contain", at least in a particular domain.
- Less-formal catalogs of components: Game Ontology Project, even TVTropes
- Historical investigations of game-element genealogy
- Discussions around specific genres
J.P. Zagal et al., "Towards an ontological language for game analysis", DiGRA 2005
J. Juul, "Swap adjacent gems to make sets of three", Artifact Journal, 2007.
J.P. Zagal, C. Fernandez-Vara, M. Mateas, "Rounds, levels, and waves: The early evolution of gameplay segmentation", Games and Culture, 2008.
Also may have formal encoding of game mechanics.
- Aim to give feedback about a design.
- May be editable, but not primarily focused on variation, or automatic design.
J. Dormans, "Machinations: Elemental feedback structures for game design", GAMEON-NA 2009.
A.M. Smith, M.J. Nelson, M. Mateas, "Computational support for play testing game sketches", AIIDE 2009.
extensible, reusable domains
- Can we codify things like "graphical logic", "combat system", and associated mechanics?
- Cyc of game design? A formal TVTropes? Something else?
- Some existing concepts: ludemes, operational logics
- My own quick-and-dirty vocabularies/mechanics
- How would generation algorithms adapt to cope?
M.J. Nelson & M. Mateas, "Recombinable game mechanics for automated design support", AIIDE 2008.
M. Mateas & N. Wardrip-Fruin, "Defining operational logics", DiGRA 2009.
Submit to FDG 2013!
If you're interested in doing or seeing more of this kind of work, consider
submitting to and attending Foundations of Digital Games 2013.
- Chania, Crete. 14-17 May 2013.
- Workshop proposal deadline: 28 October
- Paper deadline: 10 December