# On Total Coloring of Some Classes of Regular Graphs

S. Prajnanaswaroopa  Department of Mathematics, Amrita School of Engineering-
Coimbatore
Amrita Vishwa Vidyapeetham, India. sntrm4@rediffmail.com,{s_prajnanaswaroopa,
j_geetha, s_<EMAIL_ADDRESS>J. Geetha and K.Somasundaram  Department
of Mathematics, Amrita School of Engineering-Coimbatore
Amrita Vishwa Vidyapeetham, India. sntrm4@rediffmail.com,{s_prajnanaswaroopa,
j_geetha, s_<EMAIL_ADDRESS>Hung Lin-Fu  Department of Applied
Mathematics, National Chiao Tung University, Hsinchu 30010, Taiwan.
<EMAIL_ADDRESS>Narayanan. N  Department of Mathematics, Indian
Institute of Technology Madras, Chennai, India<EMAIL_ADDRESS>
Abstract: In this paper, we have obtained the total chromatic number of some
classes of Cayley graphs, odd graphs and mock threshold graphs.

Keywords: Regular graphs; Independent sets; Total coloring; Powers of Cycles;
Cayley Graphs; Chordal Graphs; Odd Graphs.

##  1 Introduction

All the graphs considered here are finite, simple and undirected.
Let $G=(V(G),E(G))$ be a graph with the sets of vertices $V(G)$ and edges
$E(G)$ respectively. A total coloring of G is a mapping $f:V(G)\cup
E(G)\rightarrow C$, where $C$ is a set of colors, satisfying the following
three conditions (a)-(c):

(a) $f(u)\neq f(v)$ for any two adjacent vertices $u,v\in V(G)$

(b) $f(e)\neq f(e^{\prime})$ for any two adjacent edges $e,e^{\prime}\in E(G)$
and

(c) $f(v)\neq f(e)$ for any vertex $v\in V(G)$ and any edge $e\in E(G)$
incident to v.

The total chromatic number of a graph G, denoted by $\chi^{\prime\prime}(G)$,
is the minimum number of colors that suffice in a total coloring. It is clear
that $\chi^{\prime\prime}(G)\geq\Delta+1$, where $\Delta$ is the maximum
degree of G. Behzad [2] and Vizing [19] independently conjectured (Total
Coloring Conjecture (TCC)) that for every graph $G$,
$\chi^{\prime\prime}(G)\leq\Delta+2$. The total coloring conjecture is a long
standing conjecture and has defied several attempts in a complete proof. It is
also proved that the decidability algorithm for total coloring is NP-complete
even for cubic bipartite graph [17]. But still, a lot of progress has been
made in proving the TCC. It is easily seen to be true for complete graphs,
bipartite, complete multipartite graphs. It was also showed to be true for all
graphs with degree $\Delta\leq 5$ and $\Delta\geq n-5$, where $n$ is the
number of vertices, using techniques like enlarge-matching argument and fan
recoloring process [20]. For planar graphs, TCC is proved for all $\Delta\neq
6$ using discharging and charging methods. The total coloring conjecture has
also been proved for several other classes of graphs. Good survey of
techniques and other results on total coloring can be found in Yap [20],
Borodin [4] and Geetha et al. [11]

##  2 Total Colorings of Cayley Graphs

Cayley graphs are those whose vertices are the elements of groups and
adjacency relations are defined by subsets of the groups. Let $\Gamma$ be a
multiplicative group with identity 1. For $S\subseteq\Gamma,1\notin S\text{
and }S^{-1}=\\{s^{-1}:s\in S\\}=S$ the Cayley Graph $X=Cay(\Gamma,S)$ is the
undirected graph having vertex set $V(X)=\Gamma$ and edge set
$E(X)=\\{(a,b):ab^{-1}\in S\\}$. The Cayley graph associated with
$\Gamma=\mathbb{Z}_{n}$, the group of integers modulo $n$ under addition
operation, is called a circulant graph. Note that the powers of cycle graph is
a circulant graph with the generating set
$S=\\{1,2,\ldots,k,n-k,\ldots,n-2,n-1\\}.$ All Cayley graphs are vertex
transitive.

In other words, given a sequence of positive integers $1\leq
d_{1}<d_{2}<...<d_{l}\leq\lfloor\frac{n}{2}\rfloor$, the circulant graph
$G=C_{n}(d_{1},d_{2},...,d_{l})$ has vertex set $V=Z_{n}=\\{0,1,2,...,n-1\\}$,
two vertices $x$ and $y$ being adjacent iff $x=(y\pm d_{i})\mod n$ for some
$i,1\leq i\leq l$ and a graph is a power of cycle, denoted $C^{k}_{n}$, $n$
and $k$ are integers, $1\leq k<\lfloor\frac{n}{2}\rfloor$, if
$V(C^{k}_{n})=\\{v_{0},v_{1},...,v_{n-1}\\}$ and $E(C^{k}_{n})=E^{1}\cup
E^{2}\cup...\cup E^{k}$, where
$E^{i}=\\{e_{0}^{i},e_{1}^{i},...,e^{i}_{n-1}\\}$ and
$e_{j}^{i}=(v_{j},v_{(j+i)\mod\ n})$ and $0\leq j\leq n-1$, and $1\leq i\leq
k$.

Campos and de Mello [6] proved that $C_{n}^{2},n\neq 7$, is type-I and
$C_{7}^{2}$ is type-II. They [5] verified the TCC for power of cycle
$C_{n}^{k},n$ even and $2<k<\frac{n}{2}$ and also showed that one can obtain a
$\Delta(C_{n}^{k})+2$-total coloring for these graphs in polynomial time. They
also proved that $C_{n}^{k}$ with $n\cong 0\mod(\Delta(C_{n}^{k})+1)$ are
type-I and they proposed the following conjecture.

######  Conjecture 2.1.

Let $G=C_{n}^{k}$, with $2\leq k<\lfloor\frac{n}{2}\rfloor$. Then,

$\chi^{\prime\prime}(G)=\begin{cases}\Delta(G)+2,&\text{ if
}k>\frac{n}{3}-1\text{ and }n\text{ is \ odd}\\\ \Delta(G)+1,&\text{
otherwise}.\end{cases}$

Recently, Zorzi et al. [21] proved the conjecture for certain classes of power
of cycle graphs. In particular, for even $k$ and large $n$ the conjecture is
true.

A latin square is an $n\times n$ array consisting of $n$ entries of numbers
(or symbols) with each row and column containing only one instance of each
element. This means the rows and columns are permutations of one single $n$
vector with distinct entries. A latin square is said to be commutative if it
is symmetric. A latin square containing numbers is said to be idempotent if
each diagonal element contains the number equal to its row (column) number. In
addition, if the rows of the latin square are just cyclic permutations (one-
shift of the elements to the right) of the previous row, then the latin square
is said to be circulant (anti-circulant, if the cyclic permutations are
actually left shifts), the matrix (corresponds to the latin square) can be
generated from a single row vector. The latin square

1 | k+2 | 2 | k+3 | … | 2k+1 | k+1
---|---|---|---|---|---|---
k+2 | 2 | k+3 | 3 | … | k+1 | 1
… | … | … | … | … | … | …
… | … | … | … | … | … | …
k+1 | 1 | k+2 | 2 | … | k | 2k+1

is anti-circulant, commutative and idempotent. The entries of the square are
as follows:

$L=(l_{ij})=\begin{cases}m,\ \text{ if }\ i+j=2m\\\ k+1+m,\
\text{otherwise.}\end{cases}$

From the above, it can be easily seen that the latin square corresponding to
the matrix $L$ is commutative, idempotent and also anti-circulant.

Campos and de Mello [6], proved the TCC for the powers of cycles of even
order. In the following theorems, using latin squares we prove some classes of
powers of cycles of even order are Type 1.

######  Theorem 2.1.

Let $G$ be a power of cycle graph $C_{n}^{k}$ with
$k=\frac{n-2}{4}+k^{\prime}$ with $n,k,k^{\prime}$ being non-negative integers
with $n\geq 4$, $n$ even and $gcd(n,x)=1$, $\frac{n-2}{4}<x<k^{\prime}$. Then,
$G$ is a type I graph.

###### Proof.

The adjacency matrix of a power of cycle graph $C_{n}^{k}$ (or, in fact, any
circulant graph) is a symmetric circulant matrix $C=(c_{ij})$ with $1$’s when
$i,j$ differ by $s$, where $s\in S$, the generating set of the Cayley graph
$C_{n}^{k}$. For example, the adjacency matrix of $C_{10}^{2}$ is

$A(C_{10}^{2})=$ $\ytableau 0&110000011\\\ 1011000001\\\ 1101100000\\\
0110110000\\\ 0011011000\\\ 0001101100\\\ 0000110110\\\ 0000011011\\\
1000001101\\\ 1100000110$.

We know that $\Delta(C_{n}^{k})=2k$. For giving a total $2k+1$ coloring of
$C_{n}^{k}$ in the case $k=\frac{n-2}{4}$, where $n,k$ are non-negative
integers, $n$ is even, we form the color matrix (a matrix which gives the
color of the vertices in the diagonals and the color corresponding to edges in
the other entries) by first filling the non-zero entries and diagonal entries
in the first $(k+1)\times n$ submatrix of the color matrix with the
corresponding entries of the first $k+1$ rows of the latin square. The first
non-zero entry of the $k+2$-th row of the color matrix is determined by the
$k+2$-th entry of the $2$-nd row of the color matrix (as the color matrix is
symmetric). The next non zero entries of the $k+2$-th row are determined by
the cyclic order of the previous rows. Similarly we determine the non-zero
entries of remaining rows (the first entry determined by the symmetric
property of the color matrix and the next entries determined by the cyclic
order of the previous rows). Thus continuing, we can fill all the entries of
the color matrix satisfying the total coloring conditions, giving us a $2k+1$
total coloring. For example, the $(5\times 5)$ anti-circulant, commutative and
idempotent latin square is

1 | 4 | 2 | 5 | 3
---|---|---|---|---
4 | 2 | 5 | 3 | 1
2 | 5 | 3 | 1 | 4
5 | 3 | 1 | 4 | 2
3 | 1 | 4 | 2 | 5

Now, this corresponds to $k=2$ (as $2k+1=5$). Thus, the filled color matrix
for $C_{10}^{2}$ (where $n=10=2(2(2)+1)=2(2k+1)$) is:

$\ytableau 1&420000053\\\ 4253000001\\\ 2531400000\\\ 0314250000\\\
0042531000\\\ 0005314200\\\ 0000142530\\\ 0000025314\\\ 5000003142\\\
3100000425$

which is seen to a $2k+1=5$-total coloring. Note that $0$-s do not constitute
colors in the above color matrix.

We see that the powers of cycles graph $C_{n}^{k}$,
$k=\frac{n-2}{4}+k^{\prime}$ is a disjoint union of $C_{n}^{\frac{n-2}{4}}$
and a circulant graph. When $\frac{n-2}{4}<k<\frac{n}{2}$ the edge disjoint
graph that is added to $C_{n}^{\frac{n-2}{4}}$ is a class I graph (as the edge
disjoint graph added is a circulant graph, which is edge colorable by $\Delta$
colors, if the generating set of the graph is also a generating set of the
group, which is guaranteed if $gcd(n,x)=1$, where $\frac{n-2}{4}<x<k^{\prime}$
; the graph is edge colorable with $\Delta$ colors, where $\Delta$ be the
maximum degree of the edge disjoint graph added [18]). Now, since in a type I
total coloring of $C_{n}^{\frac{n-2}{4}}$, we have given $\frac{n}{2}$ colors
to the vertices and $\chi(C_{n}^{k})\leq\frac{n}{2}$ (since the vertices can
always be arranged into independent sets as
$[0,\frac{n}{2}],[1,\frac{n}{2}+1],\ldots,[k,n-1]$ provided $k<\frac{n}{2}$),
we need to only give a coloring to the edges of the remaining (added)
circulant graph, which is seen to require only $\Delta$ extra colors. Thus the
total coloring of the graph $C_{n}^{k}$ is again seen to require only
$2\left(\frac{n-2}{4}\right)+1+\Delta=2\left(\frac{n-2}{4}\right)+2k^{\prime}+1=2k+1$
colors.

∎

######  Theorem 2.2.

Let $G$ be a powers of cycle graph $C_{n}^{k}$ with $n=s(2m+1)$, with $s$
being even and $2m+1-i=k\,,1\leq i\leq k+1$. Then the graph $C_{n}^{k}$ is
total colorable with $2k+1$ colors.

###### Proof.

We observe that $n\equiv 0\bmod(k+i)$ with $1\leq i\leq k+1$. We also know
that there exists a commutative idempotent latin square of odd order, $k+i$ in
this case, which we call $C^{\prime}$. Now, we consider two tableau of the
form
Tableau $B^{\prime}$:

$2m+2$ $2m+3$ $2m+2$ $2m+4$ $2m+3$ $2m+2$ … … … $2m+2$ $2k+1$ … … … $2m+2$

Tableau $A^{\prime}$:

$2k+1$ $2k$ $2k-1$ $\ldots$ $2m+2$ $2k+1$ $2k$ $\ldots$ $2m+3$ $2k+1$ $2k$
$\ldots$ $\ldots$ $\ldots$ $\ldots$ $2k+1$ $2k$ $\ldots$ $\ldots$ $\ldots$
$2k+1$

Now, arranging the two tableau and the idempotent and commutative latin square
of order $k+1$ in the below fashion, would give us the color matrix desired,
with $2k+1$ colors. The portion $C$ is the portion of the latin square
$C^{\prime}$ which fits in the color matrix.

$C$ |  $B$ |  |  |  |  $A$
---|---|---|---|---|---
$B^{T}$ | C |  $A^{T}$ |  |  |
|  $A$ | C |  $B$ |  |
|  |  $B^{T}$ | C |  $A^{T}$ |
|  |  |  $A$ | C |  $B$
$A^{T}$ |  |  |  |  $B^{T}$ | $C$

In case $i=1$, the entries of $C^{\prime}$ are written wholly, so that the
tableau $A^{\prime}$ and $B^{\prime}$ are equal to the tableau $A$ and $B$. In
case $i>1$, the tableau $A^{\prime}$ and $B^{\prime}$ could be modified to
accommodate the missed numbers in the color matrix, which are deleted from the
commutative idempotent latin square $C^{\prime}$ That is, the portion of the
$k+i$ latin square starting from the $(k+2)^{nd}$ position in the first row,
$(k+3)^{rd}$ position in the second row and so on, is cut and juxtaposed on
the tableau $A^{\prime}$ and $B^{\prime}$ to give us the tableau $A$ and $B$.
In particular, if $i=k+1$, the tableau $A^{\prime}$ and $B^{\prime}$ are
wholly replaced with the portions deleted from the latin square $C^{\prime}$.
The portion deleted from the latin square, in case $i>1$ would be $D^{\prime}$
and its transpose, where $D$ given by:

$e_{1,k+2}$ $e_{1,k+3}$ $\ldots$ $\ldots$ $e_{1,k+i}$ $e_{2,k+3}$ $e_{2,k+4}$
$\ldots$ $e_{2,k+i}$ $\ldots$ $\ldots$ $e_{3,k+i}$ $\ldots$ $e_{4,k+i}$
$e_{k+i,k+i}$ ,

where $e_{ij}$ denote the entries of the latin square $C^{\prime}$.

Say, for example, for the color matrix of the graph $C_{20}^{4}$, since
$20=2(4+1)=2(2m+1)$ for $m=2$, we take $C^{\prime}$ to be
1 4 2 5 3 4 2 5 3 1 2 5 3 1 4 5 3 1 4 2 3 1 4 2 5

$A$ to be

9 8 7 6 9 8 7 9 8 9

and $B$ to be

6 7 6 8 7 6 9 8 7 6

Therefore, the color matrix desired is:

1 4 2 5 3 9 8 7 6 4 2 5 3 1 6 9 8 7 2 5 3 1 4 7 6 9 8 5 3 1 4 2 8 7 6 9 3 1 4
2 5 9 8 7 6 6 7 8 9 1 4 2 5 3 6 7 8 4 2 5 3 1 9 6 7 2 5 3 1 4 8 9 6 5 3 1 4 2
7 8 9 3 1 4 2 5 6 7 8 9 9 8 7 6 1 4 2 5 3 9 8 7 4 2 5 3 1 6 9 8 2 5 3 1 4 7 6
9 5 3 1 4 2 8 7 6 3 1 4 2 5 9 8 7 6 6 7 8 9 1 4 2 5 3 9 6 7 8 4 2 5 3 1 8 9 6
7 2 5 3 1 4 7 8 9 6 5 3 1 4 2 6 7 8 9 3 1 4 2 5

For the case of the color matrix of the graph $C_{18}^{5}$, since
$18=2(8+1)=2(2m+1)$ for $m=4$ we have $C^{\prime}$ to be

1 6 2 7 3 8 4 9 5 6 2 7 3 8 4 9 5 1 2 7 3 8 4 9 5 1 6 7 3 8 4 9 5 1 6 2 3 8 4
9 5 1 6 2 7 8 4 9 5 1 6 2 7 3 4 9 5 1 6 2 7 3 8 9 5 1 6 2 7 3 8 4 5 1 6 2 7 3
8 4 9

$A$ to be

11 10 4 9 5 11 10 5 1 11 10 6 11 10 11

and $B$ to be

10 11 10 4 11 10 9 5 11 10 5 1 6 11 10

Therefore, the color matrix would be

1 6 2 7 3 8 11 10 4 9 5 6 2 7 3 8 4 9 11 10 5 1 2 7 3 8 4 9 5 1 11 10 6 7 3 8
4 9 5 1 6 2 11 10 3 8 4 9 5 1 6 2 7 10 11 8 4 9 5 1 6 2 7 3 11 10 9 5 1 6 2 7
3 8 4 11 10 1 6 2 7 3 8 4 9 5 11 10 2 7 3 8 4 9 5 1 6 11 10 10 11 4 9 5 1 6 2
7 3 8 10 11 5 1 6 2 7 3 8 4 9 10 11 6 2 7 3 8 4 9 5 1 10 11 7 3 8 4 9 5 1 6 2
11 10 3 8 4 9 5 1 6 2 7 10 11 8 4 9 5 1 6 2 7 3 4 10 11 9 5 1 6 2 7 3 8 9 5 10
11 1 6 2 7 3 8 4 5 1 6 10 11 2 7 3 8 4 9

∎

######  Theorem 2.3.

Let $G$ be a power of cycle graph $C_{n}^{k}$ with $n=s(2m+1)\pm 1$, with $s$
being even and $m$ being positive integers $\frac{k}{2}<m<k$ and $k=2m+1-i$.
Then the graph $C_{n}^{k}$ is total colorable with $2k+2$ colors. In fact,
$\chi^{\prime\prime}(C_{n}^{k})\leq 2k+3$.

###### Proof.

Case 1: $n=s(2m+1)-1$
From the previous theorem, it is clear that $C_{n+1}^{k}$ is $2k+1$ colorable.
It remains to show that this coloring could be extended to a $2k+2$ coloring
for $C_{n}^{k}$. The extension is made possible by deleting last row and last
coloumn of the color matrix of $C_{n+1}^{k}$ and appropriately adding a new
color in the lower and upper $(n-k+1)^{th}$ subdiagonal of the color matrix so
as to obtain the desired color matrix with $2k+2$ colors.
This method of extension applies to any powers of cycle graph of any odd
order. Since it is already proved that the even order powers of cycles satisfy
a type II coloring, therefore, by extension, since we require only one extra
color, the total chromatic number of the graph is $2k+3$.

For example, the color matrix below for $C_{14}^{3}$

1 5 2 6 3 7 4 5 2 6 3 7 4 1 2 6 3 7 4 1 5 6 3 7 4 1 5 2 7 4 1 5 2 6 3 1 5 2 6
3 7 4 2 6 3 7 4 1 5 3 7 4 1 5 2 6 4 1 5 2 6 3 7 5 2 6 3 7 4 1 6 3 7 4 1 5 2 3
7 4 1 5 2 6 7 4 1 5 2 6 3 4 1 5 2 6 3 7

is modified to that of $C_{13}^{3}$ by deletion of one row and column and
addition of the appropriate color to:
1 5 2 6 ⑧ 3 7 5 2 6 3 7 ⑧ 4 2 6 3 7 4 1 ⑧ 6 3 7 4 1 5 2 7 4 1 5 2 6 3 1 5 2 6
3 7 4 2 6 3 7 4 1 5 3 7 4 1 5 2 6 4 1 5 2 6 3 7 5 2 6 3 7 4 1 ⑧ 6 3 7 4 1 5 3
⑧ 7 4 1 5 2 7 4 ⑧ 1 5 2 6

The encircled number is the added color to the color matrix.

Case 2:$n=s(2m+1)+1$.
Here, we add a row and a column at the last and then add entries in the last
row and last column which are the $k$ deleted entries each from the lower and
upper $k^{th}$ and $(n-k+1)^{th}$ subdiagonal of the original color matrix of
$C_{n-1}^{k}$. In place of the entries deleted in the $k^{th}$ subdiagonal, we
add a new color. The new vertex is also given the new color. For example, the
color matrix can be modified by adding one row and column to give the color
matrix of $C_{15}^{3}$ as follows:
1 5 2 ⑧ ⃝ 7 4 ⑥ 5 2 6 3 ⑧ ⃝ 1 ⑦ 2 6 3 7 4 ⑧ ⃝ ① ⑧ 3 7 4 1 5 2 ⑧ 4 1 5 2 6 3 ⑧
5 2 6 3 7 4 2 6 3 7 4 1 5 3 7 4 1 5 2 6 4 1 5 2 6 3 7 5 2 6 3 7 4 1 6 3 7 4 1
5 2 ⃝ 7 4 1 5 2 6 ③ 7 ⃝ 1 5 2 6 3 ④ 4 1 ⃝ 2 6 3 7 ⑤ ⑥ ⑦ ① ③ ④ ⑤ ⑧

The encircled numbers show the changes from the color matrix of $C_{14}^{3}$ ∎

######  Theorem 2.4.

Let $G$ be the cayley graph of a nilpotent group of even order $n$ with
maximum degree $\Delta(G)\geq\frac{n}{2}$ and the generating set $S$ not
containing an element of order two. If $G$ is total colorable with
$\chi^{\prime\prime}(G)$ colors and if $G^{\prime}$ is the cayley graph of
nilpotent group of even order graph with maximum degree $\Delta(G^{\prime})$,
$\Delta(G)\leq\Delta(G^{\prime})\leq n-2$ formed by with generating set
$S^{\prime}=S\cup S^{\prime\prime}$ such that $S^{\prime\prime}$ which
generates the whole group and also does not have an order two element, then
graph $G^{\prime}$ is total colorable with
$\chi^{\prime\prime}(G)+(\Delta(G^{\prime})-\Delta(G))$ colors. In particular,
if $G$ is type I (type II), then $G^{\prime}$ is also type I (type II).

###### Proof.

Let $s$ be an element of order two in the graph (which is guaranteed by
Cauchy’s theorem). Since the vertices of the graph $g_{i},\ \
i\in\\{1,2,\ldots,n\\}$ can always be arranged in $\frac{n}{2}$ independent
color classes as
$[g_{1},g_{1}s],[g_{2},g_{2}s],\ldots,[g_{\frac{n}{2}},g_{\frac{n}{2}}s]$,
this gives us a $\frac{n}{2}$ coloring of the vertices. Therefore, we need to
take care only of the edge coloring of the graph $G^{\prime}-G$ in order to
give a total coloring of $G^{\prime}$ from the existing total coloring of $G$.
Now, since $G^{\prime}-G$ is $1-$ factorizable [18], therefore, we only need
$\Delta^{\prime}-\Delta$ extra colors, thereby giving a total coloring of
$\chi^{\prime\prime}+(\Delta^{\prime}-\Delta)$. Thus, if $G$ were a type I(
type II) graph, then $G^{\prime}$ also would be type I( type II). ∎

For a positive integer $n>1$ the unitary Cayley graph $X_{n}=Cay(Z_{n},U_{n})$
is defined by the additive group of the ring $Z_{n}$ of integer modulo $n$ and
the multiplicative group $U_{n}$ of its units. If we represent the elements of
$Z_{n}$ by the integers 0,1,…$n-1$, then it is well known that

$U_{n}=\\{a\in Z_{n}:gcd(a,n)=1\\}$.

So $X_{n}$ has vertex set $V(X_{n})=X_{n}=\\{0,1,2,...,n-1\\}$ and edge set

$E(X_{n})=\\{(a,b):a,b\in Z_{n},gcd(a-b,n)=1\\}$.

Boggess et al. [3] studied the structure of unitary Cayley graphs. They have
also discussed chromatic number, vertex and edge connectivity, planarity and
crossing number. Klotz and Sander [16] have determined the clique number, the
independence number and the diameter. They have given a necessary and
sufficient condition for the perfectness of $X_{n}$.

The graph $X_{n}$ is regular of degree $U_{n}=\varphi(n)$ denotes the Euler
function. Let the prime factorization of $n$ be
$p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{t}^{\alpha_{t}}$ where
$p_{1}<p_{2}<...<p_{t}$. If $n=p$ is a prime number, then $X_{n}=K_{p}$ is the
complete graph on $p$ vertices. If $n=p^{\alpha}$ is a prime power then
$X_{n}$ is a complete $p$-partite graph. In the following theorem we prove TCC
holds for unitary Cayley graphs.

######  Theorem 2.5.

A unitary Cayley graph $X_{n}$ is $(\Delta(X_{n})+2)$ \- total colorable.

###### Proof.

We know that a unitary Cayley graph can be obtained from a balanced $r$
partite graph by deleting some edges. Suppose $n=p$ is a prime number, then
$X_{n}$ is the complete graph on $p$ vertices. Also, if $n=p^{\alpha}$, a
prime power, then $X_{n}$ is a complete $p$-partite graph and TCC holds for
these two graphs [20].

When $n=2k,k\in N$, then the unitary Cayley graph is a bipartite graph and any
bipartite graph is total colorable.

Suppose $n\not\equiv 0\mod 2$. As $p_{1}$ is the smallest prime,
$kp_{1},kp_{1}+1,...,(k+1)p_{1}-1,$ where $k=0,1,2,...,\frac{n}{p_{1}}-1$
induces $\frac{n}{p_{1}}$ vertex disjoint cliques each of order $p_{1}$. Since
$p_{1}$ is odd, we can color all the elements of these $\frac{n}{p_{1}}$
cliques using $p_{1}$ colors [79]. Now remove the edges of these cliques. The
remaining graph is a $\varphi(n)-p_{1}+1$-regular graph where the vertices are
already coloured. We color the edges of this resultant graph with
$\varphi(n)-p_{1}+2$ colors. Thus we have used $\varphi(n)+2$ colors for the
total coloring of $X_{n}$. ∎

##  3 Mock Threshold Graphs and Odd Graphs

A graph is weakly chordal if neither the graph nor the complement of the graph
has an induced cycle on five or more vertices. A simple graph $G$ on
$[n]=\\{1,2,...,n\\}$ is threshold, if $G$ can be built sequentially from the
empty graph by adding vertices one at a time, where each new vertex is either
isolated (nonadjacent to all the previous) or dominant (connected to all the
previous). A graph $G$ is said to be mock threshold if there is a vertex
ordering $v_{1},...,v_{n}$ such that for every $i\ (1\leq i\leq n)$ the degree
of $v_{i}$ in $G:{v_{1},...,v_{i}}$ is 0, 1, $i-2$, or $i-1$. Mock threshold
graphs are a simple generalization of threshold graphs that, like threshold
graphs, are perfect graphs. Mock threshold graphs are perfect and indeed
weakly chordal but not necessarily chordal [1]. Similarly, the complement of a
mock threshold graph is also mock threshold.

In the following, we prove the TCC for Mock Threshold graphs.

Note: A total coloring of $K_{n}$ can be constructed as follows: (This total
coloring is due to Hinz and Parisse [13])

When $n$ is even, we first construct an edge coloring of $K_{n}$ and extend
it. We denote $[n]_{0}=\\{0,1,2,...,n-1\\}$. For $k\in[n]_{0}$, let $\tau_{k}$
be the transposition of $k$ and $n-1$ on $[n]_{0}$. For even $n$,
$c_{n}(i,j)=(\tau_{i}(j)+\tau_{j}(i)+2)\mod(n+1)$, for $i,j\in[n]_{0},i\neq
j$, defines a $(n+1)$-edge coloring. In this coloring assignment line
$k\in[n]_{0}$ will have the missing colors $k$ and $(k+1)\mod n$. We color
$c_{n}(i)=i$ for all $i\in[n]_{0}$.

When $n$ is odd, we use the same coloring of $K_{n-1}$. In the coloring
assignment of $K_{n-1}$, still the color $(k+1)\mod n$ is missing in line
$k\in[n]_{0}$. We use these colors to the edges incident with $n^{th}$ vertex
and color $n$ to the $n^{th}$ vertex.

######  Theorem 3.1.

Total coloring conjecture holds for any Mock threshold graph $G$.

###### Proof.

Consider the Mock threshold graph $G$ with vertex ordering
$v_{1},v_{2},...,v_{i},...,v_{n}$.

We prove this theorem using mathematical induction on the induced subgraph
$G[v_{1},v_{2},...,v_{k}]$.

For $k\leq 4$, the maximum degree of all the induced subgraphs is less than or
equal to 3. We know that a graph with maximum degree less than or equal to 3
satisfies TCC [15].

Let us assume that $G[v_{1},v_{2},...,v_{k}],k\geq 5$ satisfies TCC.

Claim: The graph $G[v_{1},v_{2},...,v_{k},v_{k+1}]$ satisfies TCC.

The degree of the vertex $v_{k+1}$ in $G[v_{1},v_{2},...,v_{k+1}]$ can be
$0,1,k-1$ or $k$.

Case-1: Suppose $d(v_{k+1})=0$.

In this case the vertex is $v_{k+1}$ is an isolated vertex. By the induction
assumption, $G[v_{1},v_{2},...,v_{k},v_{k+1}]$ satisfies TCC.

Case-2: Suppose $d(v_{k+1})=1$.

In this case, the vertex $v_{k+1}$ is adjacent to a vertex, say $v_{i}$, in
$G[v_{1},v_{2},...,v_{k}]$. Since $G[v_{1},v_{2},...,v_{k}]$ is total
colorable graph with at most $\Delta(G[v_{1},v_{2},...,v_{k}])+2$ colors, at
each vertex there will be at least one missing color. We assign this missing
color to the edge $(v_{i},v_{k+1})$, and for the vertex $v_{k+1}$, we assign a
color of a vertex which is not adjacent to $v_{k+1}$ and not the color of
$v_{i}$. Therefore, $G[v_{1},v_{2},...,v_{k+1}]$ satisfies TCC.

Case-3: Suppose $d(v_{k+1})=k-1$.

Let us assume that the vertex $v_{k+1}$ is not adjacent with $v_{i}$ and also
assume that
$\Delta(G[v_{1},v_{2},...,v_{k+1}])=k-1$. We consider following two cases:

Subcase-1: $k$ is even.

Since $k$ is even, $k+1$ is odd. Construct a complete graph induced by the
vertices $v_{1},v_{2},...v_{i-1},v_{i+1},...,v_{k+1}$. Now, color this
complete graph using colors in the set $\\{0,1,...,n+1\\}$ as given in the
note. In this coloring assignment there will be one missing color at each of
the vertices and they are distinct. Now, color the edges $(v_{i},v_{j}),i\neq
j,j=1,2,...,v_{k+1}$, with the missing colors. Assign the color $n-1$ to the
vertex $v_{i}$. To get a total coloring of $G[v_{1},v_{2},...,v_{k},v_{k+1}]$,
we remove these edges and there is no change in the maximum degree.

Subcase-2: $k$ is odd.

In this case $k+1$ is even, say $2p$. It is known that a graph of order $2p$
with maximum degree $2p-2$ satisfies TCC (see [12, 7]).

Case-4: Suppose $d(v_{k+1})=k$.

The maximum degree of $G[v_{1},v_{2},...,v_{k},v_{k+1}]$ is $k$. Construct a
complete graph on the vertex set $\\{v_{1},v_{2},...,v_{k},v_{k+1}\\}$. We
know that the complete graph satisfies TCC. After removing the added edges we
get a total coloring of $G[v_{1},v_{2},...,v_{k},v_{k+1}]$

Hence, in all the cases, the mock threshold graph satisfies TCC.

∎

The Kneser graph $K(n,k)$ is the graph whose vertices correspond to the
$k$-element subsets of a set of $n$ elements, and where two vertices are
adjacent if and only if the two corresponding sets are disjoint. A vertex in
the odd graph $O_{n}$ is a $(n-1)$-element subset of a $(2n-1)$-element set.
Two vertices are connected by an edge if and only if the corresponding subsets
are disjoint. Note that the odd graphs are particular case of Kneser graphs.

######  Theorem 3.2.

Odd graph $O_{n}$ satisfies TCC.

###### Proof.

Consider a $2n-1$ element set $X$. Let $O_{n}$ be an odd graph defined from
the subsets of $X$. Let $x$ be any element of $X$. Then, among the vertices of
$O_{n}$, exactly $\binom{2n-2}{n-2}$ vertices correspond to sets that contain
$x$. Because all these sets contain $x$, they are not disjoint, and form an
independent set of $O_{n}$. That is, $O_{n}$ has $2n-1$ different independent
sets of size $\binom{2n-2}{n-2}$. Further, every maximum independent set must
have this form, so, $O_{n}$ has exactly $2n-1$ maximum independent sets.

If $I$ is a maximum independent set, formed by the sets that contain $x$, then
the complement of $I$ is the set of vertices that do not contain $x$. This
complementary set induces a matching in $G$. Each vertex of the independent
set is adjacent to $n$ vertices of the matching, and each vertex of the
matching is adjacent to $n-1$ vertices of the independent set [8].

Based on the decomposition, we give a total coloring of $O_{n}$ in the
following way:

Assign $n$ colors to the edges between the vertices in the maximum independent
set $I$ and the vertices in the matching. Color the edges in matching and the
vertices in $I$ with a new color. Color one set of vertices in the matching
with another new color and the second set of vertices with the missing colors
at these vertices. This will give a total coloring of $O_{n}$ using at most
$n+2=\Delta(O_{n})+2$ colors.

∎

Acknowledgements: This research work was supported by SERB, India (No.SERB:
EMR/2017/001869).

## References

  * [1] R. Behr, V. Sivaraman, and T. Zaslavsky. Mock threshold graphs. Discrete Mathe- matics, 341(8):2159–2178, 2018.
  * [2] M. Behzad, Graphs and their chromatic numbers, Doctoral Thesis, Michigan State University, 1965.
  * [3] M. Boggess, T. J. Henderson, I. Jimenez, and R. Karpman. The structure of unitary cayley graphs, technical report. semanticscholar.org, 2008.
  * [4] O. V. Borodin, On the total colouring of planar graphs, J. Reine Angew. Math.394, 180–185, 1989.
  * [5] C.N. Campos and C.P. de Mello, Total colouring of $C^{2}_{n}$, Tendencias em Matematica Aplicada e Computacional, 4(2),177–186, 2003.
  * [6] C.N. Campos and C.P. de Mello, A result on the total colouring of powers of cycles, Discrete Applied Mathematics, 155(5), 585–597, 2007.
  * [7] B. L. Chen and H. L. Fu. Total colorings of graphs of order 2n having maximum degree $2n-2$. Graphs and Combinatorics, 8(2):119–123, 1992.
  * [8] C. D. Godsil. More odd graph theory. Discrete Mathematics, 32(2):205–207, 1980.
  * [9] C. Godsil. and G. F. Royle, G, Algebraic graph theory, Vol. 207, Springer-Verlag New York, 2001.
  * [10] J. H. Colin McDiarmid and A. S. Arroyo, Total coloring regular bipartite graphs is NP-hard, Discrete Mathematics, 124, 155-162, 1994.
  * [11] J. Geetha, N. Narayanan and K. Somasundaram, Total coloring- A Survey, https://arxiv.org/abs/1812.05833.
  * [12] A. J. W. Hilton. A total-chromatic number analogue of plantholt’s theorem. Discrete mathematics, 79(2):169–175, 1990.
  * [13] A. M. Hinz and D. Parisse. Coloring hanoi and sierpinski graphs. Discrete Mathematics, 312(9):1521–1535, 2012.
  * [14] H. A. Kierstead and A.V. Kostochka, A short proof of the Hajnal–Szemerédi theorem on equitable colouring, Combinatorics, Probability and Computing 17.2, 265-270, 2008.
  * [15] A. V. Kostochka. The total chromatic number of any multigraph with maximum degree five is at most seven. Discrete Mathematics, 162(1-3):199–214, 1996.
  * [16] W. Klotz and T. Sander. Some properties of unitary cayley graphs. The electronic journal of combinatorics, 14(1):45, 2007.
  * [17] A. Sánchez-Arroyo, Determining the total colouring number is NP-hard, Discrete Mathematics, 78(3), 315-319, 1989\.
  * [18] R. A. Stong, On 1-factorizability of Cayley graphs, Journal of Combinatorial Theory, Series B, 39(3),298-307, 1985.
  * [19] V. G. Vizing, Some unsolved problems in graph theory (in Russian),UspekhiMat. Nauk.(23) 117–134; English translation in Russian Math. Surveys23(1968), 125–141.
  * [20] H. P. Yap, Total Colourings of Graphs, Lecture Notes in Mathematics, Vol.1623, Springer, Berlin, 1996.
  * [21] Zorzi, Alesom, Celina de Figueiredo, Raphael Machado, and Uéverton S. Souza. ”Even-power of Cycles With Many Vertices are Type 1 Total Colorable.” Electronic Notes in Theoretical Computer Science 346 (2019): 747-758.


<EMAIL_ADDRESS>
# On the Development of Intelligent Agents for MOBA Games

Victor do Nascimento Silva and Luiz Chaimowicz

Department of Computer Science
Universidade Federal de Minas Gerais - Brazil

###### Abstract

Multiplayer Online Battle Arena (MOBA) is one of the most played game genres
nowadays. With the increasing growth of this genre, it becomes necessary to
develop effective intelligent agents to play alongside or against human
players. In this paper we address the problem of agent development for MOBA
games. We implement a two-layered architecture agent that handles both
navigation and game mechanics. This architecture relies on the use of
Influence Maps, a widely used approach for tactical analysis. Several
experiments were performed using League of Legends as a testbed, and show
promising results in this highly dynamic real-time context.

###### keywords:

Multiplayer Online Battle Arena, Influence Maps, Tactics

##  1 Introduction

The development of tactical movement systems is still a challenging task in
game AI. This is especially true when dealing with competitive or combat
scenarios. Behaving in a logical way in these cases could be very hard and
require heavy computation and domain knowledge. Thus, it is necessary to
collect data and deal with uncertainty when controlling agents in these
scenarios to be able to behave in a competitive way.

Researching tactical analysis can benefit not just games but areas like
military analysis, robotics and traffic. Moreover, any area with partial
information and dynamic environment can implement the techniques of tactical
analysis towards improving agent behavior.

In game research, the problem of navigating in a combat scenario can be
tackled by the development of specific strategies and tactical analysis.
Furthermore, the tactical analysis field has gained much attention, as games
become more complex. Tactical analysis was already performed in some agents,
like Starcraft agents and ORTS competitions [Hagelbäck and Johansson
2008b],[Uriarte and Ontañón 2012].

Another point that must be discussed is that MOBA is one of most played games
of actuality, having almost 30% of online computing gameplay time
111http://bit.ly/1OopRvh. However, there is not much attention from
researchers over this game genre. Characteristics like the continuous updates
can be cited as one of the causes of the low research rate over this domain.
We aim to encourage researchers to use MOBA as a domain as testbed for their
future research, providing gathered knowledge about this domain.

Games are a good option to serve as testbed for the development of AI. Having
a limited environment that can reproduce almost all characteristics of the
real world helps the research to perform reliable tests [Adobbati et al.
2001]. Games also provides an environment where winning, losing or drawing
have well-defined rules, making it easy for AI to evaluate these criteria.
Developing and testing AI algorithms in a game environment can benefit
research by reducing the costs of test and real world resources.

Selecting a platform for testbed in AI research can be a hard task, especially
when considering that most MOBA games are commercial. We considered several
games in our initial research phase and ended with two main options: Heroes of
Newerth (HoN) and League of Legends222http://www.riotgames.com/our-games
(LoL). When choosing between these two platforms we considered: (a) ease of
implementation, in terms of language and documentation; (b) game community, in
terms of number of players. Given these characteristics, we chose to develop
our research using League of Legends as testbed.

In addition, real-time games are gaining much attention in recent years. We
observe the growing of intelligent agents development for these games, like
Starcraft. Moreover, there have been competitions using such agents, like the
AIIDE and the CIG Starcraft agents competition [Ontanón et al. 2013]. However,
in contrast to the popularity of MOBA, there is not a great attention related
to this genre.

In this paper we address the problem of tactical analysis and navigation in
combat scenarios. For doing so, we use a widely popular MOBA game, League of
Legends, as testbed. Our approach consists in the development of an
Intelligent Agent that aims to behave competitively in the chosen domain.
Further, we implement a multi-layered architecture agent using Influence Maps
(IM) and real-time reasoning. In addition we collect and provide information
about the MOBA domain and we encourage researchers to adopt MOBA as their
research domain.

In short, our contributions in this work are:

  * •

We present MOBA games as testbed for AI;

  * •

Implementation of an game agent capable of winning the game;

  * •

An architecture for the game agent based in tactical analysis;

  * •

Our agent was capable of emerging the kiting behaviour without a dedicated
module.

The rest of this paper is organized as follows: Section 2 introduces basic
concepts about Tactical Analysis techniques, MOBA domain and LoL. In this
section we also discuss related work in agent development and MOBA. Section 3
presents the architecture of the agent implemented, showing its
characteristics and layers. Experiments performed for evaluating our approach
is presented in Section 4. Lastly, Section 5 brings the conclusion and the
directions for future work.

##  2 Background

Research in games requires collection of information about the domain to be
used as guiding tools for the research and experiments to be developed. A game
is composed of a set of rules during its execution and winning or losing
criteria. Thus, understanding these characteristics is essential for
implementation of agents, data and results collection. In this section we
present substantial knowledge about techniques that were used in our research.
Furthermore, we present the characteristics of the MOBA domain.

###  2.1 Influence Maps and Potential Fields

Tactical analysis has been studied by various researchers over time and was
applied in a wide range of games in both academia and industry. The most
common technique is to divide the game map into chunks and try to perform some
kind of feature analysis in these chunks [Millington and Funge 2012].
Analyzing the environment statically and dynamically in a consistent fashion
can help the AI to behave in a smarter way. Also, the problem of coordinating
agents in a tactical way is not new. From the work of [Reynolds 1987][Reynolds
1999], we can observe the necessity of environment analysis when driving
agents. Reynolds agents take into account the environment and other agents
when driving themselves in a flock. Potential Fields (PF), a technique
originally from Robotics area, tries to do such analyses, as presented by
[Khatib 1986] in his approach for real-time obstacle avoidance and agent
driving.

In games, Influence Maps (IM) is one the main methods applied for tactical
analysis of the features in a map [Millington and Funge 2012]. A general
definition of influence maps is presented in [Tozour 2001], which discusses
its main concepts and advantages. Basically, the environment is decomposed in
a grid, and each feature inserts points of influence in the cells where they
are positioned. This influence is then spread using a proper algorithm, like
Gaussian blur or Occlusion algorithm. Few years later, [Hagelbäck and
Johansson 2008b] presented the use of Potential Fields in games, showing a
similar approach as seen in Influence Maps. But, in spite of having the same
name of the technique used in robotics [Khatib 1986], the work of [Hagelbäck
and Johansson 2008b] divides the map in a grid, placing values over this grid
that can be attractive or repulsive.

The main difference between the approaches of IM and PF is that the first uses
spread and momentum variables. These values can be used to modify the changes
in information over time: while spread controls how far the value can reach,
momentum controls the amount of time through which the information continues
on the map. The use of such values allows IM to store historical information.
Moreover, it turns IM into a versatile technique, as it can be used for both
prediction and/or historical information just by performing parameter tuning
[Champandard et al. 2011]. On other hand, PF turns to be very static, as its
only parameter is the equation that controls the influence over the maps.
Thus, we observe that PF is mainly used in real-time environments, especially
for navigation.

###  2.2 MOBA Games

In recent years, the popularity of Real-Time Strategy has grown substantially.
With them, a community of players interested in producing new content for such
games has been created. These community is commonly called Modders, after the
acronym of modifiers, generating the alternative game modes called
modifications, or ”mods”. Among these, there was Aeon of Strife (AoS), the
first MOBA like game, created as a Starcraft mod.

After the popularity of AoS, modders used the Warcraft III engine to create a
similar game mode and name it Defense of the Ancients (DotA). The DotA maps
became popular among players, and there were many versions around. Its
mechanics were broadly known that every other game that had similar gameplay
was called ”DotA like game” for a long time. The term MOBA was first observed
in 2009 with the debuting title League of Legends, used by Riot Games to
describe their game. Furthermore, MOBA games evolved from the LAN games to
Multiplayer Online games, and even becoming more popular than MMORPGs, like
World of Warcraft [Diamaranan 2015]. Nowadays, MOBA is among the most played
game genres in the world.

In terms of academic research, there is a rising interest in developing
intelligent agents that are capable of playing games that run in real-time;
have a dynamic environment; and provide partial information. The similarity of
this kind of games to real-world problems is probably one of the main reasons
for such research, as the solutions to these problems may be applied to
various real-world scenarios [Tavares et al. 2014]. This growing interest for
game agents, in particular of RTS games, allowed the academia to develop a
novel game research scenario, creating competitions of intelligent game agents
[Ontanón et al. 2013].

Overall, it is very common to find two types of agents being studied: the
perfect agent aims to defeat all other agents, and is the most common type. On
the other hand, the human-like agents try to behave as humans in the game
environment. This kind of agent is especially popular a in First Person
Shooter (FPS) scenario, such as the 2kbotprize competition [Cothran 2009].

In spite of the agent developed in this work being a MOBA agent, we also
discuss the development of agents for RTS, since, as far as we know, there
were only a few works that try to develop an effective agent for MOBA. The
work presented by [Weber et al. 2011] develops an human-behaving agent for
Starcraft. In this work, the authors also discuss the development layers of an
agent, classifying them in heterogeneous and homogeneous. An agent that is
developed in just one layer is classified as homogeneous. This single layer
implements all features of the agent, like navigation and actuation over the
game. The work of [Uriarte and Ontañón 2012] revisits the multi-layered
system, implementing an agent that performs a kiting system using Influence
Maps (IM). Moreover, the authors present a novel approach for tactical
analysis, that was briefly discussed in [Hagelbäck and Johansson 2008a].

In general tactical analysis, we find the work of [Stanescu et al. 2013], in
which the combat outcome is discussed in Starcraft. In the field of knowledge
extraction and analysis, there is the work of [Bangay and Makin 2014], where
the attributes are analysed in a RTS game and a framework for balance analysis
is proposed. Furthermore, we believe that this knowledge extracted can be used
to model tactical analysis in a combat scenario.

The MOBA research itself is a new field, with few published works. One of the
reasons for this may be the lack of support in MOBA games to AI development.
Most of the works found present general discussions or use collected data to
extract information. The works of [Nosrati et al. 2013] and [Rioult et al.
2014], for example, present a brief analysis of MOBA games, limited to
features and specific characteristics. In the work of [Ferrari 2013] we find a
deep analysis of League of Legends, discussed by various aspects like Game
Design, e-Sport and basic MOBA characteristics.

When analysing the gameplay and player abilities, is possible to find the work
of [Drachen et al. 2014], where the spatio-temporal skill of players is
analyzed, focused in data visualization and gameplay analysis, using Dota2
data. In the same research field, there is the work of [Yang et al. 2014]
where, using Dota2 matches log, the team-fights are analysed and used to learn
patterns. These battles are modelled as interactivity graphs and later shaped
in decision trees form. The model created is then used to predict the success
of future battle in other matches. The work of [Pobiedina et al. 2013]
performs a quantitative analysis of logs collected from Dota2, analyzing the
relation between team formation and victories. It also performs an analysis of
involved players, verifying that their experience and behavior during a match
are essential to winning in MOBA.

Finally, the work of [Willich 2015], from our knowledge, is the only published
work that addresses the problem of creating an agent for MOBA. The author uses
Reinforcement Learning in HoN domain to make the agent learn how to behave in
the game environment. The author shows that the developed agent learns the
very basic mechanics of MOBA, and considers that further research is needed.

###  2.3 MOBA agents

For knowledge extraction from MOBA games, we choose to separate and simplify
the game features towards a general model that can be used to achieve victory.
First, we analyze the game model and steps that can allow an agent to win.
Further, we analyze each feature in the agent’s way to victory, dealing with
each of them separately in a knowledge model, and then unifying them in an
analytical model, in our case the Influence Map.

MOBAs, as RTS, have a highly dynamic multi-agent environment. Instead of huge
armies, MOBA focuses more in teamwork and strong micromanagement skills. The
collaboration of multiple players pushes the team towards victory, although
individual gameplay is also very valuable.

The characteristics of MOBA, in terms of gameplay, are also very similar to
RTS. Listing these we can cite:

  * •

Deterministic ambient: where the same actions have the same effect;

  * •

Partial information: there is a fog-of-war that covers areas out of agent
sight line;

  * •

Non-persistent world: In contrast to most MMOGs, in MOBA every match the world
is created; it does not exists when the match is over;

  * •

Dynamic/Real-time: The game world changes over time and accordingly to agent
actions.

In addition, MOBA games goal consists in pushing a lane and destroying an
enemy base. By analyzing various MOBAs, we can observe that very high-level
sequence of three steps can be followed toward winning:

  * •

Take enemy out of lane;

  * •

Push the lane;

  * •

Destroy structure;

Despite these high-level steps, its necessary a deep analysis to perform each
of them. The lane pushing, for instance, requires tactical analysis of creeps,
risk analysis, among others. Taking enemy out of lane requires tactical enemy
analysis, micromanagement, among others. Structure destroying, on the other
hand, requires enemy analysis, damage analysis and others. Furthermore, all
the analysis must be performed real-time and with partial information. We
discuss then how this analysis can be done and combined, generating a final
knowledge tactical model.

We divided our analysis in three basic classes: Dynamic features, semi-dynamic
features and static features. The dynamic features are the ones that can move
through the scenario and perform actions. Semi-dynamic ones are units that,
although do not move, can have a dynamic map values based in their states.
Lastly, the static features are the ones that does not change through the game
execution. We will discuss these classes further.

Dynamic units are the ones that can move through the scenario performing
changes in the tactical analysis very fast. These units also can perform
actions, like attacking or casting spells. The type of units that is contained
in this class are: heroes, neutral creeps, enemy and allied creeps. In MOBA
context, creep is a unit type that heroes can interact with but that they
cannot control directly. This type of unit is AI-driven and is usually spawned
in the team bases. Besides, neutral creeps are born in the jungle area, and do
not move or attack unless it is injured by a hero unit. In some MOBAs, creeps
can be also known as troops or minions.

Heroes can be considered as the critical unit in dynamic class, they can
change the game scenario very quickly, as most of their spells are casted
instantly and they can be considered the fastest units in game. In addition,
these units are responsible for the team fights and duels. Team fights are
combats performed in groups of a team against another team, duels are fights
that occur between two distinct players, one of each team.

Allied and enemy creeps are born in the respective team base. These units go
into a lane and battle enemy creeps and structures pushing the lane towards
enemy base. In some MOBAs, like Dota2, it is possible to both farm (kill enemy
creeps) and deny (kill ally creeps). These units normally come in groups and
have strong effect in tactical analysis, as they are very important in the
initial phase of game, as heroes must perform last hits to obtain gold from
them. Moreover, we found that it is necessary to verify the creeps that are
most likely to be killed first, maximizing the effects of resource collection
of players.

The only semi-dynamic unit contained in MOBA is the tower. The main
characteristics of the semi-dynamic class is that it can modify its influence
values based in its current aggression state. When attacking the controlled
agent it generates negative values, as the agent should avoid receiving
damage. On the other hand, the agent should attack the enemy towers, thus the
influence generated is positive when there is another target being attacked by
the tower.

Lastly, the static features of a MOBA game are considered as the terrain. The
terrain cannot be modified over time, thus we can make an influence map that
is static, performing the analysis just one time. Note that when performing
static analysis we do not consider abilities of heroes that can cast some kind
of collider or terrain modifier, considering these as dynamic characteristics.

###  2.4 League of Legends

League of Legends is a game of Multiplayer Online Battle Arena (MOBA) genre
developed by Riot Games; it was open released in 2009. MOBAs are characterized
by its online competitive nature, where two teams of players compete against
each other aiming to destroy the enemy base. A sample map can be seen in
Figure 1. In the most common game mode in MOBAs, each team is composed of five
players. The player is represented by a powerful unit called hero, that is
chosen at the beginning of each match from a hero pool. Each hero has unique
powerful skills that can be used to combat enemy players, neutral units and
creeps. Each hero starts at level one and the player has to defeat enemy, AI
driven, weak units called creeps or jungle neutral units. By defeating these
units, or enemy heroes, the player can accumulate experience points developing
skills and upgrading their hero level. At each level, the player can upgrade
one skill, making it more powerful, and the hero increases its power in terms
of status, e.g. attack power, health points, mana points. When the player
performs the last-hit in a neutral or enemy creep, his/her hero gets gold,
allowing the player to buy items that will increase hero status, making it
more powerful. Winning in a MOBA game can be achieved just by destroying an
enemy main structure, in League of Legends this structure is called Nexus.
When a team destroys the enemy Nexus the game is terminated and this is the
winner team.

Figure 1: General Map of a MOBA Game

When choosing a hero, players must have in mind what role he/she wants to
assume during gameplay. There are heroes that can be suited in various
functions inside the game, but most of them performs better when assuming the
main function that the hero was designed for. Another concept that the player
must take in account is the current metagame. The metagame takes in account
various theories about what the best compilation of heroes that tends to
perform better in the actual scenario, using knowledge from inside and outside
of the game. In addition, if the player is a human, his/her skills must be
considered. Due to the continued development and update of MOBAs, the metagame
tends to change in every balance change, done by a patch. An example of
metagame is the most common team compilation in LoL, normally two players go
to bottom lane, one Support and one Attack Damage Carry (ADC), in the middle
lane goes a Mage or Assassin, a Tank or Fighter in the Jungle/Ganker role and
a top lane player that can be an Initiator, Front-liner or Tank.

Metagame can be better understood by knowing the best functions of each class.
An ADC is a long ranged hero, capable of dealing high damage to single
targets, while a Support is a hero that can assist the ADC, healing of buffing
his skills. Mages are champions that deal damage based in spells, and
eventually are capable of performing high AoE damage. On the other hand,
Assassins are strong in duels and killing a single enemy fast. Lastly, the
top-laners are largely used to initiate the fights or block the damage
incoming from the enemy team. Thus, the top-lane champions have high HP and
defensive status, like armor. Tanks are champions capable of receiving high
amounts of damage without being killed. Initiators have the responsibility of
starting the team combats, while Front-Liners are responsible to stay between
the two teams during the combat. Its important to notice that there are heroes
that are classified in more than one function, or are suitable in more than
one lane. For example, Varus, a LoL champion, can be a mid-laner or ADC, while
Malphite can be classified as Tank, Initiator and Mage.

##  3 Agent Architecture

The use of a heterogeneous agent architecture seems reliable for the MOBA
domain. Due to the multiple tasks like building, navigating, cooperation and
combat, it is possible to use the heterogeneous architecture to implement a
multi-tasking agent. Our agent interfaces with LoL through the use of sensors
which collect data about the world. The agent also can send action to the hero
to perform, modifying the game environment with its actuators, e.g. attacking.

League of Legends has an application programming interface, called Bot of
Legends (BoL). BoL retrieves information about the game and performs the same
actions as players. This tool is very similar to the Brood War API that is
largely used in Starcraft research. Both tools have the same premise: they
collect information that is available to players and just perform actions
available to players.

The agent is composed of two layers: navigation and micromanagement. Our
primary goal is to develop an agent that could navigate and interact in a MOBA
domain in a competitive way. That means that we are developing a rational
agent with the goal of winning. However, as most agents implemented in the
video games domain, our agent is still not capable of outperforming human
players.

Figure 2: Architecture implemented for the agent.

###  3.1 Navigation Layer

The base of our agent is modeling the information collected into valuable
information that could be used by all layers. Thus, we inserted a series of
hand-authored knowledge and data collected real-time. Further, we model the
data collected and hand-authored over an grid-formatted influence map. A
visual representation of our model can be seen in Figure 2.

The influence map feeds the navigation layer that uses a case-based reasoning
(CBR) system. This layer search for best points, taking in account the
terrain, dynamic and static features from the domain. The influence maps uses
single layer, aiming to improve the agent performance. The IM models knowledge
about all agents involved in the MOBA domain. We use mathematical functions to
create a single value base in the weight of individuals, generating a 2D grid
with decimal values.

Aside from both the IM and the navigation layer, the micromanagement layer
uses sensors to perceive the enemy and ally units. Based in the information
collected, the micromanagement layer coordinates two CBRs, the target selector
and orbwalker. In high-level, target selector is responsible by defining the
unit that will be the current target of attacks and abilities. On the other
hand, the orbwalker is responsible by reasoning between attack and movement.
Both systems will be discussed further.

####  3.1.1 Enemy Towers

When analyzing the towers, in general we observe that it can assume two
states: idle or aggressive. In the idle state, the tower performs no action,
but verifies if there are enemies within its range to be attacked. As soon as
an enemy enters the turret range, it will be attacked. In addition, a tower
can just attack one enemy at a time, and does not inflict area-of-effect (AoE)
damage.

We can point a preference list for tower enemy choosing order as follows: i)
Enemy hero attacking ally hero, ii) any enemy in range, iii) enemy creep and
iv) enemy hero. Once the tower selects a target it will not change, unless it
dies of comes in first options in the preference list.

