figurec

# Evolutionary Tabletop Game Design: A Case Study in the Risk Game

Lana Bertoldo Rossato  Universidade Federal do Rio Grande do Sul  Leonardo
Boaventura Bombardelli  Universidade Federal do Rio Grande do Sul  Anderson
Rocha Tavares  Universidade Federal do Rio Grande do Sul

###### Abstract

Creating and evaluating games manually is an arduous and laborious task.
Procedural content generation can aid by creating game artifacts, but usually
not an entire game. Evolutionary game design, which combines evolutionary
algorithms with automated playtesting, has been used to create novel board
games with simple equipment; however, the original approach does not include
complex tabletop games with dice, cards, and maps. This work proposes an
extension of the approach for tabletop games, evaluating the process by
generating variants of Risk, a military strategy game where players must
conquer map territories to win. We achieved this using a genetic algorithm to
evolve the chosen parameters, as well as a rules-based agent to test the games
and a variety of quality criteria to evaluate the new variations generated.
Our results show the creation of new variations of the original game with
smaller maps, resulting in shorter matches. Also, the variants produce more
balanced matches, maintaining the usual drama. We also identified limitations
in the process, where, in many cases, where the objective function was
correctly pursued, but the generated games were nearly trivial. This work
paves the way towards promising research regarding the use of evolutionary
game design beyond classic board games.

_K_ eywords Evolutionary Game Design $\cdot$ Genetic Algorithm $\cdot$ Risk

##  1 Introduction

Creating and testing games is a challenging and costly task. A significant
number of matches are needed to determine if a game is good enough to be
published, in terms of balance and enjoyment. In this sense, Artificial
Intelligence (AI) can aid in automating such tests, speeding up the search for
balanced and enjoyable games.

