# Evolving Strategies for Competitive
Multi-Agent Search

Erkin Bahçeci, Riitta Katila, and Risto Miikkulainen This research was
supported in part by NSF under grants SBE-0914796, IIS-0915038, and
DBI-0939454.Erkin Bahçeci and Risto Miikkulainen are with the Department of
Computer Science, University of Texas at Austin, Austin, TX, 78712, USA
(e-mail<EMAIL_ADDRESS>risto@cs.utexas.edu).Riitta Katila is with the
Department of Management Science & Engineering, Stanford University, Stanford,
CA, 94305, USA (e-mail: rkatila@stanford.edu).

###### Abstract

While evolutionary computation is well suited for automatic discovery in
engineering, it can also be used to gain insight into how humans and
organizations could perform more effectively. Using a real-world problem of
innovation search in organizations as the motivating example, this article
first formalizes human creative problem solving as competitive multi-agent
search (CMAS). CMAS is different from existing single-agent and team search
problems in that the agents interact through knowledge of other agents’
searches and through the dynamic changes in the search landscape that result
from these searches. The main hypothesis is that evolutionary computation can
be used to discover effective strategies for CMAS; this hypothesis is verified
in a series of experiments on the NK model, i.e. partially correlated and
tunably rugged fitness landscapes. Different specialized strategies are
evolved for each different competitive environment, and also general
strategies that perform well across environments. These strategies are more
effective and more complex than hand-designed strategies and a strategy based
on traditional tree search. Using a novel spherical visualization of such
landscapes, insight is gained about how successful strategies work, e.g. by
tracking positive changes in the landscape. The article thus provides a
possible framework for studying various human creative activities as
competitive multi-agent search in the future.

###### Index Terms:

Competitive multi-agent search, evolutionary computation, NK model, NEAT,
CPPN.

##  I Introduction

Evolutionary computation (EC) is often used as a method for optimizing
engineering design, be it physical or abstract constructions, or descriptions
of complex processes such as lisp code or neural networks. However, EC can
also be used to gain insight into how humans perform various tasks, and how
they could perform them better. This article focuses on such a topic: It
presents a model of human problem solving in competitive domains, and
demonstrates how evolutionary computation can be used to discover effective
behavior in such domains.

More specifically, the study makes three contributions. First, it develops
_competitive multi-agent search_ (CMAS) as a formalization of human problem
solving. CMAS was originally developed to understand how high-tech companies
search for technological innovations, but the same formalization can
potentially be applied to computational modeling of scientific discovery,
engineering problem solving, and art and design. In CMAS, multiple agents
search for the same peaks (i.e. innovations) on the common fitness landscape.
They each try to find as many and as high peaks as possible over a given
amount of time, representing the cumulative value of their innovations. While
searching, they can choose to share information about what they find, or keep
such information private. Furthermore, the landscape is dynamic in that the
fitness of the points can increase or decrease when multiple agents discover
them, representing the dynamic valuation of innovations in the real world. The
CMAS formalization is useful because it makes it possible to characterize how
humans solve innovation and design problems, resulting in precise theories in
management science, psychology, and social science. However, the formalization
also makes it possible to use such models to determine how humans could
perform better than they currently do, thus informing both the individuals who
are trying to solve these problems, and the administrators that design
policies to encourage innovation and creativity.

The second contribution, and the main one of this article, focuses on this
opportunity to do better. The article demonstrates that _evolutionary
computation is a particularly good way to solve CMAS problems_. As an
experimental platform, an abstract, general CMAS domain is defined in terms of
an $N\\!K$ fitness landscape [1]. A comprehensive array of basic search
strategies is created for this domain, based on local (exploitative) search
and long-range (exploratory) search using public and/or private information
about the landscape. An advanced search strategy is also implemented based on
tree search, representing a typical AI problem solving method [2]. These
strategies are then used to instantiate several different competitive
environments, by including competitors with different strategies. New
strategies are evolved for each environment in order to perform better than
the existing ones. The results show that (1) evolution can discover customized
strategies that perform well in each environment, (2) it can discover general
strategies that perform well across many different environments, and (3) the
good evolved strategies are more complex than the basic intuitive strategies,
employing different strategies at different times, exhibiting optimal
preference for acting publicly or privately depending on the particular
environment, and resulting in overall principles such as riding a wave of
dynamically increasing landscape.

The third contribution is a technical one: a novel spherical visualization for
NK fitness landscapes. This visualization maintains the continuity of the
original high-dimensional landscape while reducing it to an intuitive 3D
surface. A focal point is selected, and continuity is maintained by
representing points further away with lesser resolution. This visualization is
useful in illustrating the search strategies: For instance, it makes it
strikingly clear why the wave-riding behavior is so effective. However, the
visualization is general, and could be useful for any study involving high-
dimensional binary spaces.

The article thus shows that CMAS is a potentially useful way to study problem
solving in the real world, and that evolutionary computation is an effective
way to gain insight into such problems.

##  II Background

This study is motivated by the real-world problem of innovation search in
organizations. The formalization of this problem, CMAS, builds on single-agent
and team-search methods, but extends them with competitive and cooperative
dynamic interactions between agents. It also builds on agent-based modeling,
but applies that general approach to doing innovation search in a landscape
that changes dynamically because of agent actions. The main contribution is to
show that evolutionary computation is a good way to discover effective
solution strategies for CMAS. While many different evolutionary approaches
could be used, the particular one tested in this article is based on NEAT
neuro-evolution [3] as one representative approach. With NEAT, strategies can
be represented naturally with neural networks whose complexity is matched with
the task.

###  II-A Organizational Theory

Even though the main focus of this article is on evolutionary optimization of
CMAS strategies, it is useful to review the motivation from the perspective of
a real-world example of CMAS, that of organizational theory in management
science. The example serves to make the issues and the motivation concrete.

Search (i.e. institutional problem solving) in the organizational theory
literature is typically thought to take place in a _knowledge space_ ,
conceptualized as a landscape. In innovation search, for example, firms
generate, recombine, and manipulate knowledge within a pool of technological
possibilities [4], and such activity can be tracked, for example, by using
patents (e.g. [5]). Such a search can be represented in an $N\\!K$ landscape
where $N$ corresponds to dimensions of knowledge and $K$ determines how
complex the relationships between them are [6, 7, 8]. This work has led to
several insights. One is that firms that search more frequently and further
away from their current knowledge bases (i.e.  _explore_) are more likely to
succeed [9, 5]. Another is that firms typically search in exactly the opposite
way: too little and too close (i.e.  _exploit_), and therefore need to find
effective strategies to resist such local tendencies [10].

Despite these insights, the focus of organizational search research has been
relatively narrow. Prior efforts typically assessed a firm’s innovation
activities only relative to its own behavior, i.e. as _single-agent search_.
Only recently, researchers have started to conceptualize search beyond its
single-agent roots and to incorporate competition. There is emerging research
on situations in which firms learn from their competitors and on why such
learning is sometimes difficult [11, 12], as well as research on how
competitors interact dynamically [13]. However, to date these studies have
been conceptual and statistical only; competition has not been integrated in
any formal models of organizational search.

The first contribution of this article is to do so, i.e. to create a
formalization that can be used to study such competitive processes with
computational techniques. It contributes thus to management science, but it
also contributes to AI, by defining a new and interesting class of search
problems relevant to the real world. Although the motivation comes from the
specific example of organizational search, the same formalization should be
useful in understanding a range of problem solving activities in human
societies, such as scientific discovery, innovation in engineering, and art
and design.

The second, main contribution of this article is then to show that new
computational techniques are useful in this new domain. The next subsection
reviews traditional search techniques in artificial intelligence and
evolutionary computation, pointing out why they are not a good fit with CMAS
problems.

###  II-B Search Algorithms

Traditionally, research on search algorithms has focused on two types of
search methods: search performed by a single agent and search performed by a
team of similar cooperating agents. Single-agent search methods, such as A*
[14] and iterative-deepening A* (IDA*) [15], have been used in well-defined
search domains, including path finding and scheduling problems. Such methods
are understood well theoretically and guarantee optimal solutions to a
problem, but they are impractical to utilize if the search space of the
problem is too large.

On the other hand, with team-search methods the individual team members search
for peaks in a fitness landscape in parallel; every point in the search space
has a certain height corresponding to its fitness value, and the knowledge of
all agents is collected into a single pool. These search methods are
appropriate in problems that are inherently large or not well-defined, such as
antenna design [16] and robot control [17]. The theory of these methods is
less well developed and they do not usually guarantee optimal solutions.

Team-search methods are typically inspired by various types of biological and
natural systems, such as evolution [18], swarm behavior [19], water drops
[20], and gravitational particle interactions [21]. For instance, Particle
Swarm Optimization [22] and Ant Colony Optimization [23] are inspired by
social swarm behaviors in nature: They make use of multiple agents that
represent solutions to optimization problems.

Competition has been incorporated into single-agent search methods by
extending them to two-player games [24] and multi-agent adversarial games
[25]. The search for the best move for a player proceeds by first considering
all moves of that player and then a subset of the moves of the opponents
(utilizing techniques such as alpha-beta pruning [26, 27]). However, since
such search methods rely on enumerating all possible moves of at least one
player, they are not practical with a large number of moves.

Competitive elements exist in team search as well. For instance, in
evolutionary search, population members compete to propagate their genes,
although the population as a whole cooperates to produce a single good
solution. Inter-population competition has been incorporated into evolutionary
search in a coevolutionary arrangement, where different populations try to
outdo each other in the task [28, 29, 30, 31]. However, there is no absolute
fitness; a team is considered successful simply if it does better than the
other team. Moreover, the teams do not alter the fitness landscape and
therefore do not influence others’ search.

Therefore, neither single-agent nor team-based search is a good fit with CMAS
problems. In CMAS, interactions among agents and between the agents and the
environment need to be taken into account explicitly. Agent-based modeling
provides a framework for doing that, as will be described next.

###  II-C Agent-Based Modeling

Agent-based modeling has been used extensively in various fields including
search and optimization in computer science [23, 22, 32], as well as real-
world social and economical interactions in political science [33] and
economics [34, 35]. The idea is to model each agent explicitly, with the goal
that global patterns emerge from this process. The agent-based approach is
therefore an appropriate formulation for competitive multi-agent search.

