# VSA: Reconfigurable Vectorwise Spiking Neural Network Accelerator

Hong-Han Lien1, Chung-Wei Hsu2, and Tian-Sheuan Chang2, Senior Member, IEEE H.
-H. Lien, C. -W. Hsu and T. -S. Chang, ”VSA: Reconfigurable Vectorwise Spiking
Neural Network Accelerator,” 2021 IEEE International Symposium on Circuits and
Systems (ISCAS), 2021, pp. 1-5, doi: 10.1109/ISCAS51556.2021.9401181. 1AI
Graduate Program, 2Institute of Electronics, Nat’l Chiao Tung Univ., Taiwan

###### Abstract

Spiking neural networks (SNNs) that enable low-power design on edge devices
have recently attracted significant research. However, the temporal
characteristic of SNNs causes high latency, high bandwidth and high energy
consumption for the hardware. In this work, we propose a binary weight spiking
model with IF-based Batch Normalization for small time steps and low hardware
cost when direct training with input encoding layer and spatio-temporal back
propagation (STBP). In addition, we propose a vectorwise hardware accelerator
that is reconfigurable for different models, inference time steps and even
supports the encoding layer to receive multi-bit input. The required memory
bandwidth is further reduced by two-layer fusion mechanism. The implementation
result shows competitive accuracy on the MNIST and CIFAR-10 datasets with only
8 time steps, and achieves power efficiency of 25.9 TOPS/W.

###### Index Terms:

Spiking neural network, deep learning accelerators

##  I Introduction

Artificial neural network (ANN) becomes popular in recent years due to its
excellent performance, but it contains a large amount of data transfer and
complex calculations that is not suitable for resource-constrained battery-
powered mobile devices. Therefore, spiking neural network (SNN), a brain-
inspired computing models, is currently developed as an alternate to ANN since
its binary spikes transmission is relatively simple for hardware
implementation. So far, [1, 2, 3, 4] have demonstrated their application
specific designs enable inference or learning with extremely low power
consumption, but they are limited to small neural network architectures or
simple datasets. Only the large-scale neuromorphic hardware systems such as
TrueNorth [5] and Loihi [6] can perform the large-scale neural network and can
reconfigure. However these modern SNN architectures achieve lower throughput
and higher energy per neuron, compared to ANN accelerators. [7] attribute this
phenomenon to the temporal aspect in SNN that process data across many time
steps. This makes the inference time extremely long and repeatedly accessing
the same data from memory will consume a lot of unnecessary energy. In
addition, a stateful spiking neuron needs to record membrane potential every
time step that will increase off-chip memory transfer, which leads to more
power consumption.

To address above issues, this paper proposes a reconfigurable vectorwise SNN
hardware accelerator that needs small time steps and low hardware cost and
memory bandwidth through model and hardware optimizations. For the SNN model,
this paper integrate the binary neural network (BNN) training method into SNN
to directly train a binary weight spiking model, which minimizes the off-chip
memory transfer and on-chip storage. The first layer is designed to be an
encoding layer [8], which receives multi-bit positive inputs and generate
spikes for the next layer. This can greatly reduces the time steps required
for inference. Furthermore, the proposed integrate and fire (IF)-based Batch
Normalization (BN) reduce BN overhead on hardware. For the hardware part, this
design can reconfigure to support different inference time steps and models,
and also supports the encoding layer to receive multi-bit inputs as well as
spiking layer processing with spike inputs with a vectorwise input format. In
addition, the memory bandwidth is further reduced by tick batching [7] and
layer fusion mechanism. The result shows better performance and implementation
cost compared to other approaches.

##  II Binary Weight Spiking Neural Network

(a) The behavior of IF

(b) IF architecture

Figure 1: IF neuron

###  II-A Spiking Networks

This work adopts spatio-temporal back propagation (STBP) [9] to directly train
the network and replace Leaky Integrate-and-Fire neuron to Integrate-and-Fire
neuron (IF) to reduce hardware cost. Fig. 1(a) shows the behavior of IF
neurons, which includes membrane potential update (Eq. (1)) and spike firing
condition (Eq. (2)).

