# Using Grammar Masking to Ensure Syntactic Validity in LLM-based Modeling
Tasks

Lukas Netz<EMAIL_ADDRESS>0000-0003-2013-2919 Chair of Software
EngineeringAachenNRWGermany ,  Jan Reimer<EMAIL_ADDRESS>Chair of
Software EngineeringAachenNRWGermany and  Bernhard Rumpe<EMAIL_ADDRESS>aachen.de 0000-0002-2147-1966 Chair of Software EngineeringAachenNRWGermany

###### Abstract.

We present and evaluate a method called grammar masking, which is used to
guide large language models (LLMs) toward producing syntactically correct
models for a given context-free grammar. Prompt engineering methods such as
few-shot learning or priming can be used to improve the chances of an LLM
producing correct syntax, but the more complex the grammar, the more time-
consuming and less promising these methods become. Previous work is focused
primarily on the usage of either language model training or prompt
engineering. In this work, a method is presented that restricts the output to
a given grammar using constrained decoding to ensure the output adheres to a
valid syntax. We use several DSLs built with MontiCore and task multiple LLMs
to produce models with and without constrained decoding. A corresponding
parser is used to confirm the syntactic correctness of each model. We show
that grammar masking can dramatically improve the modeling capabilities of
several LLMs, reducing the need for well-refined prompting while increasing
the chance of producing correct models.

LLM, MDSE, Guidance, CFG, Constrained Decoding

††copyright: cc††booktitle: Preprint

##  1\. Introduction

Large language models (LLM) (Liu et al., 2023; Zhao et al., 2023) are highly
sophisticated tools that, among other things, are capable of generating code
artifacts based on a natural language input (Barenkamp et al., 2020; Crawford
et al., 2023; Sadik et al., 2023). As we operate in the context of model-
driven software engineering, we focus on the synthesis of textual models using
the predefined syntax of a given domain-specific language (DSL). Given that
the syntax definition of the targeted DSL might not be included in the corpus
of training data used for the language model, it is necessary to rely on post-
training optimization techniques such as few-shot learning (Brown et al.,
2020; Fedele, 2023), fine-tuning (Ren et al., 2018), or prompt engineering
(Chen et al., 2024; Muktadir, 2023). However, as these methods rely on prompt
engineering, they have one common element: they only improve the likelihood
that the LLM produces syntactically correct models but cannot guarantee it.

In this work, we introduce an approach that uses the context-free grammar
(CFG) of the targeted DSL to filter out any syntactically invalid output
during the generation process of the LLM. We will evaluate results by
comparing this approach to previous successful modeling tasks for LLMs using
only few-shot learning.

##  2\. Foundations

We introduce several foundations, such as the used framework Guidance, and the
DSLs for which we will generate models.

###  2.1. Large Language Model

A LLM is a language model that is trained on a vast amount of text data. It is
distinguished by its capability for general-purpose language understanding and
generation. These models acquire their abilities by learning statistical
relationships from text documents through a computationally intensive self-
supervised and semi-supervised training process (Vaswani et al., 2017). LLMs
can perform text generation, a type of generative AI (Amaratunga, [n. d.]), by
taking an input text and iteratively predicting the next token or word. In the
context of software engineering, LLMs present significant potential to enhance
and automate various tasks (MacNeil et al., 2023), particularly those related
to Model-Driven Software Engineering (MDSE) and modeling languages (Baumann et
al., 2024; Netz et al., 2024).

###  2.2. Few-Shot learning

Few-shot learning (FSL) is a well-established in-context learning approach for
large language models (Brown et al., 2020; Fedele, 2023; Ren et al., 2018). A
pre-trained LLM can be prompted with a set of $N$ exemplary question-answer
pairs $(q^{i},a^{i})^{N}_{i=1}$ before being provided with the actual question
$q$. The FSL output $a$ for the question $q$ is defined as
$P_{LLM}(a|q,(q^{i},a^{i})^{N}_{i=1})$. In addition, further instructions can
be added to improve the results (Wei et al., 2021). Further work is published
on the FSL improvement introducing intermediate reasoning steps (e.g. Chain of
thought) (Wei et al., 2022; Dohan et al., 2022; Wang et al., 2022).

The success of few-shot in-context learning depends on the utility of the
implicit knowledge within the provided examples and the clarity with which the
task specifications are communicated through the provided examples. In the
case of Domain-Specific Languages, the structured nature of the combinatorial
output space, represented by the CFG of the DSL, is not easily covered by the
limited number of demonstrations. Thus, generating models for a DSL with an
FSL-based approach remains a significant challenge for LLMs.

###  2.3. Guidance-AI

Guidance111https://github.com/guidance-ai is a tool designed to optimize and
enhance the process of generating text output with Large Language Models. It
provides a flexible and efficient way to control and ’guide’ the output of
these models to achieve specific goals or adhere to desired formats. In our
case, we use the formatting capabilities of guidance to produce output that
adheres to the formatting rules of a given DSL. Guidance internally defines a
DSL implemented by developers from Microsoft for structured prompting of LLMs.
Any prompting template consisting of a mix of unconstrained generation,
function calls, constant strings, or grammar-constrained generation is
transformed into a tree-like data structure, where each node represents
different parts of the grammar. The core classes are Function and its
subclasses GrammarFunction, which represents grammar rules, and RawFunction,
which is used to interleave native Python functions within a grammar. Grammar
functions are either a join or a select, and regex expressions in the grammar
are reduced to these two operations. Terminals are either individual bytes or
byte ranges. Figure 1 illustrates a simple grammar tree with the possible
productions ”a” or ”ab”.

The main idea for achieving a structured output is online parser-guided
generation synchronizing a parser and scanner with an LLM to determine valid
tokens at each step dynamically. In the main Loop, as seen in figure Figure 3.
When LLM generates text, it predicts the next Token in a sequence. For each
possible token, a logit is generated, representing the confidence that this
token is correct based on the training of the LLM. To those confidence values,
a softmax function is applied to the confidence scores so they all add up to 1
and can be used as probabilities. Based on these probabilities, a multinomial
distribution is calculated. Now, for each step, the tokens are tried one by
one and checked by the guidance parser to see if they result in a valid
partial parse.

The Parser is an Earley Parser constructed by Guidance based on the supplied
grammar. An Earley parser efficiently processes context-free grammars in three
phases. During prediction, it generates new states based on grammar rules for
non-terminals. In the scanning phase, it matches and consumes terminal symbols
in the input. Completion advances states when a rule ends, preparing for the
next parsing steps. This method handles all possible paths, accommodating
ambiguous and complex grammars effectively. Many other Frameworks only support
subsets of CFGs since they are based on LR(1) or LALR(1) parsers. The Guidance
parser enhances the standard Earley parser by introducing commit points, which
force the parser to commit to specific parse paths, effectively pruning the
search space and avoiding backtracking. No other alternatives are considered
once a commit point is reached, ensuring that the parser adheres strictly to
chosen paths.

The parser in the guidance framework employs several optimization strategies
to enhance performance and efficiency by minimizing the frequency of calls to
the LLM. In figure Figure 3, we can also see that tries are used in two
instances. A trie, or prefix tree, is a data structure that efficiently stores
and retrieves keys, typically strings. Each node represents a common prefix
shared by some keys, allowing fast lookups by a prefix. The tokens of the LLM
are converted to a trie, making it possible to identify possible tokens and
constraining the search space quickly. Another trie is constructed for the
grammar, and by traversing it alongside generation, the forced prefixes and
suffixes are added to the output without invoking the LLM.

This is in contrast to template-based approaches, which may force tokens that
alter the attention distribution and potentially degrade the LLM output.
Online parsers can maintain minimal invasiveness by checking tokens one by
one. However, this method often incurs high inference overhead since they may
need to check the entire model vocabulary at each step, as seen in 1.

SelectByte(b’a’)JoinByte(b’a’)Byte(b’b’) Figure 1. Grammar Tree Structure

###  2.4. MontiCore based Modeling Languages

As the chair for Software Engineering, we develop and maintain the language
workbench MontiCore222https://monticore.github.io/ (Hölldobler et al., 2021).
The language workbench is employed to generate a number of DSLs. For brevity,
we will focus on two languages: one used to define requirements and
specifications in simplified structured English (SEN) and another used to
define UML class diagrams: CD4A.

####  2.4.1. Structured English – A Controlled Natural English (DSL) for
Regulatory Comliance

This DSL was primarily developed to standardize the definition of requirements
and is based on the work of Konrad and Cheng (Konrad and Cheng, 2005). The DSL
can be used to write requirements and expressions in controlled simplified
English (Fuchs et al., 2008), while still being able to be parsed and
processed by tooling.

⬇

1After starting the engine, each time we

2pull the turn indicator lever up, the right

3indicator blinks within 500 ms.

Generic Requirement in English

We can identify scopes and patterns in the provided Requirement:

⬇

1After Q:Formula, if P:Formula holds,

2then in response S:Formula eventually holds

3time:TimeBound.

Patterns found in Requirement

Next, we can derive the SEN-Requirement from the natural English one:

⬇

1After engine equals started, if

2turn_indicator_lever equals up holds,

3then in response right_indicator equals

4blinking eventually holds within 500

5Milliseconds.

Derived Structured English from Requirement

####  2.4.2. Class Diagrams for Analysis (CD4A)

The modeling language CD4A is based on UML class diagrams and closely
implements all common features of class diagrams e.g., inheritance,
associations, and enumerations (see (Chair of Software Engineering, 2023)).
The syntax follows a Java-notation, making it easy for developers to adopt the
language. 1 depicts a simple class diagram in CD4A syntax. The diagram is
titled ’LibraryDiagram’ and defines the four classes Library, Member,
Librarian, and Book. In addition, the inheritance from Member to Librarian and
an association from Library to Book is modeled.

⬇

1classdiagram LibraryDiagram {

2 class Library {

3 String name;

4 String adress;

5 }

6 class Member {

7 String name;

8 Long memberID;

9 String contacInfo;

10 }

11 class Librarian extends Member{}

12 class Book {

13 String title;

14 }

15 association [1]Library -> Book[*];

16}

Listing 1: CD4A Class Diagram Defining Person, Student and Animal Class and
their relations.

##  3\. Related Work

Although open-source frameworks such as Guidance have been published in recent
years, little research has been done on using LLMs with constrained decoding
as a modeling tool.

Initial work was published by Wang et al. in (Wang et al., 2024). The
presented approach uses grammar prompting to guide an LLM towards a
constrained output. They demonstrate the viability of their approach with a
selection of DSLs and LLMs.

###  3.1. MBSE with generative AI