In some MOBAs, like Dota or Dota2, the tower prefers the closest enemy, so the
players try to stay after their creeps. Using this knowledge, we were able to
identify patterns and model an influence level for enemy towers. Different
from RTS gameplay, towers in MOBA are very strong damage dealers and have high
health values. They are also critical part of the strategy, as they protect
the lanes and the structures.

For dealing with enemy towers, we modeled two sub-states for the aggressive
state: passive and active. The passive state means that there is aggression
but the target of the tower is not our hero agent. Whereas the active state
means that aggression target is our agent. The influence is then set to the
map based in the current state. However in early tests we noticed that our
tactical positioning was failing, due the resolution and that our agent was
choosing advanced points in the map, an action called tower dive, causing it
to die. We then introduced a weighting system for cells that allowed the agent
to choose best positions based on the safest place. Our solution weighted the
cells by a $\tau$ variable, that was obtained dividing the enemy unit to agent
base distance by the IM cell distance to agent base distance, as seem in the
Equation 1.

$\tau=\frac{d_{tb}}{d_{pb}}$ (1)

In addition, when performing tactical analysis, it is important to leave room
to risky plays. Sometimes an enemy hero can have a very low hp and the agent
could let it go just because it is in tower range. Therefore, when weighting
the tower we created a value $\varepsilon$ that allows agent to enter in tower
range if necessary. The value $\varepsilon$ should be calculated as the max
potential damage to be dealt by the tower. The rules for enemy tower influence
can be seen in 2.