$\displaystyle V^{l}[t+1]$
$\displaystyle=V^{l}[t](1-o^{l}[t])+w^{l}o^{l-1}[t+1]$ (1) $\displaystyle
o^{l}[t+1]$
$\displaystyle=f(V^{l}[t+1]),f(x)\left\\{\begin{array}[]{lr}1,&x\geq V_{th}\\\
0,&\text{otherwise}.\end{array}\right.$ (4)

where $V^{l}[t]$ denotes the membrane potential at the time step t, $w^{l}$ is
the weights, $o^{l-1}[t+1]$ is the output spike from previous layer at the
time step t+1, f(.) is the firing function and $V_{th}$ is the threshold.
During model inference, neurons receive asynchronous weighted input and
accumulate them into membrane potential. Whenever membrane potential reaches
the threshold, neurons fire an output spike and reset membrane potential.

###  II-B IF-based Batch Normalization

To further minimize off-chip memory transfer and on-chip storage, we further
combining the Binary Neural Networks [10] training method into the above
method to reduce the model weights to (-1,+1). For binary neural network,
batch normalization [11] is a widely mechanism to enable training of the
binary weight networks. However, BN suffers from complex computation and high
hardware cost. To solve this problem, we propose an IF-based BN, which is
inspired by the bias-based BN [12]. The IF-based BN integrates BN into IF
neuron computation by rearranging the membrane potential integration and
threshold in the firing condition from the original formulation as Eq. (3) to
Eq. (4).

$\displaystyle[\gamma(\frac{x[1]-\mu}{\sqrt{\sigma^{2}}})+\beta]+[\gamma(\frac{x[2]-\mu}{\sqrt{\sigma^{2}}})+\beta]+\cdots\geq
V_{th}$ (5)
$\displaystyle\sum_{t=1}^{T}[x[t]-(\mu-\frac{\sigma}{\gamma}\beta)]\geq\frac{\sigma}{\gamma}V_{th}$
(6)

where $\gamma,\beta,\mu,\sigma^{2}$ denote the BN parameters: gamma, beta,
running mean, running variance and x[t] denote convolution output at time step
t . As illustration in Eq. (4), the new formulation just needs to subtract the
convolution output with a new bias $(\mu-\frac{\sigma}{\gamma}\beta)$ and
compare with a new threshold $\frac{\sigma}{\gamma}V_{th}$ to generate the
desired output spike, which reduces the extra hardware BN overhead.

Figure 2: System architecture

##  III Architecture and Data Flow

###  III-A Overview

Fig. 2 shows the proposed system architecture. This design accesses weight and
input from off-chip memory and stores them into weight and spike SRAM buffers.
For the spike ping-pong buffer, one will be accessed at time-step t and the
other will be accessed at time-step t+1. The weight ping-pong buffer stores
different layer’s weight in each buffer. Each PE block processes one channel
of input spike at time step t and each PE array computes one vector of them to
generate the convolutional partial sum. Total 32 PE blocks can process 32
channels of input. The output of PEs will be accumulated by the accumulator to
complete a convolution operation. Then, the IF neurons accumulate membrane
potential and fire output spike accordingly. The result will go through the
post processing if needed. The result will be saved to temp SRAM and then
transferred to off-chip memory. Above process is repeatedly for all time steps
of a layer input spike before moving to the next layer to prevent membrane
potential from being transferred off and back on chip. With this, the weight
data is also reused during the spike processing of all time steps.

Figure 3: PE array

###  III-B PE Blocks

PE block consists of three PE arrays, which is constructed by 8$\times$3 PEs
as shown in Fig. 3. In the figure, eight input spikes broadcast horizontally
and three weights broadcast vertically. They are multiplied using AND gate
then summed up along the diagonal direction. The outputs will be stored in ten
registers individually, which are partial sums of one filter column for one
input channel column.

Both spike (0,1) and weight (-1,+1) are binary value, multiplying them will
get a set of possible multiplication result (-1,0,1). We represent weight
using only one sign bit, so weight -1 is stored as 1 and weight +1 is stored
as 0. As a result, the multiplication result can be simply computed by a logic
equation $o=\left\\{s\&w,s\right\\}$.

Figure 4: Accumulator

###  III-C Accumulator

Fig. 4 shows the accumulator, which is divided to a three-stage pipeline for
shorter critical path. Three vectorwise partial sums of the same channel from
three PE arrays is summed up first, and then the 32 output channels from 32 PE
blocks is summed up with a tree adder that is divided to two partial tree
adders.

If input channel number is larger than 32, they will be further divided to
groups with group size 32 and then each group will be sent to PEs sequentially
for processing. These partial group results are then accumulated at the last
stage of the accumulator to generate the final convolution outputs.
Simultaneously, we will also store the boundary information of a tile into the
boundary SRAM and accumulate them with output from the neighboring tile
afterward.

(a) Data flow chart of a PE block

(b) Data flow Scheduling

Figure 5: (a) Data flow chart for example in Fig. 6. For the I/O part, the
same color blocks corresponds to the same SRAM. For the computation part, the
same color blocks will be summed up as partial sums. (b) Data flow scheduling
expressed by mathematical formulas. Figure 6: A convolution example with
5$\times$5 inputs, 3$\times$3 weights, and 7$\times$3 outputs.

###  III-D Data flow of convolution

Fig. 5(a) shows the data flow of a PE block process on example as shown in
Fig. 6. This case only assume 5$\times$3 PE arrays for clarity. In our data
flow, one column vector of input is broadcasted horizontally along the PE
array row and one column vector of filter weight is broadcasted vertically
along the PE array column. With this data flow, the products along the
diagonal direction will be summed up and then accumulate with other PE arrays’
outputs in the same cycle to generate convolutional results. The bottom
boundary part of outputs (e.g. OA6, OA7) will be stored in the boundary SRAM
to be accumulated with the top boundary part of outputs (e.g. OA1, OA2) of the
neighboring tile afterward. In this schedule, all PEs are activated and
contributed to the results, which achieves full hardware utilization.It is
worth noting that each PE block only accesses one vectorwise input at a time
that efficiently reuse the data.

This vectorwise scheduling can be expressed by mathematical formulas as in
Fig. 5(b) that takes only three cycles to complete the example. This data flow
achieve high parallelism and simple control while maintaining full hardware
utilization.

Figure 7: The mapping example of encoding layer

###  III-E Encoding layer

The first layer of our model is a encoding layer [8] that receives multi-bit
inputs and generates spikes for the following spiking layer. To support the
encoding layer with the same hardware without large overhead, we split the
8-bit inputs to eight 1-bit input bitplanes, and assign each bitplane to one
PE block. Eight bitplanes will takes eight PE blocks. Thus, every eight PEs
block correspond to the same weight. With this, we use the first stage
accumulator that shifts the PE result and sums all these bitplane results to
achieve the multi-bits convolution as shown in Fig. 7.

This mechanism is applicable when the inputs are positive, thus the inputs are
normalized to (0, 1) during training.

###  III-F IF Neuron

Fig. 1(b) shows the architecture of the IF neuron that receives the
convolutional results and accumulate them with the residue membrane potential
stored in SRAM. The accumulated potential is compared with the threshold,
which will fire a spike and reset the membrane potential in the corresponding
position once reaching the threshold.

For the encoding layer, the convolutional results will be stored to the second
membrane SRAM first and then accumulated with the residue potential from the
fist membrane SRAM to continuously generate output of different time steps.

TABLE I: Two network structures on two different datasets. Datasets | Network structure
---|---
MNIST | 64Conv(encoding)-MP2-64Conv-MP2-128fc-10fc
CIFAR-10 |  | 128Conv(encoding)-128Conv-128Conv-MP2-192Conv-
---
192Conv-192Conv-192Conv-MP2-256Conv-256Conv-
256Conv-256Conv-MP2-256fc-10fc

###  III-G Layer fusion for lower memory bandwidth

Due to temporal input nature of SNN and limited on-chip buffer size, a naive
SNN implementation will execute the model layer by layer that stores per layer
output to external memory and load it back for next layer processing. This
will need to save spikes of all time-steps to off-chip memory for consecutive
processing and results in high data access and power consumption. To reduce
this overhead, we adopt the layer fusion [13] that executes two layers
successively inside the chip and then stores output to external. To support
this, we increase the weight SRAM large enough to store the weights of two
layers. The output spikes in temp SRAM won’t be transferred to off-chip memory
and will be directly sent to PE blocks to process the next layer’s
computation. The membrane potential will be stored in the second membrane SRAM
and the output will replace the value in the spike SRAM that just been
processed, then transfer to off-chip memory. Thus, the input and output
transfer reduced by half.

Figure 8: Accuracy comparison between ANN and SNN

##  IV Experimental Results

###  IV-A Network simulation result

Table. I shows two network structures for MNIST and CIFAR-10 datasets to
evaluate accuracy and analyze hardware performance. Fig. 8 shows the accuracy
comparison between full-precision ANN model and binary weight SNN model with
different time steps. Our SNN model can achieve similar accuracy as the ANN
model in short time steps. Table. II compares existing state-of-the-art
results with our model on the CIFAR-10 dataset. Our model has competitive
accuracy but with significant time step reduction and binary weight, which not
only avoids the huge computational cost, but also reduces the off-chip access
amount.

TABLE II: Comparison with the results on CIFAR-10 of other approaches. Model | Precision | Time steps | Accuracy
---|---|---|---
Sengupta et al. [14] | full-precision | 2500 | 91.55%
Wu et al. [8] | full-precision | 12 | 90.53%
Rathi et al. [15] | full-precison | 200 | 92.02%
RMP-SNN [16] | full-precision | 256 | 93.04%
Wang et al. [17] | binary | 100 | 90.19%
Ours | binary | 8 | 90.28%
TABLE III: Performance summary and comparison with other designs.

| This work | SpinalFlow [7] | BW-SNN [4]
---|---|---|---
Technology | 40nm | 28nm | 90nm
Voltage (V) | 0.9 | - | 0.6
Frequency (MHz) | 500 | 200 | 10
Reconfigurable | Yes | Yes | fixed 5-CONV
Precision (bits) | binary | 8 fixed | binary
PE number | 2304 | 128 | 8208
SRAM (KB) | 230.3125 | 585 | 12.75
Peak Throught (GOPS) | 2304 | 51.2 | 64.46
Area (KGE) (logic only) | 114.98 | - | 225
Area eff. (GOPS/KGE) |  | 20.038
---
11footnotemark: 120.038
- |  | 0.286
---
11footnotemark: 10.644
Core power (mW) | 88.968 | 162.4 | 0.625
Power eff. (TOPS/W) |  | 25.9
---
22footnotemark: 225.9
| 0.315
---
-
| 103.14
---
22footnotemark: 2103.14

11footnotemark: 1

Normalized area efficiency that is scaled to 40nm

22footnotemark: 2

Normalized power efficiency that is scaled to 40nm and 0.9V

###  IV-B Hardware analysis

Table. III shows the performance summary and comparison with other SNN
designs. This design is synthesized with TSMC 40nm library using the Synopsys
Design Compiler, achieving peak 2304 GOPS at 500MHz and consumes 88.968 mW for
CIFAR-10. The DRAM access amount is reduced from 1450.172 KB to 938.172 KB
with layer fusion, a total reduction of $35.3\%$. Compared to the other
reconfigurable design [7], they have lower throughput and power efficiency due
to their element wise sparse processing. [4] is a dedicated five layers SNN
ASIC, and thus achieves lower power by eliminating number of memory accesses.
But that design cannot be reconfigured for other models and have very low
logic area efficiency.

##  V Conclusion

In this paper, we integrate the proposed IF-based Batch Normalization into the
binary weight spiking neural network to reduce the hardware cost. Our model
achieve $90.28\%$ accuracy on CIFAR-10 using only 8 time steps. In addition,
the proposed reconfigurable vectorwise accelerator can handle the different
models at will, and supports the multi-bit input encoding layer and layer
fusion mechanism according to the configuration. Our design can operate at
25.9 TOPS/W under peak efficiency with better power and area efficiency than
the previous reconfigurable design and higher flexibility than the fixed
network design.

## Acknowledgment

This work was supported in part by the Ministry of Science and Technology,
Taiwan, under Grant 109-2634-F-009-022.

## References

  * [1] S. Yin, S. K. Venkataramanaiah, G. K. Chen, R. Krishnamurthy, Y. Cao, C. Chakrabarti, and J.-s. Seo, “Algorithm and hardware design of discrete-time spiking neural networks based on back propagation with binary activations,” in _2017 IEEE Biomedical Circuits and Systems Conference (BioCAS)_. IEEE, 2017, pp. 1–5.
  * [2] C. Frenkel, J.-D. Legat, and D. Bol, “Morphic: A 65-nm 738k-synapse/mm2 quad-core binary-weight digital neuromorphic processor with stochastic spike-driven online learning,” _IEEE Transactions on Biomedical Circuits and Systems_ , vol. 13, no. 5, pp. 999–1010, 2019.
  * [3] J. Park, J. Lee, and D. Jeon, “A 65nm 236.5 nj/classification neuromorphic processor with 7.5% energy overhead on-chip learning using direct spike-only feedback,” in _2019 IEEE International Solid-State Circuits Conference-(ISSCC)_. IEEE, 2019, pp. 140–142.
  * [4] P.-Y. Chuang, P.-Y. Tan, C.-W. Wu, and J.-M. Lu, “A 90nm 103.14 tops/w binary-weight spiking neural network cmos asic for real-time object classification,” in _2020 57th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2020, pp. 1–6.
  * [5] F. Akopyan, J. Sawada, A. Cassidy, R. Alvarez-Icaza, J. Arthur, P. Merolla, N. Imam, Y. Nakamura, P. Datta, G.-J. Nam _et al._ , “Truenorth: Design and tool flow of a 65 mw 1 million neuron programmable neurosynaptic chip,” _IEEE transactions on computer-aided design of integrated circuits and systems_ , vol. 34, no. 10, pp. 1537–1557, 2015.
  * [6] M. Davies, N. Srinivasa, T.-H. Lin, G. Chinya, Y. Cao, S. H. Choday, G. Dimou, P. Joshi, N. Imam, S. Jain _et al._ , “Loihi: A neuromorphic manycore processor with on-chip learning,” _IEEE Micro_ , vol. 38, no. 1, pp. 82–99, 2018.
  * [7] S. Narayanan, K. Taht, R. Balasubramonian, E. Giacomin, and P.-E. Gaillardon, “Spinalflow: an architecture and dataflow tailored for spiking neural networks,” in _2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 2020, pp. 349–362.
  * [8] Y. Wu, L. Deng, G. Li, J. Zhu, Y. Xie, and L. Shi, “Direct training for spiking neural networks: Faster, larger, better,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 1311–1318.
  * [9] Y. Wu, L. Deng, G. Li, J. Zhu, and L. Shi, “Spatio-temporal backpropagation for training high-performance spiking neural networks,” _Frontiers in neuroscience_ , vol. 12, p. 331, 2018.
  * [10] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio, “Binarized neural networks,” in _Advances in neural information processing systems_ , 2016, pp. 4107–4115.
  * [11] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” _arXiv preprint arXiv:1502.03167_ , 2015.
  * [12] H. Yonekawa and H. Nakahara, “On-chip memory based binarized convolutional deep neural network applying batch normalization free technique on an fpga,” in _2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)_. IEEE, 2017, pp. 98–105.
  * [13] M. Alwani, H. Chen, M. Ferdman, and P. Milder, “Fused-layer cnn accelerators,” in _2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2016, pp. 1–12.
  * [14] A. Sengupta, Y. Ye, R. Wang, C. Liu, and K. Roy, “Going deeper in spiking neural networks: Vgg and residual architectures,” _Frontiers in neuroscience_ , vol. 13, p. 95, 2019.
  * [15] N. Rathi, G. Srinivasan, P. Panda, and K. Roy, “Enabling deep spiking neural networks with hybrid conversion and spike timing dependent backpropagation,” _arXiv preprint arXiv:2005.01807_ , 2020.
  * [16] B. Han, G. Srinivasan, and K. Roy, “Rmp-snn: Residual membrane potential neuron for enabling deeper high-accuracy and low-latency spiking neural network,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 13 558–13 567.
  * [17] Y. Wang, Y. Xu, R. Yan, and H. Tang, “Deep spiking neural networks with binary weights for object recognition,” _IEEE Transactions on Cognitive and Developmental Systems_ , 2020.