Bader et al. use an FSL-based approach on the GPT-3.5-turbo-1106 LLM to
produce textual UML Models in XML notation based on natural-language input. In
this work, Bader shows that valid models can be created; however also points
out some challenges of the LLM-based approach, such as limited context length
and hallucination-related problems with the generated models (Bader et al.,
[n. d.]).

Timperley et al. assess the usage of LLMs to generate model-based spacecraft
system architectures (Timperley et al., [n. d.]). The approach relies on
generating textual models for system architectures, requirements, and
ontologies. The analysis concludes that LLMs can provide a high degree of
assistance in modeling tasks in the early stages of spacecraft design.
However, the modeling process still requires human supervision and can not be
yet fully automated. A similar conclusion is drawn by Busch et al. (Busch et
al., 2023). In their approach, a Low-Code is developed using a visual modeling
language. Similar to Timberly et al. full automation is not yet possible due
to the uncertainty introduced by relying on an LLM to generate code.

(Austin et al., 2021) explores the capabilities of current LLMs to create
general-purpose code.

###  3.2. SynCode

SynCode (Ugare et al., 2024; git, [n. d.]) is a framework for grammar-guided
generation with large language models. SynCode tries to address these
limitations by using an offline-constructed lookup table called the DFA mask
store. This table is based on the DFA of the language grammar terminals and is
designed to retain only syntactically valid tokens during the generation
process.

The core of SynCode’s approach involves a two-step process during the LLM
decoding stage. First, the partial output generated by the LLM is parsed to
produce accept sequences and a remainder. Accept sequences represent valid
terminal sequences that can follow the current partial output, while the
remainder accounts for any unparsed or partially parsed tokens. Next, using
the accept sequences and remainder, SynCode traverses the DFA states and
retrieves masks from the DFA mask store. These masks filter out syntactically
invalid tokens from the LLM’s vocabulary, ensuring that only valid tokens are
considered during each step of the generation process.

One of the greatest advantages of this approach is that the entire constraint
infrastructure can be pre-computed. By accepting a longer initial setup time
to generate the mask stores, the inference process becomes significantly
faster, with only a minimal overhead of about 10%, even for complex grammars.
This makes it particularly well-suited for handling complex grammars, such as
those found in MontiCore.

##  4\. Approach

Figure 2. Evaluating the performance of a few-shot learning-based approach

Within this work, we focus on the syntactic correctness of the models produced
by the LLM. We evaluate by comparing two approaches: one that only uses FSL
and one that combines FSL with grammar masking. Even if a model is
syntactically correct, there can still be semantic errors, e.g. the model
could be an empty model, which might be syntactically valid, but does not
satisfy the given modeling task. We were able to exclude this trivial error
case in our tests, however, an in depth semantic analysis was not performed.
Previous tests have shown that LLMs implement a large part of the requirements
in the generated artifacts in the majority of cases (Netz et al., 2024). The
generated results did not indicate a deviation from the previous measurements
on semantic accuracy.

###  4.1. Using Few-Shot learning-based Modeling Method

So far, FSL is one of the best prompting approaches to get an LLM to produce
syntax in a predefined grammar. One drawback is that its performance heavily
relies on the complexity of the grammar, the dependency on the LLM’s
familiarity with the concepts underlying the modeling task, and a good
selection of examples to represent the rules of the grammar of the targeted
DSL. FSL is limited to a set of examples to convey all syntactic relevant
elements of a grammar (Wang et al., 2024), while also passing on ’best
practices’ for a modeling task in this language. As LLMs have a tendency to
lose accuracy on increasingly larger prompts (Liu et al., 2024), we have to
choose the examples for each grammar, or even for each use case carefully. In
our FSL approach, generic domain-independent examples for each grammar were
selected, as our overreaching goal is the development of a domain-independent
DSL-specific modeling approach, that is not optimized for a specific use case
or domain. A higher accuracy is very likely, by narrowing down the approach to
specific target domains and thus choosing corresponding examples from
corresponding use cases.

Within this work, we compare our approach with the performance of the FSL
approach developed in (Netz et al., 2024). The approach is depicted in Figure
2. A user informally defines a modeling task, that is extended with sample
models of the target DSL. The extended prompt is provided to a LLM and the
resulting model is checked by a parser. All models are provided with the same
prompt-engineering and with the same set of molding tasks. The computation,
with the exception of the OpenAI model, was run on the same hardware.

Figure 3. Combining the Guidance Framework with MontiCore to generate
syntactically valid models.

###  4.2. Using a Grammar Masking-based Modeling Method

Figure 4. Evaluating the performance of a grammar-masking-based approach

