author: Ruiyuan Li
title: How to Win Friends and Influence People with Probabilistic Grammars
keywords: probabilistic grammar, procedural content generation
topics: Algorithms and Data Structures , Case studies and Applications , Creative
committee: Marcus Gerhold ,
Vadim Zaytsev
started: April 2021


This project is a crossover of game studies and generative programming.

On one side, we have procedural content generation, a powerful technique that allows to replace the static content created carefully (and expensively!) by the game designer, with the dynamic possibility to generated such content on demand. This greatly increases replayability of a game while decreasing its development costs, and opens the door to many opportunities unthinkable before, like adapting the generated content to the actual player based on the accumulated observations of the player. In one form or another, PCG has been used in Diablo, Civilization, Minecraft, Dwarf Fortress and many other innovative and commercially successful games.

On the other side, we have probabilistic grammars, capable of expressing the notion of structural correctness. When "normal" (non-probabilistic) grammars are used to express programming languages, database schemata, XML/JSON formats and communication protocols, probabilistic ones can be used to predict DNA sequences, handle uncertain and unreliable data, automate reasoning in healthcare, generate popular tweets, infer types in programs and detect rhymes in rap lyrics. So why not game content?

In particular, this project focuses on using probabilistic grammars for procedurally generating characters (and groups of them: teams, guilds, parties, etc) with their names, concepts, abilities, backgrounds, backstories, etc. There is a somewhat similar project about game locations as well.

The project will be supervised by dr. Marcus Gerhold, an expert on probabilistic systems and automata, and dr. Vadim Zaytsev, specialised in grammars and generative techniques, both enthusiastic and invested in procedural content generation.