# Quality Diversity in the Amorphous Fortress (QD-AF):
Evolving for Complexity in 0-Player Games

Sam Earle
Game Innovation Lab
New York University
Brooklyn, NY
<EMAIL_ADDRESS>
M Charity
Game Innovation Lab
New York University
Brooklyn, NY
<EMAIL_ADDRESS>
Dipika Rajesh
Independent Researcher
Chennai, India
<EMAIL_ADDRESS>Mayu Wilson
Independent Researcher
Brooklyn, NY
<EMAIL_ADDRESS>Julian Togelius
Game Innovation Lab
New York University
Brooklyn, NY
<EMAIL_ADDRESS>

###### Abstract

We explore the generation of diverse environments using the Amorphous Fortress
(AF) simulation framework. AF defines a set of Finite State Machine (FSM)
nodes and edges that can be recombined to control the behavior of agents in
the ‘fortress’ grid-world. The behaviors and conditions of the agents within
the framework are designed to capture the common building blocks of multi-
agent artificial life and reinforcement learning environments. Using quality
diversity evolutionary search, we generate diverse sets of environments. These
environments exhibit certain types of complexity according to measures of
agents’ FSM architectures and activations, and collective behaviors. Our
approach, Quality Diversity in Amorphous Fortress (QD-AF) generates families
of 0-player games akin to simplistic ecological models, and we identify the
emergence of both competitive and co-operative multi-agent and multi-species
survival dynamics. We argue that these generated worlds can collectively serve
as training and testing grounds for learning algorithms.

##  1 Introduction

Games with certain open-ended characteristics, such as sandbox simulation,
management, or multiplayer games, provide promising testbeds for learning
agents (Earle et al., 2021; Fan et al., 2022; Suarez et al., 2021). Such games
allow for a range of potentially interesting interactions between systems and
agents, often leading to emergent phenomena unforeseen by developers
(Guttenberg and Soros, 2023).

Amorphous Fortress (Charity et al., 2023) is a simulation framework that uses
finite-state machines (FSMs) to produce emergent AI behaviors. Drawing
inspiration from games such as Dwarf Fortress and Rogue, AF defines a base
reality consisting of a fortress, where multiple instances of FSM agents
interact with each other. The agents in the fortress can perform abstract
behaviors and interactions such as hunting, transforming, and reproduction,
and these behaviors are triggered by temporal or spatial conditions dependent
upon the agent’s state (Figure 1). We define a single fortress as containing a
set of FSMs (one for each entity class), and a level topology (initial entity
instances and coordinates).

Prior work discusses some of the non-trivial multi-agent dynamics that emerge
when fortresses are optimized by a simple hill-climber algorithm for both the
size of agent FSMs and the degree to which they are explored over the course
of a simulation (Charity et al., 2023). Fortresses are observed in which
symbiotic relationships exist between entities; where entity classes with both
large and small FSM graphs are integral to the fitness in the fortress.
Despite the simplicity of the hillclimber, a variety of entity classes emerge,
with diverse policies of agent behavior that depend on one another for deeper
exploration of their own graphs.

Figure 1: Left: example of a random fortress generated in the Amorphous
Fortress framework. The fortress environment contains many instances of
different entity class types. Right: An example entity class FSM definition.
This FSM defines the action behavior an instance agent of this class can take
within the fortress under the right conditions. Here, the agent is capable of
random movement as well as ‘chasing’ (moving along a path toward) and ‘taking’
(removing from the fortress) an instance of the $ entity class.

We extend this earlier work by optimizing both quality and diversity using
metrics reflecting agent behavior and interaction. We implement the quality
diversity (QD) algorithm MAP-Elites to illuminate an archive of Amorphous
Fortress fortress environments. Diversity is maintained by grouping fortresses
by behavior characteristics (BCs), and only having fortresses compete against
others with similar BCs. These BCs are measured based on the agent action
space class definitions and the ending state of the fortress after simulation.
Quality of the fortresses is optimized by evaluating what proportion of each
entity class’s finite-state machine was explored (collectively, over all
instances of the entity class) during simulation. We use these metrics to
generate collections of fortresses that exhibit a range of specific behaviors
during simulation.

QD-AF is an unsupervised approach for generating environments that are
distinct from one another, with non-trivial and controllable simulation
dynamics. The diversity and complexity of environments generated by QD-AF
makes them an ideal candidate for serving as a general testbed for evaluating
RL agents.

##  2 Background and related work

This extension of the Amorphous Fortress system emphasizes the themes of
multi-agent open-ended environments and QD algorithms. The following
subsections describes each theme in more detail along with previous works
related to the experiments in this paper.

###  2.1 Open-ended learning environments