In our constrained decoding approach we use Guidance as discussed in Section
2.3. The constrained decoding approach is evaluated similarly as the FSL
approach (cf. Figure 4. The prompt containing the modeling task is
supplemented with the same additional models, as in the previous approach. The
grammar of the target DSL is transformed and provided through Guidance to the
LLM. All generated models are parsed with a parser that is based on the same
grammar. The pipeline involves transforming the MontiCore Grammar using a
Visitor Pattern into a Lark Grammar (lar, [n. d.]) (cf. 2), which is then
integrated with Guidance. A detailed setup is shown in Figure 3. The framework
starts with an initial prompt, that at the beginning is also the current
prompt. The framework is limited to a fixed set of tokens; if there are still
tokens left, the system checks with the help of a grammar trie if there is an
unambiguous continuation for the current prompt (e.g., ’bool’ has to be
completed to ’boolean’). This is used as a shortcut to circumvent LLM usage.
If this is not the case, the LLM is used to recommend tokens (transformer),
which are passed to an earley parser, which can identify invalid token
suggestions. Valid tokens are passed on and added to the current output. The
cycle starts again at the current output.

⬇

1start: automaton

2automaton: "automaton" NAME "{" (state | transition)* "}"

3state: "state" NAME ("<<" ("initial" | "final") ">>")* ( ("{" (state | transition)* "}") | ";" )

4transition: NAME "-" NAME ">" NAME ";"

5NAME: /[a-zA-Z_$][a-zA-Z_0-9$]*/

6%ignore WS

7%import common.WS

Listing 2: Example of Lark Grammar

Currently, Guidance only uses greedy decoding, which picks the most probable
allowed token. This reduces the effect of logit probability biasing, such as
temperature, hence the same prompt will produce the same generated artifact.
Thus to test the system, we need many distinct use cases. Several modeling
tasks from software engineering exams were selected as templates to synthesize
further exam tasks. An LLM was commissioned to generate a list of 1000 domains
(cf. 3).

⬇

1 Automotive Systems,

2 Hydraulic Press Control Systems,

3 Healthcare Management Systems,

4 E-commerce Platforms,

5 Financial Trading Systems,

6 Telecommunication Networks,

7 Smart Home Automation,

8[...]

Listing 3: Except from synthesized domains. A complete list can be found at
(Netz and Reimer, 2024)

⬇

1A voting system is being designed for a local

2election. The system should be able to handle

3multiple voting stations, each with its own

4set of voters. Each voter has a unique

5identifier and can cast one vote per election.

6The vote is recorded as a preference for a

7particular candidate.

8[...]

Listing 4: Except from synthesized use case .A complete list can be found at
(Netz and Reimer, 2024)

These were in turn given individually to the LLM in order to create new tasks
using an FSL approach with the above-mentioned exam tasks. A set of 1000 exam
tasks with similar specification levels was thus created (cf. 4). The task
synthetization was executed by Llama 3 8B in a 4-bit quantization.

We then compare the artifacts that parse in constrained generation with those
that parse in unconstrained generation for each task.

##  5\. Results

To evaluate the presented approach several class diagrams and structured
English models were generated, the parsing subset (4.225 CD4A models and 359
SEN models) can be found here: (Netz and Reimer, 2024). The results (cf. Table
1) indicate that the constrained generation method significantly increases the
percentage of syntactically correct outputs from 46.52% to 92.63% (Llama 3).
However, this improvement comes at the cost of increased generation time, with
constrained generation taking an average of 74.09 seconds compared to 5.71
seconds for unconstrained generation. Similar results are observed for other
LLMs. 36.57 % of the models produced by Phi3 Mini in 4 Bit Quantization in an
unconstrained mode are parsable, compared to 86.98 % in the constrained mode.
Gemma 7B in 4-Bit Quantization produces only 0.003 % in an unconstrained mode,
compared to 93.00 % in the constrained mode. Mistral 7B in 3-Bit Quantization
produces 20.99 % parsable models compared to 92.37 % parsable models in a
constrained configuration. Quantization was chosen to accommodate the hardware
constraints of the experimental setup. Models were limited to 8GB. All models
took significantly more computation time when using constrained decoding.
Using the Phi3 model in a constrained configuration took 34 times longer than
using the Model in an unconstrained configuration. These increases could be
combated by pre/computing the constraints, e.g. by using the Syncode approach
(cf. subsection 3.2) which is connected to further challenges.

Using the same first 100 prompts, GPT-4o (OpenAI et al., 2024) was also
tested. We were unable to apply constrained decoding as it is a closed-source
model. At the time of writing, GPT-4o is one of the most capable LLMs in
several benchmarks (art, [n. d.]). Thus, it is expected that the model
performs better (76 % parsable models) in an unconstrained mode. However, most
likely due to the communication overhead, the time needed to create a model
is, on average, doubled in comparison to the locally running open-source
models.

We also tested the Structured English DSL SEN in addition to the Class Diagram
DSL CD4A. We observe the same patterns as in CD4A: In an unconstrained setting
using Llama 3, 26.54% of the produced models are parsable, whereas in a
constrained configuration, 90.26% are parsable. The same can be shown for the
LLMs Phi3 and Mistral: significantly more produced models are parsable using
constrained decoding, than using unconstrained generation. In comparison to
the CD4A modeling task, GPT-4o does not perform significantly better than the
locally running LLMs: with 24.63% parsable models in an unconstrained
configuration.

Not all runs could be completed in both cases (CD4A and SEN). Although 1000
prompts for CD4A and 123 promts for SEN were provided to the LLMs, a run was
aborted in case a token limit was reached. Thus for example Llama3 8B 4-Bit
only produced 991 models instead of 1000.

Constrained decoding does not currently achieve complete correctness because
Monticore’s grammar includes keywords not yet supported by our approach. For
example, enum (on, off, finished) is interpreted as a function. In contrast,
Monticore’s implementation would not allow enum to be read as a function name,
thereby guiding the generation incorrectly. Most of these differences were
adapted by hand.

In Table 2, we can see a peculiarity of constrained generation. While the
overall number of language constructs used is similar, the number of
compositions and associations is the same. This occurs because the model tries
to extend tokens maximally. Due to the prompting and grammar constraints, both
constructs, which have exactly 11 characters, are equally likely to be
generated.

At this point, we would like to point out that the results do not show the
best possible modeling capabilities of the individual models, as we have
deliberately not optimized the few-shot learning prompting intensively. The
results mainly show the performance gain with constant prompting with and
without grammar prompting. The results with GPT-4o, which received the same
prompts, serve as a comparison.

We encountered many unforeseen problems in achieving these results. First,
EBNF grammars, which are supported by most of the currently available
frameworks, are weak in expressing common features of interesting languages.

  * •

Whitespaces MontiCore parsers are, in parts, whitespace-agnostic and ignore
them, similar to most compilers such as the C compiler. However, whitespace is
important for the attention distribution of the LLM when evaluating input and
output. Therefore, grammars should be modified to enforce correct formatting,
for example, by integrating them with a linter.

  * •

Fuzzy Testing Additionally, grammars are often only tested against human input
instead of some extensive fuzzy testing, which usually results in no
additional benefits. However, for an LLM, the grammar should be entirely
correct. Often, in grammars that are common on the internet, some rules never
trip a human up, but an LLM will make every error you allow it to.

⬇

1modifier: stereotype? ("public" | ... | "/" | ...)*

Leading to this Code being parseable:

⬇

1 class Frame {

2 Material material; // steel

3 Wheel ;

4 }

CD4A Code

Figure 5. CD4A Example

  * •

Grammar Mistakes Instead of a modifier being only allowed once or not at all,
the Kleene star allows // to be read as a modifier as shown in Figure 5. By
abusing incorrect grammar the LLM makes comments which are not allowed by
using two modifiers.

  * •

Endless repetitions and limited tokens A CD4A file can have arbitrarily many
classes, and in fact, there can be arbitrarily many of most constructs.
However, since our VRAM is limited, the LLM can only generate a finite amount
of tokens. Therefore, grammar masking only guarantees correct artifacts if the
generation stops before the token limit is reached. In some cases, the LLM
gets stuck in endless repetitions, making it unlikely to terminate in a
parsable state.

Table 1. Mean Processing Time and Parsing Rates

| Unconstrained | Constrained
---|---|---
CD4A (1000 examples)
Llama3 8B 4-Bit |  |
Time (s) | 5.71 | 74.10
Parsed (%) | 416/991 (41.97%) | 918/991 (92.63%)
Phi3 Mini 4-Bit |  |
Time (s) | 4.63 | 138.29
Parsed (%) | 357/976 (36.57%) | 849/976 (86.98%)
Gemma 7B 4-Bit |  |
Time (s) | 2.46 | 54.20
Parsed (%) | 2/658 (0.003%) | 612/658 (93.00%)
Mistral 7B 3-Bit |  |
Time (s) | 4.89 | 73.59
Parsed (%) | 190/905 (20.99%) | 836/905 (92.37%)
GPT-4o (100 examples) |  |
Time (s) | 8.77 | N/A
Parsed (%) | 76/100 (76.00%) | N/A
SEN (123 examples)
Llama3 8B 4-Bit |  |
Time (s) | 1.04 | 5.23
Parsed (%) | 30/113 (26.54%) | 102/113 (90.26%)
Phi-3-Mini 4-Bit |  |
Time (s) | 1.13 | 10.12
Parsed (%) | 4/122 (3.27%) | 105/122 (86.06%)
Mistral 7B 3-Bit |  |
Time (s) | 1.22 | 5.39
Parsed (%) | 11/96 (11.45%) | 85/96 (88.54%)
GPT-4o |  |
Time (s) | 1.84 | N/A
Parsed (%) | 17/69 (24.63%) | N/A

  * •

Numbers include only generations without out-of-token errors.

Table 2. Mean Values of Syntactic Elements (Llama3 CD4A) | Unconstrained | Constrained
---|---|---
Composition Count | 5.669021 | 5.809284
Association Count | 0.21998 | 5.809284
Class Count | 7.849647 | 8.095863

##  6\. Discussion

The results shown in Table 1 and Table 2 show very promising results, in the
following we discuss aspects such as limitations and generalizability of the
approach.

###  6.1. Applicability to other grammars

The approach presented in this work is based on MontiCore Grammars, which are
transformed into LARK grammars. Hence this approach can be applied to any
MontiCore Grammar. MontiCore provides infrastructure that permits the
developers to define context conditions (CoCos) (Butting et al., 2023). These
CoCos are rules that check the well-formedness of models. These context
conditions are crucial for ensuring that models adhere to the specified rules
and constraints of the language. DSLs with fewer CoCos are transferable to
this method with less effort, as this approach only impacts the adherence to
the grammar and not the CoCos. In addition, grammar masking is expected to
yield fewer improvements on DSLs already encountered in pretraining, such as
PlantUML (Singh and Sidhu, 2018), or SQL, as these languages should already
perform well. LLMs that are already trained on a specific DSL will be more
likely to produce syntactically correct models.

This approach was developed with MontiCore grammars in mind. However, the
approach can be applied to any grammar that is transformable into a LARK
grammar (cf. Figure 3, Figure 4).

###  6.2. Impact Grammar Masking on Model Semantics

The approach presented in this paper relies primarily on filtering out
syntactically invalid tokens. Although we did not notice any changes in the
semantics of the resulting models, we cannot rule out the possibility that
relevant content is excluded from the model or modified so that the semantics
of the model are changed. A closer look at random samples, in which both
approaches resulted in syntactically correct models, revealed that models
generated with the constrained approach do not systematically contain fewer
elements than those generated with the unconstrained approach. Table 2 implies
the opposite. The differences observed were mainly in the formatting and
naming of elements.

Models generated with contained decoding might be less detailed, as this does
not necessarily appear in quantitative analysis (e.g. counting classes and
attributes). A further in-depth analysis of the content would be necessary.

###  6.3. Choosing Between Constrained and Unconstrained Generation

As we could show in the case of the DSL CD4A, FSL alone can suffice to create
an approach that is very likely to yield a syntactically correct model (e.g.
by using a sufisticated LLM such as GPT-4o cf. Table 1). This approach is not
limited to the DSLs presented in this paper and can be applied to further
modeling languages with sufficient prompt engineering. Nevertheless, this
approach requires experts in the field of generative AI (e.g. a Prompt
Engineer) and experts in the specific modeling language to provide specific
and ideal representative examples of the targeted language. Hence, an FSL-
only-based approach would be unsuitable for developers unfamiliar with the
targeted DSL. In contrast, the grammar-masking-based approach is less reliant
on good prompting and can be derived from a given MontiCore grammar, thus only
needing the grammar file and a few samples of the targeted modeling language
to operate. In addition, the grammar masking approach presented in this work
enables smaller less performant models to serve as modeling tools. Smaller
models such as the Llama 3 8B in a 4-bit quantization can be executed on
hardware that is available for the end user (e.g. NVIDIA GeForce RTX 3070),
making this approach independent from external server clusters such as the
ones needed for an OpenAI based approach.

###  6.4. Limitations

One of the key limitations of this approach is its missing support for context
conditions. As context conditions often need the entire model to be applied,
they can not be used in a filtering capacity during model creation. Thus, they
have to be applied in a succeeding step after a model for a specific DSL has
been created. Grammar masking reduces the number of models that do not adhere
to the provided grammar, thus also increasing the overall number of correct
models that potentially comply with the context conditions, as any
syntactically invalid models are filtered out at a very early stage. Another
limitation is the high degree of specialization in one grammar. This approach
limits the LLM to only producing models for one specific grammar. A second
setup and a delegator are needed if the framework is meant to switch between
DSLs. Switching out the prompting alone will not suffice.

As mentioned above, grammars might need to be adapted and refined to operate
with this approach, as LLMs tend to find loopholes in ’incompletely’ defined
grammars. This requires the developer who sets up the framework to have some
experience in language design.

##  7\. Conclusion

We were able to show that frameworks that enable constrained decoding enable
smaller, less performant LLMs to produce syntactically correct models at a
reasonable rate. Our experiments show, that grammar masking can significantly
increase the chance of an LLM-based approach to produce valid models for a
given DSL. We could demonstrate this improvement for two DSLs. Within this
paper, we only address syntactic validation of the produced models. Further
analysis has to be performed to systematically evaluate if there are
systematic differences in the semantics of unconstrained and constrained
models. In addition, an extensive difference in computation time between
unconstrained and constrained generation was measured. As a result, we
recommend that the method described in this work should only be used if a
satisfactory outcome cannot be achieved using conventional prompt engineering
methods. Improvements in frameworks, such as precomputations (Syncode) and
runtime optimations, could soon reduce the gap in computation time.

## References

  * (1)
  * git ([n. d.]) [n. d.].  Efficient and general syntactical decoding for Large language Models.  https://github.com/uiuc-focal-lab/syncode.  [Accessed 02-07-2024].
  * lar ([n. d.]) [n. d.].  Lark documentation.  https://lark-parser.readthedocs.io/en/stable/.  [Accessed 27-06-2024].
  * art ([n. d.]) [n. d.].  LLM Leaderboard - Compare GPT-4o, Llama 3, Mistral, Gemini & other models — Artificial Analysis — artificialanalysis.ai.  https://artificialanalysis.ai/leaderboards/models.  [Accessed 01-07-2024].
  * Amaratunga ([n. d.]) Thimira Amaratunga. [n. d.].  Understanding Large Language Models.  ([n. d.]).
  * Austin et al. (2021) Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. 2021\.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_ (2021).
  * Bader et al. ([n. d.]) Elias Bader, Dominik Vereno, and Christian Neureiter. [n. d.].  Facilitating User-Centric Model-Based Systems Engineering using Generative AI.  ([n. d.]).
  * Barenkamp et al. (2020) Marco Barenkamp, Jonas Rebstadt, and Oliver Thomas. 2020.  Applications of AI in classical software engineering.  _AI Perspectives_ 2, 1 (2020), 1.
  * Baumann et al. (2024) Nils Baumann, Juan Sebastian Diaz, Judith Michael, Lukas Netz, Haron Nqiri, Jan Reimer, and Bernhard Rumpe. 2024.  Combining Retrieval-Augmented Generation and Few-Shot Learning for Model Synthesis of Uncommon DSLs. In _Modellierung 2024 Satellite Events_. Gesellschaft für Informatik eV, 10–18420.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners.  _Advances in neural information processing systems_ 33 (2020), 1877–1901.
  * Busch et al. (2023) Daniel Busch, Gerrit Nolte, Alexander Bainczyk, and Bernhard Steffen. 2023.  ChatGPT in the loop: a natural language extension for domain-specific modeling languages. In _International Conference on Bridging the Gap between AI and Reality_. Springer, 375–390.
  * Butting et al. (2023) Arvid Butting, Rohit Gupta, Nico Jansen, Nikolaus Regnat, and Bernhard Rumpe. 2023.  Towards Modular Development of Reusable Language Components for Domain-Specific Modeling Languages in the MagicDraw and MontiCore Ecosystems.  _Journal of Object Technology_ 22, 1 (September 2023), 1:1–21.  https://doi.org/10.5381/jot.2023.22.1.a4
  * Chair of Software Engineering (2023) Chair of Software Engineering. 2023.  _Class Diagram For Analysis_.
  * Chen et al. (2024) Banghao Chen, Zhaofeng Zhang, Nicolas Langrené, and Shengxin Zhu. 2024.  Unleashing the potential of prompt engineering in Large Language Models: a comprehensive review.  arXiv:2310.14735 [cs.CL] https://arxiv.org/abs/2310.14735
  * Crawford et al. (2023) Talia Crawford, Scott Duong, Richard Fueston, Ayorinde Lawani, Samuel Owoade, Abel Uzoka, Reza M Parizi, and Abbas Yazdinejad. 2023.  Ai in software engineering: A survey on project management applications.  _arXiv preprint arXiv:2307.15224_ (2023).
  * Dohan et al. (2022) David Dohan, Winnie Xu, Aitor Lewkowycz, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A Saurous, Jascha Sohl-Dickstein, et al. 2022\.  Language model cascades.  _arXiv preprint arXiv:2207.10342_ (2022).
  * Fedele (2023) Andrea Fedele. 2023.  Explain and Interpret Few-Shot Learning.. In _xAI (Late-breaking Work, Demos, Doctoral Consortium)_. 233–240.
  * Fuchs et al. (2008) Norbert E Fuchs, Kaarel Kaljurand, and Tobias Kuhn. 2008.  Attempto controlled english for knowledge representation.  _Reasoning Web: 4th International Summer School 2008, Venice, Italy, September 7-11, 2008, Tutorial Lectures_ (2008), 104–124.
  * Hölldobler et al. (2021) Katrin Hölldobler, Oliver Kautz, and Bernhard Rumpe. 2021.  _MontiCore Language Workbench and Library Handbook: Edition 2021_.  Shaker Verlag.  http://www.monticore.de/handbook.pdf
  * Konrad and Cheng (2005) Sascha Konrad and Betty HC Cheng. 2005.  Real-time specification patterns. In _Proceedings of the 27th international conference on Software engineering_. 372–381.
  * Liu et al. (2024) Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. 2024.  Lost in the middle: How language models use long contexts.  _Transactions of the Association for Computational Linguistics_ 12 (2024), 157–173.
  * Liu et al. (2023) Yiheng Liu, Tianle Han, Siyuan Ma, Jiayue Zhang, Yuanyuan Yang, Jiaming Tian, Hao He, Antong Li, Mengshen He, Zhengliang Liu, et al. 2023\.  Summary of chatgpt-related research and perspective towards the future of large language models.  _Meta-Radiology_ (2023), 100017.
  * MacNeil et al. (2023) Stephen MacNeil, Andrew Tran, Arto Hellas, Joanne Kim, Sami Sarsa, Paul Denny, Seth Bernstein, and Juho Leinonen. 2023.  Experiences from using code explanations generated by large language models in a web software development e-book. In _Proceedings of the 54th ACM Technical Symposium on Computer Science Education V. 1_. 931–937.
  * Muktadir (2023) Golam Md Muktadir. 2023.  A Brief History of Prompt: Leveraging Language Models.(Through Advanced Prompting).  _arXiv e-prints_ (2023), arXiv–2310.
  * Netz et al. (2024) Lukas Netz, Judith Michael, and Bernhard Rumpe. 2024.  From Natural Language to Web Applications: Using Large Language Models for Model-Driven Software Engineering. In _Modellierung 2024_. Gesellschaft für Informatik eV, 179–195.
  * Netz and Reimer (2024) Lukas Netz and Jan Reimer. 2024.  _LLMs4MBSE Synthetic-Artifacts_.  https://github.com/Lukas-Netz/llm4mbse-synthetic-artifacts
  * OpenAI et al. (2024) OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapiro, Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Łukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Łukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reiichiro Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O’Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, Ian Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. 2024.  GPT-4 Technical Report.  arXiv:2303.08774 [cs.CL] https://arxiv.org/abs/2303.08774
  * Ren et al. (2018) Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B Tenenbaum, Hugo Larochelle, and Richard S Zemel. 2018.  Meta-learning for semi-supervised few-shot classification.  _arXiv preprint arXiv:1803.00676_ (2018).
  * Sadik et al. (2023) Ahmed R Sadik, Sebastian Brulin, and Markus Olhofer. 2023.  Coding by design: Gpt-4 empowers agile model driven development.  _arXiv preprint arXiv:2310.04304_ (2023).
  * Singh and Sidhu (2018) D Singh and HJS Sidhu. 2018.  Optimizing the software metrics for UML structural and behavioral diagrams using metrics tool.  _Asian Journal of Computer Science and Technology_ 7, 2 (2018), 11–17.
  * Timperley et al. ([n. d.]) Louis Timperley, Lucy Berthoud, Chris Snider, and Theo Tryfonas. [n. d.].  Assessment of Large Language Models for Use in Generative Design of Model Based Spacecraft System Architectures.  _Available at SSRN 4823264_ ([n. d.]).
  * Ugare et al. (2024) Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. 2024.  Improving llm code generation with grammar augmentation.  _arXiv preprint arXiv:2403.01632_ (2024).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention Is All You Need.  _CoRR_ abs/1706.03762 (2017).  arXiv:1706.03762
  * Wang et al. (2024) Bailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao, Rif A Saurous, and Yoon Kim. 2024.  Grammar prompting for domain-specific language generation with large language models.  _Advances in Neural Information Processing Systems_ 36 (2024).
  * Wang et al. (2022) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022.  Self-consistency improves chain of thought reasoning in language models.  _arXiv preprint arXiv:2203.11171_ (2022).
  * Wei et al. (2021) Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le. 2021.  Finetuned language models are zero-shot learners.  _arXiv preprint arXiv:2109.01652_ (2021).
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022\.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ 35 (2022), 24824–24837.
  * Zhao et al. (2023) Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, Yifan Du, Chen Yang, Yushuo Chen, Zhipeng Chen, Jinhao Jiang, Ruiyang Ren, Yifan Li, Xinyu Tang, Zikang Liu, Peiyu Liu, Jian-Yun Nie, and Ji-Rong Wen. 2023.  A Survey of Large Language Models.  arXiv:2303.18223 [cs.CL] https://arxiv.org/abs/2303.18223


# ColorShapeLinks: A board game AI competition for educators and students

Nuno Fachada<EMAIL_ADDRESS>Lusófona University, COPELABS / HEI-
Lab
Campo Grande, 376, Lisbon, Portugal

###### Abstract

ColorShapeLinks is an AI board game competition framework specially designed
for students and educators in videogame development, with openness and
accessibility in mind. The competition is based on an arbitrarily-sized
version of the Simplexity board game, the motto of which, “simple to learn,
complex to master”, is curiously also applicable to AI agents. ColorShapeLinks
offers graphical and text-based frontends and a completely open and documented
development framework built using industry standard tools and following
software engineering best practices. ColorShapeLinks is not only a
competition, but both a game and a framework which educators and students can
extend and use to host their own competitions. It has been successfully used
for running internal competitions in AI classes, as well as for hosting an
international AI competition at the IEEE Conference on Games.

###### keywords:

Board games , Videogame development , Computer games , Simplexity , AI
competition , AI agent , AI curriculum , DotNet

190mm(-3cm,-5cm) The peer-reviewed version of this paper is published in
Computers and Education: Artificial Intelligence at
https://doi.org/10.1016/j.caeai.2021.100014. This version is typeset by the
author and differs only in pagination and typographical detail.

##  1 Introduction

ColorShapeLinks is an artificial intelligence (AI) competition framework for
the Simplexity board game (Brain Bender Games, 2009) with arbitrary
dimensions. It is a similar game to Connect-4, with pieces defined not only by
color, but also by shape.

The ColorShapeLinks development framework offers Unity (Unity Technologies,
2021) and .NET console frontends. Agents are implemented in C# and run
unmodified in either frontend. Unity and C# are widely used in the games
industry (Toftedahl & Engström, 2019) and for game development education
(Dickson, 2015; Dickson et al., 2017; Comber et al., 2019; Fachada & Códices,
2020; Hmeljak, 2020), making the competition especially accessible to this
audience. The framework is open source, fully documented and developed
following best practices in software engineering, allowing it to be studied
and extended by educators, researchers and students alike (Lakhan &
Jhunjhunwala, 2008; Jiménez et al., 2017). Furthermore, it contains all the
tooling for setting up competitions. It can be used for internal competitions
in AI courses, for example, or for running international AI competitions, as
demonstrated in the 2020 edition of the IEEE Conference on Games (IEEE CoG).
In this regard, ColorShapeLinks is not simply a software tool that uses AI
technologies for educational purposes (Chen et al., 2020), but a software
toolkit to both teach and learn board game AI.

This paper is organized as follows. In Section 2, the state of the art in
board game AI—and how ColorShapeLinks fits in—is briefly discussed. The
ColorShapeLinks board game and its original version, Simplexity, are
characterized in Section 3. In Section 4, the motivation for developing
ColorShapeLinks, as well as the educational context in which the framework
took form, are examined. The development framework, namely its architecture,
existing frontends, agent implementation, included agents, and availability,
are reviewed in Section 5. In Section 6, we describe how ColorShapeLinks was
used to host two internal competitions in an AI course unit, as well as a
fully-fledged international AI competition in the IEEE CoG 2020 conference.
The implications and limitations of the framework and of the reported outcomes
are discussed in Section 7. The paper closes with Section 8, in which we
present some conclusions.

##  2 Background

Computer programs for playing classical board games such as Chess, Draughts or
Go, were the first known application of AI for games (Millington, 2019). AI
research in games has subsequently grown far beyond the domain of board games
(Yannakakis & Togelius, 2018). Nonetheless, these continue to be a focus of
active research, not only in AI techniques for playing particular games—e.g.,
Go (Silver et al., 2016)—but also for playing board games in general (Konen,
2019; Kowalski et al., 2019; Piette et al., 2020), or even creating new ones
(Stephenson et al., 2019; Kowalski & Szykuła, 2016). Furthermore, new board
game AI challenges and competitions continue to be proposed (Justesen et al.,
2019).

While board games are probably one of the easiest ways to introduce AI for
games to students (Drake & Sung, 2011; Chesani et al., 2017), state-of-the-art
board game AI research is gaining some distance from both industry and
education in videogame development. Requirements such as general game playing
capabilities for the AI or knowledge of general game specification languages
(Stephenson et al., 2019; Kowalski et al., 2019) can potentially raise the
entry level for newcomers and/or discourage prospective participants which
could otherwise bring new ideas to academia—or at least get involved in its
processes.

ColorShapeLinks aims to reduce this gap by offering an approachable, open and
flexible AI competition for the videogame development education audience. This
is accomplished by making the development of an AI agent very simple (e.g.,
write a single method and test it in Unity), while allowing for considerable
customization via a modular framework architecture. This same modularity
enables games and full tournaments to run within and without Unity. While
accessible for undergraduates and non-specialist game developers,
ColorShapeLinks provides a challenging and intricate board game competition,
addressable with vastly different techniques, from knowledge-based methods
(Allis, 1988) to machine learning techniques (Silver et al., 2016), or
anything in between.

It should be noted that ColorShapeLinks could be implemented under a general
game playing system such as RBG (Kowalski et al., 2019) or Ludii (Piette et
al., 2020), and this would probably be an excellent exercise. However, using
these frameworks would mean losing some of the educational advantages offered
by ColorShapeLinks, namely accessibility, openness (e.g., Ludii was not open
source at the time of writing) and keeping the focus on general game design
and development education while providing students with a broad AI for games
background.

##  3 ColorShapeLinks

ColorShapeLinks is a version of the Simplexity board game with arbitrary and
parameterizable dimensions. We describe Simplexity and ColorShapeLinks in
Subsections 3.1 and 3.2, respectively, highlighting their computational
characteristics in Subsection 3.3.

###  3.1 The Simplexity Board Game

The Simplexity board game is similar to Connect-4 in two regards: 1) the first
player to connect four pieces of a given type wins; and, 2) the base board
size is $6\times 7$. The crucial difference is that, in Simplexity, pieces are
defined not only by color, but also by shape—round or square. Player 1, white,
wins if it can connect either four round pieces or four white pieces. Likewise
for player 2, red, but with square or red pieces. Players begin with 21 pieces
of their color, 11 of which square, and the remaining 10 round. The catch here
is that shape has priority over color as a winning condition. Therefore, a
player can lose in its turn when placing a piece of the opponent’s winning
shape. Table 1 summarizes these rules and Figure 1 shows the possible winning
conditions.