In the multi-agent systems literature, there are many examples of domains
where the agents compete to solve problems [36]. CMAS can be seen as a special
case of such problems, characterized by four special properties: (1)
Competitive multi-agent search is modeled as search for the same highest peaks
in a common landscape. (2) The agents may not necessarily know about the other
agents’ searches, and may or may not inform them about their own searches. (3)
Their search actions have an effect on the landscape that is visible to all
agents. (4) The agents’ search strategies are stochastic, representing the
bounded rationality of real-world agents such as human decision makers and
organizations [37].

While some of these properties have been addressed in prior research, together
they define a new and interesting problem class. It shares with prior work the
idea of agents and their interactions as the appropriate level of modeling.
However, building on these specific properties, it may be possible to develop
a specific formalization and approach for CMAS problems that makes it easier
to understand and solve such problems. This is the goal of this article.

The main hypothesis tested is that while it is possible to formulate search
strategies by hand, and adapt traditional single-agent search strategies to
CMAS, better strategies can be discovered automatically by evolutionary
optimization. In order to verify this hypothesis, a particular approach is
developed using evolution of neural networks with the NEAT method [3]. While
other methods are possible as well, representing CMAS strategies as pattern-
producing neural networks (such as CPPNs [38] or CPGs [39]) is a potentially
powerful approach, as will be described in detail in Section III-F. While such
networks could be evolved through different methods, NEAT has been previously
applied to them extensively, and will therefore be used as the default
implementation in this article as well.

###  II-D Neuro-Evolution of Augmenting Topologies (NEAT)

NEAT (Neuro-Evolution of Augmenting Topologies; [3]) is a method for evolving
neural networks that adjusts both the topology and the weights as part of the
learning process (for other such methods, see [40, 41, 42]). It is based on
three synergetic ideas (see e.g. [3] for details):

First, the initial population of neural networks consists of minimally
connected individuals with no hidden nodes (i.e. nodes other than input and
output nodes). The networks gradually become more complex through mutations
that add nodes and connections. Only those additions to the topology that
improve performance are kept, which helps find small solutions to the problem.
Starting with minimal topology also speeds up learning since the number of
connection weights to be optimized during evolution, i.e. the size of the
search space for connection weights, is minimal [3].

Second, crossover between individuals with different topologies is made
possible by keeping an innovation number for each gene in the genome of a
neural network. Innovation numbers are used to match genes that have similar
historical origin. They are an abstraction of homology in biological
evolution, which is the mechanism for aligning similar genes during crossover
[43]. Keeping these numbers for each gene circumvents the expensive task of
matching topologies of networks for crossover (see [3] for details on
innovation numbers).

The third component of NEAT is that innovation in population members is
protected by separating the population into species depending on similarity.
When a structural mutation alters an individual considerably, the individual
may not initially perform as well as other population members. If this
happens, that individual will not survive even though this mutation might have
led to a better-performing individual after some optimization. Speciation
protects such individuals by putting networks that are too different from
others into separate species, allowing them to be optimized within the species
first. To prevent the whole population from being reduced to a single species,
explicit fitness sharing [44] is used. This principle means that the fitness
within the species is shared among its members, dividing the fitness of each
individual by the size of its species, preventing species from becoming too
large.

NEAT has been shown to be successful in several open-ended design domains,
such as vehicle control and collision warning [45] and controlling video game
agents [46]. Most importantly, it has been particularly effective in evolving
Compositional Pattern Producing Networks (CPPNs), i.e. networks that produce
spatial patterns [38]. The approach developed in this article will make use of
this idea: Agent strategies will be encoded as 4D and 2D patterns, as will be
described in Section III-F.

##  III Approach

In CMAS, multiple agents search for the highest peaks in the same landscape
simultaneously. The agents either share or hide their knowledge about the
landscape from other agents, and their searches change the landscape
dynamically. They select search actions (either exploit locally or explore
globally) based on a strategy that is encoded as CPPNs, and evolved through
the NEAT method. This section describes the landscapes, the agent models, the
memory types and search actions they use, how the strategies are represented
and generated from CPPNs, and how multiple agents are simulated.

###  III-A Fitness Landscape

As the search space for the experiment, abstract $N\\!K$ fitness landscapes
[1] are used. $N\\!K$ landscapes are $N$-dimensional hypercubes that assign
fitness values to the points of the space such that the _ruggedness_ of the
landscape can be adjusted (using the $K$ parameter). Such landscapes have been
used extensively to model human problem solving, such as innovation search [7,
47, 48]. Compared to alternatives such as game theoretical models, the
characteristics of the environment can be readily incorporated into an $N\\!K$
simulation, a large number of agents can be included, and they can be
boundedly rational, making it easier to draw relevant insights [7].

The $K$ parameter specifies the level of interaction among the $N$ dimensions
and can take the values between 0 and $N-1$. When $K$ is 0, the fitness
landscape is single-peaked and smooth. One can go from the lowest-fitness
point to the single peak by simply following the fitness gradient (i.e.
separately flipping each bit that causes the fitness to increase). With small
$K$, the fitness landscape becomes a little rugged, but highest peaks are
concentrated in a region. When $K$ is $N-1$, the landscape becomes fully
random with many peaks distributed all over the space.

More specifically, each point in the search space is encoded as a bit string
of length $N$. The fitness of a point is calculated by taking the average of
the fitness contributions of each bit in the bit string for that point. Each
bit’s contribution depends on the value of $K+1$ bits: that bit and the $K$
bits that interact with that bit. As suggested by Kauffman [1], for bit $i$
the interacting bits are the $K$ bits that follow it, i.e., bits $i+1$, $i+2$,
…, $i+K$ (mod $N$). These $K+1$ bit values are used as a key to look up
fitness-contribution values from a table, generated randomly from a uniform
distribution. This table has $N$ random values for each $(K+1)$-bit key, of
which there are $2^{K+1}$. Figure 1 shows how the fitness is calculated for an
$N\\!K$ fitness landscape with $N=3$ and $K=2$. In this case, the table
consists of $3\times 8$ fitness contribution values.

Figure 1: An $N\\!K$ fitness landscape, where $N=3$ is the number of
dimensions or bits of each point and $K=2$ is the number of other dimensions
that interact with each dimension. For example, dimension 2 interacts with
dimensions 1 and 3 (i.e. the two bits that follow it). To obtain the fitness
of a point, e.g., 010, the fitness contribution values for its element values
are averaged (i.e. the third row in the table). The arrows on the hypercube
represent the direction of increasing fitness. Also shown on the hypercube are
the peaks in the $N\\!K$ fitness landscape, indicated with shaded circles. The
fitness values of all points constitute the complete fitness landscape.
$N\\!K$ landscapes are useful because they are general and the difficulty
(i.e. ruggedness) can be adjusted. Such abstract landscapes can be used as a
platform to study search methods.

Dynamic fitness landscapes are modeled through _flocking_. That is, whenever
an agent visits a point, the fitness of that point and those nearby change,
depending on the _flocking intensity_ and _flocking radius_ parameters. The
fitness of the area around a point defined by the flocking radius is
multiplied by the flocking intensity. Two types of flocking are used. With
_boosting_ , flocking intensity is greater than 1.0 and the region rises,
whereas with _crowding_ , flocking intensity is less than 1.0 and the region
sinks. There is no limit on the number of times a point can be visited.
Therefore, when used in isolation, boosting and crowding will cause a point’s
fitness value to approach 1.0 and 0.0, respectively, with every visit to that
point. These changes make it possible to model the dynamics of fitness
landscapes in applications such as innovation search, where boosting
corresponds to expanding demand in new markets (such as tablet computers) and
crowding to the saturation of existing markets (such as desktops) [49]. The
details of the simulated agents are described next.

###  III-B Agents

Each search agent is a software entity that looks for high-fitness points in
the given fitness landscape. The behavior of an agent depends on the current
state of the fitness landscape, the agent’s strategy, and the current points
in its memory.

Formally, the search agent’s knowledge ${\cal X}(t)$ of the landscape and its
topography at time $t$ consists of the points ${\bf x}_{i}$ with fitness
values $z({\bf x}_{i})$ ($1\leq i\leq t$), where $z$ is the fitness function:

${\cal X}(t)=\\{[{\bf x}_{1},z({\bf x}_{1})],[{\bf x}_{2},z({\bf
x}_{2})],...[{\bf x}_{t},z({\bf x}_{t})]\\}.$ (1)

The agent moves to the next (i.e. $(t+1)$th) point using a search strategy $S$
based on what the agent already knows about the landscape (i.e. points visited
by that agent and other agents):

${\bf x}_{t+1}=S[{\cal X}(t)].\vspace*{-0.5ex}$ (2)

An agent’s strategy $S$ consists of two components that determine how the
agent will use its current knowledge. The first strategy component, $S_{1}$,
specifies which type of memory (i.e. public or private, Section III-C) and
which search method (i.e. explore globally or exploit locally, Section III-D)
the agent will employ. The second strategy component, $S_{2}$, specifies in
which type of memory the agent will place the last point it found.

Algorithm 1 Simulation algorithm

1: Initialize simulation and agents.

2: for each time step until the maximum number of steps is reached do

3: for each agent $a_{i}$ do

4: Advance $a_{i}$ one time step (Algorithm 2).

5: Record any landscape visits and public memory updates by $a_{i}$.

6: end for

7: Apply recorded landscape visits by updating fitness landscape.

8: Apply recorded public memory updates.

9: end for

The simulation runs in discrete time steps, where every time step each agent
is allowed to move according to its strategy and based on its current
knowledge (Algorithm 2). At the beginning of a time step, each agent
probabilistically selects a search method and a source memory for the search
starting point. This point is given as input to the search method chosen by
the agent to find a new high-fitness point. At the end of each time step, if
the agent has discovered a point that is better than the previous one, it
schedules that point to be placed into the destination memory.

Even though the simulation advances the agents sequentially (Algorithm 1), the
collective outcome of each time step in the simulation is independent of the
agent execution order, due to the delayed execution of the side effects of
agent actions. That is, every time step the simulator records landscape visits
performed and public memory updates scheduled by agents, without actually
making any changes immediately (line 5 in the algorithm). The recorded agent
visits are performed at the end of each time step after all the agents
complete their search steps, and the resulting landscape changes are carried
out (line 7). Similarly, public memory updates scheduled during a time step
are applied at the end of that step (line 8). The simulation is then carried
out until the agents have searched a significant part of the space (100 points
in the experiments in this article). The memory types will be described next.