$w_{p}=\left\\{\begin{array}[]{l l}\left\\{\begin{array}[]{l l}d_{pt},&\quad
d_{pt}<H_{r}-\Delta\\\ \tau*d_{pt},&\quad H_{r}-\Delta\leq d_{pt}\leq H_{r}\\\
T_{r}-d_{pt},&\quad\mathrm{else}\\\ \end{array}\right.,&\quad\alpha\geq 3\\\
\left\\{\begin{array}[]{l l}-T_{r},&\quad d_{pt}>\varepsilon\\\
-\infty,&\quad\mathrm{else}\\\
\end{array}\right.,&\quad\mathrm{else}\end{array}\right.$ (2)

Another problem faced by our agent, and often not discussed in the literature,
is the resolution loss problem. As most games dedicates a few computation for
AI, it is crucial to have cheap processing in this area [Tozour 2001].
Therefore, the IM should be tuned aiming to deal a good performance to agent
and does not consume a big computational time. The agent could then suffer
from low resolution, causing it to perform poorly due to the little amount of
data collected by the map. We then introduced a value $\Delta$, that is half
of the resolution used, to be used as an error correction. The final plot of
equation in passive aggressive state can be seen in figure 3. $H_{r}$ means
hero range; $d_{pt}$ denotes the euclidean distance between the cell and the
tower; $T_{r}$ means the tower range; and $\varepsilon$ denotes a limit area
for lowest influence values inside of tower range.

Figure 3: Plot of enemy tower in passive aggressive state. Red areas means
more desirable positions, while blue areas mean less desirable positions. Note
that red area is closer to the base of the agent’s team. Base is located in
P(1000,1000)

####  3.1.2 Enemy Creeps

Enemy creeps are the main resource collection approach for agents and players.
Each time that a player kills an enemy creep the player obtains gold and
experience. Thus, there must be a careful analysis of these components, as
they can be game changing. The correct positioning around these units will
allow the agent to perform the last-hit and, as these units are highly
dynamic, they must be observed most constantly.

When calculating the creeps influence we are covering two layers of the agent
architecture: movement and micromanagement. In this section, we discuss the
movement analysis; the micromanagement will be discussed further, in Section
3.3.1.

To compute the influence of enemy creeps we use the logic proposed by
[Hagelbäck and Johansson 2008a], staying away from the enemy as much as
possible but still maintaining it in hero range. As well, as discussed in
enemy tower section, we must consider the resolution losses, creating a
plateau in our equation, making it possible for the agent to hit the creep. We
also consider the weighting relatively to the hero ’s own team base, making it
stay in the safest place possible, making the agent avoid the damage done by
enemy creeps. A plot of the influence done by our model can be seen in Figure
4.

Figure 4: Plot of enemy creeps influence. Red areas means more desirable
positions, while blue areas mean less desirable positions. Note that the red
area is strongly influenced by the $\phi$ variable. Base is located in
P(1000,1000)

In our early tests we noticed that just by considering this influence with
weight was not enough to make the agent perform well in a prerequisite called
farming333Farming is the action of collecting resources by executing last-hits
in enemy or neutral creeps.. Making the agent be on the edge of the creeps
does not guarantee that the agent will select the creep that will die first,
or that have the lowest amount of health points (HP). We then implemented a
variable $\phi$, that calculates the creep’s missing percent of HP. We
inserted $\phi$ in the influence equation that considers the HP of a creep,
making the agent to go towards the creep that has the lowest health. Equation
3 shows the influence calculation for enemy creeps. Variable $d_{pm}$ denotes
the euclidean distance between the cell and the creep.

$w_{p}=\left\\{\begin{array}[]{l l}d_{pm},&\quad d_{pm}<H_{r}-\Delta\\\
max(\tau*(d_{pm}+100-\phi),w_{p}),&\quad\mathrm{else}\end{array}\right.$ (3)

####  3.1.3 Ally Towers

When weighting towers we observe that it is very defensive to be under the
range of own’s team towers, but for this defense to be effective, the agent
should be in a safe area. For example, the agent should be in range of an ally
tower and out of range of enemy heroes. However, the safe area is very
difficult to abstract due to the diverse mechanics found in MOBA games.
Another point that must be observed, is that the player should avoid colliding
with towers, as this could lead to time leaks in the navigation. Moreover, in
various MOBAs, there are champions that can take advantage of the proximity of
the hero to the tower. We then developed an influence equation for allied
towers based on these characteristics. The equation provides the tower a
linear decay of influence, making its best places near it and the worst ones
far away from the tower. For avoiding the collision between the player and the
tower, and avoiding to be caught by specific mechanics, we inserted a minimum
distance for influence to be set. Thus, the agent will maintain distant from
the tower in a secure way, as seen in Equation 4.

$w_{p}=\left\\{\begin{array}[]{l l}max(T_{r}-d_{pt},w_{p}),&\quad
d_{pt}>\varepsilon\\\ 0,&\quad\mathrm{else}\end{array}\right.$ (4)

####  3.1.4 Heroes

Heroes are the most dynamic units in MOBA gameplay, they can move generally
faster than creeps and also cast spells and attack. This units are the ones
that require more attention when performing tactical analysis in the MOBA
domain, due to their high potential of changing the game’s tactical landscape.
We navigate based strongly in our ally heroes and try to avoid enemy damage.

In our early research phase we implemented the influence range based in the
auto-attack range of heroes. That proved to be a bad choice by two main
reasons: (a) Melee heroes have a small range, but they can cast spells and
deal damage farther and (b) there are heroes that have a smaller range but
have a high spell cast range. Therefore, we had to compile a hand-authored
knowledge database of all 126 heroes contained in League of Legends. This
database informed our agent the distance to be considered as the current hero
range. In addition to the hand-authored data, we collected real time
information about the spells being cast, allowing the agent to dynamically
modify the influence range and perform further analysis about the risk of
engaging in a fight against an enemy.

For enemy heroes we consider the danger area as a highly undesirable plateau,
so we just attribute the tactical value of that hero, in negative form, in its
range area. For ally heroes we perform a very similar approach, applying the
calculated tactical value over the cells in range.

###  3.2 Combining influences

Performing multi-agent tactical analysis goes beyond the analysis of each
agent separately and running an agent considering it. It is necessary to
compile these influences together, making the data collected make sense for
the system. The great challenge of making a readable model for the system is
to mix them in a way that is computationally efficient.

The initial propose of [Tozour 2001] is to store various influence map layers
and then put them together. Moreover [Champandard et al. 2011] discusses that
if an additional buffer is not used for influence mapping the values can be
scattered in a non-desirable way. Thus, in these two approaches we observe
that extra memory is needed. When observing the Potential Fields approach
proposed by [Hagelbäck and Johansson 2008b] we can observe that more computing
resources is needed, as the distance between the cells in the grid must be
calculated.

Our approach uses a similar approach to the proposed by Hagelbäck, using the
distances to write in a 2D grid. We do not use extra buffering, and, as we do
not need any historical information, we do not store these data in our map.
All characteristics then drive our approach to a highly tactic map, analyzing
just the actual information and reasoning based in that.

After all influences are calculated, we need to concatenate them in a single
2D grid. In early IMs, the task of mixing the cells values was done by simple
summing each map layer, obtaining rough IMs. However, just summing does not
provide a reliable technique for extracting information from this data. For
example, summing can drive the agent to a local maximum when analyzing the
enemy agent features, as shown in Figure 5. Observe that, while the max
function allows each creep to set its own influence, the sum method tries to
sum them together. However, sum creates a local maximum that could expose the
agent to dangerous positioning during combat or even to cases where the creeps
will be able to defeat the agent due to a local maximum.

Figure 5: Comparing the max(left) to sum(right) mixing methods when analysing
enemy creeps feature. Red areas means more desirable positions, while blue
areas mean less desirable positions. In the right figure we clearly see a
local maximum (in red); in the left figure we see a better influence
distribution.

To avoid the creation of local maximum, as we are using an Influence Map based
in tactical features, we classified the agents involved based in their
importance. Doing so would require us to store various Influence Map layers
and then perform operations between these layers. However, we figured that we
could update each agent class one at a time, obtaining the same results and
saving memory. The order was done by the tactical value of each unit. We first
update creeps, then we update towers and lastly we update heroes.

Operation selection was based on the goal of minimizing the local maximum
generation and maximizing the outcome of the tactical goal related to that
unit. For example, for creeps we aim to maximize the resource collection
through last-hitting creeps while we try to minimize the local minimum of
creeps, thus the exposition of the agent to danger. Therefore, creeps uses a
maximum value function for mixing the values to the map. Our system creates a
zero-valued IM in each iteration. Further, our system calculates the influence
of creeps, comparing this value to the actual cell value and setting the
maximum to current cell.

For the setting of influence from towers, the second feature to be computed,
we overwrite the values computed previously. This aims to put the values of
towers over the values established by the creeps, showing that it is more
important than the previous one.

After setting tower values, we finally calculate and set the values from
heroes. As these are the most dynamic unities in the game, they deserve
special attention. Even more, defeating a hero can give the agent the
necessary time to gain any kind of strategic advantage in the game, so the
algorithm prioritizes them.

###  3.3 Micromanagement Layer

Along with a movement layer, it is necessary to implement a layer responsible
for coordinating the abilities and attacks from hero. In our approach, as we
aim to create a generic technique we do not focus on abilities, but first in
simple auto attacks. In the next subsections we discuss the techniques applied
in the micromanagement layer.

####  3.3.1 Orbwalking and Kiting

A very useful mechanic in game combat scenarios is to hit and run, especially
when the coordinated unit has a higher range than the enemy unit does, this is
called kiting. Human players very often perform this kind of mechanics aiming
to maximize the damage dealt to enemies both in RTS and in MOBA games.
Furthermore, that is an essential technique for damage-based carries and for
any agent who aims to farm in MOBA. There is an algorithm, called orbwalker,
that is responsible to inform when it is possible to attack or to move, very
similar to the approach presented by [Uriarte and Ontañón 2012]. However, the
orbwalking algorithm does not perform any kind of tactical analysis; that is
why further scenario analysis is necessary when performing the attack-and-flee
mechanic.

In our approach, we did not implement the kiting algorithm as proposed by
[Uriarte and Ontañón 2012]; however, our agent performed this emerged behavior
due to the enemy analysis and positioning system. The orbwalker itself
informed the agent when it was possible to attack or when to walk, based in
the animation time, turn time and latency of the game. The last parameter
showed to be crucial to MOBA approach, as this genre is mostly based in online
experience.

As the agent tends to be as far as possible from enemies and maintaining these
enemies within the agent range, it is clear that the enemies will be in the
edge of enemy attacking field. The agent then receives the repositioning task
while attack action is not available, then turns around and attack, when the
attack is available. However, our agent does not perform any analysis towards
identifying the targets whose kiting can be performed, as the approach
presented in [Uriarte and Ontañón 2012] does.

####  3.3.2 Target Selection

The target selection problem is an open challenge in most strategic games,
including RTS and MOBA. The work of [Hagelbäck and Johansson 2008a] address
this problem in a very early tactical approach. Later the work of [Uriarte and
Ontañón 2012] discuss this problem in greated detail, assigning tactical
values for each enemy based in its distance, manually-assigned tactical threat
and DPS. They show that it is an essential part of tactical behavior to select
the right enemy to attack. The work of [Liu et al. 2014] presents an automatic
target selection approach using Genetic Algorithms. However, their concept of
Target Selection, although still tactic, shows a different concept from
[Uriarte and Ontañón 2012]. Rather than using tactical values or DPS it just
considers the health points of each nearby enemy for target selection.

In our approach we collect data and combine them with hand-authored content,
building a target selector that analyses the tactical properties of each unit.
We use a preference model based in HP, Unit Tactic characteristics and Unit
danger potential, also known as aggro. This mechanism does not have any
actuator, it just provides information for the Micromanagement layer, that
actuates in the agent state.

As presented, our approach considers the danger first, targeting dangerous
enemies, aiming to survive as long as possible. Secondly, it prioritizes
resource collection, farming as much as possible. As discussed before, the
selection of creeps to be farmed is is a responsibility shared by the
micromanagement and movement. Moving next to low HP creeps allows the agent to
put them in range, allowing the target selector to aim them in the
micromanagement layer and successfully perform the last hit.

Lastly, we verify the existence of a secure scenario to take aim at enemy
towers, focusing on goal-controlling and on raising the advantage gained by
the agent. By doing so, the agent is aiming to push the lane towards the enemy
base, finally defeating the enemy by destroying the main structure.

##  4 Empirical Evaluation

In order to evaluate our approach we performed three sets of experiments in
the domain of League of Legends. The first experiment tests the effectiveness
of our agent, testing if the agent is capable of winning in a scenario where
it plays alone. Secondly, we test the efficiency of this agent, measuring its
performance in terms of resource collection. Lastly we test the agent’s
performance in a match against human players. These experiments and their
results will be discussed in the next subsections.

###  4.1 Experiment 1: Winning alone in MOBA

In this experiment we run the agent in a scenario where it is in a match
without ally or enemy heroes. This experiment shows the effectiveness of the
agent and the success of the sequence of steps presented to win in a MOBA
game. Our baseline is the work of [Willich 2015], however we were not capable
of replicating the author experiments, as code is not available. In addition,
the author uses HoN as game domain, while in this work we use LoL as testbed.

For this experiment we use a map where there is just one lane. In [Willich
2015] the author uses a similar approach, although they use a three-lane map
but considers just one.

We executed 20 matches with a hero randomly selected from the LoL champion
pool. Our agent was capable of winning all matches. In addition, our agent
always showed a KDA factor of 0, meaning that it never died and did not
present errors. Also for testing the local maximum problem we monitored the
agent also collecting the time that the matches lasted. The agent was capable
of winning in an average of 22.6 minutes with a standard deviation of 5
minutes. Further, as we were using random heroes, the agent shows consistency
for driving various characters.

We then wanted to measure how well it performed alone in the scenario. A good
measure for both the positioning is the resource collection. That leads us to
the next experiment.

###  4.2 Experiment 2: Resource Collection

Resource collection in MOBA is different from RTS, as it is performed by
killing enemy or neutral creeps, champions and structures. Furthermore, its
important to maximize the resource collection. In this test we first run our
approach without the $\phi$ variable, that represents the health of creeps.
Then we compare the performance of resource collected to the approach with
$\phi$. In MOBA community there is a common sense that the best farm score, as
performed by professional players, is to last hit 10 creeps per minute, we use
that sense as our baseline.

We first ran 10 matches with the agent using the $\phi$ variable for improving
positioning and resource collection, then we run 10 matches without using the
$\phi$ variable. The tests were executed in the same conditions from
Experiment 1, a single lane map without enemy heroes. Our experiments with the
health factor shows an average of 92,24% efficiency in farming (see Table 1),
showing that our agent is capable of efficiently collecting resources.
Further, this performance can be compared to the resource collection rate of
professional players. In contrast to the previous performance, in matches
where the health factor was disabled the efficiency was lowered to an average
of 60,84% of resource collection.

Table 1: Performance presented by the agent during resource collection Method | Creeps per Minute | Efficiency(%)
---|---|---
Baseline | 10 | 100%
$\phi$ disabled | 6.084 | 60.84%
$\phi$ enabled | 9.224 | 92.24%

With this experiment we show that our agent is capable of efficiently
collecting resources in a highly dynamic environment. It is important to
stress that despite the lack of enemies or allies in the match, the agent has
to compete with allied creeps for last hits. Moreover, this experiment shows
the consistency between the two layers implemented, demonstrating that the
combination of navigation and micromanagement system is effective. Further, we
show that with the $\phi$ variable we were capable of improve the resource
collection task by more than 30%.

###  4.3 Experiment 3: Evaluation Against Human Players

This experiment deals with a real match in League of Legends. We selected the
mode called All Random All Mid (ARAM) to be used as testbed for this
experiment. In this mode the map just has one lane and all heroes are selected
at random for players that have the chance to exchange them between allies
during the hero selection phase. This modes also provides more gold at the
beginning of the match and the heroes starts at level three instead of one.

We performed 10 matches in ARAM mode for evaluation and collected the hero
performance and win/lose from our agent. We observe that when it plays melee
characters the performance is greatly affected, doing much worse than when
playing ranged heroes.

The hero shows a high amount of deaths when playing melee champions. When
playing ranged champions it shows low death levels, but does not show a high
amount of kills. In both melee and ranged, our agent shows a high amount of
assists, showing that it helps another players to get kills. In spite of
assist characteristics, its not possible to affirm that it behaves in a
cooperative fashion, as assists can be granted by just casting an spell or
auto attacking. Lastly, as with most agents playing against humans, our agent
performed poorly with most heroes. Due the fast dynamics of MOBA, our agent
reaction time was not sufficient to play in a team.

##  5 Conclusion and Future Work

In this work we presented an approach for tactical analysis and knowledge
modeling in real-time scenario using Influence Maps. For doing so, we used
League of Legends, one of the most played games in the world nowadays.

Our experiments results show that this is a promising approach. We implemented
the game agent using an heterogeneous architecture composed of two layers:
navigation and micromanagement. Furthermore, our approach show that it is
possible, and necessary, to strongly connect these layers, as presented by the
parameters that connects movement and micromanagement towards resource
collection. We also demonstrate that simple features, like a health factor,
can greatly increase the performance of the agent. Moreover, further tactical
investigation in MOBA domain is required to behave well against humans.
Lastly, we obtained a kiting behavior by combining heterogeneous controls. In
previous research this behavior required a dedicated module.

A problem that can be tackled in future work is the competition of the current
agent against human players. It is known that current state of the arts agents
show poor performance when playing against human players, and an interesting
question to be answered is whether this happens in MOBA. Moreover, whether the
agent performs competitively cooperating with human players, as MOBA requires
multiple players to control multiple agents.

Another problem that can be addressed is the development of multiple agents
and the interactions between them. Applying approaches of distributing tasks
in games, like the presented in [Tavares et al. 2014], looks very promising
when applied to the MOBA context, as this game genre is strongly oriented to
player roles [Yang et al. 2014].

##  6 Acknowledgements

We would like to thank the BoL Community, especially Bilbao and Kenect, that
supported us in the development using BoL environment. We also thank the
reviewers, that provided insightful feedback and corrections to our paper.
This work was supported by CAPES, CNPq and FAPEMIG.

## References

  * [Adobbati et al. 2001] Adobbati, R., Marshall, A. N., Scholer, A., Tejada, S., Kaminka, G. A., Schaffer, S., and Sollitto, C. 2001\.  Gamebots: A 3d virtual world test-bed for multi-agent research.  In Proceedings of the second international workshop on Infrastructure for Agents, MAS, and Scalable MAS, vol. 5, Montreal, Canada.
  * [Bangay and Makin 2014] Bangay, S., and Makin, O. 2014\.  Generating an attribute space for analyzing balance in single unit rts game combat.  In Computational Intelligence and Games (CIG), 2014 IEEE Conference on, IEEE, 1–8.
  * [Champandard et al. 2011] Champandard, A., Dill, K., and Isla, D. 2011\.  Lay of the land: Smarter ai through influence maps.  In Game developers conference, vol. 2011.
  * [Cothran 2009] Cothran, J. 2009\.  Winning the 2k bot prize with a long-term memory database using sqlite.  Available on AiGameDev. com at http://aigamedev. com/open/articles/sqlite-bot.
  * [Diamaranan 2015] Diamaranan, A., 2015.  Most played games: May 2015 – the witcher debuts, world of warcraft stumbles, June.  http://caas.raptr.com/most-played-games-may-2015-the-witcher-debuts-world-of-warcraft-stumbles/ Raptr.com[Online; posted 26-June-2015].
  * [Drachen et al. 2014] Drachen, A., Yancey, M., Maguire, J., Chu, D., Wang, I. Y., Mahlmann, T., Schubert, M., and Klabajan, D. 2014\.  Skill-based differences in spatio-temporal team behaviour in defence of the ancients 2 (dota 2).  In Games Media Entertainment (GEM), 2014 IEEE, IEEE, 1–8.
  * [Ferrari 2013] Ferrari, S. 2013\.  From generative to conventional play: Moba and league of legends.  In Proceedings of DiGRA 2013: DeFragging Game Studies, vol. 1, 1–17.
  * [Hagelbäck and Johansson 2008a] Hagelbäck, J., and Johansson, S. J. 2008\.  The rise of potential fields in real time strategy bots.  In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment.
  * [Hagelbäck and Johansson 2008b] Hagelbäck, J., and Johansson, S. J. 2008\.  Using multi-agent potential fields in real-time strategy games.  In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2, International Foundation for Autonomous Agents and Multiagent Systems, 631–638.
  * [Khatib 1986] Khatib, O. 1986\.  Real-time obstacle avoidance for manipulators and mobile robots.  The international journal of robotics research 5, 1, 90–98.
  * [Liu et al. 2014] Liu, S., Louis, S. J., and Ballinger, C. 2014\.  Evolving effective micro behaviors in rts game.  In Computational Intelligence and Games (CIG), 2014 IEEE Conference on, IEEE, 1–8.
  * [Millington and Funge 2012] Millington, I., and Funge, J. 2012\.  Artificial intelligence for games.  CRC Press.
  * [Nosrati et al. 2013] Nosrati, M., Karimi, R., and HARIRI, M. 2013\.  General trends in multiplayer online games.  World Applied Programming 3.
  * [Ontanón et al. 2013] Ontanón, S., Synnaeve, G., Uriarte, A., Richoux, F., Churchill, D., and Preuss, M. 2013\.  A survey of real-time strategy game ai research and competition in starcraft.  Computational Intelligence and AI in Games, IEEE Transactions on 5, 4, 293–311.
  * [Pobiedina et al. 2013] Pobiedina, N., Neidhardt, J., Calatrava Moreno, M. D. C., Grad-Gyenge, L., and Werthner, H. 2013\.  On successful team formation: Statistical analysis of a multiplayer online game.  In Business Informatics (CBI), 2013 IEEE 15th Conference on, IEEE, 55–62.
  * [Reynolds 1987] Reynolds, C. W. 1987\.  Flocks, herds and schools: A distributed behavioral model.  In ACM Siggraph Computer Graphics, vol. 21, ACM, 25–34.
  * [Reynolds 1999] Reynolds, C. W. 1999\.  Steering behaviors for autonomous characters.  In Game developers conference, vol. 1999, 763–782.
  * [Rioult et al. 2014] Rioult, F., Métivier, J.-P., Helleu, B., Scelles, N., and Durand, C. 2014\.  Mining tracks of competitive video games.  AASRI Procedia 8, 82–87.
  * [Stanescu et al. 2013] Stanescu, M., Hernandez, S. P., Erickson, G., Greiner, R., and Buro, M. 2013\.  Predicting army combat outcomes in starcraft.  In AIIDE.
  * [Tavares et al. 2014] Tavares, A. R., Azpúrua, H., and Chaimowicz, L. 2014\.  Evolving swarm intelligence for task allocation in a real time strategy game.  In Computer Games and Digital Entertainment (SBGAMES), 2014 Brazilian Symposium on, IEEE, 99–108.
  * [Tozour 2001] Tozour, P. 2001\.  Influence mapping.  Game programming gems 2, 287–297.
  * [Uriarte and Ontañón 2012] Uriarte, A., and Ontañón, S. 2012\.  Kiting in rts games using influence maps.  In Eighth AAAI Artificial Intelligence and Interactive Digital Entertainment Conference.
  * [Weber et al. 2011] Weber, B. G., Mateas, M., and Jhala, A. 2011\.  Building human-level ai for real-time strategy games.  In AAAI Fall Symposium: Advances in Cognitive Systems, vol. 11, 01\.
  * [Willich 2015] Willich, J. 2015\.  Reinforcement Learning for Heroes of Newerth.  Bachelor thesis, Technische Universitat Darmstadt.
  * [Yang et al. 2014] Yang, P., Harrison, B., and Roberts, D. L. 2014\.  Identifying patterns in combat that are predictive of success in MOBA games.  In Proceedings of Foundations of Digital Games.