(a) White wins with white pieces.

(b) White wins with round pieces.

(c) Red wins with red pieces.

(d) Red wins with square pieces.

Figure 1: Possible victory conditions in ColorShapeLinks using standard Simplexity rules. Table 1: Simplexity rules. | Player 1 | Player 2
---|---|---
Plays first? | Yes | No
Plays with | White pieces | Red pieces
Begins with |  $11\times$ white square pieces |  $11\times$ red square pieces
|  $10\times$ white round pieces |  $10\times$ red round pieces
Wins with line of |  $4\times$ round pieces |  $4\times$ square pieces
(shape has priority) |  $4\times$ white pieces |  $4\times$ red pieces

###  3.2 The ColorShapeLinks Board Game

ColorShapeLinks is a Simplexity game parameterizable with respect to board
dimensions, number of pieces required for a winning sequence, and initial
number of round and square pieces. Table 2 shows the available parameters as
well as the symbols used for them in the remainder of this paper.

Table 2: ColorShapeLinks parameters. Symbol | Name | Defaulta
---|---|---
$r$ | Rows | 6
$c$ | Columns | 7
$w$ | Win sequence | 4
$s$ | Square pieces per player | 11
$o$ | Round pieces per player | 10
a i.e., a regular game of Simplexity.

###  3.3 Characteristics