###  III-C Memory

Agents can place points in two types of memory: public and private. In terms
of the innovation search example, public memory corresponds to public
knowledge through patents, and private memory to trade secrets. Public memory
can be accessed by all agents and it serves as a common knowledge base among
agents. That is, through the use of public memory, agents can communicate the
discovery of high-fitness points to the other agents. This information in turn
attracts the other agents to those good points, potentially benefiting all
agents. However, use of public memory also makes it likely for all agents to
spend their time in the same region of the search space, and through dynamic
landscape changes, may lead to decreasing fitness.

On the other hand, private memory is unique to each agent. Each agent can
place points in its own private memory, where they are hidden from other
agents. When agents make use of their private memory, they are more likely to
spread out and explore different regions of the fitness landscape, leading to
increased coverage of the search space.

Because memory contents change at each time step, public and private memory
are denoted as ${\cal X}_{\mathrm{pub}}(t)$ and ${\cal X}_{\mathrm{priv}}(t)$,
respectively. Before performing each search action, an agent takes the best
point currently in the memory (either public or private, depending on the
strategy), and performs a search using this point as the starting location.
The next section describes the two search methods.

Algorithm 2 Agent’s algorithm to complete one time step

1: Pick a search method and source memory probabilistically using $S_{1}$
strategy.

2: Perform one search step starting with the best point in the source memory.

3: if found a better point than the last one then

4: Pick a destination memory probabilistically using $S_{2}$ strategy.

5: Schedule placement of the new point in the destination memory.

6: end if

###  III-D Search Methods

The agents employ two search methods probabilistically depending on their
$S_{1}$ strategy: the exploit search method, i.e. taking a local step, and the
explore search method, i.e. making a long jump in the search space. These two
methods are motivated by how agents, such as innovating firms, search in the
real world (Section II-A; [50]; note that thus these terms in this article do
not refer to deterministic and stochastic actions like they do in the
reinforcement learning literature, but instead to the length of the search
step as they do in the management science literature).

The _exploit_ search method starts with a given point in the search space. It
then tries to discover new high-fitness points that are immediate neighbors of
that point, i.e. are at 1-bit distance from it. Each new point is generated by
flipping one bit in the point’s $N$-bit representation. If the new point has a
better fitness than the starting point, that point is placed in memory.
Otherwise, the search continues by flipping another bit of the starting point,
and so on until all bits are tried. The order of the flipped bits is a random
permutation of numbers 1 through $N$.

The _explore_ search method also starts with a given point, but it obtains new
points in a different way. From the starting point, it jumps to a new point
that is _not_ an immediate neighbor. More specifically, it generates a new
point by flipping multiple random bits of the starting point simultaneously
and continues to do so until the new point has higher fitness than the
starting point, or the maximum number of jump attempts is reached. The number
of bits to be flipped is also chosen randomly within a range given in
simulation parameters. For the experiments in this article this range is set
to [0.5, 1.0], which means that a new point in an exploration step is obtained
by flipping between 50-100% of bits of the starting point. In this manner, the
exploration action is a relatively long jump, and therefore distinctly
different from the exploitation action.

These search methods provide two actions for agents to perform on the starting
point. They are selected stochastically based on the agent’s strategy, as
described next.

State: Action: | Exploit with | Exploit with | Explore with | Explore with
---|---|---|---|---
public mem. | private mem. | public mem. | private mem.
Public: low fit. | 0.1 | 0.2 | 0.3 | 0.4
Private: low fit.
Public: low fit. | 0.0 | 1.0 | 0 | 0
Private: high fit.
Public: high fit. | 0.005 | 0.995 | 0 | 0
Private: low fit.
Public: high fit. | 0 | 0 | 0.9 | 0.1
Private: high fit.

TABLE I: An example $S_{1}$ strategy component, where each row represents a
state, and each column represents an action. $S_{1}$ consists of $4\times 4$
probability values, one per action-state combination, which are used for
selecting an action (i.e. a search method and a starting point) given the
state (i.e. the binary-valued fitness of the best points in public and private
memory). Each row of probability values adds up to 1.0, and determines what
the agent will do in the corresponding state. For instance, the second row of
this particular strategy specifies that when the best public point has low
fitness and best private point has high fitness, the agent will exploit that
public point with 0.1 probability, exploit that private point with 0.2
probability, explore starting with that public point with 0.3 probability, or
explore starting with that private point with 0.4 probability.

###  III-E Agent Strategy

Agents select among the two search methods using a search strategy. To
represent this strategy, the state of each agent is converted to a discrete
form based on whether the considered points’ fitness values are less than 0.5
(i.e.  _low fitness_) or more than 0.5 (i.e.  _high fitness_). The two
components of an agent’s strategy, $S_{1}$ and $S_{2}$, consist of a set of
probability values for each discrete state of the agent. Tables I and II show
example $S_{1}$ and $S_{2}$ strategies, respectively. Each row represents a
discrete state of an agent, and each column represents an action. The agents
choose their actions probabilistically depending on their current state,
according to the probabilities in these tables.

$\begin{array}[]{lllllll}\text{Pub. $\downarrow$}&\text{Pub.
$\downarrow$}&\text{Pub. $\uparrow$}&\text{Pub. $\uparrow$}&&&\\\ \text{Priv.
$\downarrow$}&\text{Priv. $\uparrow$}&\text{Priv. $\downarrow$}&\text{Priv.
$\uparrow$}&&\text{Point $\downarrow$}&\text{Point $\uparrow$}\end{array}$
---

Figure 2:  A pie-chart depiction of the example agent strategy shown in Tables
I and II. Each of the circles corresponds to a row of one of those two tables
(i.e. a state): four circles on the left for $S_{1}$ and two on the right for
$S_{2}$, where $\downarrow$ and $\uparrow$ represent low and high fitness,
respectively. Each shading pattern corresponds to a column of one of the two
tables (i.e. an action). The size of each slice represents the probability of
the action in the corresponding table row and column. This chart format allows
visualization of the 20 probability values of a strategy in a compact way.
Additionally, the black band around each circle indicates the average
percentage of time the agent spent in the state that corresponds to the circle
(i.e. a row in Tables I and II). The example percentages shown from left to
right are 5%, 10%, 25%, and 60% for $S_{1}$, and 20% and 80% for $S_{2}$. The
total area of gray slices overall indicates how much private memory is used,
whereas the amount of dotted shading in the first four circles tells the ratio
of exploration. For instance, the first circle shows a row with non-zero
probabilities for all actions, whereas the second circle specifies that only
one action is possible in the corresponding state (i.e. with 1.0 probability).
In certain cases, the probabilities for all but one action are close but not
equal to 1.0 (e.g. third row in Table I), which is seen in the visualization
as a sliver (e.g. the third circle). Such small but nonzero probabilities were
often discovered in the evolutionary experiments (Tables III and IV), and they
turned out to make a significant difference in performance compared to similar
fixed strategies where those probabilities are 0.0 (Figure 7).

State: Action: | Place in | Place in
---|---|---
public memory | private memory
New point: low fitness | 0.25 | 0.75
New point: high fitness | 0.7 | 0.3

TABLE II: An example $S_{2}$ strategy component. $S_{2}$ consists of $2\times
2$ probability values (for two actions and two states) for determining to
which memory to place the new point given the discrete fitness of that point.
Each row of probabilities adds up to 1.0, and determines what the agent will
do in the corresponding state. In this example, the agent will e.g. place each
new low-fitness point into public memory with 0.25 probability and into
private memory with 0.75 probability. The agent strategies can be visualized
graphically as shown in Figure 2.

The $S_{1}$ strategy component is employed by agents to visit a new point.
Using $S_{1}$, an agent selects both a search method and a starting point,
i.e. the memory’s best point from which the search begins, depending on the
discrete-valued fitness of the best points of public and private memory. The
state consists of the discrete-valued fitness of the two memories and the
action is a combination of the search method and the starting point chosen.
Thus, there are four possible states (low or high fitness for public memory’s
best point and low or high fitness for private memory’s best point) and four
possible actions (exploit or explore with public or private memory). The
search yields a new point for the agent to visit. Thus, $S_{1}$ can be
formalized as

$\displaystyle{\bf x}_{t+1}$ $\displaystyle=$ $\displaystyle S_{1}({\cal
X}_{\rm pub}(t),{\cal X}_{\rm priv}(t)).$ (3)

Using the $S_{2}$ strategy component, agents determine where to put a newly
discovered point (i.e. the action) depending on the fitness of the new point
${\bf x}_{t+1}$ (i.e. the state). Thus, there are two states (low fitness or
high fitness) and two actions (placing the point in public or private memory).
Formally, $S_{2}$ is used to update knowledge, i.e.

$\displaystyle\begin{split}{\cal X}(t+1)&=\\{{\cal X}_{\rm pub}(t+1),{\cal
X}_{\rm priv}(t+1)\\}\\\ &=S_{2}(z({\bf x}_{t+1}),{\cal X}_{\rm pub}(t),{\cal
X}_{\rm priv}(t)).\end{split}$ (4)

where $z$ is the fitness function.

The $S_{1}$ and $S_{2}$ strategies determine how agents behave and how
knowledge gets updated in the simulation. They can be represented directly as
vectors of real numbers such as those in Tables I and II, and visualized
graphically in Figure 2, and this representation is sufficient for the hand-
coded strategies in this article. However, preliminary experiments on learning
strategies showed that representing them as continuous patterns through CPPNs
leads to better results. How CPPNs are used to encode agent strategies will be
described next.

Figure 3: An example CPPN with four inputs, a bias input, and two outputs. The
number of links and hidden nodes as well as weights of existing links are not
fixed, and can change during evolution. Combinations of -1 and 1 values
supplied to input nodes $I_{1},I_{2},I_{3},I_{4}$ act as indices into the rows
and columns of Tables I and II (with -1 value representing index 0). For
$S_{1}$, $I_{1}$ specifies whether public memory has low or high fitness,
$I_{2}$ specifies whether private memory has low or high fitness, $I_{3}$
specifies whether the action is exploit or explore, and $I_{4}$ specifies
whether the action is carried out using public or private memory; the output
value of $O_{1}$ for each combination of the four inputs determines the action
probability for the state and action specified by that combination, which is
the value shown in the corresponding cell of Table I. Similarly, for $S_{2}$,
$I_{1}$ specifies whether the new point has low or high fitness, and $I_{4}$
specifies whether the action is to place that point in public or private
memory; the output value of $O_{2}$ for each combination of those two inputs
determines the action probability for the state and action specified by that
combination, which is the value shown in the corresponding cell of Table II.
While calculating probabilities for $S_{2}$, $I_{2}$ and $I_{3}$ are set to
0.0. In this manner, strategies can be represented continuously as CPPNs, with
$S_{1}$ and $S_{2}$ sharing the same network structure.