Simulation environments allow researchers to emulate real world events and
phenomena in a controlled test framework. Open-ended simulation environments
and environments that promote artificial life offer a multitude of challenges
and emergent scenarios for AI to solve (Bedau et al., 2000; Stanley et al.,
2017). Examples of simulation environments have previously been studied by
game AI researchers for developing both the artificial agents and the
environments themselves. Charity et al. (2020) and Green et al. (2021)
introduce minimal simulations of The Sims and RollerCoaster Tycoon
environments respectively to generate novel and diverse layouts based on the
game environment. Similarly, Earle (2020) introduces a training environment in
the game SimCity and examines population behaviors of cellular automata in
Conway’s Game of Life (GoL). To better understand the role of players in game
design, Björk and Juul (2012) discuss 0-player games, in which the player
interacts with the game either in some highly constrained and atypical fashion
or not at all. They describe GoL as a “setup-only” 0-player game, in which the
player is only able to interact with the system prior to the simulation. In
this light, QD-AF can be seen as optimizing the setup of such a 0-player game,
with a QD algorithm used in place of a human player to search for mechanics
and level topologies that produce interesting simulation rollouts in AF.

Minecraft has been a popular environment for open-ended reinforcement learning
tasks. Fan et al. (2022) provide and train agents on a large set of RL
tasks—some generated by humans, others the result of few-shot prompting an LLM
for similar tasks. Zhang et al. (2023) use human notions of interestingness in
conjunction with Large Language Models to explore and facilitate open-ended
learning. Wang et al. (2023) automatically prompt an LLM for new and
interesting tasks given a player’s progress, where the player is a similar
LLM, interfacing with the game via a collection of programs defining player
behavior, which it generates and may re-use over the course of play. In a
parallel line of work focused on environment generation, Evocraft Grbic et al.
(2021) is proposed as a framework for open-ended research in creating
structures and systems with various functional or aesthetic ends using the
game’s set of blocks (which include musical note generators and“redstone”
circuits), as demonstrated by Sudhakaran et al. (2021). While AF is a much
simpler framework than Minecraft, its approach to evolving populations of FSMs
could be adapted for the generation complex multi-agent dynamics in Minecraft.
Conversely, AF could be extended to involve non-agentic objects (analogous to
Minecraft blocks) serving as (possibly destructible) obstacles or resources.

Languages like Griddly (Bamford, 2021), VGDL (Schaul, 2013), and PuzzleScript
(Lavelle, 2013) provide domain-specific languages for describing game-like
environments for reinforcement learning (RL), search and planning algorithms,
or human play. Such systems are sometimes accompanied by web frameworks
allowing users to edit and upload their own maps (Bamford et al., 2022). The
trajectory of such databases over time (e.g. where RL agents learn on a
growing number of human-designed maps) can be seen as human-in-the-loop open-
ended artificial learning processes, reminiscent of PicBreeder (Secretan et
al., 2008), where users collaboratively evolved small networks encoding
images. Amorphous Fortress would make an ideal candidate framework for such an
online open-ended loop, allowing users to assign meaning via recombination of
abstract, atomic mechanics and map layouts.

###  2.2 Multi-agent interactions

In some open-ended environments, multiple decision-making agents interact with
each other co-operatively or competitively to achieve their common or opposing
objectives. Deshpande and Magerko (2021) introduce a web
application—Drawcto—which uses multiple agents that are capable of co-creating
interpretive open-ended artwork with human collaborators. Neural MMO (Suarez
et al., 2021), is a platform for multi-agent RL over large agent populations
in procedurally generated virtual maps. Lowe et al. (2017) introduce a method
that successfully learns RL policies that require complex multi-agent co-
operation and coordination. In the framework proposed by Grbic et al. (2021),
an example is given in which a human user interacts with an evolutionary
algorithm to co-operatively generate complex block structures inspired by
Minecraft.

Moreover, the diverse interactions among these multiple agents could give rise
to interesting emergent behavior within the given context. Work by Bansal et
al. (2018) and Baker et al. (2019) introduces the simulation of diverse
environments, where multiple agents engage with each other competitively,
leading to the rise of intricate and complex emergent behaviors. Such emergent
behaviors include offensive and defensive game playing strategies like
blocking and kicking (Bansal et al., 2018) or object manipulation within the
environment such as “box-surfing” and building barricades (Baker et al.,
2019). We employ multi-agent interactions to enhance the diverse and
interesting emergent behavior of different entity class types within the
fortress environment.

###  2.3 Quality diversity algorithms

Evolutionary algorithms are gradient-free optimization methods that randomly
mutate pools of individuals to maximize a computable objective function
(Russell and Norvig, 2010). Novelty search, an extension of evolutionary
algorithms, replaces the objective function with a measure of an individual
sample’s phenotypic/behavioral distance from the existing archive of
discovered individuals, in effect uniform randomly sampling the search space
(Doncieux et al., 2019), often achieving the (held-out) objective given a
sufficiently informative behavior distance metric. Novely search has been used
to generate diverse game AI components such as video game levels (Beukman et
al., 2022) and dungeons (Melotti and de Moraes, 2018). The novelty search
algorithm has served as a precursor to another derivative of evolutionary
algorithms known as Quality Diversity (QD) algorithms. These algorithnms are
designed to maintain diversity while optimizing quality among a population of
individuals.

The QD algorithm Multi-dimensional Archive of Phenotypic Elites (MAP-Elites)
(Mouret and Clune, 2015) optimizes for a fixed objective while tessellating a
behavioral search space and preventing competition between elites in different
cells. MAP-Elites has been used to generate teams of agents for automated
gameplaying (Guerrero-Romero and Perez-Liebana, 2021). MAP-Elites has also
been used to create, replicate and explore real-world adaptability by
simulated agents in virtual open-ended environment as studied by Norstein et
al. (2022). Pierrot and Flajolet (2023) evolve repertoires of full agents to
combine any RL algorithm with MAP-Elites to dynamically learn the
hyperparameters of the RL agent. This approach not only alleviates the user’s
workload but also enhances performance in the evaluated environments. In this
work, we use MAP-Elites to generate the multiple finite-state machine agents
that would be ideal use case environments for training agent learning models.

###  2.4 Unsupervised environment design

Existing work in Unsupervised Environment Design (UED) uses feedback from RL
player-agents to incentivize the generation of novel game environments (which
is in turn cast as an evolutionary or RL optimization problem) (Parker-Holder
et al., 2022; Jiang et al., 2021; Dennis et al., 2020; Wang et al., 2020),
with recent extension to multiplayer games (Samvelyan et al., 2023). In UED,
the objective of the environment generation and curation processes is some
proxy for the learnability or relevance of new environments to the RL player,
and the player is found to be more robust when trained in such a setting as
opposed to domain randomization. Elsewhere, RL and QD have been applied to a
variety of level-generation problems, where domain-specific heuristics or
fixed, search-based agents can be used to condition the goals of the generator
(Khalifa et al., 2020; Earle et al., 2022). In QD-AF, environments are
populated with FSM-based player agents, and these players and their
environments (i.e. the initial fortress topologies) are jointly optimized for
metrics of complexity based on agent interaction. Our hope is that these
metrics will serve as meaningful proxies for the generation of an initial set
of learning environments which can ultimately be used to jump-start a UED
process with online RL player agents.

##  3 Amorphous Fortress 1.0 framework

The Amorphous Fortress framework, developed by Charity et al. (2023), is an
artificial life simulation system has a hierarchy of 3 components: entities
(the agent class of the system) the fortress object (the environment class of
the system) and the engine (the “manager” and main loop of the simulation).
Each entity of the Amorphous Fortress is defined by a singular ASCII
character, a unique 4-bit identification hex number and a finite-state machine
(FSM) specifying its behavior during simulation. The finite-state machine
entity class definition is made up of a list of nodes and a set of edges. Each
node in the FSM graph represents a potential action state an entity instance
can be in. These actions define how an instance interacts with the
environment. The edges define when an instance of the entity class can change
states to another node and is dependent and prioritized based on conditions
found during simulation. Table 1 shows the possible action nodes and Table 2
shows the possible conditional edges that can define an entity class for the
Amorphous Fortress 1.0 System. At any time during the simulation, the entity
is always in a state at one of the set nodes. At each timestep—a single update
within the fortress environment—each connection is evaluated to move to the
connecting node state based on whether the conditions are met, in order of
priority defined internally. The agent will perform the action at its new
current node on the next timestep.