ColorShapeLinks can be characterized as follows (Yannakakis & Togelius, 2018;
Millington, 2019):

  * 1.

It is a turn-based game.

  * 2.

It is a two-player, zero-sum adversarial game.

  * 3.

It is deterministic, i.e., there is no random element influencing the game
state.

  * 4.

It has perfect information, i.e., the board state is fully observable.

  * 5.

The maximum number of turns is given by

$t_{\text{max}}=\min{\\{r\cdot c,2(s+o)\\}}$

i.e., it is equal to the minimum between the number of board positions,
$r\cdot c$, and the total pieces available to be played, $2(s+o)$.

  * 6.

Since each board position can be in one of five states (empty, white circle,
white square, red circle or red square), an upper bound for the state space is
given by $5^{t_{\text{max}}}$. In practice the state space will be
considerably smaller, since this value includes invalid states, for example
when pieces are on top of empty cells.

  * 7.

The initial branching factor is $2\times c$ (2 shapes, $c$ columns), although
it may decrease during the game as columns are filled and pieces of a certain
shape are played-out. Consequently, an upper bound for the game tree size is
given by $(2\cdot c)^{t_{\text{max}}}$.

These characteristics place ColorShapeLinks in an interesting position for AI
research. The game, even with standard Simplexity parameters, cannot currently
be solved using a brute force approach in a short amount of time. Like most
games nowadays, machine learning techniques (e.g., deep learning) together
with a tree search approach such as Monte Carlo Tree Search (MCTS) (Coulom,
2007), for example, will certainly be able to produce hard-to-beat agents.
However, the limited and well-defined ruleset leaves the door open for
knowledge-based or even analytical solutions.

##  4 Educational Context and Motivation

ColorShapeLinks was originally developed as a Unity-only assignment for an AI
for Games course
unit111https://github.com/VideojogosLusofona/ia_2019_board_game_ai at Lusófona
University’s Videogames BA. This is an evenly interdisciplinary degree (Mateas
& Whitehead, 2007), meaning that while it possesses solid Computer Science
(CS) fundamentals, it is more limited in this regard than technology-focused
curriculums, giving equal ground to Game Design and Art courses. The Unity
game engine is used in most of the course units, since it is easy to learn,
free, cross-platform, and widely used in education and actual game development
(Dickson, 2015; Dickson et al., 2017; Comber et al., 2019; Toftedahl &
Engström, 2019; Fachada & Códices, 2020; Hmeljak, 2020). Consequently, and to
increase student’s proficiency with Unity, the engine’s scripting language,
C#, is lectured independently in two programming course units (Fachada &
Códices, 2020). The AI for Games course unit threads this fine line by
implementing a hands-on, Unity and industry-oriented program based on selected
parts of Millington’s AI for Games textbook (Millington, 2019). The course
unit addresses topics such as heuristics, board games, movement, pathfinding,
decision making, learning and procedural content generation. However, more
complex and/or academic materials are avoided. With respect to the topic of
board games, the course focuses on the Minimax algorithm, as well as several
variations and optimizations, such as alpha-beta pruning, move ordering and
iterative deepening. Techniques such as transposition tables and MCTS are not
currently lectured, although in the specific case of MCTS this might change
given the proven usefulness of the method in a variety of different games and
scenarios (Yannakakis & Togelius, 2018).

Due to its wide-ranging design, Lusófona’s Videogames degree attracts students
from various areas of study and with substantially different interests. An
issue with this type of curriculum design is that it can be difficult to
motivate students enrolled in courses outside their main preferences. This is
often the case of art and design-inclined students in CS courses in general
(Fachada, 2018, 2020; de Andrade & Fachada, 2020), and AI in particular (Lin
et al., 2021). Thus, student motivation strategies become particularly
relevant in this context (Pintrich, 2003). Board game competitions in AI
courses have been shown to motivate students in studying course materials and
in autonomously search for solutions beyond the scope of the course’s program
and lectures (Chesani et al., 2017). Hence, and with the goal of increasing
motivation among students—particularly those whose primary interests do not
lie in CS—a board game AI assignment featuring an internal classroom
competition was devised. Given the variety of student backgrounds, the project
had to be made accessible for everyone, while challenging for more advanced
and/or CS-oriented students. A deterministic, fully observable two-player,
non-trivial board game was an obvious choice. Another requirement was that it
was not a very well-known game, so that not much AI code was available online,
forcing students to be original. Simplexity (Brain Bender Games, 2009) ticks
those boxes, as it was only used once in an AI course (Wilkins, 2012), to our
knowledge. Furthermore, Simplexity was implemented as a console C# project (no
AI) two years prior222https://github.com/VideojogosLusofona/lp1_2017_p1, thus
being a perfect choice, since students already knew the base game. This led to
the development of ColorShapeLinks, an AI assignment and competition, first
introduced in the first semester of the 2019/20 academic year.

Moreover, some authors have reported positive educational outcomes when
creating assignments based on international AI competitions (Kim & Cho, 2013;
Yoon & Kim, 2015). They argue that, by offering students the possibility of
submitting their solutions to international events, and of comparing their
solutions with the state of the art, their engagement and motivation are
improved. Following this line of reasoning, ColorShapeLinks was proposed as a
competition for the IEEE CoG 2020 conference. Since the first version of the
framework was only suitable for basic classroom competitions, it was extended
to support more advanced use cases. Additions included a console mode, for
advanced debugging and analysis of agents, and a set of scripts for setting up
automatically running tournaments. Thus, ColorShapeLinks recast its role as an
internal competition during the second semester of the 2019/20 academic year,
while at the same time hosting the eponymous competition at the IEEE CoG 2020
conference. These experiences are described in Section 6.

Beyond the educational benefits of ColorShapeLinks discussed thus far, and the
fact that Unity is widely used in education and industry, it should also be
noted that: (1) C# is used as a scripting language in several major game
engines (Unity Technologies, 2021; Bello et al., 2021; Crytek, 2021; Linietsky
et al., 2021; Spilman et al., 2021; FlaxEngine, 2021; UNIGENE Corp., 2021;
Plain Concepts, 2021); and, (2) neither Unity nor C# are very common in game
AI competitions. Thus, ColorShapeLinks has the potential to more generally
reduce the gap between academic AI and game development industry/education.
This is especially relevant for interdisciplinary and/or industry-oriented
programs such as Lusófona’s Videogames BA.

##  5 Development Framework

The ColorShapeLinks development framework offers two application frontends,
one for the Unity game engine, the other a text-based affair aimed at terminal
use. This allows students familiar with Unity to start implementing an agent
from their comfort zone, advancing to the text-based console frontend if Unity
development limitations begin to show. Advanced students or researchers can
skip the Unity frontend altogether, and start with the console frontend from
the offset. The framework architecture supporting this flexibility is
described in Subsection 5.1. Subsection 5.2 details the two available
frontends, highlighting their advantages and disadvantages. The basics of
implementing an agent are discussed in Subsection 5.3, while the agents
included with the framework are presented in Subsection 5.4. Finally, the
framework’s availability, documentation and licensing are outlined in
Subsection 5.5.