###  III-F Encoding Strategy Patterns

Compositional Pattern Producing Networks (CPPNs) are neural networks with
nodes that have various activation functions. They are particularly useful for
creating geometric patterns such as symmetric ones [38]. Preliminary
experiments on learning strategies showed that representing them as continuous
patterns through CPPNs leads to better results than evolving a set of distinct
probability values that correspond to strategy tables.

To represent strategies as CPPNs, note that the $S_{1}$ and $S_{2}$ strategy
components can be seen as functions that output the probability values in
Tables I and II. For instance in the case of $S_{2}$, the function takes two
binary inputs: whether the new point has low or high fitness, and whether the
destination memory being considered is the public or private memory. Each
combination of these binary inputs generates one of the probability values in
Table II. This function can be implemented as a CPPN with two inputs and one
output, which can be evolved with a neuro-evolution algorithm.

On the other hand, in the case of $S_{1}$ there are four discrete inputs:
whether the best point in public memory has low or high fitness, whether the
best point in private memory has low or high fitness, whether exploit or
explore action is being considered, and whether the source memory for that
action is public or private memory. This function can also be represented as a
CPPN with one output, but with four inputs instead of only two, to produce
probability values as in Table I.

To simplify the approach further, the functions for $S_{1}$ and $S_{2}$ can be
represented together by a single CPPN with four inputs and two outputs (one
output per strategy component; Figure 3) instead of by two separate CPPNs with
one output each. Utilizing such a combined CPPN for both $S_{1}$ and $S_{2}$
allows a single population of networks to be evolved. The components that
belong together to evolve together, sharing common structure.

To generate the 16 probability values in $S_{1}$ (as in Table I), all four
inputs of the CPPN network are used. The inputs are set to each combination of
-1 or 1 in turn, representing the different cells in the strategy table (where
-1 corresponds to the 0 index). The activation of the first output unit is
passed through a Gaussian or sigmoid function to limit its value within the
(0, 1) range, and the resulting number entered into the corresponding $S_{1}$
table cell. After all cells have been filled in this manner, the rows of
$S_{1}$ are normalized to add up to 1. If all values in a row are very small,
then all cells in that row are set to equal probability. The process for
$S_{2}$ is similar to $S_{1}$, except that only the first two inputs of the
CPPN are used, and the second output unit of the network is used to calculate
the values for the $S_{2}$ cells. This approach allows agent strategies to be
evolved conveniently as CPPNs.

##  IV Experiments

This section provides an experimental analysis of CMAS using the simulation
setup described in the previous section. The experiments aim to characterize
various environments, determine what kind of strategies work best, and test
the hypothesis that evolutionary optimization can be used to learn better
agent strategies (in particular specific strategies for a given environment
and general strategies that perform well across multiple environments). The
agent strategies are encoded as CPPNs, and evolved using NEAT.

###  IV-A Simulation Environments

The simulation environments all had eight agents. The first agent’s strategy
was evaluated and the remaining seven agents were given the role of
_opponents_ , all with a common manually specified and fixed strategy. The
$S_{1}$ and $S_{2}$ components of the opponents’ strategies were set to
constant probabilities, resulting in a CMAS environment with specific
characteristics. Six distinct opponent strategies (i.e. six different
environments) were implemented: always exploit or always explore, and always
using the best point from the public memory, always using the best point from
the private memory, or using either of those two points with a 50%
probability. These hand-coded strategies were selected because they are
intuitive, clear, and represent common strategies in innovation search [5, 9,
10].

The environments also varied in search space dimensions ($N$), resulting in
two different densities of agents (i.e. number of agents divided by search
space size) since the number of agents was the same: (1) sparse environments
with $N=20$ and (2) dense ones with $N=10$. The $K$ parameter of the $N\\!K$
landscapes was set to three in all environments to provide a moderate level of
interaction among the $N$ dimensions. Such moderate interaction is motivated
from the organizational search perspective [51]. The fitness landscape changed
via initial boosting and subsequent crowding as agents moved in the landscape,
achieved by decaying the flocking intensity from 1.05 to 0.9 linearly for each
point over 10 agent visits to the same point, with a flocking radius constant
at 2.0. Due to this dynamic nature of the fitness landscape, which is directly
related to how many agents there are on average per search space point, the
environments are more naturally characterized by agent density rather than
search space size. These environment parameter values were chosen because they
resulted in meaningful innovation search behavior in preliminary simulations.

(a) Sparse environments

(b) Dense environments

Figure 4: Performance comparison among manually specified strategies in sparse
($N=20$) and dense ($N=10$) environments. Statistical significance is
estimated between averages over 200 starting locations and shown for the fixed
strategies in each environment. Significant differences are indicated by
stars. Error bars denote one unit of standard error of the mean. Note that
because there is more interaction in the dense environment and therefore more
crowding, the $y$-axes have different scales. Each strategy (represented by a
bar of different color) was evaluated in six different homogeneous
environments with seven identical opponents whose strategy is identified along
the $x$-axis. Performance on each environment was averaged over 200 evaluation
runs. Different strategies perform best in different environments; finding an
effective strategy for a given environment is possible and an important and
interesting challenge.

Performance with several distinct strategies in such environments is compared
in Figure 4. In each environment and for each evaluated strategy the
simulation was repeated 200 times with randomized agent starting points in
each run. The performance of the strategy was then calculated by averaging the
performance across those runs, which in turn was defined as the average
fitness of the points that the agent with that strategy visited during the 100
time steps (i.e the duration of the run). Since fitness of points in the
search space varies between 0 and 1, so does each strategy’s performance.

In the sparse environments (Figure 4a), the _exploit with private memory_
strategy performed the best among all evaluated strategies (with $p$-value
$<10^{-9}$ compared to the one with the second highest mean performance),
except in the environments where the opponents used only private memory. In
those environments it tied with the _exploit with public memory_ strategy.
Indeed, when the opponents never access the public memory, that memory becomes
equivalent to the private memory for the evaluated agent. Thus, the successful
strategy in the sparse environments can be described as _exploit with a memory
that is not accessible by the opponents_.

On the other hand, when the environment was dense (Figure 4b) exploring
performed better than exploiting in general. However, the best memory type to
use while exploring depended on the opponent strategy. For instance, when the
opponents _explored with public memory_ , it was better for the evaluated
agent to use public memory (with $p$-value $<10^{-3}$), whereas when the
opponents _exploited with public memory_ , it was better to use private memory
(with $p$-value $<10^{-8}$). Indeed, in this case the regions around good
public memory points would generally become crowded and therefore have low
fitness, making private memory search more effective.

These results suggest that different environments require different search
strategies. Further, finding an effective strategy for a given environment is
possible and constitutes an interesting and important challenge.

Obviously, such a hand-coded comparison can ever only include a small subset
of all possible strategies. The ones included are prototypical and cover the
space well, but there is no reason to believe that they are the best for the
given environments. In order to determine experimentally whether better
strategies exist, a machine discovery method can be employed, as will be done
in the next two sections. First, a strategy will be optimized for each
environment separately; then, the same method will be used to create a general
strategy by optimizing the average performance of a strategy across multiple
environments.

###  IV-B Evolving Strategies for a Particular Environment

To test the hypothesis that better strategies exist, strategies were evolved
using NEAT with a population of size 100 in the same homogeneous environments
as before. NEAT was allowed to run for 500 generations, which was the point by
when performance plateaued in preliminary runs (Figure 5). Evolutionary runs
were repeated 64 times. Other parameters were standard for NEAT [3] or
otherwise listed in Table V in the Appendix.

At each generation of an evolutionary run, the fitness of each population
individual, i.e. each CPPN, was calculated by first generating the $S_{1}$ and
$S_{2}$ probability tables from the CPPN, and then using those tables to
control the single evaluated agent in the environment. Sizes of evolved CPPNs
vary, but average 26.6 and 26.9 nodes, and 75.4 and 75.6 links for sparse and
dense environments, respectively.

Figure 5: Learning curve for one of the evolutionary runs, showing the maximum
and mean performance of the evolved population. The shaded region indicates
standard error of the mean. Maximum performance usually plateaued well before
500 generations.

Sparse Environment | PCA for All Evolved Strategies | Sample Strategies
---|---|---
Id | Opponents
|  |  $\longleftarrow$ Public Private $\longrightarrow$ |  $\begin{array}[]{lllllll}\text{Pub. $\downarrow$}&\text{Pub. $\downarrow$}&\text{Pub. $\uparrow$}&\text{Pub. $\uparrow$}&&&\\\ \text{Priv. $\downarrow$}&\text{Priv. $\uparrow$}&\text{Priv. $\downarrow$}&\text{Priv. $\uparrow$}&&\text{Point $\downarrow$}&\text{Point $\uparrow$}\end{array}$
1 |  Exploit with public memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
2 |  Explore with public memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
3 |  Exploit with private memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]2 |
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]3 |
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]4 |
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]5 |
4 |  Explore with private memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]2 |
5 |  Exploit with either memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
6 |  Explore with either memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
7 |  $\begin{array}[]{l}\text{Environments 1-6 above and}\\\ \text{one with RTTS opponents}\\\ \text{(Avg. over all environments)}\end{array}$ |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
8 |  $\begin{array}[]{l}\text{One opponent from env.}\\\ \text{1-6 and one RTTS opponent}\\\ \text{(Heterogeneous environment)}\end{array}$ |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
|  |  |

TABLE III:  Strategies evolved in sparse environments ($N=20$). The third
column shows all 64 strategies evolved in the environment with the opponents
specified in the second column. The $x$-axis is the first principal component
(from PCA across all strategies in all sparse environments) and the $y$-axis
is the fitness of the strategy. The $x$-axis represents primarily public vs.
private memory preference, with public memory use increasing toward the left
and private memory use toward the right. Using the pie-chart format of Figure
2, the fourth column displays sample strategies for each environment, numbered
to indicate their positions on the PCA plot. The black band around each circle
indicates the average percentage of time the evolved agent spent in the
corresponding state. Most strategies cluster to the right, indicating that
private memory search works well, except in Environments 3 and 4, where the
distribution is bimodal because the opponents do not use public memory. In
some cases, parts of the strategy do not matter and there is considerable
diversity (e.g. in Environment 3). The best strategies are slightly less than
extreme, which allows them to perform better than fixed strategies.