The fortress of the Amorphous Fortress contains the environment where the
simulation takes place and stores general information accessible to all of the
entities in the fortress. The borders and size of the fortress are defined
initially with a set character width $w$ and height $h$ to enclose the
entities. On initialization, the fortress generates each entity class FSM for
each character defined at the start of the simulation. This global dictionary
of entity classes allows any instance of an entity to add or transform
different entity instances even if none exist on the map at initialization.
The fortress maintains a list of currently active entity instances in the
simulation and adds or removes them by their ID value. The fortress also
maintains positional data about each entity to return for conditional checks
(i.e. whether a particular position has an instance of an entity class located
there.) The engine of the Amorphous Fortress system maintains the execution of
the simulation and exports any log files or entity class data information such
as the node and edges definitions. In this experiment, the fortress area
itself where the entities interact is 15 spaces wide by 8 spaces
tall—including the walls—allowing for a total traversable area of 78 tiles.
Each fortress contains 15 entity classes, where each class can have a minimum
of 1 action node and a maximum of 94 action nodes.

As an update from this first Amorphous Fortress framework, the push action
node was modified to include an entity character target. The move_wall action
node is also an addition from the previous iteration of the Amorphous Fortress
system.

##  4 Methods

###  4.1 MAP-Elites for Amorphous Fortress

We implement the MAP-Elites QD algorithm (Mouret and Clune, 2015) to evolve
multiple entity classes towards a diversity of emergent behaviors. MAP-Elites
evaluates a population of samples based on a fitness function while
maintaining a grid of these samples and organizing them based on pre-defined
Behavior Characteristics (BCs) exhibited during evaluation to maintain both
quality and diversity of generated individuals. The emergent behaviors of the
entities defined within this system are dependent upon interactions with other
instances within the same fortress. Therefore a single cell of the MAP-Elites
grid contains a fortress with a set of entity class definitions. Figure 2
illustrates a small example of the evolution and evaluation process as the
fortresses are placed in the MAP-Elites archive for the experiment (described
in more detail later in this section).

Figure 2: QD-AF uses MAP-Elites to iterate on an archive of elites
differentiated in terms of the size of their FSMs, and the mean number of
surviving instances in the fortress after simulation. Fortresses in the same
part of the archive compete to maximize the overall proportion of agent FSMs
explored during simulation.

#### Behavior Characteristics

We use the following BCs: a) the mean number of total instances in the
fortress at the end of the simulation and b) the mean number of total nodes
across all entity class definitions.

Behavior characteristic (a), based on the average number of entity instances
surviving in the fortress over the course of a set of simulation episodes
(with different random seeds), is intended to explore the population dynamics
within fortresses. That is, we seek fortresses in which the entity class
combinations result in an overpopulation of entity instances, an extinction of
all instances, or a stability or “equilibrium” of instances within the
fortress. The values of this dimension can range from 0 to 156—the maximum
number of instances allowed to exist in the fortress before it terminates
based on an “overpopulation” condition.

Behavior characteristic (b), based on the collective class FSM size, looks to
examine the complexity and depth of the entity classes; whether the combined
set includes a majority of simple entity class definitions with only 1 action
node or conversely with extremely large entity class definitions. The values
of this dimension can range from 15 nodes—where each of the entity classes has
only 1 node—to 1410 nodes ($max\\_num\\_nodes=[(6\times n)+4]\times n$ where
$n$ is the number of entity classes in the fortress, with $n=15$ in our
experiments)—where each possible node is included every entity class FSM
definition. The exploration of this dimension by the MAP-Elites algorithm will
demonstrate the growth and utility of varying sized entity class FSMs.

#### Mutation

A fortress individual in the population is mutated by modifying its genotype:
the class level definitions of the FSMs. As in Charity et al. (2023), where
separate coin-flip probabilities determine whether a node, edge, and/or entity
instance in the fortress itself is added, removed, or altered. Here, the node
mutation is adjusted to increase exploration within the grid. A random range
of nodes can be added, removed, or altered into another action node definition
during a single step of mutation. For example, 10 nodes can be added to one
entity class definition, while 4 are removed from another (or the same if
randomly chosen again). Algorithm 1 shows a pseudocode algorithm for the
mutation process of the evolution.

In our experiments, for every $9$ mutated individuals, a random fortress is
added to the offspring pool to encourage exploration within the MAP-Elites
grid and to prevent the algorithm from reaching a local minimum during
evolution. On initialization, all 15 of the entity class FSMs are randomly
generated for each fortress.

We randomly initialize fortresses so as to sample uniformly along the axis
measuring number of aggregate FSM nodes. We first uniformly sample this
aggregate number, then split it into as many summands as there are entity
types using an evenly weighted multinomial distribution, where each summand
corresponds to the number of nodes to be assigned a given entity. It is
possible in this setting for an entity type to be assigned more nodes than
there are distinct node types; in this case, we (greedily) re-assign the
surplus nodes to one or more non-overfilled entity classes, until no surplus
nodes remain.

#### Fitness

The fortress is simulated for 100 steps, where each instance of an entity
class present in the fortress enacts the current action node of its FSM graph
once per step and then evaluates the next action node to move to based on the
state conditions it ends in. The fitness $f\in[0,1]$ of a fortress is given by
$f=e/t$. $t$ is the total number of nodes and edges in the set of entity FSMs,
and $e$ counts the number of explored nodes and edges across entity FSMs—those
that were activated at least once over the course of simulation. The fitness
function is similar to the hill-climber experiment from the original Amorphous
Fortress work, which is based on the average proportion of nodes and edges
that have been explored, i.e., the percentage of nodes over the whole entity
class activated during simulation by all instances of said class. inline]cut
this sentence or split into 2 This fitness definition encourages each class
entity to explore the full possibility of its emergent behaviors demonstrated
within the simulation. The final exploration of a class definition’s nodes and
edges are also aggregated over evaluation trials in case different behaviors
occur due to different seed evaluations. inline]specify fitness—FSM activation

#### Entropy of FSM definitions

Given an archive of fortresses—optimized to maximize FSM exploration while
diversifying along number of surviving entity instances and number of total
FSM nodes—we additionally investigate the distribution of total FSM nodes
among entity classes. More specifically, we define a handful of FSM size
buckets, and measure the entropy of the distribution of entity class FSMs
among these buckets (Figure 5(b)). The entropy of the FSM size distribution is
necessarily minimal at the extremes along the axis measuring number of nodes:
only a set of minimum/maximum size FSMs can sum to a minimum/maximum number of
total FSM nodes, where in either case, all FSMs must have the same size
(falling into to the same FSM size bucket and minimizing distributional
entropy). The values of this dimension range from 0 to 1, with 0 meaning all
of the entity class FSMs have the same number of nodes and no variation, and 1
meaning the number of nodes are different for each entity class FSM
definition. We use Shannon Entropy to calculate the entropic value of the FSM
sizes with a $b$ base $N$ where $N$ is the number of FSM size bins (which for
this experiment is equal to the number of entity classes). inline]set number
of size buckets the same as entity classes inline]maybe describe that the
shannon entropy represents bits of info needed to encode a thing inline]the
base change is an implementation detail that we use to get our values between
0 and 1

Figure 3 shows how the BCs, fitness value, and entropy value are calculated
for any given fortress.

Figure 3: Diagram of the calculations for MAP-Elites BCs, fitness values, and
entropy value. Our BCs involve counting the number

###  4.2 Experiment setup

Using the fitness function, AF mutation operators, and AF initialization
schemes described above, we use MAP-Elites to iterate on an archive of AF
samples, evaluating them to determine fitness measures and characteristics,
sorting them into their respective MAP-Elites grid cells, re-sampling from the
archive to create the new population of samples and repeating for a set number
of generations. We set the number of entity classes to 15, evaluate these
fortresses across 5 randomly chosen seeds, and evolve the populations for
10,000 generations.

###  4.3 Considerations for injecting learning agents into the fortress

We envision fortresses as potential training grounds for learning agents.
Though the joint optimization of entities and maps toward complex 0-player
rollouts is worth studying on its own merits—and in one sense, the agents in
QD-AF might be seen as learning (via evolution) to cooperatively maximize
complexity metrics—we believe the fortress environment would be an ideal
testbed for Multi-Agent Reinforcement Learning.

As an intermediary step, we can imagine training a predictive model or binary
classifier to generate or identify possible completions in a series of frames
from a sequence rollout. We expect that fortresses exhibiting more complex
behavior could take more time and/or network capacity to learn with high
precision. These discrepancies could be used as a more general and principled
complexity metric—albeit one that is very expensive to compute—which could be
used to validate the cheaper, domain specific FSM-based complexity measures
explored here. Such a measure of neural predictability or compressibility
would also likely be indicative of the level of challenge a particular
fortress would present to an RL agent assigned to control one or a set of
agents within the fortress, in an embodied fashion. This is because an agent
having to deal with the activity within the fortress will most likely have to
(at least partially) model the behavior of the other entities within it.