###  5.1 Architecture

The development framework is organized around three main components, namely
the Unity frontend (UnityApp, a single .NET/Mono project), the console
frontend (ConsoleApp, composed of two .NET projects), and the Common .NET
project. This organization is shown in Figure 2, and discussed with additional
detail in the following paragraphs.

Figure 2: Internal organization of the ColorShapeLinks development framework.
Arrows represent dependencies between separate .NET projects.

####  5.1.1 The Common Project

The Common project is a .NET class library which constitutes the core of the
framework. It defines the fundamental models—from a Model-View-Controller
(MVC) perspective (Sarcar, 2020)—of the ColorShapeLinks game, such as the
board, its pieces or performed moves, and is a dependency of the remaining
projects. It is further subdivided in the AI and Session namespaces. The
former defines AI-related abstractions, such as the AbstractThinker class,
which AI agents must extend, as well as a manager for finding and
instantiating concrete AI agents. The latter specifies a number of match and
session-related interfaces, as well as concrete match and session (i.e.,
tournament) models.

####  5.1.2 The ConsoleApp Frontend Projects

The ConsoleApp is composed of two .NET projects, App and Lib, both of which
depend on the Common class library, as shown in Figure 2. The App project is a
.NET console application with an internal dependency on the Lib project,
itself a .NET class library. The App project provides the actual console
frontend, namely the text user interface (TUI) with which the user interacts
in order to run ColorShapeLinks matches and sessions.

The Lib class library acts as an UI-independent “game engine”, offering match
and session controllers, as well as interfaces for the associated event
system, allowing to plug in renderers (views, in MVC parlance) or other event
handling code at runtime. It serves as a middleware between the Common library
and frontend applications, such as the one implemented in the App project. It
is not used by the Unity implementation, since Unity already provides its own
game engine logic, forcing match and session controllers to be tightly
integrated with its frame update cycle. Nonetheless, the Lib class library
makes the creation of new ColorShapeLinks TUIs or GUIs very simple, as long as
they are not based on highly prescriptive frameworks such as Unity.

####  5.1.3 The UnityApp Frontend Project

The UnityApp is a ColorShapeLinks frontend implemented in the Unity game
engine. Like the ConsoleApp, it is designed around the MVC design pattern,
making use of the models provided by the Common library. In this case,
however, the views and controllers are tightly integrated with the Unity
engine.

###  5.2 Frontends

The two available frontends, for Unity and console, have similar capabilities.
Both are capable of performing matches and tournaments involving multiple AI
agents and human players. An agent can be used without modification when
moving from one frontend to the other. There are, however, advantages in using
the console frontend. The following paragraphs offer additional detail on each
frontend.

####  5.2.1 The Unity Frontend

In the Unity frontend, matches and tournaments are played within the Unity
Editor, though it is possible to create a standalone build with prefixed match
or tournament configurations. The rationale behind this choice is that
ColorShapeLinks is at its core a development framework. Therefore, it makes
sense this is done within the Unity Editor, which is a development
environment. A game of ColorShapeLinks running within the Unity Editor is
shown in Figure 3.

Figure 3: Running ColorShapeLinks using the Unity Editor UI.

Developing an agent within the Unity editor has the disadvantage that games
run considerably slower than in the console. Furthermore, constantly creating
standalone builds with prefixed configurations is not practical. Therefore,
while this frontend makes ColorShapeLinks approachable, it should be
considered more of an introduction to the competition than a definitive way of
implementing advanced state-of-the-art ColorShapeLinks agents.

####  5.2.2 The Console Frontend

The console UI allows for a more refined control of ColorShapeLinks matches
and sessions. Being based on MVC, it allows for easily swapping the UI, as
well as running matches at full speed, contrary to the Unity editor. Figure 4
shows running a ColorShapeLinks match using the console UI.

While the console frontend offers many extensibility points, its default
configuration will likely suffice in most situations. For example, users can
run a learning algorithm on top of the console app, making use of its return
values, which indicate the match result or if an error occurred.

Figure 4: Running ColorShapeLinks using the console UI. Only the start of the
match is shown.

###  5.3 Implementing an Agent

The first step to implement an AI agent is to extend the AbstractThinker base
class. This class has three overridable methods, but it is only mandatory to
override one of them, as shown in Table 3.

Table 3: Overridable Methods in the AbstractThinker class Method | Mandatory | Purpose
---|---|---
| override? |
Setup() | No | Setup the AI agent.
Think() | Yes | Select the next move to perform.
ToString() | No | Return the AI agent’s name.

There is also the non-overridable OnThinkingInfo() method, which can be
invoked for producing “thinking” information, mainly for debugging purposes.
In the Unity frontend this information is printed on Unity’s console, while in
the console frontend the information is forwarded to the registered thinker
listeners (or views, from a MVC perspective).

Classes extending AbstractThinker also inherit a number of useful read-only
properties, namely board and match configuration properties (number of rows,
number of columns, number of pieces in sequence to win a game, number of
initial round pieces per player and number of initial square pieces per
player) and the time limit for the AI to play. Concerning the board/match
configuration properties, these are also available in the board object given
as a parameter to the Think() method. However, the Setup() method can only
access them via the inherited properties.

The following subsections address the overriding of each of these three
methods.

####  5.3.1 Overriding the Setup() method

If an AI agent needs to be configured before starting to play, the Setup()
method is the place to do it. This method receives a single argument, a
string, which can contain agent-specific parameters, such as maximum search
depth, heuristic to use, and so on. It is the agent’s responsibility to parse
this string. In the Unity frontend, the string is specified in the “Thinker
params” field of the AIPlayer component. When using the console frontend, the
string is passed via the \--white/red-params option for simple matches, or
after the agent’s fully qualified name in the configuration file of a complete
session. Besides the parameters string, the Setup() method also has access to
board/match properties inherited from the base class.

The same AI agent can represent both players in a single match, as well as
more than one player in sessions/tournaments. Additionally, separate instances
of the same AI agent can be configured with different parameters. In such a
case it might be useful to also override the ToString() method for
discriminating between the instances configured differently. This is an
essential feature if ColorShapeLinks is running under a machine learning
and/or optimization infrastructure.

Note that concrete AI agents require a parameterless constructor in order to
be found by the various frontends. Such constructor exists by default in C#
classes if no other constructors are defined. However, it is not advisable to
use a parameterless constructor to setup an AI agent, since the various
board/match properties will not be initialized at that time. This is yet
another good reason to perform all agent configuration tasks in the Setup()
method. In any case, concrete AI agents do not need to provide an
implementation of this method if they are not parameterizable or if they do
not require an initial configuration step.

####  5.3.2 Overriding the Think() method

The Think() method is where the AI actually does its job and is the only
mandatory override when extending the AbstractThinker class. This method
accepts the game board and a cancellation token, returning a Future-Move
object. In other words, the Think() method accepts the game board, the AI
decides the best move to perform, and returns it. The selected move will
eventually be executed by the match engine.

The Think() method is called in a separate thread. Therefore, it should only
access local instance data. The main thread may ask the AI to stop thinking,
for example if the thinking time limit has expired. Thus, while thinking, the
AI should frequently test if a cancellation request was made to the
cancellation token. If so, it should return immediately with no move
performed.

The game board can be freely modified within the Think() method, since this is
a copy and not the original game board being used in the main thread. More
specifically, the agent can try moves with the DoMove() method, and cancel
them with the UndoMove() method. The board keeps track of the move history, so
the agent can perform any sequence of moves, and roll them back afterwards.
For parallel implementations, the agent can create additional copies of the
board, one per thread, so that threads can search independently of each other.

The CheckWinner() method of the game board is useful to determine if there is
a winner. If there is one, the solution is placed in the method’s optional
parameter. For building heuristics, the game board’s public read-only variable
winCorridors will probably be useful. This variable is a collection containing
all corridors (sequences of positions) where promising or winning piece
sequences may exist.

The AI agent will lose the match in the following situations:

  * 1.

Causes or throws an exception.

  * 2.

Takes too long to play.

  * 3.

Returns an invalid move.

####  5.3.3 Overriding the ToString() method

By default, the ToString() method removes the namespace from the agent’s fully
qualified name, as well as the “thinker”, “aithinker” or “thinkerai” suffixes.
However, this method can be overridden in order to behave differently. One
such case is when agents are parameterizable, and differentiating between
specific parameterizations during matches and sessions becomes important.

####  5.3.4 Summing-up

Building an AI agent for ColorShapeLinks is very simple, asking only the
implementer to extend a class and implement one method. A basic Minimax
algorithm with a simple heuristic can be implemented in less than 30 minutes.
Educators can use it to demonstrate how to create a simple agent from scratch,
during a class for example, and leave up to the students to find better, more
efficient solutions. This can be done as an assignment, a competition, or
both.

###  5.4 Included Agents

Three test agents are included with the framework, serving both as an example
on how to implement an agent, as well as a baseline reference for testing
other agents.

The sequential agent always plays in sequence, from the first to the last
column and going back to the beginning, although skipping full columns. It
will start by using pieces with its winning shape, and when these are over, it
continues by playing pieces with the losing shape. Therefore, it is not a
“real” AI agent.

The random agent plays random valid moves, avoiding full columns and
unavailable shapes. It can be parameterized with a seed to perform the same
sequence of moves in subsequent matches (as long as the same valid moves are
available from match to match).

The minimax agent uses a basic, unoptimized Minimax algorithm with a naive
heuristic which privileges center board positions. It can be parameterized
with a search depth, and, although simple, is able to surprise unseasoned
human players—even at low search depths.

###  5.5 Availability

The development framework is available at
https://github.com/VideojogosLusofona/color-shape-links-ai-competition and is
fully open source, licensed under the Mozilla Public License
2.0333https://www.mozilla.org/en-US/MPL/2.0/ (MPL2), which requires changes to
the source code to be shared, although allowing for integration with
proprietary code if the MPL2 licensed code is kept in separate files. The
framework is completely documented and the documentation is available at
https://videojogoslusofona.github.io/color-shape-links-ai-
competition/docs/html/.

##  6 Deployments

The ColorShapeLinks framework has been used to host two internal competitions
(in separate semesters) in an AI for Games course unit at Lusófona
University’s Videogames BA, as well as an international AI competition in the
IEEE CoG 2020 conference. These deployments are discussed in the next two
subsections.