Dense Environment | PCA for All Evolved Strategies | Sample Strategies
---|---|---
Id | Opponents
|  |  $\longleftarrow$ Public Private $\longrightarrow$ |  $\begin{array}[]{lllllll}\text{Pub. $\downarrow$}&\text{Pub. $\downarrow$}&\text{Pub. $\uparrow$}&\text{Pub. $\uparrow$}&&&\\\ \text{Priv. $\downarrow$}&\text{Priv. $\uparrow$}&\text{Priv. $\downarrow$}&\text{Priv. $\uparrow$}&&\text{Point $\downarrow$}&\text{Point $\uparrow$}\end{array}$
1 |  Exploit with public memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
2 |  Explore with public memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]2 |
3 |  Exploit with private memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]2 |
4 |  Explore with private memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]2 |
5 |  Exploit with either memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
6 |  Explore with either memory |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
[rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]2 |
7 |  $\begin{array}[]{l}\text{Environments 1-6 above and}\\\ \text{one with RTTS opponents}\\\ \text{(Avg. over all environments)}\end{array}$ |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
8 |  $\begin{array}[]{l}\text{One opponent from env. 1-6}\\\ \text{and one RTTS opponent}\\\ \text{(Heterogeneous environment)}\end{array}$ |  |  |  [rounded,border-color=gray!90,border-width=0.033em,border-radius=0.3em]1 |
---|---
|  |  |

TABLE IV: Strategies evolved in dense environments ($N=10$). The $x$-axis
scale in the PCA plots is inverted so that the shift from public to private
memory use is in left-to-right direction as in Table III; the $y$-axes have a
different scale from Table III. In the dense environments, there is less
variability due to stronger evolutionary pressure. Memory preference in
different environments is similar to that in Table III, with the exception of
Environment 2, where an opposite memory preference emerged. This effect is
investigated further in Figure 6.

Tables III and IV show distributions of strategies evolved on sparse and dense
environments, respectively, with example evolved strategies depicted in pie-
charts as in Figure 2. To visualize the distribution of the 64 evolved
strategies, they were first represented as 20-dimensional vectors and their
dimensionality was then reduced to one using PCA (separately for sparse and
dense environments). In the dense environments, the first principal component
captured 83% of the variance, and in the sparse environments, 39%, whereas the
second principal component captured 8% and 16%, respectively, suggesting that
one-dimensional visualization is indeed meaningful.

The first PCA dimension is the $x$-axis of the plots in the third column of
Tables III and IV. Note that the $x$-axis scale is the same for all sparse
environments, but different from the axis for the dense environments. The
$y$-axis of the PCA plots indicates the fitness of the strategies.
Interestingly, in both sparse and dense environments the $x$-axis corresponds
to a preference for using public or private memory: The leftmost strategies
across all plots have the highest public memory use, whereas the rightmost
ones use private memory the most. This tendency can be clearly seen e.g. in
the two sample strategies for Environment 4 in Table III.

Several interesting observations can be made based on Tables III and IV.
First, most strategies cluster on one side of the PCA plot, except for
Environments 3 and 4, where a bimodal distribution is observed. These two
environments are the only ones where the opponents uses only private memory.
Since the opponents never use public points, public memory effectively becomes
just another private memory for the evolved agent, and a bimodal distribution
results. This result is very similar to the observation in Section IV-A where
public and private memory use resulted in similar performance when the
opponents used only private memory.

Second, the distribution of strategies evolved in most of the remaining
environments is biased toward strategies that prefer private memory over
public memory. Thus, evolution discovered that it is good to be different from
competitors. This result also parallels the performance comparison of manual
strategies in Figure 4.

Third, in Environment 2 in Table IV, where opponents explore with public
memory, a surprising opposite effect is seen: public memory is preferred over
private memory. Not only is this result counterintuitive, it is also the
opposite of that in its sparse counterpart.

This effect can be explained by measuring the number of prior visits to a
given area by the agent and its opponents. As Figure 6 shows, the number of
prior visits that affect the evaluated agent is usually higher when the agent
uses a public-memory strategy than when it uses a private-memory strategy, and
therefore evolution usually favors private memory. However, the opposite is
true for dense environment 2: The public-memory strategy actually results in
fewer prior visits. The reason becomes clear when the source of prior visits
is considered. When the evaluated agent uses private memory, it is affected by
many of its own prior visits, but manages to avoid opponent’s prior visits
relatively well. When it switches to using public memory, it reduces its own
prior visits, but also increases the opponent’s visits. Such a trade is
usually detrimental, but not so in the dense environment 2. Because the
environment is dense and the opponents are exploring, even when the agent is
using private memory, the opponents make many prior visits already by chance.
Switching to public strategy therefore does not increase the opponent visits
much, but it does reduce self-visits significantly. The net effect is
therefore beneficial, and evolution will select for public-memory strategy for
dense environment 2.

