# Grammar-based Game Description Generation
using Large Language Models

Tsunehiko Tanaka, Edgar Simo-Serra The authors are with Waseda University,
Tokyo, Japan. (Corresponding author: Tsunehiko Tanaka, email:
<EMAIL_ADDRESS>
###### Abstract

To lower the barriers to game design development, automated game design, which
generates game designs through computational processes, has been explored. In
automated game design, machine learning-based techniques such as evolutionary
algorithms have achieved success. Benefiting from the remarkable advancements
in deep learning, applications in computer vision and natural language
processing have progressed in level generation. However, due to the limited
amount of data in game design, the application of deep learning has been
insufficient for tasks such as game description generation. To pioneer a new
approach for handling limited data in automated game design, we focus on the
in-context learning of large language models (LLMs). LLMs can capture the
features of a task from a few demonstration examples and apply the
capabilities acquired during pre-training. We introduce the grammar of game
descriptions, which effectively structures the game design space, into the
LLMs’ reasoning process. Grammar helps LLMs capture the characteristics of the
complex task of game description generation. Furthermore, we propose a
decoding method that iteratively improves the generated output by leveraging
the grammar. Our experiments demonstrate that this approach performs well in
generating game descriptions.

###### Index Terms:

Large Language Model, Ludii, Game Description Language, Grammar, Game
Description Language Generation

##  I Introduction

Game design and development requires a significant amount of expertise,
creating barriers that limit individuals trying to create game experiences in
various fields such as education, cultural participation, healthcare, and
engineering. To reduce these skill barriers and promote the democratization of
the game design process, techniques to reduce the workload and streamline the
design process have become increasingly important. Various machine learning
(ML) techniques have been successful in automated game design, including MCTS
[1], random forests [2], and concept expansion [3]. Deep learning-based ML is
often used in the domain of procedural content generation for level design [4,
5, 6]. However, despite the progress of Game Description Language (GDL)
frameworks [7, 8, 9, 10] in automated game design, there are few examples of
applying deep learning techniques from natural language processing to GDL.
This is because deep learning techniques require a large amount of training
data, making them less prominent in automated game design, where data is
scarce. Further validation of the applicability of modern machine learning
techniques in automated game design is needed [11].

In this work, we focus on Large Language Models (LLMs) [12, 13] as a new
approach to solving tasks with limited data. LLMs are transformer [14]-based
deep learning models with a vast number of parameters, pre-trained on a large
corpus of textual data. One of the outstanding abilities of LLMs is their
capacity to solve various tasks, such as program synthesis [15, 16], using the
capabilities acquired during pre-training without additional training. By
providing LLMs with task demonstrations consisting of several input-output
pairs $(x^{(i)},y^{(i)})$ and a natural language instruction $x$, LLMs can
capture the features of the task, in a process known as in-context learning
[17]. In automated game design, by providing LLMs with demonstrations of past
high-quality game designs represented in a GDL, LLMs can generate game
descriptions $y$ using the extensive knowledge obtained during pre-training.

It is challenging to characterize minor domain-specific concepts and semantics
from only a few demonstrations [18], even for LLMs. In this work, we propose
augmenting the LLM with a grammar $G$ of a GDL into the game design process,
as shown in Fig. 1. A GDL represents the game design space structure well, and
its grammar can represent the features of the game design generation task with
high data efficiency. The minimum grammar $G[y^{(i)}]\subseteq G$ required to
construct $y^{(i)}$ is added to the demonstrations. The generation process
consists of two stages: the generation of rules in grammar $G[y]$ and the
generation of the game description $y$. Furthermore, we propose decoding
methods specialized for each stage, which iteratively improve the output of
the LLMs using the grammar $G$.

Our contributions can be summarized as follows:

  * •

We propose a novel framework for automated game design by combining Large
Language Models (LLM) and Game Design Languages (GDL).

  * •

Our framework introduces the grammar of a GDL into the generation process
based on in-context learning with LLMs.

  * •

We propose iterative improvement decoding methods specialized for grammar
generation and game description generation, respectively.

  * •

We demonstrate the effectiveness of our framework through extensive
experiments on game description generation.

Figure 1: An overview of our framework for grammar-based game description
generation. We use the grammar of a Game Description Language (GDL) and Large
Language Model (LLM) to generate the game description $y$. First, we generate
the grammar $\hat{G}[y]$ required to construct $y$ in the Rule Decoding stage,
and then generate $\hat{y}$ based on $\hat{G}[y]$ in the Game Description
Decoding stage. The core of our framework consists of iteratively decoding to
improve the generation, and employing LLMs and the explicit GDL grammar.

##  II Related Work

###  II-A Game Description Language

Game Description Language (GDL) is a domain-specific language for games. GDL
[9] was introduced in 2005 and has become the standard in General Game
Playing, where artificial agents are developed to play a wide variety of
games. After GDL, various types of GDL have been developed. VGDL [8] is a
language that represents both the levels and rules of 2D sprite-based games.
RBG [10] models complex board games by combining low-level and high-level
languages. Ludii [7] is a game system developed based on the ludemic approach,
which decomposes games into conceptual units of game-related information.
Ludii models more than 1,000 traditional games, including board games, card
games, dice games, and tile games. The Ludii system generates a complete game
description in the Extended Backus-Naur Form (EBNF) style. Diverse analyses of
games using Ludii, especially focusing on board games, have been conducted
[19, 20, 21, 22, 23]. For example, [19] calculates the distance between board
games using concept values extracted from Ludii. Matthew _et al._ [20]
proposes a framework for automatically generating board game manuals using
Ludii. In our work, we use Ludii as our GDL. Furthermore, unlike these works,
we add a new perspective to the analysis by focusing on game description
generation using grammar.

###  II-B Automated Game Design

Automated game design [24, 25] is one of the core themes in the field of game
AI. As AI technology rapidly advances, various aspects of how AI can be
utilized in automated game design have been discussed, including the design
process [26], design patterns [27], and creative machine learning [28].
Several studies [29, 30] propose methods to generate a game by integrating
multiple elements such as visuals, audio, narrative, levels, rules, and
gameplay. Generating games using new representations such as answer set
programming [31] and game graphs [3] is also explored.

Automated game design for generating game designs in the VGDL [8] format has
been explored [32, 33, 1, 2]. Thorbjørn _et al._ [32] explores the approach to
generate VGDL for arcade games using evolutionary algorithms. GVG-RG [1]
proposes a framework for generating appropriate game rules for given game
levels. Cicero [33] is a mixed-initiative tool that assists in prototyping 2D
sprite-based games using VGDL. Thomas _et al._ [2] aims to acquire a fitness
function that guides game design generation using adversarial random forest
classifiers. Our approach shares the use of VGDL with these works but differs
in exploring new possibilities for automated game design using LLMs.

###  II-C Large Language Models in Games

Since the advent of ChatGPT [34] in late 2022, Large Language Models (LLMs)
have attracted significant attention, and various ways of using LLMs in the
game domain are being explored [11]. The goal of procedural content generation
(PCG) is to generate content used in digital games, such as rules and levels,
and LLMs are frequently tested in this field [4, 5, 6, 35, 36]. Several works
[4, 5, 6] use LLMs to generate 2D tile-based game levels. Another work [35]
trains a GPT model to generate quests for role-playing games. LLMGG [36]
generates both the rules and levels of games represented in VGDL using LLMs.
In LLMGG, LLMs take a part of the VGDL [8] representation or examples of other
games as prompts, which generate a complete VGDL-based game in one step. The
authors discuss that incorrect game levels and rules not included in the VGDL
grammar are generated. In contrast, our approach involves multi-step
generation, and the necessary grammar rules to build a game are generated as
intermediate representations in the middle steps. Additionally, grammar rules
and games are generated conditioned on Ludii [7]’s grammar, preventing
incorrect syntax and improving consistency.

###  II-D Program Synthesis

In program synthesis, the task of generating programs from natural language is
called semantic parsing. Semantic parsing has benefited from the advancements
in LLMs. Several efforts [15, 16] have already explored generating code in
general-purpose programming languages such as Python using LLMs. To improve
the accuracy of the generated programs, constrained decoding [37, 38, 39] has
also been studied. In domain-specific language (DSL) generation, a prompting
method [18] has been proposed that introduces grammar as an intermediate
product while LLMs iteratively reason to solve tasks (also known as a chain-
of-thought [40]). However, in [18], the evaluation targets simple and short
DSLs such as SMCalFlow [41] and GeoQuery [42], and the use of LLMs in the
approach is limited. We aim to make more effective use of LLMs in our approach
and evaluate it with complex and lengthy DSLs that represent game design, such
as Ludii [7].

##  III Background

In this section, we define our problem setting. We first describe the
generation of games written in Game Description Language (GDL). We next review
in-context learning in game generation.

###  III-A Game Description Generation

Let $\Sigma^{\ast}$ be the set of all finite strings composed of the alphabet
set $\Sigma$. We center our work on a language $D\in\Sigma^{\ast}$ that cam be
used to describe games, that is, a GDL. Thus, our goal is to input a natural
language query $x$ that describes the content and rules of a game, and
generate a corresponding game description $y\in D$. In particular, we use
Ludii [7] as our GDL. An example of a Ludii game description generation is
shown in Fig. 2.

Figure 2: An example of Ludii game description for the game “Tic-Tac-Toe”.
Figure 3: Minimal Backus-Naur Form (BNF) grammar $G[y]$ for Tic-Tac-Toe.
Redundant rules are omitted for simplicity.

Ludii is a game system that models over 1,000 traditional games, including
board games, card games, dice games, and tile games. Ludii can generate
complete game descriptions in Extended Backus-Naur Form (EBNF) syntax. Ludii’s
game descriptions include domain-specific abstract concepts, known as ludemes,
and their corresponding semantics. We assume full access to the Ludii grammar,
denoted as $G$, which has been developed to model a diversity of different
games. Let $L(G)$ be the language generated by grammar $G$. Only those game
descriptions that are semantically valid become playable games, which we
denote as $D$. In other words, we define compilable game descriptions as
$L(G)$ and playable game descriptions as $D$.

###  III-B In-Context Learning

Providing a pretrained Large Language Model (LLM) with a few examples related
to a specific task is an efficient way of obtaining more precise and accurate
results, and is called in-context learning. This approach does not require
additional training or fine-tuning; instead, it relies on the LLM’s ability to
identify and apply patterns from the provided examples. In in-context
learning, LLM is conditioned on $N$ demonstrations
$(x^{(i)},y^{(i)})_{i=1}^{N}$ followed by a test example query $x$, and
generates $y$ as $P_{\mathrm{LLM}}(y|(x^{(i)},y^{(i)})_{i=1}^{N},x)$. Recent
studies [43, 44] have reported that the few-shot performance on complex
reasoning tasks can be improved by inserting intermediate reasoning steps
between $x^{(i)}$ and $y^{(i)}$ in the demonstrations.

The effectiveness of in-context learning depends on how effectively the
solution to a task can be conveyed through demonstrations. Intuitively,
providing more demonstrations to the LLM seems to be beneficial. However, the
context length, which is the maximum length that the LLM can capture, is
determined during pre-training. Therefore, it is not possible to input a
number of demonstrations that exceed this context length. For example, when
applying Llama3 [12], one of the leading open-source LLMs, to Ludii’s game
descriptions, the context length can easily be exceeded. In particular, the
average token length of Ludii’s game descriptions using the Llama3-8B-Instruct
tokenizer is 2,458. The context length of Llama3-8B-Instruct is 8,192, which
limits the number of Ludii demonstrations that can be input to a few at most.
This limitation when using complex examples such as those described in Ludii
is common to many LLMs. It is challenging to capture the structure of the wide
output space of Ludii’s grammar $G$ from a few demonstrations.

##  IV Methodology

Figure 4: An example of grammar-based game description generation result. We
generate game descriptions in two stages: first we generate the required
grammar, and then generate the game description based on the grammar. The
prompt includes demonstrations for in-context learning and the test example
query $x$, and the demonstration contains the grammar $G[y^{(i)}]$. In the
first stage, the minimal grammar $\hat{G}[y]$ that composes $y$ is generated.
In the second stage, game description $\hat{y}$ is generated based on the
generated $\hat{G}[y]$.

We introduce grammar into intermediate reasoning steps as an extension of in-
context learning. A simple approach to game description generation using in-
context learning is to provide several examples of a query $x^{(i)}$ and a
game description $y^{(i)}$, along with a test query $x$, to a LLM and have the
LLM generate a game description $y$. However, this simple approach does not
produce decent results. We believe this is because texts related to Ludii are
scarcely included in the training corpus for LLMs, and the model has no
information about the grammatical structure of Ludii.

In contrast, Backus-Naur Form (BNF) grammars are commonly used to define the
structure of languages and are commonly found in the training data of LLM.
Inspired by Bailin _et al._ [18], we incorporate knowledge of BNF grammars in
our generation process. Our approach aims to help the LLM capture the
structure of the Game Design Language (GDL) by adding the minimal BNF grammar
$G[y^{(i)}]$ necessary to compose $y^{(i)}$ in the demonstrations. An example
of $G[y]$ for Tic-Tac-Toe is shown in Fig. 3.

Our generation process consists of two stages: first, we input the test
example query $x$ into the LLM to generate the minimal grammar $\hat{G}[y]$
necessary to compose $y$. Next, based on $\hat{G}[y]$, the LLM generates the
game description $\hat{y}$. To improve the generation performance, we propose
methods to decode BNF grammar rules $\hat{G}[y]$ and game descriptions
$\hat{y}$ iteratively using the fully accessible Ludii grammar $G$ as our GDL.
Afterwards, the decoder evaluates whether $\hat{G}[y]$ (or $\hat{y}$) conforms
to the Ludii grammar $G$ (or $\hat{G}[y]$). In each stage, this generation and
evaluation process is repeated. In this section, we first explain the two-
stage generation in-depth, and then describe the decoding process at each
stage in Subsection IV-B.

Figure 5: Processing flow of Rule Decoding stage. The Rule Decoding stage
starts from the minimal grammar $\hat{G}[y]$ necessary to compose $y$
generated by the LLM, and improves it iteratively. From the grammar
$\hat{G}[y]$, the set of rules included in the original grammar $G$ is
extracted as $\hat{G}[y]_{\mathrm{valid}}$. Next, undefined non-terminal
symbols $N_{U}$ are extracted from $\hat{G}[y]_{\mathrm{valid}}$. The rules
$G_{N_{U}}$ concerning $N_{U}$ are obtained from the original grammar $G$ and
input to the LLM along with $\hat{G}[y]_{\mathrm{valid}}$. The LLM then
generates rules $\hat{G}{N_{U}}$ for the undefined non-terminal symbols.
Finally, $\hat{G}[y]$ is updated by combining $G_{N_{U}}$ with
$\hat{G}[y]_{\mathrm{valid}}$.

Figure 6: Processing flow of Game Description Decoding stage. The Game
Description Decoding stage starts from the initial game description $\hat{y}$
generated by the LLM, and then enhances the results iteratively. Using an
Earley parser [45] based on $\hat{G}[y]$, the longest valid subsequence
$\hat{y}_{\mathrm{valid}}$ and the subsequent terminal symbol candidates
$\Omega_{\mathrm{candidate}}$ are obtained. The LLM then selects the candidate
$\omega$ from $\Omega_{\mathrm{candidate}}$ that is most suitable as the
successor to $\hat{y}_{\mathrm{valid}}$. $\omega$ is appended to the end of
$\hat{y}_{\mathrm{valid}}$, and the LLM generates the remaining part of the
game description $\hat{y}$ that follows. The generated $\hat{y}$ replaces the
previous $\hat{y}$ from the earlier step.

###  IV-A Grammar-based Game Description Generation

We first introduce the minimal grammar $G[y]\subseteq G$ necessary to compose
$y$. $G[y]$ is a subset of the full grammar $G$, where $y\in L(G[y])$ and
$\forall{r}\in G[y],y\notin L(G[y]\setminus\\{r\\})$. We can obtain $G[y]$ by
parsing $y$ with $G$ and collecting the rules to derive $y$. Each
demonstration consists of $(x^{(i)},\,G[y^{(i)}],\,y^{(i)})$.

The generation process consists of two stages. In the first stage, a few
demonstration examples and a test example query $x$ are input to the LLM as a
prompt to generate the minimal grammar $\hat{G}[y]$ necessary to compose $y$.
The grammar $G^{\prime}$ that maximizes the following probability is selected
as $\hat{G}[y]$,

$\displaystyle
P_{\mathrm{LLM}}(G^{\prime}|(x^{(i)},G[y^{(i)}],y^{(i)})_{i=1}^{N},x).$ (1)

In the second stage, the generated $\hat{G}[y]$ is added to the prompt to
generate the game description $\hat{y}$, and the $y’$ that maximizes the
following probability is selected as $\hat{y}$:

$\displaystyle
P_{\mathrm{LLM}}(y^{\prime}|(x^{(i)},G[y^{(i)}],y^{(i)})_{i=1}^{N},x,\hat{G}[y]).$
(2)

We show an overview of the two-stage generation process in Fig. 4.

Additionally, in the second stage, although $y$ is conditioned on the grammar
$\hat{G}[y]$, the generated game description may not adhere to $\hat{G}[y]$.
This is because the LLM just selects the words with the highest likelihood,
and does not necessarily comply with the conditions set by the prompt.
Similarly, $\hat{G}[y]$ may not be a subset of the original grammar $G$.
Therefore, in the next subsection, we propose decoding methods to improve the
consistency of the minimal grammar $\hat{G}[y]$ with the original grammar $G$,
and the consistency of the game description $\hat{y}$ with the grammar
$\hat{G}[y]$.

###  IV-B Grammar-based Iterative Decoding

In order to overcome issues of inconsistent grammars, we propose decoding
methods that iteratively improve the generated grammars. In particular, our
decoding methods are divided into two types, one specialized for the grammar
$\hat{G}[y]$, and one for the game description $\hat{y}$. When decoding the
grammar $\hat{G}[y]$, undefined non-terminal symbols are extracted in one
step, and rules to define them are then generated in the next step, in what we
call the Rule Decoding stage. Similarly, when generating the game description
$\hat{y}$, we use the Earley parser [45] to obtain the longest valid
continuation that adheres to the grammar $\hat{G}[y]$ in one step, and then
complete the remaining parts following the valid continuation in the next
step. We refer to this as Game Description Decoding stage.

#### Rule Decoding Stage

Our rule decoding stage iteratively applies rule decoding while aiming to
ensure that the generated $\hat{G}[y]$ is a subset of the original grammar
$G$. In our rule decoding stage, the generation process is multi-step, where
each step iteratively improves the grammar $\hat{G}[y]$. The goal of each step
is to define the non-terminal symbols that were not defined in the grammar
$\hat{G}[y]$ generated in the previous step. We illustrate our rule decoding
process in Fig. 6. Initially, $\hat{G}[y]$ is generated using the LLM in the
same way as in Eq. (1). From $\hat{G}[y]$, only the valid grammar rules
$\hat{G}[y]_{\mathrm{valid}}$ are retained, which are included in the original
grammar $G$. Among $\hat{G}[y]_{\mathrm{valid}}$, the set of undefined non-
terminal symbols $N_{U}$ is extracted. The undefined non-terminal symbols are
those that are used on the right-hand side of rules in
$\hat{G}[y]_{\mathrm{valid}}$ but are not defined (_i.e._ , they do not appear
on the left-hand side of any rules), and can be automatically extracted
easily. The set of grammar rules for the undefined non-terminal symbols
$G_{N_{U}}$ is extracted from the original grammar $G$. $G_{N_{U}}$ is added
to the prompt, and the LLM selects only the necessary rules from $G_{N_{U}}$
based on the query $x$. Since $G_{N_{U}}$ is extracted from the original
grammar $G$, it contains more rules than the minimum required for $y$. The
role of the LLM is to extract only the rules
$\hat{G}_{N_{U}}=\hat{G}[y]\setminus\hat{G}[y]_{\mathrm{valid}}$ necessary to
compose $y$ from $G_{N_{U}}$. The rules that maximize the following
probability are selected:

$\displaystyle
P_{\mathrm{LLM}}(\hat{G}_{N_{U}}|(x^{(i)},G[y^{(i)}],y^{(i)})_{i=1}^{N},x,\hat{G}[y]_{\mathrm{valid}},G_{N_{U}}).$
(3)

$\hat{G}_{N_{U}}$ is combined with $\hat{G}[y]_{\mathrm{valid}}$ to update
$\hat{G}[y]$. This process is repeated until there are no more non-terminal
symbols or a predetermined limit of updates is reached.

Figure 7: Our prompts for grammar-based iterative decoding.

#### Game Description Decoding stage

The game description decoding stage consists of iterative application of game
description decoding to generate game descriptions that more accurately adhere
to the grammar $\hat{G}[y]$. In each step, it aims to complete the parts of
$\hat{y}$ generated in the previous step that cannot be parsed. Initially,
$\hat{y}$ is generated using the LLM in the same way as in Eq. (2). An Earley
parser [45] is then employed using $\hat{G}[y]$. The Earley parser explores
the program from left to right, extracting the longest valid subsequence and
the subsequent candidate terminal symbols. Using the generated $\hat{y}$, the
Earley parser obtains the valid subsequence $\hat{y}_{\mathrm{valid}}$ and the
set of candidate terminal symbols $\Omega_{\mathrm{candidate}}$. The LLM
selects the most suitable candidate $\omega$ from
$\Omega_{\mathrm{candidate}}$. The $\omega^{\prime}$ that maximizes the
following probability is then chosen:

$\displaystyle
P_{\mathrm{LLM}}(\omega^{\prime}|(x^{(i)},G[y^{(i)}],y^{(i)})_{i=1}^{N},x,\hat{G}[y],\hat{y}_{\mathrm{valid}},\Omega_{\mathrm{candidate}}).$
(4)

The selected candidate is appended to the end of $\hat{y}_{\mathrm{valid}}$,
and the LLM generates the remaining part of the game description $\hat{y}$.
Next, the $y^{\prime}$ that maximizes the following probability is generated:

$\displaystyle
P_{\mathrm{LLM}}(y^{\prime}|(x^{(i)},G[y^{(i)}],y^{(i)})_{i=1}^{N},x,\hat{G}[y],\hat{y}_{\mathrm{valid}}+\omega).$
(5)

The generated $\hat{y}$ updates $\hat{y}$ from the previous step. This process
is repeated until the entire generated $\hat{y}$ becomes parsable by the
Earley parser or until a predetermined number of updates is reached.

##  V Experiments

###  V-A Datasets

The game descriptions generated by Ludii [7] that we use for evaluation are
obtained from the publicly available Ludii software [46]. In Ludii, each game
is assigned a category (_e.g._ , “Tic-Tac-Toe” is categorized under
“Board/Space/Line”, and “Tower of Hanoi” under “Puzzle/Planning”). From the
same category, one test example and three demonstration examples are extracted
as a single instance. Note that only examples where the token length of the
game description $y$ is 300 or less are used. The token length is calculated
using the tokenizer of Llama3-8B-Instruct [12]. The dataset is constructed
from 100 randomly selected instances from all categories, and the same set of
instances is used in all evaluations. Each example consists of a natural
language instruction $x$, a Ludii game description $y$, and the minimal
grammar $G[y]$ required to construct $y$. The instruction $x$ is composed of
the metadata “Description” and “Rules” provided by the Ludii game system (see
Fig. 2 for an example). The game description $y$ consists of the extended game
description derived from the raw text .lud game description files. The
extended version is instantiated with primitive options and rulesets to avoid
using the Ludii game system’s meta-language features (definitions, options,
rulesets, ranges, constants, etc.). We use this extended version to reduce
game-specific representations as much as possible. For more details of the
Ludii language, please refer to the Ludii language reference [47]. The grammar
$G[y]$ is automatically extracted by the parser using the Lark library [48],
which is explained in the next subsection.

###  V-B Implementation Details

We use a parser built with a Python library called Lark [48] to extract the
grammar rules of the Ludii game description. The Ludii grammar in the Lark
parser employs the rules listed in the Ludii language reference. In our
grammar-based iterative decoding, we set an upper limit on the number of
iterations to suppress the number of LLM calls. The iteration limit is set to
20 for rule decoding and 30 for game description decoding. Our prompts for
grammar-based iterative decoding are shown in Fig 7.

We use the Llama3-8B-Instruct [12] model as the LLM for our experiments.
Llama3 is the latest series of open-source large language models provided by
Meta. The Llama3 series includes pre-trained models with 8B and 70B
parameters. Compared to other models of similar size, the Llama3 series
demonstrates superior performance across various benchmarks. To ensure that
our framework is practical with limited computational resources such as local
environments, we select the smaller 8B model. Additionally, we use the
instruction fine-tuning [49, 50] version to make the model accurately respond
to the various instructions used in our framework. Since the Llama3 series
models are pre-trained with sequences of up to 8,192 tokens, it is necessary
to keep the prompts within this length (context length). To address this, we
set the number of demonstration examples to three. We use two NVIDIA RTX 6000
Ada GPUs for our experiments.

###  V-C Evaluation Metrics

To evaluate the generated game descriptions, we use the following metrics:

  * •

Grammar Parsability: The proportion of generated game descriptions that can be
parsed by the Lark parser, which is based on the Ludii grammar $G$.

  * •

System Parsability: The proportion of generated game descriptions that can be
read by the Ludii game system. Descriptions that are grammatically correct as
per the Lark parser but lack any of the necessary functions for a game can not
be read by the Ludii game system.

  * •

Playability: The proportion of generated game descriptions that require a
reasonable number of player actions per trial. A trial is considered
successful if it fulfills the specified termination conditions in at least 5
out of 10 attempts. In particular, we consider the game to be playable if, by
continuously choosing legal actions, the number of actions necessary to reach
a termination condition should range between 2 and 1,800. This metric
evaluates whether the generated game has a reasonable length of play
experience. For a game description to satisfy the Playability criteria, it
also has to satisfy the Grammar Parsability and System Parsability criteria.
We use the implementation [46] in the Ludii game system for this metric.

  * •

ROUGE [51]: This is a metric that measures the degree of match between the
generated game description and the ground truth game description. It ranges
from 0 to 100, with higher values indicating a greater degree of match. The
calculation of this metric does not consider syntactic correctness but instead
focuses on the similarity between texts. We use the F1 score of ROUGE-L. This
value is calculated for each piece of test data, and the average of all data
is reported.

###  V-D Quantitative Results

TABLE I: Results of game description generation. Best results shown in bold. Method | Grammar | RD | GDD | Grammar Parsability | System Parsability | Playability | ROUGE
---|---|---|---|---|---|---|---
GDG |  |  |  | 0.23 | 0.21 | 0.19 | 63.7
GGDG | $\checkmark$ |  |  | 0.32 | 0.26 | 0.18 | 60.8
GGDG + RD | $\checkmark$ | $\checkmark$ |  | 0.50 | 0.40 | 0.22 | 60.2
GGDG + RD + GDD | $\checkmark$ | $\checkmark$ | $\checkmark$ | 0.68 | 0.40 | 0.25 | 60.1
(Oracle Grammar) |  |  |  |  |
GGDG | $\checkmark$ |  |  | 0.40 | 0.28 | 0.18 | 77.1
GGDG + GDD | $\checkmark$ |  | $\checkmark$ | 0.62 | 0.39 | 0.28 | 78.0

We compare the following methods:

  * •

Game Description Generation (GDG): Predicts the game description $y$ directly
from the demonstration examples and the query $x$ without using the predicted
grammar $\hat{G}[y]$.

  * •

Grammar-based Game Description Generation (GGDG): Generates the grammar
$\hat{G}[y]$ required to construct the game description $y$, and then
generates $\hat{y}$ based on $\hat{G}[y]$.

  * •

GGDG + Rule Decoding (RD): Uses the proposed rule decoding in addition to
GGDG.

  * •

GGDG + RD + Game Description Decoding (GDD): Uses both the proposed rule
decoding and game description decoding in addition to GGDG.

In addition to these, for GGDG and GGDG + GDD, we also compare the methods
that use the oracle grammar $G[y]$ obtained from the ground truth with a
parser based on grammar $G$ instead of the generated $\hat{G}[y]$.

The results are summarized in Tab. I. In all metrics, GGDG + RD + GDD shows
the highest performance, indicating that introducing rule decoding
significantly improves both System Parsability and Playability. Additionally,
incorporating game description decoding further enhances Grammar Parsability
and Playability. This highlights how both of our decoding methods play an
important role in increasing the quality of the generated game descriptions.
GDG demonstrates high ROUGE scores but has low scores for Grammar Parsability,
System Parsability, and Playability. This suggests that while LLM alone can
generate descriptions superficially similar to the ground truth, it is
challenging to generate grammatically correct descriptions without accessing
Ludii’s grammar. In the case of the oracle grammar, using game description
decoding significantly improves Grammar Parsability, System Parsability, and
Playability scores. Additionally, compared to not using the oracle grammar,
Playability and ROUGE scores are improved, indicating that accurate grammar
prediction greatly contributes to the improvement of game descriptions.

###  V-E Qualitative Results

Figure 8: Qualitative results of game description generation for Tic-Tac-Toe.
The columns from left to right are the ground truth, Game Description
Generation (GPG), Grammar-based Game Description Generation (GGDG), GGDG with
Rule Decoding (GGDG + RD), and GGDG‘+ RD with Game Description Decoding (GGDG
+ RD + GGD). The middle row shows the game description, and the bottom row
shows the results of grammar generation for only the methods that performed
grammar generation. Since the grammar results are highly redundant, only the
important parts are shown. The highlighted boxes indicate the unnecessary
generated parts compared to the ground truth. The further to the right, the
fewer such unnecessary parts.

We present the generation results of Tic-Tac-Toe in Fig. 8. The results
demonstrate the effectiveness of our proposed framework, particularly the
iterative decoding methods. The first row of Fig. 8 displays the results of
the game description generation for each method. The far-left column is the
ground truth, and the results from the second column onwards are the methods
with grammar prediction, rule decoding, and game description decoding added
respectively. The second row shows the results of the grammar generation,
including only the methods that performed this task. We use Tic-Tac-Die, Order
and Chaos, and Unfair as demonstration examples for this test case.

We observe that all results show “Disc” and “Cross” as “X” and “O”. We believe
that the LLM is influenced by the “X” and “O” in the query for Tic-Tac-Toe.
Tic-Tac-Toe is described in the query $x$ as follows: “Play occurs on a 3x3
grid. One player places an X, the other places an O and players take turns
placing their marks in the grid, attempting to get three in a row of their
colour.”

The generated description of GDG is not Grammar Parsable (nor System Parsable
or Playable), and they include the term “count Pips” (highlighted in red) not
present in the ground truth. We think that the term “pips” appears because the
LLM is influenced by the dice used in the demonstration example of Tic-Tac-
Die. The description of Tic-Tac-Die is as follows: “Tic-Tac-Die is played
similarly to Tic-Tac-Toe except that players roll a D9 dice each turn to
dictate where they move (dice pips show the cell index to move to).”

In the game description results of GGDG, we observe that the influence of
demonstration examples such as “Pips” has decreased. However, compared to the
ground truth, there are extraneous clauses about “move” (highlighted in blue).
This occurs because the grammar of “move” predicts a “PASS” clause that is not
included in the ground truth.

The grammar results of GGDG + RD show that adding rule decoding aligns them
with the grammar of the ground truth. Additionally, the generated game
description is System Parsable (but not Playable). However, this description
includes the term “do,” which is not in the predicted grammar. This term,
found in the demonstration example of Tic-Tac-Die, suggests that the LLM has
imitated it.

In the game description results of GGDG + RD + GDD, adding game description
decoding reduces the occurrence of expressions not defined in the grammar,
such as “do.” Although this description does not fully match the ground truth,
it represents the same meaning and is Playable.

##  VI Limitation

Our proposed framework may have issues with inference time and cost because it
repeats LLM inference multiple times. This issue can be mitigated by caching
LLM responses, setting appropriate limits on the number of LLM inferences, and
improving the prompts.

The evaluation in this paper relies solely on automatically calculable metrics
and does not include human evaluations of user experience. The grammar
introduced in our framework shows its greatest strength in lower-layer aspects
such as Parsability and Playability, rather than in user experience. However,
we believe that insights gained from playing the generated games could also
lead to further improvements.

##  VII Broader Impact

The use of LLMs in the field of video games is associated with ethical issues
related to sustainability, copyright, explainability, and biases [11]. In this
section, we discuss the problems and their mitigation strategies within our
proposed framework from these perspectives.

Our research raises concerns about the carbon footprint of LLMs. Our framework
does not include training LLMs, and only LLMs’ inference impacts the
environment. This issue can be mitigated by reducing the number of inference
calls through caching LLM responses and providing more effective
demonstrations. Additionally, using models that offer enhanced performance for
the same computational load can further reduce environmental impact.

Our research is related to copyright issues concerning input and output data.
It is common practice for LLMs to be trained using copyrighted data [11].
Since our framework does not include the training process, it does not
directly cause this issue. However, when using our framework, attention should
be paid to the training data of LLMs. Our framework automatically generates
game descriptions without human intervention. The output generated by our
framework may not be copyrighted. Developing our framework into an interactive
approach with human designers may allow the final output to qualify for
copyright.

The generation process of LLMs is opaque, and in our research, the process for
each LLM call is similarly unclear. However, our grammar-based iterative
decoding method breaks down the generation process into multiple steps, which
should enhance our understanding of it.

LLMs are trained on data collected from the internet, which introduces biases.
Since game design tends to reflect the culture of its time and region, these
biases negatively impact the design process when using LLMs. Our framework
could potentially mitigate the issue by incorporating examples from various
eras and regions in the demonstrations for LLMs. Ludii collects historically
influential games from diverse regions and provides metadata on the regions
where each game is rooted, which can contribute to mitigating this problem.

##  VIII Conclusions

In this paper, we proposed an automated game design framework using Large
Language Models (LLMs) with the Ludii grammar as our Game Design Language
grammar. Our framework generates Ludii game descriptions based on in-context
learning with LLMs. The generation process is performed in two stages:
generating the grammar necessary for the game description, and generating the
game description itself. Our proposed approach enables the LLMs to capture the
features of the game description generation task with fewer demonstration
examples. We further propose iterative decoding methods specialized for both
the grammar and the game descriptions, which improve the grammatical
correctness of the generated game descriptions. Extensive experimental results
show the effectiveness of our framework in the game description generation
task.

## References

  * [1] A. Khalifa, M. C. Green, D. Perez-Liebana, and J. Togelius, “General video game rule generation,” in _Proc. of CIG_ , 2017.
  * [2] T. Maurer and M. Guzdial, “Adversarial random forest classifier for automated game design,” in _Proc. of FDG_ , 2021.
  * [3] M. Guzdial and M. O. Riedl, “Conceptual game expansion,” _IEEE Trans. Games._ , vol. 14, no. 1, pp. 93–106, 2022.
  * [4] G. Todd, S. Earle, M. U. Nasir, M. C. Green, and J. Togelius, “Level generation through large language models,” in _Proc. of FDG_ , 2023.
  * [5] S. Sudhakaran, M. González-Duque, M. Freiberger, C. Glanois, E. Najarro, and S. Risi, “MarioGPT: Open-ended text2level generation through large language models,” in _Proc. of NeurIPS_ , 2023.
  * [6] F. Abdullah, P. Taveekitworachai, M. F. Dewantoro, R. Thawonmas, J. Togelius, and J. Renz, “The 1st ChatGPT4PCG competition,” 2024, pp. 1–17.
  * [7] É. Piette, D. J. N. J. Soemers, M. Stephenson, C. F. Sironi, M. H. M. Winands, and C. Browne, “Ludii – the ludemic general game system,” in _Proc. of ECAI_ , 2020.
  * [8] T. Schaul, “A video game description language for model-based or interactive learning,” in _Proc. of CIG_ , 2013.
  * [9] N. Love, T. Hinrichs, D. Haley, E. Schkufza, and M. Genesereth, “General game playing: Game description language specification,” 2008.
  * [10] J. Kowalski, M. Mika, J. Sutowicz, and M. Szykuła, “Regular boardgames,” in _Proc. of AAAI_ , 2019.
  * [11] R. Gallotta, G. Todd, M. Zammit, S. Earle, A. Liapis, J. Togelius, and G. N. Yannakakis, “Large language models and games: A survey and roadmap,” in _arXiv preprint arXiv:2402.18659_ , 2024.
  * [12] “Introducing meta llama 3: The most capable openly available llm to date,” 2024.
  * [13] J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat _et al._ , “Gpt-4 technical report,” 2023.
  * [14] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Proc. of NeurIPS_ , 2017.
  * [15] J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q. Le, and C. Sutton, “Program synthesis with large language models,” 2021.
  * [16] F. F. Xu, U. Alon, G. Neubig, and V. J. Hellendoorn, “A systematic evaluation of large language models of code,” in _Proc. of ACM SIGPLAN_ , 2022.
  * [17] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” in _Proc. of NeurIPS_ , 2020.
  * [18] B. Wang, Z. Wang, X. Wang, Y. Cao, R. A. Saurous, and Y. Kim, “Grammar prompting for domain-specific language generation with large language models,” in _Proc. of NeurIPS_ , 2023.
  * [19] M. Stephenson, D. J. N. J. Soemers, E. Piette, and C. Browne, “Measuring board game distance,” in _Proc. of Computer and Games_ , 2023.
  * [20] M. Stephenson, E. Piette, D. J. N. J. Soemers, and C. Browne, “Automatic generation of board game manuals,” in _Proc.of Advances in Computer Games_ , 2021.
  * [21] E. Piette, M. Stephenson, D. J. Soemers, and C. Browne, “General board game concepts,” in _Proc. of CoG_ , 2021.
  * [22] M. Stephenson, D. J. N. J. Soemers, E. Piette, and C. Browne, “General game heuristic prediction based on ludeme descriptions,” in _Proc. of CoG_ , 2021.
  * [23] D. J. N. J. Soemers, Éric Piette, M. Stephenson, and C. Browne, “The ludii game description language is universal,” 2024.
  * [24] J. Togelius and J. Schmidhuber, “An experiment in automatic game design,” in _IEEE Symposium On Computational Intelligence and Games_ , 2008.
  * [25] C. Browne and F. Maire, “Evolutionary game design,” _IEEE Trans. Computational Intelligence and AI in Games_ , vol. 2, no. 1, pp. 1–16, 2010.
  * [26] M. P. Eladhari, A. Sullivan, G. Smith, and J. Mccoy, “Ai-based game design : Enabling new playable experiences,” 2011.
  * [27] M. Treanor, A. Zook, M. P. Eladhari, J. Togelius, G. Smith, M. Cook, T. Thompson, B. Magerko, J. Levine, and A. Smith, “Ai-based game design patterns,” in _Proc. of FDG_ , 2015.
  * [28] A. Sarkar and S. Cooper, “Towards game design via creative machine learning (gdcml),” in _Proc. of CoG_ , 2020.
  * [29] M. Cook, S. Colton, and J. Gow, “The angelina videogame design system—part i,” _IEEE Trans. Computational Intelligence and AI in Games_ , vol. 9, no. 2, pp. 192–203, 2017.
  * [30] A. Liapis, G. N. Yannakakis, M. J. Nelson, M. Preuss, and R. Bidarra, “Orchestrating game generation,” _IEEE Trans. Games._ , vol. 11, no. 1, pp. 48–68, 2019.
  * [31] A. Summerville, C. Martens, B. Samuel, J. Osborn, N. Wardrip-Fruin, and M. Mateas, “Gemini: Bidirectional generation and analysis of games via asp,” in _Proc. of AAAI_ , 2018.
  * [32] T. S. Nielsen, G. A. B. Barros, J. Togelius, and M. J. Nelson, “Towards generating arcade game rules with vgdl,” in _Proc. of CIG_ , 2015.
  * [33] T. Machado, D. Gopstein, A. Nealen, O. Nov, and J. Togelius, “Ai-assisted game debugging with cicero,” in _Proc. of CEC_ , 2018.
  * [34] OpenAI, Nov 2022. [Online]. Available: https://openai.com/blog/chatgpt
  * [35] S. Värtinen, P. Hämäläinen, and C. Guckelsberger, “Generating role-playing game quests with gpt language models,” _IEEE Trans. Games._ , vol. 16, no. 1, pp. 127–139, 2024.
  * [36] C. Hu, Y. Zhao, and J. Liu, “Game generation via large language models,” 2024.
  * [37] R. Shin, C. Lin, S. Thomson, C. Chen, S. Roy, E. A. Platanios, A. Pauls, D. Klein, J. Eisner, and B. Van Durme, “Constrained language models yield few-shot semantic parsers,” in _Proc. of EMNLP_ , 2021.
  * [38] T. Scholak, N. Schucher, and D. Bahdanau, “PICARD: Parsing incrementally for constrained auto-regressive decoding from language models,” in _Proc. of EMNLP_ , 2021.
  * [39] G. Poesia, A. Polozov, V. Le, A. Tiwari, G. Soares, C. Meek, and S. Gulwani, “Synchromesh: Reliable code generation from pre-trained language models,” in _Proc. of ICLR_ , 2022.
  * [40] J. Wei, X. Wang, D. Schuurmans, M. Bosma, b. ichter, F. Xia, E. Chi, Q. V. Le, and D. Zhou, “Chain-of-thought prompting elicits reasoning in large language models,” in _Proc. of NeurIPS_ , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., 2022.
  * [41] J. Andreas, J. Bufe, D. Burkett, C. Chen, J. Clausman, J. Crawford, K. Crim, J. DeLoach, L. Dorner, J. Eisner, H. Fang, A. Guo, D. Hall, K. Hayes, K. Hill, D. Ho, W. Iwaszuk, S. Jha, D. Klein, J. Krishnamurthy, T. Lanman, P. Liang, C. H. Lin, I. Lintsbakh, A. McGovern, A. Nisnevich, A. Pauls, D. Petters, B. Read, D. Roth, S. Roy, J. Rusak, B. Short, D. Slomin, B. Snyder, S. Striplin, Y. Su, Z. Tellman, S. Thomson, A. Vorobev, I. Witoszko, J. Wolfe, A. Wray, Y. Zhang, and A. Zotov, “Task-oriented dialogue as dataflow synthesis,” _IEEE Trans. Association for Computational Linguistics._ , vol. 8, pp. 556–571, 2020.
  * [42] J. M. Zelle and R. J. Mooney, “Learning to parse database queries using inductive logic programming,” in _Proc. of national conference on artificial intelligence_ , 1996.
  * [43] L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y. Yang, J. Callan, and G. Neubig, “PAL: Program-aided language models,” in _Proc. of ICML_ , 2023.
  * [44] J. Wei, X. Wang, D. Schuurmans, M. Bosma, brian ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou, “Chain of thought prompting elicits reasoning in large language models,” in _Proc. of NeurIPS_ , 2022.
  * [45] J. Earley, “An efficient context-free parsing algorithm,” _Commun. ACM_ , vol. 13, no. 2, p. 94–102, 1970.
  * [46] Digital Ludeme Project, “Ludii portal.” [Online]. Available: https://ludii.games/index.php
  * [47] ——, “Ludii language reference.” [Online]. Available: https://ludii.games/downloads/LudiiLanguageReference.pdf
  * [48] ——, “Lark parser.” [Online]. Available: https://github.com/lark-parser/lark
  * [49] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Gray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. Christiano, J. Leike, and R. Lowe, “Training language models to follow instructions with human feedback,” in _Proc. of NeurIPS_ , 2022.
  * [50] R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn, “Direct preference optimization: Your language model is secretly a reward model,” in _Proc. of NeurIPS_ , 2023.
  * [51] C.-Y. Lin, “ROUGE: A package for automatic evaluation of summaries,” in _Proc. of Text Summarization Branches Out_ , 2004.