To inject an RL agent into a fortress, we would perform an analysis of its
FSMs and of the results of several simulated rollouts to generate plausible
tasks for the agent. Selecting one entity type over which to give the RL agent
control, we would allow the RL controller determine the low-level
movement/directional actions that would normally be automatically generated by
move, chase, and push nodes, whenever these nodes are active in an entity
instance’s FSM. We would still allow non-navigational nodes such as
‘transform’ or ‘take’ to become active should the relevant edges be triggered,
so that the original action space of the entity remains unchanged. We would
take note of entity populations showing variance over the course of multiple
rollouts, the implication being that the RL controller should be able to
affect the ultimate population size by executing careful low-level movement.
We could then reward the RL agent for simulations that approach certain
population targets, with targets further away from the mean population values
during random rollouts constituting more challenging tasks.

##  5 Results

(a) Archive of fortresses discovered by QD. Behavior characteristics are the
number of instances at the end of the simulation vs. total number of nodes.
The graph on the left shows the heatmap with respect to the fitness
measurement—the proportion of FSMs explored in the fortresses. Naturally, FSMs
with fewer nodes (left) are more easily explored. The graph on the right shows
the same archive of fortresses, with heat denoting the entropy of FSM sizes
within each fortress.

(b) Intra-fortress population. For select fortresses in the archive, we
measure the number of instances over time, across entity types. The vertical
dashed blue line is the number of iterations the fortress was simulated for
during evolution. The cell with the highest entropy of entity class
definitions achieves an ecological equilibrium. This behavior is distinct from
the extremes of the archive, which either overpopulate or rarely add any
additional entities.

Figure 4: Exploring complexity of agent FSMs and inter-agent-type population
dynamics in archives of fortresses evolved to optimize FSM exploration
(avoiding unneeded nodes/edges) while exploring along axes of mean FSM size
and overall agent population after simulation.

Figure 5(a) a heatmap of fitness over individuals in the MAP-Elites archive
(where color indicates fitness). Nearly every possible grid cell is filled for
this experiment. Fortresses with fewer total nodes have the highest fitness
values in the grid—most likely because it becomes increasingly challenging to
explore different nodes in larger FSM graphs. Predictably, many fortresses
recording a large number of surviving entity instances at the end of an
episode were terminated early due to overpopulation. The number of total
surviving entity instances does not seem to be limited by the total number of
nodes, with fortress environments with varying FSM sizes leading to either
extremes of near extinction (0-1 instances) or overpopulation (156 instances)
and various states of equilibrium in between.

#### Measuring entropy

Higher entropy FSM size distributions appear in the subsection of the axis
containing fortresses with medium-high numbers of nodes. It is possible that
more variably-sized sets of FSMs could be beneficial for maximizing fitness
(in terms of FSM exploration during simulation), which might explain their
prominence in this section of the archive. This prominence is striking given
the evenly-weighted multinomial distribution used to distribute FSM nodes
among entity classes from a fixed number of aggregate number of FSM nodes,
which normally lead to low-entropy FSM size distributions (because each FSM is
likely to be assigned roughly equal numbers of nodes). On the other hand,
fitness in this section of the archive is low, such that it may be unlikely
very much such selection pressure has been applied, making further analysis
necessary to come to form conclusions along these lines.

##  6 Discussion

Our results show promise in generating a diverse set of environments for
learning agents. Our fitness function emphasizes environments in which
entities exhibit a diversity of behaviors (i.e. explore as many nodes in their
constituent FSMs as possible). By combining this objective with behavior
characteristics measuring the overall size of FSMs (via number of nodes), we
seek to generate a set of environments that may act as a curriculum for a
future embodied learning agent, which would have to navigate and perhaps
(indirectly) model the varyingly complex behavioral policies governing the
activity of NPCs in the fortress.

After the QD search process, we additionally evaluate the diversity of the
entity classes within each fortress, measured as the entropy over the
distribution of entity class FSM sizes. We note that high entropy—exhibited in
a large swath of the archive with a medium-high number of nodes—corresponds to
sets of entities with variably sized FSMs. When such individuals are fit (and
FSMs have few ineffective nodes/edges), we have some indication that different
types of entities will exhibit diverse behavior. In this case, a hypothetical
learning agent will be forced to adapt to a diversity of behavior profiles,
increasing the richness of its task.

We observed an interesting phenomena within the MAP-Elites cells concerning
the population numbers of each of the entities. Ideally, we were aiming to
find fortresses with balanced interactions between entities. The cells found
at the extreme points of the archive (i.e. cells with lowest and highest
possible behavior characteristics) exhibited uncooperative behavior between
the instances. Fortresses with lower instance numbers refused to populate and
caused a stagnation in the fortress. Conversely, fortresses with higher
instance numbers quickly overpopulated. However, fortress individuals found in
the middle of the archive had more “equilibrium” and cooperation. The fortress
in the exact middle of the archive achieved much more diversity in terms of
the entity class population; some entity classes having a sudden growth in
instance number before dying off, while others slowly expanded their presence
over time. This “equilibrium” was most noticeable in the fortress individual
that demonstrated the highest entropy between entity class FSM sizes. This
fortress showed a near perfect balance between all entity classes; neither
dominating nor diminishing in numbers. The entities found in this fortress
find a “harmony” of co-existence where the ecosystem does not find itself in
danger of overpopulation nor extinction. From this, we can conclude that
having a diversity of entity class sizes leads to better balance of entity
populations and allows for more exploration of co-operative class behaviors.

The main weakness of our results is the generally low fitness, which indicates
that much of the larger FSMs generated by our system could be pruned to
drastically smaller size without having any effect on environment dynamics. We
hypothesize that this lack of FSM exploration is the result of limited compute
resources. In particular, $100$ steps of simulation is not likely enough to
explore FSMs with up to $94$ nodes. Or, the small map size of generated
environments may make prohibit more interesting large-scale dynamics. We
observe the QD score to still be rising steadily after 10k iterations, such
that further evolution would be beneficial. Qualitatively, we see that certain
fortresses in the archive maintain varying equilibria between entity types
over long time horizons, potentially showing how to optimize for environments
facilitating novel dynamics for lifelong learning agents.

##  7 Future work

From the engineering side, the fortress engine could likely be drastically
accelerated if it was implemented in a batched, GPU-compatible manner, similar
to the recent trend in RL environments which has allowed for orders of
magnitude increases in simulation speed (Lange, 2023; Freeman et al., 2021).

Future work could explore adding BCs to control specific aspects of agent
behavior. For example, one archive dimension could measure how many times the
“take” node is enacted by entities could encourage the evolution of fortresses
with more or less aggressive entities. We would also like to examine the
compressibility (e.g. via a simple gzip algorithm) or predictability (e.g. by
a a neural network trained with supervised learning) of environment rollouts
generated by a given fortress definition. We expect that such measures will
provide a reasonable estimate of a hypothetical learning agent’s ability to
model and/or adapt its behavior to a given fortress (Gomez et al., 2009), and
could thus be used to validate the effectiveness of our FSM-based complexity
metrics (themselves being cheaper to compute) and/or supplant them (if
necessary).

A different line of future work—emphasizing the QD-AF paradigm as a design
tool in its own right—will involve developing a mixed-initiative online system
in which users are free to design their own fortresses and entity class
definitions. The MAP-Elites fortress illumination process could create “casts”
of generated characters for the user to include, acting as a recommendation
engine. These generated entity classes would be selected to highlight and
enhance the potential behaviors singular “main character” entity within the
fortress (e.g. by leading to particular activity in the main character’s FSM).
Future systems could then augment QD-AF with learned models of human
preference and style gathered consensually via such an interface. Users could
even be invited to narrativize the emergent dynamics of fortresses in natural
language, opening the door for training models converting human narrative and
first-hand experience into environments—with real stakes and incentives beyond
next-token prediction—for learning agents.

##  8 Conclusion