Figure 6: The number of prior agent visits within the flocking radius of the
evaluated agent in Environments 1 and 2 in Tables III and IV. Agent visits
cause the landscape to sink due to crowding, and lead to lower fitness. The
bars labeled Public represent the average number of prior visits when the
evaluated agent uses one of the 64 evolved strategies that prefer public
memory the most (i.e. the leftmost 64 strategies in the PCA plots of all
environments in Tables III, for the bars labeled Sparse, and IV, for the bars
labeled Dense. Similarly, the bars labeled Private show the average number of
visits with the rightmost 64 strategies in the same tables. The bars’ colors,
white and gray, indicate prior visits by the evaluated agent (i.e. “self”) or
by its opponents, respectively. Switching from private strategies to public
ones increases the total number of prior visits in three out of the four
environments, but not in dense environment 2. As a result, evolution selects
for a public memory strategy in this case demonstrating that it can find
effective strategies that would be difficult to discover by hand.

Fourth, the agents encounter different states in dense and sparse
environments. This result can be seen by observing the black bands around the
circles of sample strategies in Tables III and IV, which represent the average
percentage of time spent in each $S_{1}$ and $S_{2}$ state. Across all evolved
strategies in dense environments, the $S_{1}$ state where public and private
memory have low fitness (i.e. the first circle) is encountered 34% of the time
on average, whereas in sparse environments only 0.011%. Similarly, in dense
environments the evolved agents spent 69% of their time in the $S_{2}$ state
where the new point has low fitness, but only 0.593% in sparse environments.
The reason is that the fitness landscape sinks more in dense environments, and
by the end of the 100-step simulation, all points in the search space have low
fitness. In contrast, in sparse environments, there are often points with high
fitness that the agents can visit, and the agents evolve to do so. Therefore,
evolved agents spend most of their time in high-fitness states in sparse
environments and low-fitness states in dense environments.

Fifth, a comparison of the PCA plots across the two tables indicates that the
strategies evolved in sparse environments vary more than those evolved in
dense ones. For example, in Environment 3 in Table III the evolved strategies
are dispersed much more than their counterparts in Table IV. It is interesting
to analyze why. First, note that strategies located on the left side (i.e.
those that use public memory more often than private memory) mostly differ in
which actions they take when fitness of public memory is low (i.e. the first
two circles of sample strategies 1, 2, and 3), and when the points they visit
have low fitness (i.e. the fifth circle). Note further that such states are
visited only rarely (i.e. less than 1% of the time), as indicated by very
little black band around the circles. The reason is that only the agent itself
changes public memory (not its opponents, which exploit with private memory),
and it places only high-fitness points in it. Therefore, public memory always
has a high fitness, and as a result, the first two states are rarely
encountered and the corresponding parts of the strategy (represented by the
first two circles) are rarely used. Also, since low-fitness points are usually
not visited in sparse environments, the fifth circle is rarely used. Similar
observations can be made for the strategies on the right side (i.e. those that
use private memory more often, such as sample strategies 4 and 5): They vary
mostly in states where private memory has low fitness (i.e. the first and
third circle) as well as when visited points have a low fitness (i.e. the
fifth circle), and these are indeed states they rarely visit. Thus, changes to
those parts of the strategy do not affect the evolved agent’s performance, and
evolution results in diverse solutions for them. In contrast, in dense
environments all states are encountered at least 9% of the time on average:
All parts of the strategy are therefore useful, and there is less variance.

In Environment 3, opponents exploit private memory, and place the new points
they find in private memory, which makes the evolved agent the only one (among
the eight agents in the simulation) that changes public memory. Since each one
of sample strategies 1, 2, and 3 places new high-fitness points in public
memory (i.e. the sixth circle), public memory always has high fitness.
Therefore, the first two states (which together represent public memory having
low fitness) are not observed with those strategies. Thus, the corresponding
parts of the strategy (i.e. the first two circles and rows in the $S_{1}$
table) are not used during simulation. In contrast, if the evolved agent uses
private memory instead of public, as in sample strategy numbered 4 and 5, the
unused states are different: The first and third circles, which together
represent the state of private memory having low fitness, do not get used.
Since low fitness points are usually not visited in sparse environments, the
parts of the strategy for new low-fitness points (i.e. the fifth circle and
the first row of the $S_{2}$ table) are not used either. Thus, changes to
those parts of strategy do not affect the evolved agent’s performance, and
during evolution strategy variants with differences in those unused parts do
arise, which leads to higher diversity in the evolved strategies in sparse
environments. On the other hand, in dense environments all states are
encountered at least 9% of the time on average, which makes most states useful
in each environment for the evolved strategies. Since most parts of the
strategies are used in dense environments, there is relatively lower variance
in evolved strategies compared to sparse environments.

Sixth, the best strategies are not perfectly extreme, unlike the fixed hand-
coded ones, but often contain small slivers of probability for alternative
actions. Such small differences allow them to perform better. As can be seen
in Figure 7, in each environment the evolutionary optimization resulted in a
strategy that performs at least as well as the best manual strategy.

Thus, the results verify the hypothesis that custom-designed strategies are
usually more successful than generic ones. An interesting question is: Is
there a general strategy that works well on all environments?

(a) Sparse environments

(b) Dense environments

Figure 7: Performance comparison among evolved strategies as well as the best
manual strategy from Figure 4 in sparse ($N=20$) and dense ($N=10$)
environments. Statistical significance is estimated between averages over 64
evolution runs. Significant differences are indicated by stars. The same six
environments are included as in Figure 4, as well as a seventh one where each
opponent had a different hand-coded strategy, where the strategies whose
performance is shown with the second and fourth bars in the plot are
identical. Hence the 1.0 $p$-value between those two bars. Strategies evolved
for each environment separately perform the best in all cases, while the
general strategies evolved in multiple environments are better than the best
manual overall strategy in almost all cases. Machine discovery is therefore a
powerful approach to develop CMAS strategies.

###  IV-C Evolving General Strategies

Two ways of evolving general strategies were tested: evolving in multiple
homogeneous environments and in a single heterogeneous environment. In the
first approach, seven homogeneous environments were used, consisting of the
six environments above, and an environment with seven opponents that use an
adapted RTTS strategy (which will be described in the next section). During
evolution the fitness of each evaluated strategy was calculated by averaging
the fitness score across those environments. The main disadvantage of this
approach is that it takes a very long time: each strategy must be evaluated in
seven environments in the using a total of 700 simulation steps.

The approach that uses a single heterogeneous environment avoids this problem.
There is one opponent of each type in this environment, allowing the agent to
interact with various types of opponents at once. Therefore, evaluation only
requires one environment and 100 simulation steps. As in previous experiments,
there are seven opponents but now each of them comes from a different
homogeneous environment.

The strategies evolved using these two approaches can be seen in Tables III
and IV as Environments 7 and 8. Private memory was mostly preferred over
public memory in both sparse and dense environments. With the homogeneous
approach, strategies evolved in the sparse environment exploited private
memory when private memory had high fitness (Environment 7 in Table III);
otherwise, their behavior varied, including exploring private memory while
still sometimes exploiting it, as shown in the sample strategy. When the
environments were dense (Environment 7 in Table IV), this approach evolved
strategies that mostly explored, but also rarely exploited with private
memory.

Similarly, in the heterogeneous approach (Environment 8), the evolved
strategies in the sparse environment exploited with private memory when
private memory had high fitness, but also explored when private memory had low
fitness. On the other hand, the strategies evolved in the dense heterogeneous
environment always explored with private memory. The likely reason is the same
as in Section IV-B: there are opponents that use public memory, making it less
beneficial to use.

Performance of the best strategies evolved using the two general approaches
was compared to that of the best strategy evolved specifically for that
particular environment, as well as to the manual strategy that performed best
in that environment. The results can be seen in Figure 7. In both sparse and
dense environments, the performance of the strategy that was evolved for that
particular environment was always the best of the evolved strategies (with
$p$-value $<10^{-9}$ compared to the strategy with the second highest mean in
most environments, and $<10^{-3}$ in the rest), and that was always followed
by the single strategy that was evolved in multiple homogeneous environments,
which in turn always performed better than the one evolved in the single
heterogeneous environment (with $p$-value $<10^{-7}$ in all environments).
Interestingly, the performance of the single heterogeneous environment was on
average within 1% of that of multiple homogeneous environments, even though it
required one-seventh of the evolution time. Thus, evolution in a heterogeneous
environment is an elegant and effective approach to finding general
strategies.

Overall, the similarity in performance between the different learning
approaches suggests that it may be possible to evolve a single strategy that
is effective in various environments, although the very best results are
obtained by customizing the strategy to each particular environment
separately.

###  IV-D Real-Time Tree-Search Agents

In order to highlight how different CMAS problems are from conventional search
problems, a real-time tree search (RTTS) algorithm was devised for the $N\\!K$
fitness landscape. RTTS is real-time in the sense that it does not perform the
whole search offline like A* does, but instead alternates between planning and
execution phases by performing a limited look-ahead search at each state
before selecting an action and moving to a new state. In this respect, this
algorithm is similar to e.g. Real-Time A* (RTA*) [2], a well-known search
method in the single-agent tradition. Further, at each step RTTS, like RTA*,
performs a full exploitation search from the current point, i.e. considers all
successor states reachable by exploitative search actions. In contrast, CMAS
also includes exploratory search actions, which can potentially reach any
point in the search space.

The reason for defining and employing RTTS instead of simply using RTA* is
that the search domain of $N\\!K$ fitness landscapes differs in several ways
from those for which RTA* was designed: (1) The goal is not to reach a certain
point in the search space as in RTA*, but rather to follow a path that yields
as much fitness as possible; (2) Since there is no goal point, there cannot be
a heuristic to calculate the cost of reaching a goal point; (3) Avoiding loops
is not a concern as long as the revisited points have high fitness; (4) The
search space is dynamic due to flocking of agents, which makes it less useful
to keep a hash table of observed states and their estimated costs for
returning to those states. Thus, RTTS can be seen as an adaptation of RTA* to
CMAS problems.

The RTTS algorithm works as follows. Given an agent’s state $s$ (in this case,
the last point the agent has visited), a score is calculated for each
successor state $s^{\prime}$. Since only exploit actions are considered, a
successor of a state is equivalent to a neighbor of a point in the space. Each
point has one neighbor $s^{\prime}_{i}$ per dimension $i$ ($1\leq i\leq N$),
obtained by flipping the bit of that dimension in point $s$. For each neighbor
$s^{\prime}_{i}$, RTTS carries out a look-ahead search starting from that
state, and calculates the score of $s^{\prime}_{i}$ by summing the fitness of
that point and the maximum fitness among those of the successors of
$s^{\prime}_{i}$. The agent’s next move is chosen as the exploitation action
that results in the state with the maximum score among all $s^{\prime}_{i}$.

In fact, what the RTTS agent does for each $s^{\prime}_{i}$ is identical to
what the agent does for $s$ itself. Thus, the agent’s search can be described
as fixed-depth tree search. When the depth of this search tree is set to two,
the points that RTTS evaluates consist of point $s$ itself, all neighbors
$s^{\prime}_{i}$ of $s$ ($1\leq i\leq N$), and all neighbors of all
$s^{\prime}_{i}$. The number of these points is $1+N(N+1)/2$, which amounts to
56 and 211 points for $N=10$ and $N=20$, respectively. Therefore, to keep the
number of evaluations at a reasonable level, the RTTS search depth was limited
to two (Figure 8).

The results, compared to best evolved CMAS strategies, are shown in Figure 9.
Note that RTTS with search of depth one would only reach the nearest
neighbors, amounting to the _always exploit_ strategy, with the small
difference that all neighbors are considered instead of stopping at the first
neighbor that improves over the current point. At depth two, however, RTTS is
a distinctly different strategy from those considered so far; it is a
traditional single-agent search method adapted to the CMAS setting.

Figure 8:  Point evaluations with RTTS and an evolved strategy. The
environment is 20-dimensional and shown in a spherical visualization where
elevation and brightness represent fitness, and distance from the center point
approximates the Hamming distance from it (see Appendix A for details of this
visualization). The 211 search points that the RTTS agent evaluates in a
single time step in order to determine which action to take are shown as
triangles. All of them are within two steps of the starting point for the
search, shown at the center. In contrast, evolved strategies perform eight
point evaluations on average (shown as squares), underscoring how different
the CMAS strategies are from classical single-agent search methods.

(a) Sparse environments

(b) Dense environments

Figure 9: Performance of the RTSS strategy compared to the best manual
strategy (Section IV-A) and the best evolved strategy (Section IV-B), in
sparse ($N=20$) and dense ($N=10$) environments. The non-limited version was
based on a complete 2-ply lookahead at each step, whereas the matched version
evaluated the same number of points as the other methods. The non-limited
version is comparable to the other methods, but the matched version is much
worse. The assumptions of RTSS do not hold in CMAS problems, which thereby
require a different approach.

The differences between RTTS and CMAS methods are clear in the results. The
evolved agents as well as the manual CMAS strategies evaluate only eight
points per step on average (Figure 8). Thus, they are significantly more
economical than RTTS in a high-dimensional landscape (i.e. 26 times more in
the sparse environments and seven times more in the dense ones). To make RTTS
more comparable with the CMAS methods, it is possible to match the number of
points it considers with that of the CMAS methods, by limiting it to one
action every 26 time steps in the sparse environments and every seven time
steps in the dense ones. As can be seen in Figure 9, under such limited
resources, RTTS makes very little progress. Whereas the CMAS methods are
designed to proceed with the information gained from only a few points, RTTS
expects to see the entire depth-2 search tree before making a decision.

Interestingly, even without the resource limitation, RTTS is still not better
than the CMAS methods (Figure 9). The reason is that it is constantly mislead
by the dynamic landscape: The fitness value of a point that looked promising
during the look-ahead may diminish once the agent gets there, and it may miss
points whose value increased.

Thus, CMAS problems are different from classical single-agent search problems,
and can be solved better by methods designed for such problems in mind, such
as those proposed in this article.

###  IV-E Visualizing Evolved Strategies

A particularly interesting behavior was observed in strategies evolved in
sparse environments. The probability of an agent encountering other agents in
sparse fitness landscapes is rather small. Therefore, short exploitation jumps
allow the agent to _ride a boosting wave_ , i.e. to stay at the forefront of
the area that is being boosted as it moves through the landscape, leaving a
trail of past visited points that have sunk in fitness (Figure 10). At each
step, the agent boosts all nearby points in the neighborhood defined by the
flocking radius. Therefore, as the new point starts losing fitness due to
crowding, the agent can find a nearby point with similar fitness that is
partially boosted, similarly to a surfer riding a wave.

Figure 10: A single agent’s wave-riding behavior shown in the spherical
visualization, with agent’s past visited points marked with dark dots and its
last position pointed to by the box (see Appendix A for details of the
visualization). The agent follows a movement pattern of jumping to a point
that has been partially boosted, then as the current point starts getting
crowded, jumping to a similar nearby point. This behavior is clearest in
sparse environments, demonstrating how agents can compete well by being
constantly on the move. It is also similar to incremental improvements in many
high-technology industries, giving them a computational interpretation. An
animation of wave-riding behavior can be seen at
http://nn.cs.utexas.edu/?waveriding.

Such _wave-riding_ behavior is particularly interesting because it resembles
what happens in real-world innovation search. Companies often make slight
improvements to their existing products, exploiting their initial design for
many years without a significant redesign. The evolutionary simulations in
this article rediscovered this strategy and demonstrated computationally why
it is effective.

##  V Discussion and Future Work

The experiments in Section IV-B showed that distinctly different search
strategies evolve in different environments, and they are generally better
than strategies evolved in other environments, evolved general strategies, and
manual strategies. They are also significantly more complex than the manual
strategies, and would be difficult to design without an automatic machine
discovery method such as evolutionary computation. The main hypothesis of the
article was therefore verified with these results: evolutionary computation is
useful in discovering good strategies for CMAS problems.

The main areas of future work include developing more versatile strategy
representations, applying the framework to analyzing real-world archival data,
characterizing CMAS theoretically, and extending the framework with opponent
modeling and communication.

First, the strategies were only coarsely encoded in this study. For instance,
agents currently choose the best point of either the public memory or the
private memory. A new action could be added to let the agents pick the best of
both memories, depending on their fitness. The observation time of memory
points could also be taken into account to allow the agents treat outdated
points in memory differently. Furthermore, the power of CPPN to represent
strategies was not yet fully utilized. Because their inputs and outputs are
continuous, CPPNs could in principle represent strategies over very large
number of (even continuous) states and actions. Such an approach would make it
possible to represent much more refined strategies, which could in turn lead
to more complex emergent behaviors, and to more accurate modeling of real-
world search.

In addition to evolving environment-specific strategies, Section IV-C showed
how a single general strategy can be evolved to perform well across multiple
different environments, with only a small cost in performance. For such a
strategy to scale up to even more diverse environments, it might be beneficial
to allow multimodal behaviors, so that the same agent strategy can have
distinct behaviors in different contexts [52]. A further step in this
direction would be to coevolve all or a subset of the opponents as well. In
this manner, the environment could present more diverse challenges, and more
interesting and perhaps realistic general strategies could evolve.

More generally, the simulations in this article suggest that the CMAS approach
could be used to provide insight into what kinds of strategies work well in
real-world competitive multi-agent search. One possibility is to set up the
search space and the agent parameters based on real-world archival data, such
as the historical record on patents and products in a particular industry.
Search can then be simulated on that landscape, explaining why certain
strategies were effective, and potentially discovering new strategies that
would have worked even better.

On the other hand, CMAS is a general and formally defined problem domain,
which should make it possible to analyze it theoretically. For example,
stochastic processes could be used to characterize the scope and power of the
search methods, deriving convergence and dominance conditions, as has been
done in prior work on coevolution and estimation of distribution algorithms
[31, 53, 54, 55].

Aspects of real-world competitive multi-agent search that were not addressed
in this study include opponent modeling and explicit interactions between
agents via direct communication. The former would let agents adapt to the
environment by altering their strategies depending on the behavior of
opponents they observe [56]. The latter would allow agents to cooperate more
effectively, form coalitions, and negotiate. These extensions would all be
useful in modeling real-world innovation search, and constitute a most
interesting direction of future work.

##  VI Conclusion

In this article, competitive multi-agent search was introduced as a
formalization of human problem solving, with innovation search in
organizations as a specific motivating example. In this formalization, the
agents interact through knowledge of other agents’ searches and through the
dynamic changes in the search landscape that result from these searches. The
main contribution is to show that evolutionary computation is a useful method
for CMAS problems: it is possible to discover effective search strategies that
might be hard to design by hand, and understand why they are effective. CMAS
thus demonstrates an interesting role for evolutionary computation: not only
it can be used as an automated method for engineering, but also a way to
understand how human behavior can be more effective. In the future, it may be
possible to use CMAS simulations to make recommendations to human decision
makers, as well as inform policy makers that aim at encouraging innovation and
creativity.

## Appendix A. Spherical _NK_ Fitness Landscape Visualization

Although high-dimensional $N\\!K$ landscapes are useful in testing ideas about
search and optimization in complex domains, it is not possible to visualize
them accurately, and it is therefore difficult to develop an intuitive
understanding of what happens in such spaces. In a typical visualization, two
dimensions are chosen to be represented accurately along each axis, and the
visualization is repeated for the different combinations of values for the
other dimensions. The main problem with such a visualization is that the
continuity of the space is lost, i.e. nearby points can end up very far apart
on the visualization, disallowing natural intuitions about space. Another
issue with this kind of visualization is that it shows all $2^{N}$ points in
the space; as $N$ grows, this number becomes prohibitively large, making it
impossible to visualize $N\\!K$ landscapes with sufficiently large $N$.

A different, novel approach is taken in Figures 8 and 10. In this spherical
approach, the continuity of the space is preserved, and the space is
represented with variable resolution. One point is chosen as the focus (e.g.
11111 in the five-dimensional case), and all of its neighbors in the original
space (e.g. 01111, 10111, 11011, 11101, and 11110) are shown as its neighbors
on the sphere, around a circle at distance 1. At distance 2, points with two
bits away from the original are shown, by combining bit flips of the adjacent
neighbors (to 00111, 10011, 11001, 11100, 01110), and so on until the
complement (00000) of the focus point is reached at the other side of the
sphere. In this manner, continuity of the original space is maintained in the
grid that results on the sphere: nearby points in the grid are indeed
neighbors in the original space, differing by one bit. The elevation and
brightness of the spherical surface represents the fitness of the points on
it: The higher the point and the lighter it is, the higher the fitness.

The continuity, however, imposes a trade-off: The grid is a complete
representation of the space only near the poles (i.e. at distance 1 and 4 in
the five-dimensional case); at the equator, it can only represent sample
points in the space (i.e. at distances 2 and 3, only five of the ten points
are located on the grid). For visualization (as in Figures 8 and 10), other
points of interest can be shown in the quadrilateral regions between the
actual grid points, although their specific locations within those regions are
undetermined. They are placed so that the distance between each point and the
north pole point corresponds to the Hamming distance between them. Among the
quadrilateral regions along the meridian at that distance, each point is in
the one whose corners are closest to the point.

The main purpose of this visualization is to represent the local neighborhood
of a specific point intuitively as a continuous space, with gradually less
resolution towards the horizon. It thus gives a concrete snapshot of the
current state of the search. The focus point can also be moved as the search
progresses, resulting in a detailed track of the process. Such a visualization
tool is implemented in a software package _NKVis_ , i.e. a visualization tool
for $N\\!K$ fitness landscapes, which is freely available at
http://nn.cs.utexas.edu/?nkvis.

Appendix B. Simulation and NEAT Parameters
Simulation Parameter Value $N$ (for the $N\\!K$ model) 10 and 20 $K$ (for the
$N\\!K$ model) 3 Number of agents 8 Number of time steps per run 100 Number of
runs per strategy evaluation 200 Flocking intensity 1.05 $\rightarrow$ 0.9
Flocking radius 2 Evolutionary generations 500 Evolutionary repeats per setup
64 Evolutionary population size 100 NEAT Parameter Value AddBiasToHiddenNodes
1 AdultLinkAge 2 AgeSignificance 1.2 AllowAddNodeToRecurrentConnection 0
AllowRecurrentConnections 0 AllowSelfRecurrentConnections 0
CompatibilityModifier 0 CompatibilityThreshold 20 DisjointCoefficient 1.0
DropoffAge 10 ExcessCoefficient 1.0 ExtraActivationFunctions 1
ExtraActivationUpdates 19 FitnessCoefficient 1.0 ForceCopyGenerationChampion 1
LinkGeneMinimumWeightForPhentoype 0 MutateAddLinkProbability 0.2
MutateAddNodeProbability 0.2 MutateDemolishLinkProbability 0.04
MutateLinkProbability 0.2 MutateLinkWeightsProbability 0.8
MutateNodeProbability 0.05 MutateOnlyProbability 0.5
MutateSpeciesChampionProbability 0 MutationPower 2 OnlyGaussianHiddenNodes 0
SignedActivation 0 SmallestSpeciesSizeWithElitism 1 SpeciesSizeTarget 0
SurvivalThreshold 0.2 WeightDifferenceCoefficient 0.8

TABLE V: Parameters used in the experiments for the multi-agent simulation and
NEAT.

## References

  * [1] S. A. Kauffman, _The Origins of Order_. New York: Oxford University Press, 1993.
  * [2] R. E. Korf, “Real-time heuristic search,” _Artificial Intelligence_ , vol. 42, no. 2-3, pp. 189 – 211, 1990. [Online]. Available: http://www.sciencedirect.com/science/article/pii/0004370290900544
  * [3] K. O. Stanley and R. Miikkulainen, “Evolving Neural Networks Through Augmenting Topologies,” _Evolutionary Computation_ , vol. 10, pp. 99–127, 2002. [Online]. Available: http://nn.cs.utexas.edu/keyword?stanley:ec02
  * [4] D. A. Levinthal and J. G. March, “A model of adaptive organizational search,” _Journal of Economic Behavior and Organization_ , vol. 2, pp. 307–333, 1981\.
  * [5] R. Katila, “New product search over time: Past ideas in their prime?” _Academy of Management Journal_ , vol. 45, pp. 995–1010, 2002.
  * [6] R. Katila, E. Bahceci, and R. Miikkulainen, “Organizing for innovation: Exploratory, ambidextrous and exploitative units in competitive environments,” 2010, working paper.
  * [7] D. A. Levinthal, “Adaptation on rugged landscapes,” _Management Science_ , vol. 43, no. 7, pp. pp. 934–950, 1997. [Online]. Available: http://www.jstor.org/stable/2634336
  * [8] G. Gavetti and D. Levinthal, “Looking forward and looking backward: Cognitive and experiential search,” _Administrative Science Quarterly_ , vol. 45, pp. 113–137, 2000.
  * [9] H. Greve, “A behavioral theory of R&D expenditures and innovations: Evidence from shipbuilding,” _Academy of Management Journal_ , vol. 46, pp. 685–702, 2003.
  * [10] C. Helfat, “Evolutionary trajectories in petroleum firm R&D,” _Management Science_ , vol. 40, pp. 1720–1747, 1994.
  * [11] H. Greve and A. Taylor, “Innovations as catalysts for organizational change: Shifts in organizational cognition and search,” _Administrative Science Quarterly_ , vol. 45, pp. 54–80, 2000.
  * [12] J. Rivkin, “Imitation of complex strategies,” _Management Science_ , vol. 46, pp. 824–845, 2000.
  * [13] R. Katila, J. Rosenberger, and K. Eisenhardt, “Swimming with sharks: Technology ventures, defense mechanisms, and corporate relationships,” _Administrative Science Quarterly_ , vol. 53, pp. 295–332, 2008.
  * [14] P. Hart, N. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” _Systems Science and Cybernetics, IEEE Transactions on_ , vol. 4, no. 2, pp. 100 –107, july 1968.
  * [15] R. E. Korf, “Depth-first iterative-deepening: An optimal admissible tree search,” _Artificial Intelligence_ , vol. 27, pp. 97–109, 1985.
  * [16] J. Lohn, D. Linden, G. Hornby, W. Kraus, A. Rodriguez-Arroyo, and S. Seufert, “Evolutionary design of an X-band antenna for NASA’s space technology 5 mission,” in _National radio science meeting_ , 2004, pp. 2313–2316.
  * [17] V. K. Valsalam, J. A. Bednar, and R. Miikkulainen, “Developing complex systems using evolved pattern generators,” _IEEE Transactions on Evolutionary Computation_ , vol. 11, no. 2, pp. 181–198, 2007. [Online]. Available: http://nn.cs.utexas.edu/keyword?valsalam:ieeetec07
  * [18] M. Mitchell, _An Introduction to Genetic Algorithms_. Cambridge, MA: MIT Press, 1996.
  * [19] J. Kennedy, R. Eberhart, and Y. Shi, _Swarm intelligence_. Morgan Kaufmann Publishers, 2001.
  * [20] H. Hosseini, “The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm,” _International Journal of Bio-Inspired Computation_ , vol. 1, no. 1/2, p. 71, 2009. [Online]. Available: http://www.inderscience.com/link.php?id=22775
  * [21] E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, “GSA: A Gravitational Search Algorithm,” _Information Sciences_ , vol. 179, no. 13, pp. 2232–2248, June 2009. [Online]. Available: http://dx.doi.org/10.1016/j.ins.2009.03.004
  * [22] J. Kennedy, R. Eberhart, _et al._ , “Particle swarm optimization,” in _Proc. of IEEE international conference on neural networks_ , vol. 4. Piscataway, NJ: IEEE, 1995, pp. 1942–1948.
  * [23] M. Dorigo and T. Stützle, _Ant colony optimization_. MIT Press, 2004. [Online]. Available: http://books.google.com/books?id=_aefcpY8GiEC&pgis=1
  * [24] J. Pearl, _Heuristics: Intelligent Search Strategies for Computer Problem Solving_. Reading, MA: Addison-Wesley, 1984.
  * [25] I. Zuckerman and A. Felner, “The MP-MIX algorithm: Dynamic search strategy selection in multiplayer adversarial search,” _Computational Intelligence and AI in Games, IEEE Transactions on_ , vol. 3, no. 4, pp. 316 –331, dec. 2011.
  * [26] D. E. Knuth and R. W. Moore, “An analysis of alpha-beta pruning,” _Artificial Intelligence_ , vol. 6, no. 4, pp. 293 – 326, 1975. [Online]. Available: http://www.sciencedirect.com/science/article/pii/0004370275900193
  * [27] R. E. Korf, “Multi-player alpha-beta pruning,” _Artificial Intelligence_ , vol. 48, no. 1, pp. 99 – 111, 1991. [Online]. Available: http://www.sciencedirect.com/science/article/pii/000437029190082U
  * [28] J. B. Pollack, A. D. Blair, and M. Land, “Coevolution of a backgammon player,” in _Proceedings of the 5th International Workshop on Artificial Life: Synthesis and Simulation of Living Systems (ALIFE-96)_ , C. G. Langton and K. Shimohara, Eds. Cambridge, MA: MIT Press, 1996.
  * [29] H. Juille and J. B. Pollack, “Dynamics of co-evolutionary learning,” in _In Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior_. MIT Press, 1996, pp. 526–534.
  * [30] J. Werfel, M. Mitchell, and J. Crutchfield, “Resource sharing and coevolution in evolving cellular automata,” _Evolutionary Computation, IEEE Transactions on_ , vol. 4, no. 4, pp. 388 – 393, nov 2000.
  * [31] K. O. Stanley and R. Miikkulainen, “Competitive coevolution through evolutionary complexification,” _Journal of Artificial Intelligence Research_ , vol. 21, pp. 63–100, 2004. [Online]. Available: http://nn.cs.utexas.edu/keyword?stanley:jair04
  * [32] K. Knight, “Are many reactive agents better than a few deliberative ones?” in _Proceedings of the 13th international joint conference on Artifical intelligence - Volume 1_. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1993, pp. 432–437. [Online]. Available: http://dl.acm.org/citation.cfm?id=1624025.1624086
  * [33] R. Axelrod, _The complexity of cooperation: Agent-based models of competition and collaboration_. Princeton Univ Pr, 1997.
  * [34] J. Epstein, “Agent-based computational models and generative social science,” _Complexity_ , vol. 4, no. 5, pp. 41–60, May 1999.
  * [35] J. Holland and J. Miller, “Artificial Adaptive Agents in Economic Theory,” _American Economic Review_ , vol. 81, no. 2, pp. 365 – 71, 1991. [Online]. Available: http://ideas.repec.org/a/aea/aecrev/v81y1991i2p365-71.html
  * [36] P. J. Hoen, K. Tuyls, L. Panait, S. Luke, and J. A. L. Poutré, “An overview of cooperative and competitive multiagent learning.” in _LAMAS_ , 2005, pp. 1–46.
  * [37] J. March and H. Simon, _Organizations_. New York: Wiley, 1958.
  * [38] K. Stanley, “Compositional pattern producing networks: A novel abstraction of development,” _Genetic Programming and Evolvable Machines_ , vol. 8, no. 2, pp. 131–162, June 2007.
  * [39] H. J. Chiel, R. D. Beer, and J. C. Gallagher, “Evolution and analysis of model CPGs for walking: I. Dynamical modules,” _Journal of Computational Neuroscience_ , vol. 7, no. 2, pp. 99–118, 1999.
  * [40] I. Harvey, P. Husbands, D. Cliff, A. Thompson, and N. Jakobi, “Evolutionary robotics: the sussex approach,” _Robotics and autonomous systems_ , vol. 20, no. 2, pp. 205–224, 1997.
  * [41] B. Hutt and K. Warwick, “Synapsing variable length crossover: Biologically inspired crossover for variable length genomes,” in _Artificial Neural Nets and Genetic Algorithms_ , D. Pearson, N. Steele, and R. Albrecht, Eds. Springer Vienna, 2003, pp. 198–202. [Online]. Available: http://dx.doi.org/10.1007/978-3-7091-0646-4˙36
  * [42] H. Moriguchi and S. Honiden, “Cma-tweann: efficient optimization of neural networks via self-adaptation and seamless augmentation,” in _Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference_. ACM, 2012, pp. 903–910.
  * [43] N. Sigal and B. Alberts, “Genetic recombination: The nature of a crossed strand-exchange between two homologous DNA molecules,” _Journal of Molecular Biology_ , vol. 71, no. 3, pp. 789–793, November 1972. [Online]. Available: http://www.ncbi.nlm.nih.gov/pubmed/4648347?dopt=abstract
  * [44] D. E. Goldberg and J. Richardson, “Genetic algorithms with sharing for multimodal function optimization,” in _Proceedings of the Second International Conference on Genetic Algorithms_ , J. J. Grefenstette, Ed. San Francisco: Morgan Kaufmann, 1987, pp. 148–154.
  * [45] N. Kohl, K. O. Stanley, R. Miikkulainen, M. Samples, and R. Sherony, “Evolving a real-world vehicle warning system,” in _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2006. [Online]. Available: http://nn.cs.utexas.edu/keyword?kohl:gecco06
  * [46] K. O. Stanley, B. D. Bryant, and R. Miikkulainen, “Real-time neuroevolution in the NERO video game,” _IEEE Transactions on Evolutionary Computation_ , vol. 9, no. 6, pp. 653–668, 2005. [Online]. Available: http://nn.cs.utexas.edu/keyword?stanley:ieeetec05
  * [47] P. Anderson, “Complexity theory and organization science,” _Organization Science_ , vol. 10, no. 3, pp. 216–232, 1999. [Online]. Available: http://orgsci.journal.informs.org/content/10/3/216.abstract
  * [48] G. Gavetti and D. Levinthal, “Looking forward and looking backward: Cognitive and experiential search,” _Administrative Science Quarterly_ , vol. 45, no. 1, pp. pp. 113–137, 2000. [Online]. Available: http://www.jstor.org/stable/2666981
  * [49] R. Katila, E. Chen, and H. Piezunka, “All the right moves: How entrepreneurial firms compete effectively,” _Strategic Entrepreneurship Journal_ , 2012, in press.
  * [50] J. G. March, “Exploration and exploitation in organizational learning,” _Organization Science_ , vol. 2, no. 1, pp. pp. 71–87, 1991. [Online]. Available: http://www.jstor.org/stable/2634940
  * [51] T. Knudsen and D. Levinthal, “Two faces of search: Alternative generation and alternative evaluation,” _Organization Science_ , vol. 18, pp. 39–54, 2007\.
  * [52] J. Schrum and R. Miikkulainen, “Evolving multimodal networks for multitask games,” in _Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG 2011)_. Seoul, South Korea: IEEE, September 2011, pp. 102–109, (Best Paper Award). [Online]. Available: http://nn.cs.utexas.edu/?schrum:cig11
  * [53] M. E. Alden, “MARLEDA: Effective distribution estimation through markov random fields,” Ph.D. dissertation, Department of Computer Sciences, The University of Texas at Austin, 2007, technical Report AI07-349. [Online]. Available: http://nn.cs.utexas.edu/keyword?alden:phd07
  * [54] S. G. Ficici and J. B. Pollack, “Pareto optimality in coevolutionary learning,” in _Sixth European Conference on Artificial Life_ , J. Kelemen, Ed. Berlin: Springer, 2001\.
  * [55] H. Mühlenbein and R. Höns, “The estimation of distributions and the minimum relative entropy principle,” _Evolutionary Computation_ , vol. 13, no. 1, pp. 1–27, 2005.
  * [56] D. Carmel and S. Markovitch, “Opponent modeling in multi-agent systems,” _Adaption And Learning In Multi-Agent Systems_ , pp. 40–52, 1996.