###  6.1 Internal Competitions in AI for Games Course Units

ColorShapeLinks was used as an assignment and internal competition in an AI
for Games course unit during the two semesters of the 2019/20 academic year.
In both semesters, the submitted AI agents and associated reports were graded
preliminarily and separately from the final competition. Since students work
in groups of 2 or 3 elements, an individual discussion was also performed.
Results from the internal competition were used to potentially improve the
preliminary grades, not lower them, since the main goal was to motivate
students and have an engaging class where students watched and commented on
the performance of each others’ agents in real time. Nonetheless, if an agent
was not competent enough to enter the competition, i.e., it freezed the Unity
project or did not respond to cancellation requests, up to 1 point could be
subtracted from the final grade. No students from the first semester repeated
the course during the second semester.

However, there were several differences between the two semesters. In the
first semester, ColorShapeLinks was a Unity-only assignment, as stated in
Section 4. The minimum requirement for passing—i.e., to have a grade of 10 or
higher (grades are given in a 0–20 scale)—was that students implemented an
agent capable of defeating the sequential and random agents. The basic minimax
agent, described in Subsection 5.4, was not included in the framework at this
time. In the second semester, the console frontend and the basic minimax agent
were added to the framework, with the assignment coinciding with the first few
weeks of the international competition. The minimum passing requirement in the
second semester was for the submitted agent to beat the basic minimax
implementation. Grade distribution and summary statistics for the
ColorShapeLinks assignment in both semesters are shown in Fig. 5 and Table 4,
respectively.

Figure 5: Grade distribution for the ColorShapeLinks AI assignment in the two semesters of the 2019/20 academic year. Grades are given in a 0–20 scale. Table 4: Summary statistics for the ColorShapeLinks AI assignment grades in the two semesters of the 2019/20 academic year, namely, number of students enrolled, $n_{\text{all}}$, number of students evaluated in the assignment, $n_{\text{eval}}$, mean grade, $\overline{x}$, median grade, $\widetilde{x}$, and percentage of students with a passing grade, $\%_{\geq 10}$. Grades are given in a 0–20 scale. | $n_{\text{all}}$ | $n_{\text{eval}}$ | $\overline{x}$ | $\widetilde{x}$ | $\%_{\geq 10}$
---|---|---|---|---|---
Semester 1 | 27 | 25 | $12.02$ | $12.00$ | $80.00\text{\,}\mathrm{\char 37\relax}$
Semester 2 | 25 | 22 | $13.64$ | $13.00$ | $86.36\text{\,}\mathrm{\char 37\relax}$

Looking at the overall results in both semesters, at least 80% of the students
had a passing grade ($\geq 10$) and participated actively in the assignment.
Students less interested in the AI aspect of game design and development
mostly submitted Minimax-based agents, e.g. with alpha-beta pruning, just to
pass the project. They were, nonetheless, generally more committed than in
other AI and programming assignments. On the other end, students more
comfortable with programming and AI generally dedicated more hours to the
assignment and came up with interesting and competitive agents. Most, if not
all students were highly engaged with the final live competition during class
(e.g., “my AI is better than yours”!).

There were some notable grading variations between the two semesters. Grades
in the second semester were higher in average, and more students met the
passing grade (Table 4), even though the minimum requirement was higher. Grade
distribution (Fig. 5) shows that, in the first semester, a considerable number
of students aimed at the bare minimum just to get a passing grade, while in
the second semester students generally went for more elaborate solutions. Some
of these went beyond the scope of the lectured materials, making use of
transposition tables, search parallelization and heuristics parameter
learning. We argue there were three main reasons, which separately or in
combination, led to this outcome:

  1. 1.

The console app allowed some students to better test and debug their agent
implementations, without being constrained by Unity.

  2. 2.

Some students might have been motivated due to working on an assignment which
was at the same time an international AI competition.

  3. 3.

The minimax agent allowed students to study and better understand how a “real”
agent could be implemented, allowing them to build upon it.

These results suggest that ColorShapeLinks was successful in allowing students
with various interests and with different capabilities within game making—as
is the case of students in Lusófona’s Videogames BA—to be able to produce
palpable, working AI code, and to feel included when addressing this
challenging topic.

###  6.2 IEEE CoG 2020 International Competition

ColorShapeLinks was accepted as an official AI competition at the IEEE CoG
2020 conference, and was funded with a prize money of 500 USD for the winner
of each track. The competition ran on two distinct tracks:

  1. 1.

The Base Track, which used standard Simplexity rules with a time limit of 0.2
seconds per move. Only one processor core was available for the AI agents.

  2. 2.

The Unknown Track, which was played on a multi-core processor under a
parameterization known only after the competition deadline, since it was
dependent on the result of a public lottery draw.

The goal of the Base Track was to test agent capabilities in the standard
Simplexity game. The Unknown Track evaluated the generalization power of the
submitted solutions when applied to a most likely untested parameterization.

For each track, the submitted agents played against each other two times, so
each had the opportunity of playing first. Agents were awarded 3 points per
win, 1 point per draw and 0 points per loss, with the final standings for each
track depending on the total number of points obtained per agent.

Classifications for the Base Track were updated daily during a five month
period, up until the submission deadline, together with two larger test
parameterizations. This allowed participants to have an idea of how their
submission was faring, and update it accordingly.

The competition had a total of six submissions, four of which were from
undergraduate students, both solo and in teams. Two of the submissions were
from students of the author which fared well in the internal competition
discussed in the previous subsection. Although the number of submissions was
low, the fact that four of them were from undergrads, partially demonstrated
that the competition was accessible.

Eita Aoki, from Japan, won the Base Track with his Thunder agent, which used
MCTS together with a custom bit board implementation. The winner and runner-up
of the Unknown Track were teams from Portugal and students of the author which
attended the AI for Games course in the second semester. João Moreira won the
track with SureAI, a highly optimized Minimax-based agent. The SimpAI agent,
developed by a team of three students, was the runner-up, implementing a set
of hand-crafted heuristics balanced with an evolutionary algorithm (Fernandes
et al., 2021). While interesting, none of these agents was truly state-of-the-
art, leaving the door open for better agents going forward.

##  7 Implications and Limitations

The deployments discussed in the previous sections demonstrate the potential
and usefulness of the ColorShapeLinks framework. The internal competition
appeared to motivate the students, who were highly engaged during the class
tournaments held in both semesters. The introduction of the international
competition during the second semester had a more pronounced effect, though.
Overall grades and dedication improved, with students generally showing more
autonomy and going beyond what was lectured in the classes, effectively
validating the works of Kim & Cho (2013) and Yoon & Kim (2015). The authors of
SimpAI, a student group of the second semester, were able to publish a paper
describing their solution and the second place it obtained in the Unknown
Track of the international competition (Fernandes et al., 2021). These results
show that AI competitions in general, and ColorShapeLinks in particular, have
clear educational benefits with respect to student motivation, engagement and
autonomy. This is further highlighted by the fact that Lusófona’s Videogames
degree is interdisciplinary (non-CS focused) and industry-driven (not academy-
oriented). The fact that students from such a degree were able to compete in
an international competition with good results indicates that ColorShapeLinks
shows good promise in bridging the gap between game development education and
academic AI.

However, the research presented in this paper has two main limitations which
should be highlighted. First, no survey was done in order to assess students’
reflections on the competitions. The stated student motivation and engagement
during the internal competitions are taken from the author’s observations, and
thus, entirely subjective and potentially biased, no matter how clear or
obvious they might have been. Second, the underlying game has a very narrow
focus. Even as an unbounded version of Simplexity, ColorShapeLinks—as a
game—is relatively simple. Thus, many good and excellent solutions are bound
to appear on the short to medium term, possibly even analytical solutions,
such as the case of Connect-4 (Allis, 1988). Consequently, ColorShapeLinks—as
a framework—might have a short service life before the problem it addresses
becomes effectively solved. Still, this is not the case at the time of
writing, as ColorShapeLinks will again be one of the competitions being held
at the IEEE CoG 2021 conference.

##  8 Conclusions

In this paper we presented ColorShapeLinks, and AI board game competition
framework specifically designed for game development students and educators,
with openness and accessibility at its core. The arbitrarily-sized Simplexity
board game—implemented by the framework—offers a good balance between
simplicity and complexity, being approachable by undergraduates, while posing
a non-trivial challenge to researchers and more advanced students. The
framework has been successfully used for running internal competitions in an
AI for Games course unit, as well as for hosting an international AI
competition, validating its usefulness. Although the problem addressed by the
proposed framework is bound to be solved in the next few years—thus rendering
the framework obsolete—the general ideas presented in this paper, such as
running internal and international AI competitions using industry standard
tools and software best practices for educational purposes, were confirmed,
and remain valid for similar future endeavors.

## Statements on open data and ethics

The data reported in this paper is fully anonymized and publicly available at
the Zenodo open-access scientific repository (Fachada, 2021).

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Acknowledgments

This work is supported by Fundação para a Ciência e a Tecnologia under Grants
UIDB/04111/2020 (COPELABS) and UIDB/05380/2020 (HEI-Lab). The author would
like to thank André Fachada for proof-reading the text. The author would also
like to thank the anonymous referees for their valuable comments and helpful
suggestions.