We use quality diversity evolutionary search to create an archive of grid-
world environments using the mechanics of Amorphous Fortress, with an eye
toward generating diverse training sets for learning agents. By searching for
diverse fortresses in terms of number of surviving entities at the end of a
simulation, we guarantee that a hypothetical learning agent will be exposed to
a variety of environment states. In the archives generated by QD search, we
find a large swath of environments which avoid extinction or population
explosion to maintain equilibria that appear robust to stochasticity and
longer episode lengths. We select for fortresses with well-explored FSMs to
prohibit the growth of ineffective FSM components. By diversifying the
aggregate size of entity FSMs within an individual fortress, we seek to
provide a set of environments containing a smooth increase in the complexity
of agent behavior profiles.

##  9 Acknowledgements

We would like to thank Daphne Cornelisse, Noelle Law, Lisa Soros, and Graham
Todd for their valuable input and feedback on drafts of this paper.

## References

  * (1)
  * Baker et al. (2019) Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. 2019.  Emergent tool use from multi-agent autocurricula.  _arXiv preprint arXiv:1909.07528_ (2019).
  * Bamford (2021) Christopher Bamford. 2021.  Griddly: A platform for AI research in games.  _Software Impacts_ 8 (2021), 100066.
  * Bamford et al. (2022) Christopher Bamford, Minqi Jiang, Mikayel Samvelyan, and Tim Rocktäschel. 2022.  GriddlyJS: A Web IDE for Reinforcement Learning.  _Advances in Neural Information Processing Systems_ 35 (2022), 15051–15065.
  * Bansal et al. (2018) Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. 2018.  Emergent Complexity via Multi-Agent Competition. In _International Conference on Learning Representations_.
  * Bedau et al. (2000) Mark A Bedau, John S McCaskill, Norman H Packard, Steen Rasmussen, Chris Adami, David G Green, Takashi Ikegami, Kunihiko Kaneko, and Thomas S Ray. 2000.  Open problems in artificial life.  _Artificial life_ 6, 4 (2000), 363–376.
  * Beukman et al. (2022) Michael Beukman, Christopher W Cleghorn, and Steven James. 2022.  Procedural content generation using neuroevolution and novelty search for diverse video game levels. In _Proceedings of the Genetic and Evolutionary Computation Conference_. 1028–1037.
  * Björk and Juul (2012) Staffan Björk and Jesper Juul. 2012.  Zero-player games or: what we talk about when we talk about players. In _Philosophy of Computer Games Conference, Madrid_.
  * Charity et al. (2023) M Charity, Dipika Rajesh, Sam Earle, and Julian Togelius. 2023.  Amorphous Fortress: Observing Emergent Behavior in Multi-Agent FSMs.  _arXiv preprint arXiv:2306.13169_ (2023).
  * Charity et al. (2020) M Charity, Dipika Rajesh, Rachel Ombok, and Lisa B Soros. 2020.  Say “sul sul!” to simsim, a sims-inspired platform for sandbox game ai. In _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , Vol. 16. 182–188.
  * Dennis et al. (2020) Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. 2020.  Emergent complexity and zero-shot transfer via unsupervised environment design.  _Advances in neural information processing systems_ 33 (2020), 13049–13061.
  * Deshpande and Magerko (2021) Manoj Deshpande and Brian Magerko. 2021.  Drawcto: A Multi-Agent Co-Creative AI for Collaborative Non-Representational Art.  (2021).
  * Doncieux et al. (2019) Stephane Doncieux, Alban Laflaquière, and Alexandre Coninx. 2019.  Novelty search: a theoretical perspective. In _Proceedings of the Genetic and Evolutionary Computation Conference_. 99–106.
  * Earle (2020) Sam Earle. 2020.  Using fractal neural networks to play simcity 1 and conway’s game of life at variable scales.  _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ (2020).
  * Earle et al. (2022) Sam Earle, Justin Snider, Matthew C Fontaine, Stefanos Nikolaidis, and Julian Togelius. 2022.  Illuminating diverse neural cellular automata for level generation. In _Proceedings of the Genetic and Evolutionary Computation Conference_. 68–76.
  * Earle et al. (2021) Sam Earle, Julian Togelius, and Lisa B Soros. 2021.  Video games as a testbed for open-ended phenomena. In _2021 IEEE Conference on Games (CoG)_. IEEE, 1–9.
  * Fan et al. (2022) Linxi Fan, Guanzhi Wang, Yunfan Jiang, Ajay Mandlekar, Yuncong Yang, Haoyi Zhu, Andrew Tang, De-An Huang, Yuke Zhu, and Anima Anandkumar. 2022.  Minedojo: Building open-ended embodied agents with internet-scale knowledge.  _Advances in Neural Information Processing Systems_ 35 (2022), 18343–18362.
  * Freeman et al. (2021) C Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem. 2021.  Brax-A Differentiable Physics Engine for Large Scale Rigid Body Simulation. In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)_.
  * Gomez et al. (2009) Faustino J Gomez, Julian Togelius, and Juergen Schmidhuber. 2009.  Measuring and optimizing behavioral complexity for evolutionary reinforcement learning. In _International Conference on Artificial Neural Networks_. Springer, 765–774.
  * Grbic et al. (2021) Djordje Grbic, Rasmus Berg Palm, Elias Najarro, Claire Glanois, and Sebastian Risi. 2021.  Evocraft: A new challenge for open-endedness. In _Applications of Evolutionary Computation: 24th International Conference, EvoApplications 2021, Held as Part of EvoStar 2021, Virtual Event, April 7–9, 2021, Proceedings 24_. Springer, 325–340.
  * Green et al. (2021) Michael Cerny Green, Victoria Yen, Sam Earle, Dipika Rajesh, Maria Edwards, and Lisa B Soros. 2021.  Exploring open-ended gameplay features with Micro RollerCoaster Tycoon.  _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ (2021).
  * Guerrero-Romero and Perez-Liebana (2021) Cristina Guerrero-Romero and Diego Perez-Liebana. 2021.  Map-elites to generate a team of agents that elicits diverse automated gameplay. In _2021 IEEE Conference on Games (CoG)_. IEEE, 1–8.
  * Guttenberg and Soros (2023) Nicholas Guttenberg and LB Soros. 2023.  Designing Emergence in Games. In _ALIFE 2023: Ghost in the Machine: Proceedings of the 2023 Artificial Life Conference_. MIT Press.
  * Jiang et al. (2021) Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel. 2021.  Prioritized level replay. In _International Conference on Machine Learning_. PMLR, 4940–4950.
  * Khalifa et al. (2020) Ahmed Khalifa, Philip Bontrager, Sam Earle, and Julian Togelius. 2020.  Pcgrl: Procedural content generation via reinforcement learning. In _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , Vol. 16. 95–101.
  * Lange (2023) Robert Tjarko Lange. 2023.  evosax: Jax-based evolution strategies. In _Proceedings of the Companion Conference on Genetic and Evolutionary Computation_. 659–662.
  * Lavelle (2013) Stephen Lavelle. 2013.  Puzzlescript.  https://www.puzzlescript.net/.  Accessed: 2023-12-03.
  * Lowe et al. (2017) Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. 2017.  Multi-agent actor-critic for mixed cooperative-competitive environments.  _Advances in neural information processing systems_ 30 (2017).
  * Melotti and de Moraes (2018) Alexandre Santos Melotti and Carlos Henrique Valerio de Moraes. 2018.  Evolving roguelike dungeons with deluged novelty search local competition.  _IEEE Transactions on Games_ 11, 2 (2018), 173–182.
  * Mouret and Clune (2015) Jean-Baptiste Mouret and Jeff Clune. 2015.  Illuminating search spaces by mapping elites.  _arXiv preprint arXiv:1504.04909_ (2015).
  * Norstein et al. (2022) Emma Stensby Norstein, Kai Olav Ellefsen, and Kyrre Glette. 2022.  Open-ended search for environments and adapted agents using map-elites. In _International Conference on the Applications of Evolutionary Computation (Part of EvoStar)_. Springer, 651–666.
  * Parker-Holder et al. (2022) Jack Parker-Holder, Minqi Jiang, Michael Dennis, Mikayel Samvelyan, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. 2022.  Evolving curricula with regret-based environment design. In _International Conference on Machine Learning_. PMLR, 17473–17498.
  * Pierrot and Flajolet (2023) Thomas Pierrot and Arthur Flajolet. 2023.  Evolving Populations of Diverse RL Agents with MAP-Elites.  _arXiv preprint arXiv:2303.12803_ (2023).
  * Russell and Norvig (2010) Stuart J Russell and Peter Norvig. 2010.  _Artificial intelligence a modern approach_.  London.
  * Samvelyan et al. (2023) Mikayel Samvelyan, Akbir Khan, Michael Dennis, Minqi Jiang, Jack Parker-Holder, Jakob Foerster, Roberta Raileanu, and Tim Rocktäschel. 2023.  MAESTRO: Open-ended environment design for multi-agent reinforcement learning.  _arXiv preprint arXiv:2303.03376_ (2023).
  * Schaul (2013) Tom Schaul. 2013.  A video game description language for model-based or interactive learning. In _2013 IEEE Conference on Computational Inteligence in Games (CIG)_. IEEE, 1–8.
  * Secretan et al. (2008) Jimmy Secretan, Nicholas Beato, David B D Ambrosio, Adelein Rodriguez, Adam Campbell, and Kenneth O Stanley. 2008.  Picbreeder: evolving pictures collaboratively online. In _Proceedings of the SIGCHI conference on human factors in computing systems_. 1759–1768.
  * Stanley et al. (2017) Kenneth O Stanley, Joel Lehman, and Lisa Soros. 2017.  Open-endedness: The last grand challenge you’ve never heard of.  _While open-endedness could be a force for discovering intelligence, it could also be a component of AI itself_ (2017).
  * Suarez et al. (2021) Joseph Suarez, Yilun Du, Clare Zhu, Igor Mordatch, and Phillip Isola. 2021.  The neural mmo platform for massively multiagent research.  _arXiv preprint arXiv:2110.07594_ (2021).
  * Sudhakaran et al. (2021) Shyam Sudhakaran, Djordje Grbic, Siyan Li, Adam Katona, Elias Najarro, Claire Glanois, and Sebastian Risi. 2021.  Growing 3d artefacts and functional machines with neural cellular automata. In _Artificial Life Conference Proceedings 33_ , Vol. 2021. MIT Press One Rogers Street, Cambridge, MA 02142-1209, USA journals-info …, 108.
  * Wang et al. (2023) Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. 2023.  Voyager: An open-ended embodied agent with large language models.  _arXiv preprint arXiv:2305.16291_ (2023).
  * Wang et al. (2020) Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeff Clune, and Kenneth O Stanley. 2020.  Enhanced POET: open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. In _Proceedings of the 37th International Conference on Machine Learning_. 9940–9951.
  * Zhang et al. (2023) Jenny Zhang, Joel Lehman, Kenneth Stanley, and Jeff Clune. 2023.  OMNI: Open-endedness via Models of human Notions of Interestingness.  _arXiv preprint arXiv:2306.01711_ (2023).