Evolutionary game design [1] combines evolutionary algorithms to evolve game
rules, defined by a grammar, with automated playtesting with general game
playing [2] algorithms. It has proven effective on board games, even creating
the relatively successful commercial game Yavalath111Yavalath
(https://boardgamegeek.com/boardgame/33767/yavalath) is a board game created
via the Ludi framework [1]. Its rules are regarded as interesting by humans..
However, the original evolutionary game design process is limited to
traditional board games with simple equipment and does not support the
inclusion of cards, dice, and maps found in tabletop games.

This work proposes extending evolutionary game design techniques to
accommodate for the more complex rules and equipment of tabletop games, such
as dice and cards. Our chances also include the replacement of genetic
programming by a genetic algorithm, allowing a more aggressive exploration of
the search space. We apply our extended evolutionary game design approach to
Risk, a game where players battle to conquer all territories displayed on the
map. In Risk, dice rolls determine the outcome of battles, adding uncertainty
to the gameplay. Additionally, cards can be traded for troops, increasing the
strategic possibilities of the game. We aim to create novel and interesting
variants of the game. Risk already has many different published variations of
its original game, which turns it into a good tabletop game to test the
automatic generation of variants through evolutionary game design.

To allow the evaluation of our extended evolutionary game design process, we
use a simplified, two-player version of Risk. We also replaced the playtesting
agent based on Monte Carlo Tree Search (MCTS) [3] with a faster and simpler
rule-based agent to make playtesting feasible. Our empirical results indicate
that our approach is able to generate Risk versions with smaller maps,
resulting in shorter matches. Also, the variants were more balanced,
maintaining the usual drama, where a losing player can hope to turn the tides
of a match and win. However, we identified the limitation that, in many cases,
the generated games had very small maps, which led to trivial games, despite
the good evaluation of the objective function. Moreover, the rule-based agent
provides limited coverage of the strategic possibilities of the generated
versions.

The main contributions of this work include deepening the investigation of
evolutionary game design for tabletop games. Our findings show that aiming to
minimize Risk’s branching factor favors the predominance of small maps. The
source code of the implementation for reproducibility purposes is
available222https://github.com/lanabr/Risk-Generation.

##  2 Background

###  2.1 Evolutionary Game Design

The Ludi framework [1] was proposed with the aim of creating exciting and
novel board games via software. To accomplish this, the system is capable of
playing and evaluating newly created games. The remainder of this subsection
describes the components of the Ludi framework.

The Game Description Language (GDL) defines the rules and components of the
games. The GDL needs to be robust and comprehensive in order to represent
known and unknown games, and it also needs to be understandable and coherent
for human creators. Ludi’s GDL is based on the concept of ludemes, which are
units of game information that can be replicated and transformed.

The General Game Player (GGP) is capable of interpreting and playing any game
described in GDL. Includes the rule parser, the game object, the play manager,
which includes move scheduling and cycle detection, and the user interface.

The Strategy Module is responsible for finding the move to be made in each
round of the game. It uses advisors and policies to evaluate the current state
of the game and determine the best move.

The Evaluation Module measures the evaluation criteria of the games. These
criteria encompass intrinsic (based on rules and equipment) and extrinsic
(based on game moves and outcomes) characteristics of the games.

The Synthesis Module is responsible for creating new sets of rules using
evolutionary algorithms. The process involves selection, crossover, mutation,
and rule validations. The initial population consists of real games with rule
diversity.

The current version of the system, Ludii (two “i” mean “second version” of
Ludi) [4], does not yet generate new games. The main goal of Ludii now is to
reconstruct ancient games from partial rule descriptions and equipment from
archaeological findings.

###  2.2 The Risk Game

Risk is a strategy tabletop game for up to six players, simulating military
conflicts in a world map333https://www.hasbro.com/common/instruct/risk.pdf. On
the basic version, a player wins by conquering all map territories (i.e. by
placing at least one troop piece at each territory). This section briefly
describes the Rules of the Risk game. At the beginning of the game, the
territories are distributed evenly for each player. After that, each player
plays a turn consisting of four steps:

  * •

Receive and place troops: players receive troops proportional to the
territories and continents they own, and may be able to exchange territory
cards for extra troops;

  * •

Attack opponents: players may attack neighboring territories. Both the
attacker and the defender roll a die for each attacking or defending troop, at
the maximum of three. Draws favor the defender. If the attacker wins by
defeating all defending troops, he conquers and occupies the disputed
territory;

  * •

Fortify territories and receive territory card: on the aftermath of all
attacks, the player may move troops to reinforce territories on enemies’
borders. If the player conquered at least one territory, it receives a
territory card.

Players alternate turns until a single player own all game territories.

##  3 Related Work

We begin by showing that research on content generation for Risk has not been
previously considered (Section 3.1). Then, Section 3.2 shows that, although
the automatic generation of specific content for games, such as maps, cards,
sounds, and textures has been widely explored [5, 6] by researchers in both
physical and digital games [7, 8] the generation a complete game becomes more
challenging due to the need to consider important features such as rule
coherence and game enjoyment.

###  3.1 Risk and applications

Much of the research on Risk focuses on game-playing agents. Different methods
are employed, such as Monte Carlo Tree Search (MCTS) [9], heuristic-based
approaches [10], and Convolutional Neural Networks [11]. Some works combine
the use of MCTS with Neural Networks [12], while others utilize linear
evaluation functions [13]. Although competent game-playing agents might be
useful for playtesting, these works did not focus on content creation for the
game. Moreover, the agents might not be able to cope with a game with changing
rules.

Some studies [9, 10, 11] utilize Lux Delux444https://sillysoft.net/lux/, an
online platform based on Risk, to test different game profiles and AI.
However, this is a commercial platform not focused on content generation, and
some rules are different from the original Risk.

Other research examines more specific situations in the games, such as battle
outcome estimation [14] or even the use of Risk or particular variants as
learning tools [15].

###  3.2 Automated game generation

In the field of automated game generation, researchers have focused on
different aspects and challenges. Some works aim to generate specific game
content, such as maps for video games [16, 8] or cards for collectible card
games [17], while preserving the overall environment and original rules. These
works employ automated techniques to create game elements efficiently.

When it comes to generating an entire game, including the rules, the
challenges become more complex. Early attempts, such as Togelius and
Schmidhuber’s work, focused on evolving the rules of a game, particularly in
the context of the Pac-Man game style. The objective was not to generate
optimal games right away, but to demonstrate the possibility and explore new
research areas.

Other approaches, like Hom and Marks’s, aimed to generate balanced games using
evolutionary techniques. The goal was to create games without favoritism
towards the player going first, and the process achieved considerable success.

The testing platform used in automated game generation plays a crucial role.
Lux Delux, developed by Sillysoft, is widely utilized by several works [20,
21, 22]. However, Lux Delux has limitations, particularly in rule
modification, as it is not an open-source software. The TAG (Tabletop Games)
framework [23] provides a structure to encompass different types of modern
games in a common platform. However, incorporating the framework into the
evolutionary design process presents challenges, as metrics acquisition and
game definitions differ.

In summary, although game creation has been explored in the literature, little
attention has been given to an automatic generation of tabletop games.
Regarding Risk, specifically, most research focuses on game-playing agents or
educational aspects of the game.

##  4 Evolutionary Design of Risk Variants

The Evolutionary Game Design framework has been proven successful at
generating enjoyable board games for human players (see Section 2.1). However,
the framework handles board games with simple equipment, basically the board
itself, with various forms of regular connectivity (e.g. squares, hexagons),
and pieces of various types. This allows the definition of games such as Hex,
Go or Chess, but not games that use different equipment such as dice and cards
or are played on environments with nontrivial connectivity, such as maps.

This section presents our evolutionary game design approach for tabletop
games, containing dices, cards and a map. We focus on Risk, a military
strategy game of map domination (see Section 2.2), but the principles can be
applied to any tabletop game. The definition of a game description language
for tabletop games would be very complicated to accommodate the different
equipment and the nontrivial connectivity of a map, and it is out of the scope
of this work. Instead, we define basic, non-changeable game rules (Section 4.1
and expose a set of parameters that define many features of the game behavior
(Section 4.2). We use a genetic algorithm as our evolutionary approach
(Section 4.3), combining game metrics from the original evolutionary game
design process into our fitness function. The genetic algorithm allows for
more aggressive exploration of the search space as the entire population is
generated every generation, whereas in the genetic programming [24] approach
of the original evolutionary game design process creates a single individual
per generation.

The proposed process of automatically generating versions of Risk is thus
capable of creating, playing, and evaluating the generated versions. The
implementation was done in the Python language and is openly available on
GitHub555https://github.com/lanabr/Risk-Generation.

###  4.1 Simplified Risk

In this pipeline, a simpler version of Risk was used. Our main simplification
is the restriction to two players, to allow for more direct application of the
game quality metrics (see Section 4.3). Moreover, the original Risk has a
variant with objective cards. Our version disregards these cards, so that the
goal of each player is always to conquer all map territories.

The implemented game engine provides a simple visualization, as shown in
Figure 1. Circles represent territories, and lines connect neighbor
territories. Nodes are numbered as “ID(troops)”. Colors surrounding nodes
indicate their continents, whereas color filling the nodes indicate the owner.

Figure 1: Map visualization on the implemented Risk engine.

The game engine has a command line interface for a human player. Although
primitive, the interface allows the player to perform all possible actions and
play the game properly.

###  4.2 Parameters

The game parameters define the map and some aspects of the rules, as outlined
next. We call the three first parameters as “attributes” and the last one is
the “map”. Attributes and map have different treatment under crossover and
mutation.

  * •

Initial territory distribution: flag indicating whether territories are
randomly distributed or alternately selected by players;

  * •

Number of defensive dice: two or three. As the attacker can choose up to three
dice, two defending dice favors the attacker;

  * •

Maximum troops moved to a conquered territory: it is either the number of
battle-surviving troops minus one or the number of all troops in the attacking
territory minus one. The latter favors that a recently occupied territory
becomes the starting point of a new attack;

  * •

Bonus troop factor: at the beginning of each turn, each player receives troops
equal to the number of owned territories divided by this factor, which can be
1, 2, 3 or 4. The player receives 3 troops if the division falls below three;

  * •

Map: the map is represented by a graph. Every possible connected graph is a
valid game map, hence the possible maps are infinite.

###  4.3 Genetic Algorithm

Our Genetic Algorithm (GA) follow the usual processes of selection,
reproduction, and replacement, detailed next. The stopping criterion on this
work is the number of generations. This entire process is presented in Figure
2.

Figure 2: Genetic algorithm for generating Risk game versions. Numbers
indicate the subsection describing each component. Playtests generate turn and
endgame metrics, being described in the same subsection. Crossover, mutation
and map validity are also described in a single subsection.

####  4.3.1 Initial Population

The initial population is randomly created. The parameter values for each
individual are chosen from the predefined possibilities. Possible starting
maps include 5 official maps and 5 artificial ones. The official maps,
although balanced, are large, with 42 territories divided into 6 continents,
often resulting in long games. They were taken from the original risk and the
variations: StarCraft, Transformer Edition, Star Wars: Clone Wars and Halo
Wars. The 5 artificial maps are smaller, ranging from 9 to 17 territories.
They aim to create more diverse individuals.

####  4.3.2 Playtest

As reported by [25], initial experiments have shown that Risk was challenging
for basic Monte Carlo Tree Search (MCTS). It would either require too much
time to perform a decent move, delaying the entire evolutionary process, or
return poor decisions if allowed a short time. Thus, each individual of the GA
is evaluated through a playtest composed of J matches between handcrafted
rule-based players, described next.

During the allocation phase, the rule-based agent tries to place its troops in
territories within the continent that provides the highest bonus troops. By
conquering this continent early in the game, the agent gains the maximum troop
bonus in the first attack phase. The agent performs card exchanges when it
owns a territory on its cards to gain extra troops. Otherwise, it holds the
cards until the maximum of 5, where an exchange is mandatory. When attacking,
the agent looks for battles where it has a numerical advantage. If there are
no such situations, the agent stops attacking.

In the fortification phase, the agent follows the same strategy as in the
allocation phase. It moves troops to less populated territories that are
bordering the opponent. Non-border territories can remain with only one troop.

The described agent is fast, allowing for the evaluation of many games, which
is necessary for the genetic algorithm.

During and at the end of a match, we calculate some metrics regarding the
plays in order to evaluate the game in the next step of the pipeline.

####  4.3.3 Evaluation and Fitness

Each game is evaluated for its quality. However, assessing how fun,
interesting, or engaging a game is can be challenging, as the perception of
fun and entertainment is subjective. Nevertheless, it is possible to evaluate
some characteristics related to the quality of a game from the players’
perspective. Browne presented 57 criteria for measuring the quality of a game,
and we use 7 of these criteria, which were considered the most relevant for
our purposes. Criteria related to rules and equipment were discarded because
we generate games with the same equipment and base rules. Also, criteria that
evaluate characteristics such piece color, that are not relevant in Risk, or
based on lookahead searches, which are not performed due to the game
complexity (see Section 4.3.2), were discarded. Other criteria were either
complementary or redundant to the ones we chose. For example: tendency of
draws (discarded) versus completion (included, see below).

The criteria are described below, and their equations are in Appendix A.

_Completion_ improves when a game results in victories more often than draws,
regardless of the player.

The _duration_ criteria measure how long a game tends to be, because it is
neither desirable for a game to last too long as it can become tiresome and
monotonous nor too short to become trivial.

The _advantage_ metric measures the unbalance of the game in favor of the
first player. It is necessary to maintain balance in order to keep both
players engaged.

The _branching factor_ (number of possible moves per turn) indicates the
complexity of a game, that is, how many possibilities the player needs to
consider.

The _drama_ measures the possibility, or expectation, that a player has to
turn the tide of a losing game. If there is no chance of winning (low drama),
the game will no longer be interesting for the player.

_Killer moves_ significantly change a player’s situation, turning them from a
loser to a winner quickly. Such moves are interesting since they can
dramatically change the evaluation of the players at that moment.

_Lead changes:_ similar to drama, if a game does not alternate the leader, it
becomes tedious. However, too much lead changes make the game too
unpredictable or chaotic. Turn metrics measure events inside a match whereas
endgame metrics are used to measure characteristics related to the game
termination or result. Our turn metrics are branching factor, drama, killer
moves and lead changes, whereas our endgame metrics are completion, duration
and advantage.

Fitness function: for fitness calculation, the approach tested was based on
distance. In this method, optimal values are chosen for each evaluation
criteria. The distance between the analyzed individual and an optimal
individual is then calculated. The optimal values can be seen in Table 1.

Table 1: Optimal values for the evaluation criteria. Criterion | Optimal Value
---|---
Completion | 1 (does not end up in draws)
Duration | 0 (each game ends in 24 turns)
Advantage | 0 (50% wins for both players)
Branching Factor | 0.5 (avg. of 50 possible moves per turn)
Drama | 0.5 (avg. degree of drama)
Killer Moves | 0.5 (avg. degree of killer moves)
Lead Change | 0.5 (avg. degree of lead change)

The fitness calculation is performed as shown in Equation 1, where $v_{i}$ is
the i-th criterion of the individual $v$, I is the set of criteria, and
$o_{i}$ is the optimal value of criterion $i$.

$fitness_{v}=\sum_{i=1}^{I}{|v_{i}-o_{i}|}$ (1)

We highlight that our fitness imposes a minimization problem, i.e., the lower
the fitness the better. This is a mismatch with the evolutionary metaphor of
“survival of the fittest”, but we maintain our formulation to keep Eq. 1
simple and meaningful (the closer to the desired values, the better) rather
than changing it towards a fitness-maximizing equation.

####  4.3.4 Selection

The GA uses tournament selection. Each tournament has k participants randomly
drawn from the population, and the two with the best fitness become the
parents of two new individuals. Moreover, elitism is applied, where the best
individual from the previous generation is copied to the new population.

####  4.3.5 Crossover and Mutation

After selecting two individuals from the population, we use a crossover
function to generate a new individual inheriting characteristic from both of
the selected individuals. The crossover is done by selecting some continents
from the first and second parents and combining them in a new map, creating
new connections between these continents’ territories. Now, on the new map,
these continents will inherit the same territory structure and bonus units
that the parent continents have.

The crossover and mutation operations are divided into two parts: attributes
and the map. The attributes are recombined using a random mask that always
splits the individual in half. Half of one parent is combined with the
complementary half of the other parent, generating one child, and the reverse
combination generates the second child. During attribute mutation, if the
mutation rate is reached, the new parameter value is flipped or chosen from
the possibilities, if applicable. Each mutation occurs independently, meaning
that one mutation does not imply that other parameters will mutate as well.
Multiple changes can occur in the same individual.

Map operations are more complex. During crossover, some continents from both
parents are chosen to be combined. They are brought with their original
connections, and additional connections are created to maintain coherence when
merging. During mutation, several operations can be performed, including
creating a new connection, removing a connection, moving a territory from one
continent to another, swapping the bonus value between two continents, or
modifying the continent bonus value by 1 unit.

The map resulting from this process needs to follow some rules. It must be
planar, to represent a map, and connected, so that all territories are
reached. We did this verification using the Networkx library. Planarity is
checked by the Left-Right Planarity Test [26] and connectivity is checked with
a depth-first search algorithm.

####  4.3.6 Replacement

After each iteration, the entire population used to generate the next one is
replaced. Thus, the new population consists of the best individual from the
previous population (elitism), along with the offspring produced by that
population.

##  5 Experiments

The first step of the experiments was to find the best values for the
hyperparameters of the genetic algorithm. After that, we show how maps evolved
and their main characteristics in the final generations. Then we show the
results of the evolution of the remaining parameters. We remark that, in our
formulation, we aim for as low fitness as possible, as it indicates that the
individual has metrics approaching the desired values.

###  5.1 Hyperparameters

During this initial testing phase, different values of 4 hyperparameters were
analyzed. 100 matches are played for each generated game, with a maximum limit
of 48 turns and a maximum time of 60 seconds per match. These hyperparameters
were chosen to consider the time for game testing, aiming to find the best
combination for future tests.

The parameters and tested values are as follows:

  * •

Number of generations: 10, 30, 50, 70, 90, 110, 130, 150, 170, 190.

  * •

Offspring size: 5, 10, 15, 20, 25, 30, 35, 40, 45, 50.

  * •

Tournament size: the number of participants in the selection tournament can
vary from 2 to half the number of individuals in the population, rounded down,
in increments of 2. For example, if the population size is 30, the tournament
participants range from 2 to 14.

  * •

Mutation rate: 0.1, 0.2, 0.4, 0.6, 0.8. The rate of 0.1 was added, considering
the parameter used by Browne.

All possible combinations of these 4 hyperparameters were tested to evaluate
and find the best option, i.e., the one that resulted in a fitness value
closest to the optimal value, according to the distance-based calculation. In
total, there were 3,250 distinct executions. Table 2 shows the fitness of the
top 10 executions, identified as 1 to 10, with the hyperparameters. It is
important to note that these values were obtained at the end of the last
generation of each execution.

Table 2: Parameters of each run generating the top 10 fitness Run | Fitness |  Num. of Gen. |  Off. Size |  Tourn Size |  Mutation Rate
---|---|---|---|---|---
1 | 0.779 | 10 | 50 | 22 | 0.6
2 | 0.798 | 150 | 30 | 12 | 0.1
3 | 0.800 | 50 | 50 | 16 | 0.6
4 | 0.823 | 150 | 30 | 8 | 0.6
5 | 0.847 | 150 | 20 | 6 | 0.8

Analyzing the parameters that led to a lower fitness value, it is interesting
to note that a lower number of generations was found. In this context, it is
expected that a low number of generations is not sufficient to evolve
individuals to their maximum. To understand the situation, Figure 3 shows the
fitness over generations for the best (a) and second-best (b) hyperparameter
configurations (configurations 1 and 2 in Table 2). It can be observed that in
the second-best execution, there was significant variation in the lowest
fitness value of each generation. In the best execution, since the number of
generations is much lower, this oscillation was smoother.

(a) Configuration 1 (best): 10 generations, 50 individuals in the offspring,
22 individuals in the tournament, 0.6 mutation rate

(b) Configuration 2 (2nd best): 150 generations, 30 individuals in offspring,
12 individuals in the tournament, 0.1 mutation rate

Figure 3: Fitness throughout the execution that resulted in the best fitness
and the second-best fitness at the end of the process.

When elitism is applied in the replacement of a population, the best
individual from the previous population is retained in the composition of the
new population. When this happens, the individual is reevaluated. The
evaluation is stochastic due to randomness in dice rolls. This can cause the
previously best individual to not have as good an evaluation as before.
Analyzing Figure 3(a), the minimum fitness value was quickly found, and since
there was no time for the various changes seen in Figure 3(b) to occur, it
remained stable.

Therefore, a high number of generations can lead to a low fitness value, and
that is what is expected. However, with a high number of generations, there is
a possibility that a low value will appear and be lost in a new evaluation.

Continuing with the analysis of hyperparameters, we can extract the best
values for each of them independently and also understand how each
characteristic influences the fitness outcome. When analyzing the number of
generations (Figure 4), it was not possible to identify a clear pattern. The
values shown in the graphs are the average of each set of runs and the lowest
value found in the last generation. The minimum fitness starts low, increases,
and then decreases with 150 generations of execution, while the average value
remains relatively stable. This suggests that the number of generations
evaluated alone does not have a significant influence on the fitness outcome,
as no significant pattern was identified.

Figure 4: Final fitness versus number of generations.

Considering the mutation rate (Figure 5) we observe an effect on both the
minimum and average values. The higher the mutation rate, the lower the
average fitness. This indicates that this characteristic may not have a
drastic impact on the minimum value but contributes to reducing the average
value.

Figure 5: Final fitness versus mutation rates.

When analyzing the number of individuals in the tournament and in the
offspring, we observe a pattern similar to the offspring size. There is
variation in the minimum fitness values and a decrease in the average as the
tournament size increases. We conclude that this hyperparameter is not a
measure to find the minimum fitness, but rather to decrease the values in
general. However, the best fitness values were obtained with varied tournament
sizes, although smaller values prevail.

In summary, no hyperparameter has complete responsibility for the final
fitness values. What occurs is a decrease in the average values, improving the
population as a whole. However, these values do not come very close to the
ideal or minimum value. Nevertheless, the runs used in the next tests will be
selected among the top 10 shown in Table 2.

###  5.2 Map Evolution

This section is dedicated to evaluating one of the most important aspects of
the game: the map, since it can influence all evaluation metrics. The
branching factor and duration are the most affected, as the possible movements
consider the number of territories on the map, and the more territories, the
longer it takes to conquer the entire map. In this section, the isomorphism of
maps and their viability are evaluated. Isomorphism was analyzed using the VF2
algorithm [28] implemented in the Networkx library.

The first step is to identify maps with isomorphic graphs to verify if there
were populations dominated by one map. Two runs exhibited this characteristic,
meaning that all maps in the last generation of both runs were isomorphic to
an initial map. Both runs had 10 generations and a 10% mutation rate. These
two factors may have strongly contributed to the propagation of only one map.
From the initial population, only 2 individuals carried this map. In the final
population, all individuals had maps that were isomorphic to Map 9.

The main strength of Map 9 is the small number of territories compared to
actual Risk maps. With 13 territories, the game time is significantly reduced,
as is the branching factor. Although it does not drastically affect the other
criteria, the decrease in the number of possible movements is something that
not all maps can offer.

On average, the best individuals from all test runs had a minimum of 2
territories, a maximum of 24 territories, and an average of 3.39 territories.
Even the individual with the highest number of territories has fewer
territories than real Risk maps, which have 42 territories.

In another analysis, a comparison of maps from the fastest run and the longest
run was conducted to understand the effects of extreme hyperparameter values.
The hyperparameters for the fastest run are 10 generations, 5 individuals in
the population, 2 as the tournament size, and 0.1 mutation rate. The
hyperparameters for the longest run are 190 generations, 50 individuals in the
population, 24 as the tournament size, and 0.8 mutation rate.

The map of the best individual generated by the fastest run can be seen in
Figure 6(a), and the map from the longest run is shown in Figure 6(b). Both
maps have a significantly reduced number of territories, with the fast run map
having 7 territories and the long run map having 2 territories, very close to
the average.

(a) Map representation of the best individual of the fast run.

(b) Map representation of the best individual of the long run.

Figure 6: Map representation of the best individual of the fast and the long
run.

Looking at the criteria shown in Table 3, we can see why the best individuals
had these maps. The advantage of both maps is very close to the ideal value,
with the fast run achieving this ideal value, and the branching factor also
remained close to the ideal value. Additionally, the duration was also reduced
in both runs.

Table 3: Scoring of the fastest and longest runs in each criteria and their respective distances from ideal values. Criteria | Ideal | Fast |  Fast Dist. | Long |  Long Dist.
---|---|---|---|---|---
Completion | 1 | 0.98 | 0.02 | 1 | 0
Duration | 0 | 0.41 | 0.41 | 0.69 | 0.69
Advantage | 0 | 0 | 0 | 0.02 | 0.02
Branching F. | 0.5 | 0.76 | 0.26 | 0.50 | 0
Drama | 0.5 | 0.30 | 0.2 | 0.42 | 0.08
Killer Moves | 0.5 | 0.78 | 0.28 | 0.56 | 0.06
Lead Change | 0.5 | 0.25 | 0.25 | 0.42 | 0.08
Fitness | 0 |  | 1.42 |  | 0.93

The values considered ideal for the criteria have a limitation. The duration
and branching factor criteria favor the emergence of small maps, such as the
one in Figure 6(a), as the number of territories strongly influences these
criteria. Therefore, since the fitness function requires low values for these
criteria, the number of territories needs to be small.

Among all 3250 executions, 3236 (99.56%) have their best individual with up to
10 territories. This shows a strong predominance of small maps, and it is
possible to conclude that in order to achieve ideal criterion values, the
generated maps need to be small.

###  5.3 Game Evolution

After understanding the evolution of maps, we need to also examine the
remaining parameters. Although they have a smaller set of combinations, they
are equally important as the map in fulfilling the objectives of this work.

Overall, the parameters do not have a predominant influence on the final
generation. The two values for the initial territory distribution mode
parameter were evenly divided:

  * •

Randomly distributed territories: 1900

  * •

Players choose territories: 1350

These values suggest that this parameter has little influence on the game
performance. When players choose their territories, there is a high chance
that both will start the game with the advantage of owning an entire
continent. When the distribution is random, neither player has this advantage.

Looking at the defensive dice quantity parameter, there is some difference in
the number of games with each value, but it is not very significant:

  * •

2 dice: 1674

  * •

3 dice: 1576

When only 2 defensive dice are used, there is an advantage for the attacker,
as the player has one more chance to roll a higher number than the opponent.
With 3 dice, this advantage decreases, as both players have an equal number of
dice.

In the parameter of the number of troops moved when conquering a new
territory, a larger difference can be observed:

  * •

Minimum quantity (number of attacking dice - 1): 2629

  * •

Maximum quantity (number of troops in the attacking territory - 1): 621

When the minimum quantity is transferred to the new territory, the number of
possible attacks from this conquered territory is small and likely limits the
player’s consecutive actions. With the maximum quantity, the game can become
longer.

Lastly, the factor that calculates the number of troops received at the
beginning of each turn obtained more uniform results:

  * •

Factor = 1: 773

  * •

Factor = 2: 807

  * •

Factor = 3: 845

  * •

Factor = 4: 825

Considering the minimum number of troops that must be received by the player
at the start of their turn, which is 3, they need to have 12 territories to
obtain that amount. As mentioned earlier in Section 5.2, the average number of
territories in the maps of the individuals in the last generation of the test
runs was 3.39. Therefore, it is impossible to obtain more than 3 troops,
rendering the factor irrelevant.

###  5.4 Gameplay, Generated Versions and Real Versions

Testing the gameplay of the best generated games requires many responsible
human participants with available time. Therefore, due to time limitations,
the author was the only one who conducted real tests.

The tested games are playable and consistent with the ideal criterion values.
However, it is only through tests with human players that it will be possible
to evaluate if the generated games are fun, challenging, and engaging enough.

Considering that the map size is the factor that can vary the most in the
evolution process, games from the initial generations have larger maps than
those generated in the end. However, this criterion alone is not sufficient to
determine if a game is good or bad, as there may be a combination of other
parameters that make a game good on a map considered bad.

The evaluation of Risk versions can be compared with the generated games. The
parameters for Risk include free initial territory choice, a factor of 3 in
the calculation of received troops, 2 defense dice, and the maximum number of
troops moved when conquering a new territory. It is also important to note
that the maximum number of turns played before declaring the game unfinished
is 24, with 12 turns for each player. The values of the criteria for Risk,
along with the ideal criteria and the best-generated game, are listed in Table
4.

Table 4: Values of criteria calculated for the original parameters of Risk Criteria | Risk | Ideal | Best Gen.
---|---|---|---
Completion | 0.063 | 1 | 1
Drama | 0.890 | 0.5 | 0.427
Duration | 0.994 | 0 | 0.637
Branching F. | 1 | 0.5 | 0.514
Killer Moves | 0.273 | 0.5 | 0.475
Lead Change | 0.009 | 0.5 | 0.489
Advantage | 0.96 | 0 | 0.02
Fitness | 4.498 | 0 | 0.779

The branching factor for both games was 1, indicating that there are many
possible moves in each turn. When calculating the branching factor, the
possibilities are truncated at 100. So, if the branching factor is equal to 1,
it means that the player had an average of 100 possible moves in the test
round. Additionally, the advantage for Risk games was high, 0.96, indicating
that the first player has a higher chance of winning than the second. The
completeness for Risk was extremely low, reaching the limit of turns imposed,
which is 24.

The duration of Risk has a very high value, indicating that the games last
much longer than ideal. Also, Risk has a balanced advantage. The other metrics
help stabilize the evaluation and represent a significant part of the fun of a
game. The original parameters of Risk result in different versions of the same
game with distinct metrics.

It is important to note that the parameters are applied to a simplified
implementation of the game and are played with a rule-based agent. The
original parameters in the original rules are suitable for human players,
given the commercial success of the games.

###  5.5 Analysis

In the first experiment, different hyperparameters were tested to identify
combinations that result in individuals with higher fitness. The results are
summarized in Table 2. Analysis of Figures 4 and 5 showed that increasing the
values of the hyperparameters only decreased the average fitness over
generations.

It was observed that the evolutionary process tends to generate smaller maps,
with 99.56% of the best individuals having 10 territories or fewer. This
pattern likely occurs due to the attempt to reach the desired values of
branching factor and duration metrics.

Furthermore, analysis of the other parameters revealed that certain values
favor the generation of better games. The random distribution of territories,
the use of 2 dice for the defender, the minimum number of troops moved in
conquering a territory, and a factor of 3 were the most common parameters
among the best individuals, including the individual with the best fitness.

Considering the experiments and results presented, we can conclude that the
pipeline is capable of generating new variations of the Risk game. All
generated variations are playable; however, those that underwent more
generations resulted in small maps, with an average of 3.39 territories. Those
result in nearly trivial games.

A limitation of this work is that the evolution process heavily depends on the
agent used for the game. It is necessary to implement a skilled agent to allow
the generation of versions with more strategic depth. The generated games are
evaluated based on the players’ actions, and if they play in a basic manner,
the games also tend to be basic. The rule-based player is fast but simple. On
the other hand, AI algorithms that perform well in board games are not
efficient for tabletop games.

The use of the genetic algorithm brings a new approach to the experiments that
were previously conducted with genetic programming. With the genetic
algorithm, the parameter exploration is more aggressive and can provide
greater variability to the generated individuals.

##  6 Conclusion

This work expanded the evolutionary game design process to include tabletop
games, being assessed in Risk, a territorial-domination military strategy
game. The game is represented by basic, immutable rules, but its behavior is
highly customized by the exposed set of parameters. The genetic algorithm used
aims to find the best possible combination of these parameters. The fitness
function is calculated by summing the distances of quality metrics to their
desired values. The metrics are assessed via playtests with a rule-based
agent.

During the execution of this work, various approaches were explored for the
game Risk, which had been little explored until then. From expanding a rule-
based agent to creating a new version of the game, different methodologies
were tested in different areas. It was possible to explore different ways to
analyze game quality and understand how they influence the evolution
parameters.

For future work, it is important to address the limitations identified in this
study. The first one is the fitness instability due to the randomness of the
game. Increasing the number of matches to calculate the metrics can make the
values more stable. Furthermore, a more in-depth study of the metrics that
make up the fitness and their target values can improve the quality of the
generated games, since in our tests, very small maps that induced nearly
trivial games had good fitness. Developing a more sophisticated agent is
another area of utmost importance. The challenge is to create an agent that
efficiently handles the complexity of the game, as a simple fitness evaluation
requires hundreds of matches. Exploring extensions of techniques such as MCTS
[3] or RMEA [29], used in digital games, may be promising.

Additionally, tests with human players can provide different perspectives and
insights into the game and its versions. In the future, the continuation of
this work will require test groups to find better versions and also to define
ideal values for evaluation metrics. Finally, adapting this work to a wide
range of games is an interesting project. Challenges such as including cards
and pieces with different movements can be explored. An even greater challenge
would be the establishment of a game description language for board games,
enabling the creation of completely new games.

## Acknowledgements

This study was financed in part by the Coordenação de Aperfeiçoamento de
Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.

## References

  * Browne [2011] Cameron Browne.  _Evolutionary Game Design_.  SpringerBriefs in Computer Science. Springer London, London, UK, 2011.  ISBN 9781447121794.  URL https://doi.org/10.1007/978-1-4471-2179-4.
  * Genesereth et al. [2005] Michael Genesereth, Nathaniel Love, and Barney Pell.  General game playing: Overview of the AAAI competition.  _AI magazine_ , 26(2):62–62, 2005.
  * Browne et al. [2012] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton.  A survey of monte carlo tree search methods.  _IEEE Transactions on Computational Intelligence and AI in games_ , 4(1):1–43, 2012.
  * Browne [2018] Cameron Browne.  Modern Techniques for Ancient Games.  In _IEEE Conference on Computational Intelligence and Games_ , pages 490–497, Maastricht, 2018. IEEE Press.
  * Hendrikx et al. [2013] Mark Hendrikx, Sebastiaan Meijer, Joeri Van Der Velden, and Alexandru Iosup.  Procedural content generation for games: A survey.  _ACM Transactions on Multimedia Computing, Communications, and Applications_ , 9(1), feb 2013.  ISSN 1551-6857.  doi: 10.1145/2422956.2422957.  URL https://doi.org/10.1145/2422956.2422957.
  * Togelius et al. [2011] Julian Togelius, Georgios N. Yannakakis, Kenneth O. Stanley, and Cameron Browne.  Search-based procedural content generation: A taxonomy and survey.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 3(3):172–186, 2011.  doi: 10.1109/TCIAIG.2011.2148116.
  * Summerville and Mateas [2016] Adam Summerville and Michael Mateas.  Mystical tutor: A magic: The gathering design assistant via denoising sequence-to-sequence learning.  _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , 12(1):86–92, 2016.
  * Uriarte and Ontañón [2013] Alberto Uriarte and Santiago Ontañón.  PSMAGE: balanced map generation for starcraft.  In _2013 IEEE Conference on Computational Inteligence in Games (CIG)_ , pages 1–8, Niagara Falls, ON, Canada, 2013. IEEE.  doi: 10.1109/CIG.2013.6633644.  URL https://doi.org/10.1109/CIG.2013.6633644.
  * Brand and Kroon [2014] Dirk Brand and Steve Kroon.  Sample evaluation for action selection in Monte Carlo tree search.  In _Proceedings of the Southern African Institute for Computer Scientist and Information Technologists Annual Conference 2014 on SAICSIT 2014 Empowered by Technology_ , pages 314–322, Centurion, South Africa, 2014. Association for Computing Machinery.  ISBN 9781450332460.  doi: 10.1145/2664591.2664612.  URL https://dl.acm.org/doi/10.1145/2664591.2664612.
  * Olsson [2005] Fredrik Olsson.  A multi-agent system for playing the board game Risk.  Master’s thesis, Blekinge Institute of Technology, 2005.  URL https://www.diva-portal.org/smash/get/diva2:831093/FULLTEXT01.pdf.
  * Carr [2020] Jamie Carr.  Using graph convolutional networks and TD($\lambda$) to play the game of risk, 2020.  URL https://arxiv.org/abs/2009.06355.
  * Heredia and Cazenave [2021] Lucas Gnecco Heredia and Tristan Cazenave.  Expert iteration for Risk.  In _Advances in Computer Games: 17th International Conference, ACG 2021_ , pages 27–37, Virtual Event, 2021. Springer-Verlag.  ISBN 978-3-031-11487-8.  doi: 10.1007/978-3-031-11488-5_3.  URL https://doi.org/10.1007/978-3-031-11488-5_3.
  * Wolf [2005] Michael Wolf.  _An Intelligent Artificial Player for the Game of Risk_.  PhD thesis, Darmstadt University of Technology, 2005.
  * Harju [2012] Manu Harju.  On probabilities of Risk type board game combats, 2012.  URL https://arxiv.org/abs/1204.4082v1.
  * Marks [1998] Michael P. Marks.  Using the game of Risk to teach international relations.  _International Studies Notes_ , 23(1):11–18, 1998.  ISSN 00947768.  URL http://www.jstor.org/stable/44235311.
  * Snodgrass and Ontañón [2017] Sam Snodgrass and Santiago Ontañón.  Learning to generate video game maps using markov models.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 9(4):410–422, 2017.  doi: 10.1109/TCIAIG.2016.2623560.
  * Chen and Guy [2020] Tiannan Chen and Stephen Guy.  Chaos cards: Creating novel digital card games through grammatical content generation and meta-based card evaluation.  _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , 16(1):196–202, 2020.  doi: https://doi.org/10.1609/aiide.v16i1.7430.  URL https://ojs.aaai.org/index.php/AIIDE/article/view/7430.
  * Togelius and Schmidhuber [2008] Julian Togelius and Jurgen Schmidhuber.  An experiment in automatic game design.  In _2008 IEEE Symposium On Computational Intelligence and Games, CIG 2008_ , pages 111–118, Perth, Australia, 2008. IEEE.  ISBN 9781424429745.  doi: 10.1109/CIG.2008.5035629.
  * Hom and Marks [2007] Vincent Hom and Joe Marks.  Automatic design of balanced board games.  _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , 3:25–30, 2007.  ISSN 2334-0924.  doi: 10.1609/AIIDE.V3I1.18777.  URL https://ojs.aaai.org/index.php/AIIDE/article/view/18777.
  * Wiklund et al. [2015] Mats Wiklund, William Rudenmalm, Lena Norberg, Thomas Westin, and Peter Mozelius.  Evaluating educational games using facial expression recognition software: measurement of gaming emotion.  In _Proceedings of the European Conference on Games Based Learning_ , pages 605–612, Steinkjer, Norway, 2015. Academic Conferences and Publishing International Limited.
  * Ferrari and Assunção [2022] René Ferrari and Joaquim Assunção.  Towards playing risk with a hybrid Monte Carlo based agent.  In _Anais Estendidos do XXI Simpósio Brasileiro de Jogos e Entretenimento Digital_ , pages 301–306, Porto Alegre, RS, Brasil, 2022. SBC.  doi: 10.5753/sbgames_estendido.2022.225471.  URL https://sol.sbc.org.br/index.php/sbgames_estendido/article/view/23664.
  * Gibson et al. [2010] Richard Gibson, Neesha Desai, and Richard Zhao.  An automated technique for drafting territories in the board game Risk.  _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , 6(1):15–20, 2010.
  * Gaina et al. [2020] Raluca D. Gaina, Martin Balla, Alexander Dockhorn, Raul Montoliu, and Diego Perez-Liebana.  TAG: A Tabletop Games Framework.  In _Experimental AI in Games (EXAG), AIIDE 2020 Workshop_ , Virtual Event, 2020. CEUR Workshop Proceedings.
  * Koza [1994] John R Koza.  Genetic programming as a means for programming computers by natural selection.  _Statistics and computing_ , 4:87–112, 1994.
  * Bombardelli [2022] Leonardo Boaventura Bombardelli.  _Generating variations of the board game risk through evolutionary game design_.  Bachelor’s thesis, Universidade Federal do Rio Grande do Sul, 2022.  URL https://lume.ufrgs.br/handle/10183/252514.
  * Boyer et al. [2003] John M Boyer, Pier Francesco Cortese, Maurizio Patrignani, and Giuseppe Di Battista.  Stop minding your P’s and Q’s: Implementing a fast and simple DFS-based planarity testing and embedding algorithm.  In _International Symposium on Graph Drawing_ , pages 25–36, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
  * Browne [2008] Cameron Browne.  _Automatic Generation and Evaluation of Recombination Games_.  PhD thesis, Queensland University of Technology, 2008.  URL https://eprints.qut.edu.au/17025/1/Cameron_Browne_Thesis.pdf.
  * Cordella et al. [2001] Luigi Pietro Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento, et al.  An improved algorithm for matching large graphs.  In _3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition_ , pages 149–159, Ischia, Italy, 2001. Citeseer.
  * Islam et al. [2007] Md. Monirul Islam, Mohammad Shafiul Alam, and Kazuyuki Murase.  A new recurring multistage evolutionary algorithm for solving problems efficiently.  In Hujun Yin, Peter Tino, Emilio Corchado, Will Byrne, and Xin Yao, editors, _Intelligent Data Engineering and Automated Learning - IDEAL 2007_ , pages 97–106, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.  ISBN 978-3-540-77226-2.

##  Appendix A Evaluation Metrics’ Equations

The evaluation of the board for each player $p$ ($H_{p}$) is a heuristic that
combines the number of territories and troops (Eq. 2). To achieve this,
weights wterr and wunit define the importance of territories and units,
respectively, on the game. Additionally, Tp is player p’s territory count,
Ttotal is the total territory count, Up is player p’s troop count and Utotal
the total troop count.

$H_{p}=\frac{T_{p}}{T_{total}}*w_{terr}+\frac{U_{p}}{U_{total}}*w_{unit}$ (2)

Completion (Ccomp) is calculated based on the number of games won by players 1
or 2, divided by the number of played games $J$ (Eq. 3). The best Ccomp is 1
(there is always a winner).

$C_{comp}=\frac{wins_{1}+wins_{2}}{J}$ (3)

Duration (Cdur on Eq. 4), considers the preferred duration (Dpref) and the
duration of each game $j$ played (Dj) out of $J$ games. The preferred duration
was set as 24, representing 12 turns per player. Cdur can range from 0 (best)
to 1 (worst).

$C_{dur}=\frac{1}{J}\sum_{j=1}^{J}{\frac{|D_{pref}-D_{j}|}{D_{pref}}}$ (4)

Advantage ($C_{adv}$ on Eq. 5) is determined by the win rate of player 1.
$C_{adv}=0.5$ means a balanced game, less or greater than 0.5 implies
disadvantage or advantage for player 1, respectively.

$C_{adv}=\frac{|wins_{1}-(wins_{1}+wins_{2})/2|}{(wins_{1}+wins_{2})/2}$ (5)

The number of possible moves is measured in all three phases of the game: when
the player must add new units (Madd), attack (Mattack), and move their troops
(Mfort). Madd (Eq. 6) is the product of player p’s available units up by its
territory count Tp.

$M_{add}=u_{p}\times T_{p}$ (6)

Mattack is given by Eq. 7. For all player p’s territories Tp, the number of
neighboring enemy territories Tfb(terr) is multiplied by uterr-1 troops, with
3 being the limit.

$M_{attack}=\sum_{terr=1}^{T_{p}}{T_{fb}(terr)\times\min(3,u_{terr}-1)}$ (7)

To calculate Mfort (Eq. 8), for each territory terr of the player, the units
uterr in terr are multiplied by the number of neighboring territories
Tnb(terr) controlled by the player.

$M_{fort}=\sum_{terr=1}^{T_{p}}{T_{nb}(terr)\times(u_{terr}-1)}$ (8)

Then, the branching factor (Cbf) is calculated with Eq. 9, where M(tn) = Madd
\+ Mattack \+ Mfort, and Tj is the total number of turns played on game j. The
log10 component is divided by 2 to set a limit of nearly 100 moves. The best
Cbf is 0.5, meaning 50 moves per turn on average.

$C_{bf}=\frac{1}{J}\sum_{j=1}^{J}\min\left(1,\log_{10}\left(\frac{\sum_{n=0}^{T_{j}-1}M(t_{n})}{T_{j}}+1\right)\Bigg{/}2\right)$

(9)

Drama (Cdra on Eq. 10) considers number of times the winner suffered a
setback. The heuristic evaluation of the winner Hg(tn) the loser Hp(tn) on
turn tn are used. Cdra can range from 0 to 1, with the optimal value being
0.5.

$C_{dra}=\frac{1}{J}\sum_{j=1}^{J}{\left(\frac{\sum\left(H_{g}(t_{n})<H_{p}(t_{n})\left\\{\sqrt{H_{p}(t_{n})-H_{g}(t_{n})}\right\\}\right)}{\text{count}(H_{g}(t_{n})<H_{p}(t_{n}))}\right)}$

(10)

The killer move rate (Ckm) is given by Eq 11. Only the largest difference
between the evaluations of players ($H_{a}$ and $H_{o}$) in subsequent turns
($t$ and $t-1$) is considered for each game j out of $J$ games. Ckm can range
from 0 to 1, with the optimal of 0.5 (moderate amount of extreme moves).

$C_{km}=\frac{1}{J}\sum_{j=1}^{J}\max_{1\leq n\leq
T_{j-1}}[H_{a}(t_{n})-H_{o}(t_{n})]-[H_{a}(t_{n-1})-H_{o}(t_{n-1})]$

(11)

Lead change (Clc on Eq. 12) counts the times of times the leader of the
current turn leader(tn) is different from the previous turn leader(tn-1). Only
non-final turns Tj-1 of all $J$ games are considered. Clc can range from 0 to
1, with the optimal of 0.5 (moderate lead change).

$C_{lc}=\frac{1}{J}\sum_{j=1}^{J}{\left(\frac{\text{count}(leader(t_{n})\neq
leader(t_{n-1}))}{T_{j}-1}\right)}$

(12)