## References

  * Allis (1988) Allis, L. V. (1988).  A Knowledge-Based Approach of Connect-Four. The Game is Solved: White Wins.  Master’s thesis Vrije Universiteit Amsterdam, Netherlands.
  * de Andrade & Fachada (2020) de Andrade, D., & Fachada, N. (2020).  Fun maths for all game development students.  In Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education ITiCSE ’20 (pp. 529–530).  New York, NY, USA: ACM.  URL: https://doi.org/10.1145/3341525.3393992. doi:10.1145/3341525.3393992.
  * Bello et al. (2021) Bello, V. et al. (2021).  Stride.  URL: https://stride3d.net/.
  * Brain Bender Games (2009) Brain Bender Games (2009).  Simplexity.  Discovery Bay Games.  https://boardgamegeek.com/boardgame/55810/simplexity.
  * Chen et al. (2020) Chen, X., Xie, H., & Hwang, G.-J. (2020).  A multi-perspective study on artificial intelligence in education: Grants, conferences, journals, software tools, institutions, and researchers.  Computers and Education: Artificial Intelligence, 1, 100005. URL: http://www.sciencedirect.com/science/article/pii/S2666920X20300059. doi:10.1016/j.caeai.2020.100005.
  * Chesani et al. (2017) Chesani, F., Galassi, A., Mello, P., & Trisolini, G. (2017).  A game-based competition as instrument for teaching artificial intelligence.  In F. Esposito, R. Basili, S. Ferilli, & F. A. Lisi (Eds.), AI*IA 2017 Advances in Artificial Intelligence Lecture Notes in Computer Science (pp. 72–84).  Springer International Publishing.  doi:10.1007/978-3-319-70169-1_6.
  * Comber et al. (2019) Comber, O., Motschnig, R., Mayer, H., & Haselberger, D. (2019).  Engaging students in computer science education through game development with unity.  In 2019 IEEE Global Engineering Education Conference (EDUCON) (pp. 199–205).  IEEE.  doi:10.1109/EDUCON.2019.8725135.
  * Coulom (2007) Coulom, R. (2007).  Efficient selectivity and backup operators in monte-carlo tree search.  In H. J. van den Herik, P. Ciancarini, & H. H. L. M. J. Donkers (Eds.), Computers and Games (pp. 72–83).  Berlin, Heidelberg: Springer Berlin Heidelberg volume 4630 of Lecture Notes in Computer Science.  doi:10.1007/978-3-540-75538-8_7 international Conference on Computers and Games. CG 2006.
  * Crytek (2021) Crytek (2021).  CryEngine.  URL: https://www.cryengine.com/.
  * Dickson (2015) Dickson, P. E. (2015).  Using unity to teach game development: When you’ve never written a game.  In Proceedings of the 2015 ACM Conference on Innovation and Technology in Computer Science Education ITiCSE ’15 (pp. 75–80).  New York, NY, USA: ACM.  URL: http://doi.acm.org/10.1145/2729094.2742591. doi:10.1145/2729094.2742591.
  * Dickson et al. (2017) Dickson, P. E., Block, J. E., Echevarria, G. N., & Keenan, K. C. (2017).  An experience-based comparison of unity and unreal for a stand-alone 3d game development course.  In Proceedings of the 2017 ACM Conference on Innovation and Technology in Computer Science Education ITiCSE ’17 (pp. 70–75).  New York, NY, USA: ACM.  URL: http://doi.acm.org/10.1145/3059009.3059013. doi:10.1145/3059009.3059013.
  * Drake & Sung (2011) Drake, P., & Sung, K. (2011).  Teaching introductory programming with popular board games.  In Proceedings of the 42nd ACM Technical Symposium on Computer Science Education SIGCSE ’11 (pp. 619–624).  New York, NY, USA: ACM.  URL: https://doi.org/10.1145/1953163.1953338. doi:10.1145/1953163.1953338.
  * Fachada (2018) Fachada, N. (2018).  Teaching database concepts to video game design and development students.  Revista Lusófona de Educação, 40, 151–165. URL: http://revistas.ulusofona.pt/index.php/rleducacao/article/view/6437. doi:10.24140/issn.1645-7250.rle40.10.
  * Fachada (2020) Fachada, N. (2020).  Desafios no ensino da programação a alunos de videojogos.  In Atas do 1.º SEVj - Seminário Sobre Ensino de Videojogos (pp. 59–73).  Sociedade Portuguesa de Ciências dos Videojogos.  URL: http://hdl.handle.net/10316/89402.
  * Fachada (2021) Fachada, N. (2021).  ColorShapeLinks 2019/20 grades dataset.  Zenodo.  doi:10.5281/zenodo.4543679 (Version 1.0.0) [Data set].
  * Fachada & Códices (2020) Fachada, N., & Códices, N. (2020).  Top-down design of a CS curriculum for a computer games BA.  In Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education ITiCSE ’20 (pp. 300–306).  New York, NY, USA: ACM.  URL: https://doi.org/10.1145/3341525.3387378. doi:10.1145/3341525.3387378.
  * Fernandes et al. (2021) Fernandes, P. A., Inácio, P. A., Feliciano, H., & Fachada, N. (2021).  SimpAI: Evolutionary heuristics for the ColorShapeLinks board game competition.  In I. Barbedo, J. P. Sousa, & B. Legerén (Eds.), Videogame Sciences and Arts, VJ 2020 Communications in Computer and Information Science.  Springer.  IN PRESS.
  * FlaxEngine (2021) FlaxEngine (2021).  Flax Engine.  URL: https://flaxengine.com/.
  * Hmeljak (2020) Hmeljak, M. (2020).  Developing a computer graphics course with a game development engine.  In Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education ITiCSE ’20 (pp. 75–81).  New York, NY, USA: ACM.  URL: https://doi.org/10.1145/3341525.3387428. doi:10.1145/3341525.3387428.
  * Jiménez et al. (2017) Jiménez, R. C., Kuzak, M., Alhamdoosh, M., Barker, M., Batut, B., Borg, M., Capella-Gutierrez, S., Hong, N. C., Cook, M., Corpas, M. et al. (2017).  Four simple recommendations to encourage best practices in research software [version 1; peer review: 3 approved].  F1000Research, 6. doi:10.12688/f1000research.11407.1.
  * Justesen et al. (2019) Justesen, N., Uth, L. M., Jakobsen, C., Moore, P. D., Togelius, J., & Risi, S. (2019).  Blood Bowl: A new board game challenge and competition for AI.  In 2019 IEEE Conference on Games (CoG) (pp. 1–8).  IEEE.  doi:10.1109/CIG.2019.8848063.
  * Kim & Cho (2013) Kim, K.-J., & Cho, S.-B. (2013).  Game ai competitions: An open platform for computational intelligence education [educational forum].  IEEE Computational Intelligence Magazine, 8, 64–68. doi:10.1109/MCI.2013.2264568.
  * Konen (2019) Konen, W. (2019).  General board game playing for education and research in generic AI game learning.  In 2019 IEEE Conference on Games (CoG) (pp. 1–8).  IEEE.  doi:10.1109/CIG.2019.8848070.
  * Kowalski et al. (2019) Kowalski, J., Mika, M., Sutowicz, J., & Szykuła, M. (2019).  Regular boardgames.  In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (pp. 1699–1706).  volume 33 of AAAI-19.
  * Kowalski & Szykuła (2016) Kowalski, J., & Szykuła, M. (2016).  Evolving chess-like games using relative algorithm performance profiles.  In G. Squillero, & P. Burelli (Eds.), Applications of Evolutionary Computation (pp. 574–589).  Springer International Publishing volume 9597 of Lecture Notes in Computer Science.  doi:10.1007/978-3-319-31204-0_37 european Conference on the Applications of Evolutionary Computation.
  * Lakhan & Jhunjhunwala (2008) Lakhan, S. E., & Jhunjhunwala, K. (2008).  Open source software in education.  EDUCAUSE Quarterly, 31, 32–40. URL: https://er.educause.edu/articles/2008/5/open-source-software-in-education.
  * Lin et al. (2021) Lin, P.-Y., Chai, C.-S., Jong, M. S.-Y., Dai, Y., Guo, Y., & Qin, J. (2021).  Modeling the structural relationship among primary students’ motivation to learn artificial intelligence.  Computers and Education: Artificial Intelligence, 2, 100006. URL: https://www.sciencedirect.com/science/article/pii/S2666920X20300060. doi:https://doi.org/10.1016/j.caeai.2020.100006.
  * Linietsky et al. (2021) Linietsky, J., Manzur, A. et al. (2021).  Godot Engine.  URL: https://godotengine.org/.
  * Mateas & Whitehead (2007) Mateas, M., & Whitehead, J. (2007).  Design issues for undergraduate game-oriented degrees.  In Proceedings of the 2007 Microsoft Academic Days on Game Development in Computer Science Education (pp. 85–89).
  * Millington (2019) Millington, I. (2019).  AI for Games.  (3rd ed.).  Boca Raton, FL, USA: CRC Press.  URL: https://doi.org/10.1201/9781351053303. doi:10.1201/9781351053303.
  * Piette et al. (2020) Piette, E., Soemers, D. J., Stephenson, M., Sironi, C. F., Winands, M. H., & Browne, C. (2020).  Ludii – the ludemic general game system.  In G. De Giacomo, A. Catala, B. Dilkina, M. Milano, S. Barro, A. Bugarín, & J. Lang (Eds.), ECAI 2020 (pp. 411–418).  volume 325 of Frontiers in Artificial Intelligence and Applications.  doi:10.3233/FAIA200120.
  * Pintrich (2003) Pintrich, P. (2003).  A motivational science perspective on the role of student motivation in learning and teaching contexts.  Journal of Educational Psychology, 95, 667–686. doi:10.1037/0022-0663.95.4.667.
  * Plain Concepts (2021) Plain Concepts (2021).  Wave Engine.  URL: https://waveengine.net/.
  * Sarcar (2020) Sarcar, V. (2020).  Design Patterns in C#: A Hands-on Guide with Real-world Examples.  (2nd ed.).  Apress.  doi:10.1007/978-1-4842-6062-3.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M. et al. (2016).  Mastering the game of go with deep neural networks and tree search.  Nature, 529, 484–489. doi:10.1038/nature16961.
  * Spilman et al. (2021) Spilman, T. et al. (2021).  MonoGame.  URL: http://www.monogame.net/.
  * Stephenson et al. (2019) Stephenson, M., Piette, E., Soemers, D. J., & Browne, C. (2019).  Ludii as a competition platform.  In 2019 IEEE Conference on Games (CoG) (pp. 1–8).  IEEE.  doi:10.1109/CIG.2019.8848084.
  * Toftedahl & Engström (2019) Toftedahl, M., & Engström, H. (2019).  A taxonomy of game engines and the tools that drive the industry.  In A. Nakamura (Ed.), DiGRA ’19 - Proceedings of the 2019 DiGRA International Conference: Game, Play and the Emerging Ludo-Mix.  DiGRA: Digital Games Research Association.
  * UNIGENE Corp. (2021) UNIGENE Corp. (2021).  Unigene.  URL: https://unigine.com/.
  * Unity Technologies (2021) Unity Technologies (2021).  Unity®.  URL: https://unity.com/.
  * Wilkins (2012) Wilkins, D. (2012).  Program 4a: Simplexity.  CSCI 531: Artificial Intelligence, Computer and Information Science Department, University of Mississippi.  https://john.cs.olemiss.edu/~dwilkins/CSCI531/fall12/prog4.html.
  * Yannakakis & Togelius (2018) Yannakakis, G. N., & Togelius, J. (2018).  Artificial Intelligence and Games.  Springer.  http://gameaibook.org.
  * Yoon & Kim (2015) Yoon, D.-M., & Kim, K.-J. (2015).  Challenges and opportunities in game artificial intelligence education using angry birds.  IEEE Access, 3, 793–804. doi:10.1109/ACCESS.2015.2442680.