Table 1: Entity FSM action node definitions Action Node |  Definition
---|---
idle |  the entity remains stationary atfferently-sizedsame position
move |  the item moves in a random direction (north, south, east, or west)
die |  the entity is deleted from the fortress
clone |  the entity creates another instance of its own class
push (c) |  the entity will attempt to move in a random direction and will push an entity of the specified target character into the next space over (if possible)
take (c) |  the entity removes the nearest entity of the specified target character
chase (c) |  the entity will move towards the position of the nearest entity of the specified target character
add (c) |  the entity creates another instance from the class of the specified target character
transform (c) |  the entity will change classes altogether to an entirely different entity class - thus changing its FSM definition entirely
move_wall (c) |  the entity will attempt to move in a random direction unless there is an entity of the specified class at that position - otherwise it will remain idle
Table 2: Entity FSM conditional edge definitions (ordered by least to greatest priority) Action Node |  Definition
---|---
none |  no condition is required to transition states
step (int) |  every x number of simulation ticks the edge is activated and the node transitions
within (char) (int) |  checks whether the entity is within a number of spaces from an instance of another entity with the target character
nextTo (char) |  checks whether the entity is within one space (north, south, east, or west) of another entity of the target character
touch (char) |  checks whether the entity is in the same space as another entity of the target character

Input: $node\\_prob$, $edge\\_prob$, $instance\\_prob$

1

2$node\\_r$ = random();

3 $edge\\_r$ = random();

4 $instance\\_r$ = random();

5

/* Mutate random entity class nodes */

6 while  _$node\\_r <node\\_prob$_ do

7 $i$ = random(0,2);

8 $e$ = random($fortress.ent\\_def$);

9 $n$ = random(log_f());

10 if  _$i==0$_ then

11 $fortress.\\_delete\\_nodes(e,n)$;

12

13 else if  _$i==1$_ then

14 $fortress.\\_add\\_nodes(e,n)$;

15

16 else if  _$i==2$_ then

17 $fortress.\\_alter\\_nodes(e,n)$;

18

19 $node\\_r$ = random();

20

/* Mutate random entity class edges */

21 while  _$edge\\_r <edge\\_prob$_ do

22 $i$ = random(0,2);

23 $e$ = random($fortress.ent\\_def$);

24 if  _$i==0$_ then

25 $fortress.\\_delete\\_edge(e)$;

26

27 else if  _$i==1$_ then

28 $fortress.\\_add\\_edge(e)$;

29

30 else if  _$i==2$_ then

31 $fortress.\\_alter\\_edge(e)$;

32

33 $edge\\_r$ = random();

34

/* Mutate random entity instances in the fortress */

35 while  _$instance\\_r <instance\\_prob$_ do

36 $i$ = random(0,1);

37 $e$ = random($fortress.entities$);

38 if  _$i==0$_ then

39 $fortress.\\_remove\\_entity(e)$;

40

41 else if  _$i==1$_ then

42 $x,y$ = random(fortress.pos);

43 $fortress.\\_add\\_entity(e,x,y)$;

44

45 $instance\\_r$ = random();

46

Algorithm 1 Mutation function for the Fortress

(a) Proportion of FSMs explored in fortresses. Naturally, FSMs with fewer
nodes (left) are more easily explored.

(b) Entropy of distribution of FSM sizes across entity types. Fortresses with
very few/many nodes (left/right) across all FSMs must have low entry because
all entity FSMs are necessarily small/large. Fortresses with a medium-high
number of nodes—allowing for diverse FSM sizes between entities—exhibit high
entropy. This suggests that sets of differently-sized FSMs are more likely to
result in thorough FSM exploration.

Figure 5: Archive of fortresses resulting from maximizing proportion of FSMs
explored while maintaining diversity in terms total size of FSMs and number of
entity instances present in the fortress at the end of simulation.

(a) Proportion of FSMs explored in fortresses. Low entropy fortresses
(left)—in which all entities have similar FSM size—allow for the most thorough
exploration.

(b) Number of nodes over all entity types. Naturally, minimal FSMs lead to the
fittest low-entropy fortresses (left), while higher entropy FSM size
distributions require more nodes overall (right).

Figure 6: Archive of fortresses resulting from maximizing proportion of FSMs
explored while maintaining diversity in terms of number of entity instances
present in the fortress at the end of simulation, and entropy of the
distribution of FSM sizes across entity types.

behavior characteristics | new seeds | n. episode steps | best score | QD score | archive size
---|---|---|---|---|---
n. entities, n. nodes | no | 100 | 0.941 | 2,235 | 9,986
yes | 100 | 0.941 | 2,197 | 9,975
500 | 0.941 | 2,086 | 9,962
n. entities, FSM size entropy | no | 100 | 0.958 | 2,156 | 6,974
yes | 100 | 0.958 | 2,005 | 6,951
500 | 0.958 | 2,011 | 6,950

Table 3: Re-evaluation of elites with new random seeds and longer episodes.
After aggregating (re-evaluated) elites from 10 trials, we see that the
stochastic nature of our environment leads to some variance, with some
shrinking of the archive and decrease in QD score.

Because our domain is stochastic—in particular, re-simulating the same
fortress (with the same entity class FSMs and initial entity instances and
starting positions) will result in different random movement actions from any
agent in a ‘move’, ‘push’, or ‘chase’ state—we re-evaluate the the fortresses
in the archive using new random seeds and re-insert fortresses into a fresh
archive. The results of these re-evaluations (for a single trial) are
visualized against the archive resulting from QD search in Figure 7. In Table
3, we repeat the re-evaluation process for 10 archives, each generated by a
separate QD search. We then consider the aggregate archive of overall best
elites before and after re-evaluation.

(a) Original archive after QD search.

(b) Archive after re-evaluation with new random seeds.

(c) Archive after re-evaluation with new random seeds and longer episodes.

Figure 7: Using the archive from a single trial of QD search (left) (with n.
entities and n. nodes as BCs), we observe that re-evaluating on new seeds
(middle) and with longer episodes (right) leads to increasingly “holey”
archives, due to random variation in the number of surviving entities after
each episode.