# Palindromic concatenations of two distinct repdigits in Narayana’s cows
sequence†

Mahadi Ddamulira1,∗, Paul Emong2, and Geoffrey Ismail Mirumbe3

###### Abstract

Let $(N_{n})_{n\geq 0}$ be Narayana’s cows sequence given by a recurrence
relation $N_{n+3}=N_{n+2}+N_{n}$ for all $n\geq 0$, with initial conditions
$N_{0}=0$, and $N_{1}=N_{2}=1$. In this paper, we find all members in
Narayana’s cow sequence that are palindromic concatenations of two distinct
repdigits. Our proofs use techniques on Diophantine approximation which
include the theory of linear forms in logarithms of algebraic numbers and
Baker’s reduction method. We show that $595$ is the only member in Narayana’s
cow sequence that is a palindromic concatenation of two distinct repdigits in
base $10$.

Keywords and phrases: Narayana’s cow sequence; Repdigit; Linear forms in
logarithms; Baker’s method.

2020 Mathematics Subject Classification: 11B37, 11D61, 11J86.

†This research was supported by Africa-UniNet, financed by the Austrian
Federal Ministry of Education, Science and Research (BMBWF) and implemented by
OeAD.

∗ Corresponding author

##  1 Introduction.

Narayana’s cows sequence $(N_{n})_{n\geq 0}$ was named after the Indian
mathematician Narayana [2], who proposed the problem of a herd of cows and
calves. He described the sequence as the number of cows present each year,
starting from one cow in the first year, where every cow has one calf every
year starting in its fourth year.

Narayana’s cow sequence is a sequence of positive integers and its first few
terms are

$1,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406,595,872,1278,1873,\ldots.$

In this sequence, the number of cows in each year is equal to the number of
cows in the previous year, plus the number of cows three years ago.
Translating this description into recurrence sequences, we have that in the
$n^{\text{th}}$ year, Narayana’s cows sequence problem is given by the
following recurrence relation:

$N_{n+3}=N_{n+2}+N_{n},$

for all $n\geq 0$, with the initial conditions $N_{0}=0$, and $N_{1}=N_{2}=1$.

Let $q\geq 2$ be an integer. We say that a positive integer $R$ is called a
base q-repdigit if all its digits are equal in base $q$. If $q=10$, then we
omit the base and simply say that $R$ is a repdigit. That is, $R$ is of the
form

$\displaystyle R=\overline{\underbrace{b\cdots b}_{\text{$k$
times}}}=b\left(\frac{10^{k}-1}{9}\right),$

for some non negative integers $b$ and $k$ with $1\leq b\leq 9$ and $k\geq 1$.
Given $s\geq 1$, we say that $R$ is a concatenation of $s$ repdigits if $R$
can be written in the form

$\overline{\underbrace{b_{1}\cdots b_{1}}_{\text{$k_{1}$
times}}\underbrace{b_{2}\cdots b_{2}}_{\text{$k_{2}$
times}}\cdots\underbrace{b_{s}\cdots b_{s}}_{\text{$k_{s}$ times}}}.$

Diophantine equations involving repdigits have been studied in several papers
by different authors. For instance, the problem of writing repdigits as sum of
three Fibonacci numbers has been studied by Luca [15]. Alvarado and Luca [3]
solved the Diophantine equation which involved expressing Fibonacci numbers as
sum of two repdigits. In [9, 10], Ddamulira studied the problem of searching
for Padovan and tribonacci numbers which are concatenations of two repdigits,
respectively. In [1], the authors proved that the only Fibonacci numbers that
are concatenations of two repdigits are $\\{13,21,34,55,89,144,233,377\\}$.
Erduvan and Keskin, in their paper obtained all Lucas numbers which are
concatenations of two repdigits, see [13]. The same authors determined Lucas
numbers which are concatenations of three repdigits [14]. Other results on
concatenation of repdigits appear in [5, 6, 17, 18, 20]. Furthermore, the
authors in [11] showed that $\\{13,19,28,41,60,88,277\\}$ are the only members
of Narayana’s cow sequence that are concatenation of two repdigits.

In this paper, we study a related problem and find all members in Narayana’s
cow sequence which are palindromic concatenations of two distinct repdigits.
To be more specific, we solve the Diophantine equation

$\displaystyle N_{n}=\overline{\underbrace{f_{1}\cdots f_{1}}_{\text{$u_{1}$
times}}\underbrace{f_{2}\cdots f_{2}}_{\text{$u_{2}$
times}}\underbrace{f_{1}\cdots f_{1}}_{\text{$u_{1}$ times}}},$ (1)

with $f_{1}\neq f_{2}\in\\{0,1,2,3,\ldots,9\\},\ f_{1}>0$, and $u_{1},\
u_{2}\geq 1$.

Therefore, we have the following result:

######  Theorem 1.

The only member in Narayana’s cows sequence which is a palindromic
concatenation of two distinct repdigits is $595$.

##  2 Preliminary results.

In this section, we gather the tools needed to prove Theorem 1.

###  2.1 Some properties of the Narayana’s cows sequence.

We consider the characteristic polynomial of the Narayana’s cows sequence
defined by
$f(x):=x^{3}-x^{2}-1$. Its roots are
$\alpha_{1},~{}\alpha_{2},~{}\text{and}~{}\alpha_{3}=\overline{\alpha_{2}}$,
where $|\alpha_{2}|=|\alpha_{3}|<1$. We also note that $f(x)$ is irreducible
in $\mathbb{Q}[x]$. The Binet formula for $N_{n}$ is given by

$\displaystyle
N_{n}=a_{1}\alpha_{1}^{n}+a_{2}\alpha_{2}^{n}+a_{3}\alpha_{3}^{n},$ (2)

and holds for all $n\geq 0$, where

$\displaystyle
a_{1}=\dfrac{\alpha_{1}}{(\alpha_{1}-\alpha_{2})(\alpha_{1}-\alpha_{3})},~{}a_{2}=\dfrac{\alpha_{2}}{(\alpha_{2}-\alpha_{1})(\alpha_{2}-\alpha_{3})},~{}~{}\text{and}~{}~{}a_{3}=\dfrac{\alpha_{3}}{(\alpha_{3}-\alpha_{1})(\alpha_{3}-\alpha_{2})}=\overline{a_{2}}.$

Numerically, we have the following:

$\displaystyle 1.46<$ $\displaystyle\alpha_{1}<1.47,$ $\displaystyle
0.82<|\alpha_{2}|=$ $\displaystyle|\alpha_{3}|<0.83,$ $\displaystyle 0.41<$
$\displaystyle a_{1}<0.42,$ $\displaystyle 0.27<|a_{2}|=$
$\displaystyle|a_{3}|<0.28.$

Considering the estimates for
$\alpha_{1},\alpha_{2},\alpha_{3},a_{1},a_{2},a_{3}$, and putting

$\displaystyle
r(n):=N_{n}-a_{1}\alpha_{1}^{n}=a_{2}\alpha_{2}^{n}+a_{3}\alpha_{3}^{n},~{}\text{we
have that}~{}|r(n)|<\frac{1}{\alpha_{1}^{n/2}}\quad\text{for all}\quad n\geq
1.$

Furthermore, the minimal polynomial of $a_{1}$ in $\mathbb{Z}[x]$ is
$31x^{3}-3x-1$, and the inequality

$\displaystyle\alpha_{1}^{n-2}\leq N_{n}\leq\alpha_{1}^{n-1},$ (3)

holds for all positive integers $n\geq 1$, and this can be proved by
induction.

###  2.2 Linear forms in logarithms.

Consider the algebraic number $\lambda$ of degree $d$. Let $c>0$ be the
leading coefficient of its minimal polynomial over integers, and
$\lambda=\lambda^{(1)},\cdots,\lambda^{(d)}$ denote its conjugates. The
logarithmic height of $\lambda$ is defined by

$\displaystyle h(\lambda):=\dfrac{1}{d}\left(\log
c+\sum_{i=1}^{d}\log\left(\max\\{|\lambda^{(i)}|,1\\}\right)\right).$

If $\lambda=\dfrac{p}{q}$ is a rational number with $\gcd(p,q)=1$, and $q>0$,
then $h(\lambda)=\log\max\\{|p|,q\\}.$

The logarithmic height has the following properties:

  * (i)

$h(\lambda_{1}\pm\lambda_{2})\leq h(\lambda_{1})+h(\lambda_{2})+\log 2,$

  * (ii)

$h(\lambda_{1}\lambda_{2}^{\pm})\leq h(\lambda_{1})+h(\lambda_{2}),$

  * (iii)

$h(\lambda^{v})=|v|h(\lambda),~{}\text{for}~{}v\in\mathbb{Z}.$

The following is a result of Matveev [16]; also see Bugeaud, Mignotte, and
Siksek ([8], Theorem 9.4).

######  Theorem 2.

Let $\lambda,\ldots,\lambda_{s}$ be positive real algebraic numbers in a real
algebraic number field $\mathbb{K}\subset\mathbb{R}$ of degree $d$. Let
$b_{1},\ldots,b_{s}$ be nonzero integers such that

$\displaystyle\varGamma:=\lambda_{1}^{b_{1}}\ldots\lambda_{s}^{b_{s}}-1\neq
0.$

Then

$\displaystyle\log|\varGamma|>-1.4\times 30^{s+3}\times s^{4.5}\times
d^{2}(1+\log d)(1+\log D)A_{1}\ldots A_{s},$

where

$\displaystyle D\geq\max\\{|b_{1}|,\ldots,|b_{s}|\\},$

and

$\displaystyle
A_{j}\geq\max\\{dh(\lambda_{j}),|\log\lambda_{j}|,0.16\\},\quad\text{for
all}\quad j=1,\ldots,s.$

We recall the following result by Guzmán and Luca that appears in [19].

######  Lemma 1.

Let $m\geq 1$ and $T>0$ be such that $T>(4m^{2})^{m}$ and $T>x/(\log x)^{m}$.
Then

$\displaystyle x<2^{m}T(\log T)^{m}.$

###  2.3 Reduction method.

We need a version of the reduction method of Baker and Davenport [4] based
their lemma. Here, we use the one given by Bravo and Luca [7], which is a
slight variation of a result due to Dujella and Pethő (see [12], Lemma 5a).
This is useful in reducing the bounds arising from applying Theorem 2.

######  Lemma 2.

Let $\kappa\neq 0,A,B$ and $\mu$ be real numbers such that $A>0$ and $B>1$.
Let $M>1$ be a positive integer and suppose that $\dfrac{p}{q}$ is a
convergent of the continued fraction expansion of $\tau$ with $q>6M$. Let

$\displaystyle\xi:=\parallel\mu q\parallel-M\parallel\vartheta q\parallel,$

where $\parallel\cdot\parallel$ denotes the distance from the nearest integer.
If $\xi>0$, then there is no solution of the inequality

$\displaystyle 0<|m\vartheta-n+\mu|<AB^{-\kappa}$

in positive integers $(m,n,\kappa)$ with

$\displaystyle\dfrac{\log(Aq/\xi)}{\log B}\leq\kappa\quad\text{and}\quad m\leq
M.$

##  3 Proof of Theorem 1.

###  3.1 The small range.

A computer search with Mathematica program for solutions of (1) in the range
$f_{1}>0,\\\ f_{2}\geq 0,\ \text{for}\ f_{1}\neq
f_{2}\in\\{0,1,2,\ldots,9\\}$, $1\leq u_{1},u_{2}\leq 100$, and $n\leq 500$,
revealed only one solution stated in Theorem 1. From now on, we assume that
$n>500$.

###  3.2 Bounding $n$.

First, we consider the Diophantine equation $(\ref{eq1})$, and rewrite it as

$\displaystyle N_{n}$ $\displaystyle=\overline{\underbrace{f_{1}\cdots
f_{1}}_{\text{$u_{1}$ times}}\underbrace{f_{2}\cdots f_{2}}_{\text{$u_{2}$
times}}\underbrace{f_{1}\cdots f_{1}}_{\text{$u_{1}$ times}}},$
$\displaystyle=\overline{\underbrace{f_{1}\cdots f_{1}}_{\text{$u_{1}$
times}}}\cdot 10^{u_{1}+u_{2}}+\overline{\underbrace{f_{2}\cdots
f_{2}}_{\text{$u_{2}$ times}}}\cdot
10^{u_{1}}+\overline{\underbrace{f_{1}\cdots f_{1}}_{\text{$u_{1}$ times}}},$
$\displaystyle=f_{1}\left(\dfrac{10^{u_{1}}-1}{9}\right)\cdot
10^{u_{1}+u_{2}}+f_{2}\left(\dfrac{10^{u_{2}}-1}{9}\right)\cdot
10^{u_{1}}+f_{1}\left(\dfrac{10^{u_{1}}-1}{9}\right),$
$\displaystyle=\dfrac{1}{9}\left(f_{1}\cdot
10^{2u_{1}+u_{2}}-(f_{1}-f_{2})\cdot 10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot
10^{u_{1}}-f_{1}\right).$ (4)

Next, we give a result on the size of $n$ versus $2u_{1}+u_{2}$.

######  Lemma 3.

All solutions to equation $\eqref{eq4}$ satisfy

$\displaystyle(2u_{1}+u_{2})\log 10-2<n\log\alpha_{1}<(u_{1}+u_{2})\log 10+1.$

###### Proof.

The proof follows from equations $(\ref{eq3})$ and $(\ref{eq4})$, and it can
be seen that

$\displaystyle\alpha_{1}^{n-2}\leq N_{n}<10^{2u_{1}+u_{2}}.$

Applying logarithms on the above inequality gives

$\displaystyle(n-2)\log\alpha_{1}<(2u_{1}+u_{2})\log 10,$

which further yields

$\displaystyle n\log\alpha_{1}<(2u_{1}+u_{2})\log
10+2\log\alpha_{1}<(2u_{1}+u_{2})\log 10+1.$ (5)

For the lower bound, one can obtain

$\displaystyle 10^{2u_{1}+u_{2}-1}<N_{n}\leq\alpha_{1}^{n-1},$

and applying logarithms, we have

$\displaystyle(2u_{1}+u_{2}-1)\log 10<(n-1)\log\alpha_{1},$

which leads to

$\displaystyle(2u_{1}+u_{2})\log 10-2<(2u_{1}+u_{2}-1)\log
10+\log\alpha_{1}<n\log\alpha_{1}.$ (6)

Comparison of (5) and (6) finishes the proof of Lemma 3. ∎

We continue to examine (3.2) in three steps as follows:

Step 1. Equations (2) and (3.2) give

$\displaystyle
a_{1}\alpha_{1}^{n}+a_{2}\alpha_{2}^{n}+a_{3}\alpha_{3}^{n}=\dfrac{1}{9}\left(f_{1}\cdot
10^{2u_{1}+u_{2}}-(f_{1}-f_{2})\cdot 10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot
10^{u_{1}}-f_{1}\right),$

which can be rewritten as

$\displaystyle 9a_{1}\alpha_{1}^{n}-f_{1}\cdot
10^{2u_{1}+u_{2}}=-9r(n)-(f_{1}-f_{2})\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{1}}-f_{1}.$

We can now deduce that

$\displaystyle|9a_{1}\alpha_{1}^{n}-f_{1}\cdot 10^{2u_{1}+u_{2}}|$
$\displaystyle=|-9r(n)-(f_{1}-f_{2})\cdot 10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot
10^{u_{1}}-f_{1}|$ $\displaystyle\leq 9\alpha_{1}^{-n/2}+18\cdot
10^{u_{1}+u_{2}}$ $\displaystyle<27\cdot 10^{u_{1}+u_{2}},$

and the fact that $n>500$ has been used. Multiplying both sides of the
inequality by
$f_{1}^{-1}\cdot 10^{-2u_{1}-u_{2}}$, we obtain

$\displaystyle\left|\left(\dfrac{9a_{1}}{f_{1}}\right)\cdot\alpha^{n}\cdot
10^{-2u_{1}-u_{2}}-1\right|<\dfrac{27\cdot 10^{u_{1}+u_{2}}}{f_{1}\cdot
10^{2u_{1}+u_{2}}}\leq\frac{27}{10^{u_{1}}}.$ (7)

We define the expression inside the absolute value on the left-hand side of
inequality $(\ref{eqn7})$ by

$\displaystyle\varLambda_{1}:=\left(\dfrac{9a_{1}}{f_{1}}\right)\cdot\alpha_{1}^{n}\cdot
10^{-2u_{1}-u_{2}}-1.$ (8)

We compare the upper bound in $(\ref{eq8})$ with the lower bound on the
quantity $\varGamma$ given by Theorem 2. First, we have that
$\varLambda_{1}\neq 0$. If $\varLambda_{1}=0$, then it is seen that

$a_{1}\alpha^{n}=\dfrac{f_{1}}{9}\cdot 10^{2u_{1}+u_{2}}.$

To check this, we consider the $\mathbb{Q}-$automorphism $\sigma$ of the
Galois extension $\mathbb{Q}(\alpha_{1},\alpha_{2})$ over $\mathbb{Q}$ defined
by $\sigma(\alpha_{1}):=\alpha_{2}$, and $\sigma(\alpha_{2}):=\alpha_{1}$, and
have

$\displaystyle\left|\sigma\left(\dfrac{f_{1}}{9}\cdot
10^{2u_{1}+u_{2}}\right)\right|=|\sigma(a_{1}\alpha_{1}^{n})|=|a_{2}\alpha_{2}^{n}|<1,$

which is false. Using the notations of Theorem 2, we have

$\displaystyle\lambda_{1}:=\dfrac{9a_{1}}{f_{1}},\ \lambda_{2}:=\alpha_{1},\
\lambda_{3}:=10,\ b_{1}:=1,\ b_{2}:=n,\ b_{3}:=-2u_{1}-u_{2},\ s:=3.$

Since $2u_{1}+u_{2}<n$, we can take $D:=n$. Observe that
$\mathbb{Q}(\lambda_{1},\lambda_{2},\lambda_{3})=\mathbb{Q}(\alpha_{1})$,
thus, $d:=3$. Furthermore,

$h(\lambda_{1})=h\left(\dfrac{9a_{1}}{f_{1}}\right)\leq
h(9)+h(a_{1})+h(f_{1})\leq\log 9+\dfrac{1}{3}\log 31+\log 9.$

Thus, it follows that $h(\lambda_{1})<5.54$. We also have that
$h(\lambda_{2})=h(\alpha_{1})=\displaystyle\dfrac{\log\alpha_{1}}{3}$, and
$h(\lambda_{3})=h(10)=\log 10$. Thus, we can take

$\displaystyle A_{1}:=16.62,\ A_{2}:=\log\alpha_{1},~{}\text{and}~{}\
A_{3}:=3\log 10.$

Theorem 2 tells us that

$\displaystyle\log|\Lambda_{1}|$ $\displaystyle>-1.4\cdot 30^{6}\cdot
3^{4.5}\cdot 3^{2}\cdot(1+\log 3)\cdot(1+\log n)\cdot
16.62\cdot(\log\alpha)(3\log 10)$ $\displaystyle>-1.20\times 10^{14}(1+\log
n),$

combining with (7), we obtain

$\displaystyle u_{1}\log 10-\log 27<1.20\times 10^{14}(1+\log n),$

which is simplified to

$\displaystyle u_{1}\log 10<1.21\times 10^{14}(1+\log n).$ (9)

Step 2. Equation $\eqref{eq4}$ is rewritten as

$\displaystyle 9a_{1}\alpha_{1}^{n}-(f_{1}\cdot 10^{u_{1}}-(f_{1}-f_{2}))\cdot
10^{u_{1}+u_{2}}=-9r(n)+(f_{1}-f_{2})\cdot 10^{u_{1}}-f_{1},$

which gives us

$\displaystyle|9a_{1}\alpha_{1}^{n}-(f_{1}\cdot 10^{u_{1}}-(f_{1}-f_{2}))\cdot
10^{u_{1}+u_{2}}|$ $\displaystyle=|-9r(n)+(f_{1}-f_{2})\cdot
10^{u_{1}}-f_{1}|$ $\displaystyle\leq 9\cdot\alpha_{1}^{-n/2}+18\cdot
10^{u_{1}}<27\cdot 10^{u_{1}}.$

If we divide both sides of the inequality by $(f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2}))\cdot 10^{u_{1}+u_{2}}$, then

$\displaystyle\left|\left(\dfrac{9a_{1}}{f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2})}\right)\cdot\alpha_{1}^{n}\cdot
10^{-u_{1}-u_{2}}-1\right|$ $\displaystyle<\dfrac{27\cdot
10^{u_{1}}}{(f_{1}\cdot 10^{u_{1}}-(f_{1}-f_{2}))\cdot
10^{u_{1}+u_{2}}}<\dfrac{27}{10^{u_{2}}}.$ (10)

Set

$\displaystyle\varLambda_{2}:=\left(\dfrac{9a_{1}}{f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2})}\right)\cdot\alpha_{1}^{n}\cdot 10^{-u_{1}-u_{2}}-1.$

Similar to the previous case as in $\varLambda_{1}$, we have that
$\varLambda_{2}\neq 0$. If $\Lambda_{2}=0$, then

$\displaystyle a_{1}\alpha_{1}^{n}=\left(\dfrac{f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2})}{9}\right)\cdot 10^{u_{1}+u_{2}}.$

This can be seen when we take the $\mathbb{Q}-$automorphism $\sigma$ of the
Galois extension $\mathbb{Q}(\alpha_{1},\alpha_{2})$ over $\mathbb{Q}$ defined
by $\sigma(\alpha_{1}):=\alpha_{2}$, and $\sigma(\alpha_{2}):=\alpha_{1}$.
Thus, we have

$\displaystyle\left|\left(\dfrac{f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2})}{9}\right)\cdot
10^{u_{1}+u_{2}}\right|=|\sigma(a_{1}\alpha_{1}^{n})|=|a_{2}\alpha_{2}^{n}|<1,$

which is not true. We apply Theorem 2 with the obvious notations as follows:

$\displaystyle\lambda_{1}:=\dfrac{9a_{1}}{f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2})},\ \lambda_{2}:=\alpha_{1},\ \lambda_{3}:=10,\
b_{1}:=1,\ b_{2}:=n,\ b_{3}:=-u_{1}-u_{2},\ s:=3.$

We also have that $u_{2}<n$, and therefore, we can have $D:=n$. For
$\lambda_{1}$, we use the properties of logarithmic heights to deduce that

$\displaystyle h(\lambda_{1})$ $\displaystyle=h\left(\dfrac{9a_{1}}{f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2})}\right)$ $\displaystyle\leq
h(9)+h(a_{1})+u_{1}h(10)+h(f_{1})+h(f_{1}-f_{2})+\log 2$ $\displaystyle\leq
3\log 9+h(a_{1})+u_{1}\log 10+\log 2$ $\displaystyle<3\log
9+\displaystyle\frac{1}{3}\log 31+1.21\times 10^{14}(1+\log n)$
$\displaystyle<1.22\times 10^{14}(1+\log n).$

We also have that

$\displaystyle|\log\lambda_{1}|$
$\displaystyle=\bigg{|}\log\left(\dfrac{9a_{1}}{f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2})}\right)\bigg{|}$ $\displaystyle\leq\log a+\log
9+|\log(f_{1}\cdot 10^{u_{1}}-(f_{1}-f_{2}))|$ $\displaystyle\leq\log
a_{1}+\log 9+\log(f_{1}\cdot
10^{u_{1}})+\bigg{|}\log\left(1-\dfrac{(f_{1}-f_{2})}{(f_{1}\cdot
10^{u_{1}})}\right)\bigg{|}$ $\displaystyle\leq u_{1}\log 10+\log f_{1}+\log
9+\log(0.55)+\bigg{|}\dfrac{|(f_{1}-f_{2})|}{(f_{1}\cdot
10^{u_{1}})}+\dfrac{1}{2}\left(\dfrac{|(f_{1}-f_{2})|}{(f_{1}\cdot
10^{u_{1}})}\right)^{2}+\cdots\bigg{|}$ $\displaystyle\leq u_{1}\log 10+3\log
9+\dfrac{1}{10^{u_{1}}}+\dfrac{1}{2.10^{2u_{1}}}+\cdots$
$\displaystyle<1.21\times 10^{14}(1+\log n)+3\log 9+\dfrac{1}{10^{u_{1}}-1}$
$\displaystyle<1.22\times 10^{14}(1+\log n).$

Note that (9) has been used in the second last inequality. It is clear that
$d\cdot h(\lambda_{1})>|\log\lambda_{1}|$.

Thus, we have

$\displaystyle A_{1}:=3.66\times 10^{14}(1+\log n),\ A_{2}:=\log\alpha_{1},\
\text{and}\ A_{3}:=3\log 10.$

From Theorem 2, we obtain

$\displaystyle\log|\varLambda_{2}|$ $\displaystyle>-1.4\cdot 30^{6}\cdot
3^{4.5}\cdot 3^{2}\cdot(1+\log 3)(1+\log n)(3.66\times 10^{14}(1+\log
n))(\log\alpha_{1})(3\log 10)$ $\displaystyle>~{}-2.64\times 10^{27}(1+\log
n)^{2},$

and combining with $\eqref{eq10}$ leads to

$\displaystyle u_{2}\log 10<2.64\times 10^{27}(1+\log n)^{2}+\log
27<2.65\times 10^{27}(1+\log n)^{2}.$ (11)

Step 3. Rewriting (3.2), we have that

$\displaystyle 9a_{1}\alpha_{1}^{n}-f_{1}\cdot
10^{2u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{1}+u_{2}}-(f_{1}-f_{2})\cdot
10^{u_{1}}=-9r(n)-d_{1}.$

This further yields

$\displaystyle\bigg{|}9a_{1}\alpha_{1}^{n}-(f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{2}}-(f_{1}-f_{2}))\cdot
10^{u_{1}}\bigg{|}$ $\displaystyle=\bigg{|}-9r(n)-f_{1}\bigg{|}$
$\displaystyle\leq\dfrac{9}{\alpha_{1}^{n/2}}+9<18.$

As a result, we obtain

$\displaystyle\bigg{|}\left(\dfrac{1}{9a_{1}}\right)(f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot
10^{u_{2}}-(f_{1}-g_{2}))\cdot\alpha_{1}^{-n}\cdot
10^{u_{1}}-1\bigg{|}<\dfrac{18}{9a_{1}\alpha_{1}^{n}}<\dfrac{2}{\alpha_{1}^{n}}.$
(12)

We let

$\displaystyle\varLambda_{3}:=\bigg{(}\left(\dfrac{1}{9a_{1}}\right)(f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot
10^{u_{2}}-(f_{1}-f_{2}))\bigg{)}\cdot\alpha_{1}^{-n}\cdot 10^{u_{1}}-1.$

Using similar arguments as in $\varLambda_{1}$ and $\varLambda_{2}$, we notice
that $\varLambda_{3}\neq 0$. If $\varLambda_{3}=0$, then we would have

$\displaystyle a_{1}\alpha_{1}^{n}=\dfrac{1}{9}\bigg{(}f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{2}}-(f_{1}-f_{2})\bigg{)}\cdot
10^{u_{1}}.$

We verify this by considering the $\mathbb{Q}-$automorphism $\sigma$ of the
Galois extension $\mathbb{Q}(\alpha_{1},\alpha_{2})$ over $\mathbb{Q}$ given
by $\sigma(\alpha_{1}):=\alpha_{2}$, and $\sigma(\alpha_{2}):=\alpha_{1}$.
Hence, we obtain

$\displaystyle\left|\dfrac{1}{9}\bigg{(}f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{2}}-(d_{1}-d_{2})\bigg{)}\cdot
10^{u_{1}}\right|=|\sigma(a_{1}\alpha_{1}^{n})|=|a_{2}\alpha_{2}^{n}|<1,$

which is false. Thus, applying Theorem 2, we have

$\lambda_{1}:=\left[\dfrac{1}{9a_{1}}\bigg{(}f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{2}}-(f_{1}-f_{2})\bigg{)}\right],\
\lambda_{2}:=\alpha_{1},\ \lambda_{3}:=10,$

$b_{1}:=1,\ b_{2}:=-n,\ b_{3}:=u_{1},\ s:=3.$

Similarly, $D:=n$, and $d:=3$. We also have that

$\displaystyle h(\lambda_{1})$ $\displaystyle\leq
h(9)+h(a_{1})+h(f_{1})+(u_{1}+u_{2})h(10)+h(f_{1}-f_{2})+u_{2}h(10)+h(f_{1}-f_{2})+3\log
2$ $\displaystyle\leq 5\log 9+\dfrac{\log 31}{3}+(u_{1}+u_{2})\log
10+u_{2}\log 10$ $\displaystyle\leq 6\log 9+(u_{1}+u_{2})\log 10+u_{2}\log
10.$

Inequalities $(\ref{eq9})$ and $(\ref{eq11})$ give

$\displaystyle(u_{1}+u_{2})\log 10$ $\displaystyle<1.21\times 10^{14}(1+\log
n)+2.65\times 10^{27}(1+\log n)^{2}$ $\displaystyle<2.66\times 10^{27}(1+\log
n)^{2}.$ (13)

Hence, we can deduce that

$\displaystyle h(\lambda_{1})<5.32\times 10^{27}(1+\log n)^{2}.$

Still further, we have

$\displaystyle|\log\lambda_{1}|$
$\displaystyle=\bigg{|}\log\left(\dfrac{1}{9a_{1}}(f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{2}}-(f_{1}-f_{2}))\right)\bigg{|}$
$\displaystyle\leq\log 9+\log a_{1}+|\log(f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{2}}-(f_{1}-f_{2}))|$
$\displaystyle\leq 2\log 9+\log(f_{1}\cdot
10^{u_{1}+u_{2}})+\bigg{|}\log\left(1-\dfrac{(f_{1}-f_{2})(10^{u_{2}}-1)}{f_{1}\cdot
10^{u_{1}+u_{2}}}\right)\bigg{|}$ $\displaystyle\leq 3\log 9+(u_{1}+u_{2})\log
10+\bigg{|}\log\left(1-\dfrac{(f_{1}-f_{2})(10^{u_{2}}-1)}{f_{1}\cdot
10^{u_{1}+u_{2}}}\right)\bigg{|}$ $\displaystyle\leq 3\log 9+(u_{1}+u_{2})\log
10+\bigg{|}\dfrac{|(f_{1}-f_{2})(10^{u_{2}}-1)|}{f_{1}\cdot
10^{u_{1}+u_{2}}}+\dfrac{1}{2}\left(\dfrac{|(f_{1}-f_{2})(10^{u_{2}}-1)|}{f_{1}\cdot
10^{u_{1}+u_{2}}}\right)^{2}+\cdots\bigg{|}$ $\displaystyle\leq 3\log
9+(u_{1}+u_{2})\log 10+\dfrac{1}{10^{u_{1}}}+\dfrac{1}{2\cdot
10^{2u_{1}}}+\cdots$ $\displaystyle<3\log 9+(u_{1}+u_{2})\log
10+\dfrac{1}{10^{u_{1}}-1}.$

Using inequality (3.2), we get $|\log\lambda_{1}|<2.67\times 10^{27}(1+\log
n)^{2}$. It is also seen that $d\cdot h(\lambda_{1})>|\log\lambda_{1}|$.
Therefore, we have $A_{1}:=8.01\times 10^{27}(1+\log n)^{2},\
A_{2}:=\log\alpha_{1},\ \text{and }A_{3}:=3\log 10$. Theorem 2 leads to

$\log|\varLambda_{3}|>-5.77\times 10^{40}(1+\log n)^{3},$

and comparing it with inequality (12), we obtain

$n\log\alpha_{1}-\log 2<5.77\times 10^{40}(1+\log n)^{3}.$

Thus, we infer that

$n<1.53\times 10^{41}(\log n)^{3},$

and applying Lemma 1, we have

$m:=3,\ x:=n,\ \text{and}\ T:=1.53\times 10^{41}.$

Hence, we obtain the inequality

$\displaystyle n<2^{3}\cdot 1.53\times 10^{41}\cdot(\log 1.53\times
10^{41})^{3},$

which simplifies to

$\displaystyle n<1.05\times 10^{48}.$

From Lemma 3, one can conclude that

$\displaystyle 2u_{1}+u_{2}<1.76\times 10^{47}.$

The following result is a summary of what has been proved.

######  Lemma 4.

All solutions to equation $(\ref{eq4})$ satisfy

$\displaystyle 2u_{1}+u_{2}<1.76\times 10^{47}\quad\text{and}\quad
n<1.05\times 10^{48}.$

###  3.3 Reducing the bounds.

We return to the inequality $(\ref{eqn7})$, and let

$\displaystyle\Gamma_{1}:=(2u_{1}+u_{2})\log
10-n\log\alpha_{1}+\log\left(\dfrac{d_{1}}{9a_{1}}\right).$

Inequality $(\ref{eqn7})$ is now rewritten as

$\displaystyle\left|e^{-\varGamma_{1}}-1\right|<\dfrac{27}{10^{u_{1}}}.$

We see that $-\varGamma_{1}\neq 0$, since
$e^{-\varGamma_{1}}-1=\varLambda_{1}\neq 0$. Assuming that $u_{1}\geq 2$, then
the above inequality becomes

$\left|e^{-\varGamma_{1}}-1\right|<\displaystyle\frac{27}{100}<\displaystyle\frac{1}{2}.$

It is known that $\text{if}~{}z<0~{}\text{and}~{}\mid
e^{z}-1\mid<\frac{1}{2},~{}\text{then}~{}\mid z\mid<2\mid e^{z}-1\mid.$
Consequently, we get the inequality

$\left|\varGamma_{1}\right|<\dfrac{54}{10^{u_{1}}},$

which leads to

$\displaystyle\left|(2u_{1}+u_{2})\left(\dfrac{\log
10}{\log\alpha_{1}}\right)-n+\left(\dfrac{\log(f_{1}/9a_{1})}{\log\alpha_{1}}\right)\right|<\dfrac{54}{10^{u_{1}}\log\alpha_{1}}.$

It now follows from Lemma 2 that:

$\displaystyle\vartheta:=\dfrac{\log
10}{\log\alpha_{1}},\quad\mu(f_{1}):=\dfrac{\log(f_{1}/9a_{1})}{\log\alpha_{1}},\quad
1\leq f_{1}\leq 9,\quad
A:=\dfrac{54}{\log\alpha_{1}},\quad\text{and}~{}~{}B:=10.$

We choose $M:=10^{48}$ as the upper bound on $2u_{1}+u_{2}$. A quick
computation with Mathematica program shows that the convergent of $\vartheta$
is such that $q_{81}>6M$, and $\xi>0.0549802$. Thus, we have that

$\displaystyle u_{1}\leq\dfrac{\log(54/\log\alpha_{1})q/\xi)}{\log 10}<52.$

This tell us that $u_{1}\leq 52$. In fact $u_{1}<2$ is also true since
$u_{1}<2<52$.

Next, for $f_{1}\neq f_{2}\in\\{0,1,2,\cdots,9\\},\ f_{1}>0$, and $1\leq
u_{1}\leq 52$, we go back and use (10). Let us define

$\displaystyle\varGamma_{2}:=(u_{1}+u_{2})\log
10-n\log\alpha_{1}+\log\left(\dfrac{d_{1}.10^{u_{1}}-(d_{1}-d_{2})}{9a_{1}}\right).$

Rewriting (10) gives the inequality

$\displaystyle\left|e^{-\varGamma_{2}}-1\right|<\dfrac{27}{10^{u_{2}}},$

where $-\varGamma_{2}\neq 0$, since $e^{-\varGamma_{2}}-1=\varLambda_{2}\neq
0$. If we assume that $u_{2}\geq 2$, then we also obtain

$\displaystyle\left|e^{-\Gamma_{2}}-1\right|<\displaystyle\frac{27}{100}<\displaystyle\frac{1}{2}.$

Consider the fact that $\text{if}~{}z<0~{}\text{and}~{}\mid
e^{z}-1\mid<\dfrac{1}{2},~{}\text{then}~{}\mid z\mid<2\mid e^{z}-1\mid.$ As a
result, we obtain the inequality

$\left|\varGamma_{2}\right|<\dfrac{54}{10^{u_{2}}},$

which further yields

$\displaystyle\left|(u_{1}+u_{2})\left(\dfrac{\log
10}{\log\alpha_{1}}\right)-n+\left(\dfrac{\log((f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2}))/9a_{1})}{\log\alpha_{1}}\right)\right|<\dfrac{54}{10^{u_{2}}\log\alpha_{1}}.$

Applying Lemma 2 gives us

$\displaystyle\vartheta:=\dfrac{\log
10}{\log\alpha_{1}},\quad\mu(f_{1},f_{2}):=\dfrac{\log((f_{1}\cdot
10^{u_{1}}-(f_{1}-f_{2}))/9a_{1})}{\log\alpha_{1}},\quad
A:=\dfrac{54}{\log\alpha_{1}},~{}~{}\text{and}\quad B:=10.$

We take $M:=10^{48}$ as the upper bound on $u_{1}+u_{2}$, since
$u_{1}+u_{2}<2u_{1}+u_{2}$. A quick computation using Mathematica program
reveals the convergent of $\vartheta$ such that $q_{81}>6M$, and
$\xi>0.0000252223$. Hence, we write

$\displaystyle u_{2}\leq\dfrac{\log(54/\log\alpha_{1})q/\xi)}{\log 10}<57.$

This implies that $u_{2}\leq 57$. Similarly, the case $u_{2}<2$ holds since
$u_{2}<2<57$.

Finally, for $f_{1}\neq f_{2}\in\\{0,1,2,\cdots,9\\},~{}1\leq u_{1}\leq 52$
and $1\leq u_{2}\leq 57$, we consider (12), then set

$\displaystyle\varGamma_{3}:=u_{1}\log
10-n\log\alpha_{1}+\log\left(\dfrac{f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot 10^{u_{2}}-(f_{1}-f_{2})}{9a_{1}}\right).$

It is noted that (12) is equivalent to the inequality

$\displaystyle\left|e^{\varGamma_{3}}-1\right|<\dfrac{1}{\alpha_{1}^{n}}.$

Similarly, $\varGamma_{3}\neq 0$, since
$e^{\varGamma_{3}}-1=\varLambda_{3}\neq 0$. Using the assumption $n>500$, we
clearly see that

$\left|e^{\varGamma_{3}}-1\right|<\displaystyle\dfrac{1}{2}.$

Again using the fact that $\text{if}~{}z<0~{}\text{and}~{}\mid
e^{z}-1\mid<\dfrac{1}{2},~{}\text{then}~{}\mid z\mid<2\mid e^{z}-1\mid.$ Thus,
it follows that

$\left|\varGamma_{3}\right|<\dfrac{2}{\alpha_{1}^{n}},$

which yields the inequality

$\displaystyle\left|u_{1}\left(\dfrac{\log
10}{\log\alpha_{1}}\right)-n+\left(\dfrac{\log((f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot
10^{u_{2}}-(f_{1}-f_{2}))/9a_{1})}{\log\alpha_{1}}\right)\right|<\dfrac{4}{\alpha_{1}^{n}\log\alpha_{1}}.$

Similarly, we apply Lemma 2, with known parameters;

$\displaystyle\vartheta$ $\displaystyle:=\dfrac{\log
10}{\log\alpha_{1}},\quad\mu(f_{1},f_{2}):=\dfrac{\log((f_{1}\cdot
10^{u_{1}+u_{2}}+(f_{1}-f_{2})\cdot
10^{u_{2}}-(f_{1}-f_{2}))/9a_{1})}{\log\alpha_{1}},$ $\displaystyle A$
$\displaystyle:=\dfrac{4}{\log\alpha_{1}},\quad\text{and}\quad B:=\alpha_{1}.$

Again, we take $M:=10^{48}$ as the upper bound for $u_{1}$, since
$u_{1}<2u_{1}+u_{2}$. With the help of Mathematica program, it is seen that
convergent of $\vartheta$ is such that $q_{81}>6M$, and $\xi\geq
0.000000902495$. This implies that

$\displaystyle
n\leq\dfrac{\log((4/\log\alpha_{1})q/\xi)}{\log\alpha_{1}}<332.$

Therefore, $n\leq 332$, which contradicts the assumption that $n>500$. This
finishes the proof of Theorem 1. ∎

## Acknowledgements.

The authors thank the anonymous referees for the careful reading of the
manuscript, as well as the useful comments and suggestions that have greatly
improved on the quality of presentation of this paper.

## Declarations.

The authors declare no conflict of competing interests.

## References

  * [1] Alahmadi, A., Altassan, A., Luca, F., & Shoaib, H. (2021). Fibonacci numbers which are concatenations of two repdigits. Quaestiones Mathematicae, 44(2), 281-290.
  * [2] Allouche, J. P., & Johnson, T. (1996). Narayana’s cows and delayed morphisms. Troisiemes Journées d’Informatique Musicale (JIM 96), 4.
  * [3] Alvarado, S. D., & Luca, F. (2011, July). Fibonacci numbers which are sums of two repdigits. In Proceedings of the XIVth International Conference on Fibonacci numbers and their applications (Vol. 20, pp. 97-108). Aportaciones Matemáticas, Investigación.
  * [4] Baker, A., & Davenport, H. (1969). The equations $3x^{2}-2=y^{2}$ and $8x^{2}-7=z^{2}$. The Quarterly Journal of Mathematics, 20(1), 129-137.
  * [5] Batte, H., Chalebgwa, T. P., & Ddamulira, M. (2022). Perrin numbers that are concatenations of two repdigits. Arabian Journal of Mathematics, 1-10.
  * [6] Bravo, E. F., Bravo, J. J., & Gómez, C. A. (2021). Generalized Lucas Numbers Which are Concatenations of Two Repdigits. Results in Mathematics, 76(3), 1-16.
  * [7] Bravo, J. J., & Luca, F. (2013). On a conjecture about repdigits in k-generalized Fibonacci sequences. Publ. Math. Debrecen, 82(3-4), 623-639.
  * [8] Bugeaud, Y., Mignotte, M., & Siksek, S. (2006). Classical and modular approaches to exponential Diophantine equations I. Fibonacci and Lucas perfect powers. Annals of mathematics, 969-1018.
  * [9] Ddamulira, M. (2021). Padovan numbers that are concatenations of two distinct repdigits. Mathematica Slovaca. 71(2), 275-284.
  * [10] Ddamulira, M. (2020). Tribonacci numbers that are concatenations of two repdigits. Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas, 114(4), 1-10.
  * [11] Ddamulira, M., Emong, P., & Mirumbe, G. I. (2022). Members of Narayana’s cow sequence that are concatenations of two repdigits. arXiv preprint arXiv:2210.00926.
  * [12] Dujella, A., & Pethő, A. (1998). A generalization of a theorem of Baker and Davenport. The Quarterly Journal of Mathematics, 49(195), 291-306.
  * [13] Erduvan, F., & Keskin, R. (2021). Lucas numbers which are concatenations of two repdigits. Boletín de la Sociedad Matemática Mexicana, 27(1), 1-11.
  * [14] Erduvan, F., & Keskin, R. (2021). Lucas numbers which are concatenations of three repdigits. Results in Mathematics, 76(1), 1-13.
  * [15] Luca, F. (2012). Repdigits as sums of three Fibonacci numbers. Mathematical Communications, 17(1), 1-11.
  * [16] Matveev, E. M. (2000). An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers. II. Izvestiya: Mathematics, 64(6), 1217.
  * [17] Qu, Y., & Zeng, J. (2020). Lucas numbers which are concatenations of two repdigits. Mathematics, 8(8), 1360.
  * [18] Rayaguru, S. G., & Panda, G. K. (2020). Balancing numbers which are concatenation of two repdigits. Boletín de la Sociedad Matemática Mexicana, 26(3), 911-919.
  * [19] Guzmán Sanchez, S., & Luca, F. (2014). Linear combinations of factorials and $S$-units in a binary recurrence sequence. Annales mathématiques du Québec, 38(2), 169-188.
  * [20] Trojovský, P. (2020). Fibonacci numbers with a prescribed block of digits. Mathematics, 8(4), 639.

## Addresses

1 Department of Mathematics, Makerere University, P.O. Box 7062 Kampala,
Uganda

Email<EMAIL_ADDRESS>
2 Department of Mathematics, Makerere University, P.O. Box 7062 Kampala,
Uganda

Email<EMAIL_ADDRESS>
3 Department of Mathematics, Makerere University, P.O. Box 7062 Kampala,
Uganda

<EMAIL_ADDRESS>


# Rolling Horizon Evolutionary Algorithms for General Video Game Playing
††thanks: Raluca D. Gaina, Simon M. Lucas, Diego Pérez-Liébana (School of
Electronic Engineering and Computer Science, 10 Godward Square, Queen Mary
University of London, Mile End Rd, London E1 4FZ, UK; email:
{r.d.gaina,simon.lucas,diego.perez}@qmul.ac.uk),
Sam Devlin (Microsoft Research Cambridge; email<EMAIL_ADDRESS>
Raluca D. Gaina, Sam Devlin, Simon M. Lucas, Diego Perez-Liebana

###### Abstract

Game-playing Evolutionary Algorithms, specifically Rolling Horizon
Evolutionary Algorithms, have recently managed to beat the state of the art in
win rate across many video games. However, the best results in a game are
highly dependent on the specific configuration of modifications and hybrids
introduced over several papers, each adding additional parameters to the core
algorithm. Further, the best previously published parameters have been found
from only a few human-picked combinations, as the possibility space has grown
beyond exhaustive search. This paper presents the state of the art in Rolling
Horizon Evolutionary Algorithms, combining all modifications described in
literature, as well as new ones, for a large resultant hybrid. We then use a
parameter optimiser, the N-Tuple Bandit Evolutionary Algorithm, to find the
best combination of parameters in 20 games from the General Video Game AI
Framework. Further, we analyse the algorithm’s parameters and some interesting
combinations revealed through the optimisation process. Lastly, we find new
state of the art solutions on several games by automatically exploring the
large parameter space of RHEA.

###### Index Terms:

Evolutionary computation, rolling horizon, computational intelligence,
artificial intelligence, games, general video game playing, real-time games

##  I Introduction

In this paper we revisit the application of game-playing Evolutionary
Algorithms with a deeper analysis of algorithm modifications and hybrids. We
argue that automatic exploration (or algorithmic optimisation) of algorithm
variations is essential for problems with large search spaces, although not
exhaustive due to computation speed limitations. This optimisation process can
further lead to insights into the algorithm being optimised, and as such we
additionally conduct an in-depth analysis of the parameter space, while
highlighting performance gain in various games.

There have been several recent advances in game-playing Evolutionary
Algorithms [1, 2] and a multitude of modifications and hybrids proposed to
improve performance across a large number of games. The result is that the
possibility space for algorithm configurations has grown beyond efficient
manual optimisation. Although preforming grid-search is sometimes possible for
finding good values for some parameters [3], more recent works find the need
to reduce more and more the number of parameter combinations chosen for
analysis [4]. Therefore, the interesting insights into which variation of the
algorithm is actually best are limited to human exploration of very small
sections of the entirety of the search space.

The specific novel application of Evolutionary Algorithms as game-playing
methods (referred to as Rolling Horizon Evolutionary Algorithms, or RHEA) was
introduced for the first time in 2013 by Perez et al. [5]. In the context of
playing games, RHEA evolves, at every game step, a sequence of actions to play
in the game; the first action of the best sequence found is played at the end
of the evolutionary process and a new sequence is evolved for the subsequent
game step. This base algorithm has been extended in several works. Gaina et
al. [3] performed an in-depth analysis of the algorithm’s main parameters
(population size and individual length), generally finding that the higher the
parameter values (even reaching the extreme of Random Search), the better RHEA
performs across several games; this work further highlights an increase in
performance with the increase of the available budget and correspondingly
higher parameter values. Different population initialisation methods were
explored in [6]; this work was important in highlighting the benefit of using
different options in different game types, as some games saw increased
performance with greedy initialisation, while others preferred a statistical
approach instead. Furthermore, Gaina et al. tested in [7] various hybrids and
combinations with other techniques, which further pinpointed not only the
difference in performance of certain parameter configurations across the
different games, but also that the RHEA parameter space was already being
expanded beyond the possibility of exhaustively exploring all parameter
combinations. Some of these enhancements were further tested by Santos et al.
[8] in General Video Game AI (GVGAI) and by Tong et al. [9] in MuJoCo’s
physical control tasks, both with great success. Finally, a study on
dynamically adjusting individual length based on the fitness landscape
observed during evolution [4] shows that some parameters might be conflicting
with each other and cause poor performance in some games and suggests a need
for carefully constructed parameter search spaces.

The work in this paper is carried out within the domain of general video game
playing, which focuses on finding general-purpose Artificial Intelligence
players that are able to play any game, even those unseen previously. The
concepts behind this could be further extended to general AI which is able to
solve any given task (as opposed to any given game), as methods developed for
games have been shown to be applicable to wider domains, such as chemistry
[10]. Two large categories of players can be differentiated in this domain:
planning and learning. The latter requires training for several episodes on a
game before it can figure out how to play it, which is often an expensive
process leading to narrow results: the agent trained for one game would be
unlikely to be able to play another without significant training on the new
game. The former category, which RHEA belongs to, refers to methods which work
online, during the game, to search for the appropriate solutions. These
methods require an internal model of the games (referred to as a forward
model, or FM) to be able to simulate possible futures and effects of their
actions. Although planning methods are more generally applicable, they face
the drawback of the lack of a FM in some games, as this is not always
feasible. The problem of learning any game’s model is an active research area
[11] which would make our methods even more widely applicable, even in complex
commercial games; however, in this work we apply our algorithms to games which
do have a model available.

In this context, Monte Carlo Tree Search (MCTS) had for a long time
represented the state of the art in general video game playing. However, RHEA
has been shown to outperform MCTS in multiple games in some of its variations
[7], while other combinations of modifications led to significantly worse
results. As highlighted by Lucas et al. [12], there can be a large difference
in performance for the same base algorithm when using different parameters,
and optimisation is essential. Ashlock et al. [13] emphasise this in the
context of general game playing, where one single method (or single parameter
configuration, in our approach) is unlikely to achieve high performance across
all possible tasks. Our specific problem is additionally highly noisy: most
games are stochastic and the same sequence of actions in a game could lead to
different outcomes; furthermore, the algorithm itself is stochastic and may
produce different outputs given the same game state.

In this paper, we use the N-Tuple Bandit Evolutionary Algorithm (NTBEA) [14]
for optimising RHEA parameters, an algorithm which has shown robust high
performance in noisy optimisation problems, even when compared with
alternatives. It features high sample efficiency, fast convergence and good
scaling for large search spaces [12]. Simulations of AI players on a multitude
of games can be very expensive, therefore sample efficiency is key, making
NTBEA suitable for optimising RHEA parameters. The algorithm has been
previously successfully employed in several noisy optimisation problems, such
as tuning game parameters [15] as well as AI game-player parameters [16, 12,
17]. A highly adaptive system which can optimise its parameters and structure
so as to achieve best performance in various games could easily feed into a
generic life-long learning system such as that presented in [18].

A summary of our contributions is as follows:

  1. 1.

We give an overview of the current state of the art in Rolling Horizon
Evolutionary Algorithms within the context of general video game playing.

  2. 2.

We perform an in-depth analysis and optimisation of the algorithm’s parameters
with respect to its performance across the various games tested.

  3. 3.

We find new configurations which outperform the previous state of the art on a
range of GVGAI games.

##  II Background

This section describes the two key concepts employed in this paper, the
Rolling Horizon Evolutionary Algorithm (RHEA) and the N-Tuple Bandit
Evolutionary Algorithm (NTBEA), as well as introducing the framework and game
set used for experiments.

###  II-A Rolling Horizon Evolution

RHEA utilises Evolutionary Algorithms (EA) to evolve an in-game sequence of
actions at every game tick, with restricted computation time per execution.
This subsection will describe the baseline algorithm, often referred to as
vanilla; modifications applied are detailed in Section III.

In this application of EAs for game-playing, the genotype is described as a
vector of integers of length $L$ (individual length), where each integer $a$
is in the range $[0,N)$, with $N$ being the maximum number of actions in a
given game. This translates to a phenotype as a sequence of actions played in
the game starting from state $S_{0}$, or, in other words, the behaviour of the
player. If the action chosen at any game step is illegal or cannot reasonably
be played (e.g. walking into a wall), it is automatically treated as “do
nothing” by the game engine, thus the EA does not see any individuals, or
genes in the individuals, as illegal or infeasible. In order to evaluate an
individual in this context, RHEA uses the forward model (FM) of the game, an
internal model of the world, to simulate through the actions, one at a time.
The game state reached at the end is then evaluated with a heuristic function
$h$ and this value becomes the fitness of the individual: therefore, we are
evolving action sequences which lead to the best game outcome, limited to the
exploration range $L$. The heuristic function $h$ is always kept to a generic
form throughout the experiments; this aims to maximize the game score, while
favouring wins and discouraging losses, see Equation 1 ($s$ is the game state
being evaluated and $score$ is the game score normalised in $(0,1)$).

$h(s)=\begin{cases}1&\text{win = True}\\\ 0&\text{win = False}\\\
score&\text{otherwise}\end{cases}$ (1)

Using this method to evaluate individuals, the vanilla algorithm follows a
typical EA process. It begins by initialising a population of $P$ individuals
of length $L$ at random and evaluates them. At every generation, while budget
is still available, it promotes $E$ individuals directly to the next
generation through elitism. It then generates $P$ offspring by repeatedly
selecting parents through tournament selection, crosses them with uniform
crossover to create a child, and mutates the child through uniform mutation
before adding it to the pool of offspring. The best $P-E$ individuals from
both parents and offspring pools are added to the next generation and the
process repeats. Typically, a budget of $40$ms per game tick is given to the
algorithm for real-time decision-making.

We would further like to highlight the benefits of choosing RHEA over Monte
Carlo Tree Search (MCTS), as the current favourite in general game-playing
methods: RHEA is easily parallelizable, with each individual being independent
from the rest and from the search process. It is able to handle continuous
actions without modification, which has been previously explored in [19]. It
can easily adapt to n-player games with minimal changes through co-evolution
[20] and the many possible enhancements and modifications make it highly
adaptive and controllable for different given problems.

TABLE I: Game set including feature analysis. The last 3 columns show clusters as depicted in previous works; games with the same value are denoted as part of the same cluster. As [21] do not include all of these games in their study, column [22] shows the game indexes between which the missing games are placed by Mark Nelson (lower-higher); [23] shows more recent work clustering all GVGAI games. Idx | Game | Stoch. | Rewards | Win | Lose | Levels | NPCs | Res. | Actions | [21] | [22] | [23]
---|---|---|---|---|---|---|---|---|---|---|---|---
0 | Dig Dug | x | D | Puzzle/Kill | Timeout | L/Dense | E |  | Move+Shoot | 4 |  | 5
1 | Lemmings |  | D | Exit/Puzzle | Death | L/Dense | N |  | Move+Shoot | 4 |  | 5
2 | Roguelike | x | D | Exit | Death | L/Dense | E | x | Move+Shoot | 4 |  | 4
3 | Chopper | x | D+Disq | Kill | No-kill | L/Dense | E | x | Move+Shoot |  | g4-g1 | 2
4 | Crossfire | x | N | Exit | Death | M/Dense | E |  | Move | 2 |  | 4
5 | Chase |  | D | Kill | Death | M/Sparse | F+E |  | Move | 2 |  | 4
6 | Camel Race |  | N | Exit | Timeout | L/Sparse | E |  | Move | 2 |  | 3
7 | Escape |  | N | Exit/Puzzle | Death | M/Dense |  |  | Move | 2 |  | 3
8 | Hungry Birds |  | Disq | Exit | Timeout | M/Sparse |  | HP | Move |  | g7-g10 | 3
9 | Bait |  | N | Puzzle/Exit | Timeout | S/Sparse |  | x | Move | 4 |  | 4
10 | Wait for Breakfast |  | N | Puzzle | Timeout | M/Dense | N |  | Move | 2 |  | 3
11 | Survive Zombies | x | D | Timeout | Death | M/Dense | F+E |  | Move | 3 |  | 4
12 | Modality |  | N | Puzzle | Timeout | S/Dense |  |  | Move | 3 |  | 4
13 | Missile Command |  | D+Disq | Kill | No-kill | M/Sparse | E |  | Move+Shoot | 3 |  | 2
14 | Plaque Attack |  | D | Kill | No-kill | L/Dense | E |  | Move+Shoot | 3 |  | 2
15 | Sea Quest | x | D+Disq | Timeout | Death | M/Dense | F+E | x | Move+Shoot | 3 |  | 2
16 | Infection | x | D | Kill | Timeout | M/Dense | F+E |  | Move+Shoot | 1 |  | 1
17 | Aliens | x | D | Kill | Death | M/Dense | E |  | LR+Shoot | 1 |  | 1
18 | Butterflies | x | D | Kill | Timeout | M/Dense | F |  | Move | 1 |  | 2
19 | Intersection | x | D+Disq | Timeout | Death | L/Dense | E | HP | Move |  | g18-g17 | 1

###  II-B N-Tuple Bandit Evolutionary Algorithm

NTBEA is a model-based optimiser based on an Evolutionary Algorithm. It begins
by randomly initiating a solution $o$, or with a given solution (referred to
as seed, and the process as seeding the algorithm) if specified in its
application. It then evaluates one solution at a time, with the evaluation
method determined by the specific application, and adds it to its internal
$n$-tuple model - that is, all combinations of $n$ parameters are registered
to have observed the fitness of the evaluated solution. We use $1$, $2$ and
$L$ tuples, where $L$ is the solution length.

$n=50$ neighbours of the solution are then generated through uniform random
mutation, with probability $1/L$, forming neighbourhood $N$. The fitness of
all neighbours is estimated based on previously observed $n$-tuple values, by
calculating: the average values of the neighbour’s tuples, as well as the
average number of times each tuple was previously explored. These two
statistics are used within a bandit equation (see Equation 2) to choose the
neighbour with the highest value to be the solution evaluated next. This
equation aims to balance between promising solutions by exploiting high
fitness values $Q(o)$ and uncertain solutions by exploring those seen less
during the process $exp(o)$. The constant $k=2$ sets the focus of the
algorithm, whether more exploitative or more exploratory. Small random noise
(maximum $\epsilon=0.5$) is added to each neighbour’s final value to randomly
break ties.

The process then repeats with the new chosen solution ($o^{\prime}$) for a set
number of iterations.

$o^{\prime}=\operatorname*{arg\,max}_{o\in N}\left\\{Q(o)+k\times
exp(o)+noise\right\\}$ (2)

###  II-C Framework

We use NTBEA to tune RHEA parameters within the General Video Game AI (GVGAI)
framework [24]. GVGAI is a framework widely used in research [25] which
features a corpus of over $100$ single-player games and $60$ two-player games.
These are fairly small games, each focusing on specific mechanics or skills
the players should be able to demonstrate, including clones of classic arcade
games such as Space Invaders, puzzle games like Sokoban, adventure games like
Zelda or game-theory problems such as the Iterative Prisoners Dilemma. All
games are real-time and require players to make decisions in only $40$ms at
every game tick, although not all games explicitly reward or require fast
reactions; in fact, some of the best game-playing approaches add up the time
in the beginning of the game to run Breadth-First Search in puzzle games in
order to find an accurate solution [25]. However, given the large variety of
games (many of which are stochastic and difficult to predict accurately),
scoring systems and termination conditions, all unknown to the players,
highly-adaptive general methods are needed to tackle the diverse challenges
proposed.

GVGAI includes several different tracks which tackle different problems:
single-player planning [26], two-player planning [27] and single-player
learning tracks focus on finding general game-playing AI agents which would be
capable of planning (with internal models of the world) or learning across all
the games in the framework. More recently, level generation [28] (creating
levels for any game) and rule generation [29] (creating rules for any given
level) challenges were introduced as well, to push the limits of general game
AI.

For the purpose of the experiments described in this paper, we will focus on
the single-player planning track, although the work could easily be expanded
to include two-player games.

###  II-D Game set

We select $20$ single-player games out of the larger GVGAI corpus, as
previously analysed in several works. First introduced in [3] and described in
Table I, the game set used in this study is sampled based on GVGAI competition
entries performance across large subsets, so as to include games of varying
difficulty. Additionally, half of the games are deterministic and half are
stochastic, introducing additional noise to the parameter optimisation problem
explored in this paper.

The game table includes additional information about each game. They showcase
varying reward structures, such as games with no rewards (with the possibility
of gaining points on win/lose conditions only), games with dense rewards
(multiple interactions with the environment result in a score change) or games
with discontinuous rewards (a longer sequence of actions is required to obtain
the reward). Four different types of winning conditions are featured, in which
the player has to kill certain game objects (Kill), reach an exit point
(Exit), wait for a timer to run out (Timeout) or complete a certain more
precise sequence of actions (Puzzle, such as move a box onto a specific
point). Three types of losing conditions are included, which result in the
player losing if they run out of time (Timeout), die (Death) or fail to kill
specific game objects (No-kill).

Additionally, the 5 levels included with each game vary in size (Large - L,
Medium - M or Small - S) and density of interactive tiles (that is, tiles
which produce some sort of effect when the player interacts with it, such as
blocking the player’s path, moving or getting destroyed). Some games include
Non-Player Character (NPCs) that might either help the player (F), hurt the
player (E) or have no direct influence on the player’s win/lose condition or
score (N) through their behaviour. The player may need to collect resources or
pay particular attention to their avatar’s hitpoints (HP). Finally, games vary
in the actions available to the players (Move includes movement in all 4
directions, up, down, left and right; LR includes only left and right
movement; a special Shoot action might be available in some games, with
different effects). All symbols mentioned here refer strictly to the table
notation.

When discussing parameter choices, we will refer to games as similar based on
the features described in Table I, or the clustering identified from previous
works

##  III RHEA Parameter Space

This section describes all the evolutionary algorithm hyper-parameters used
for the experiments, including hybrids and game-specific modifications, some
introduced in previous work [3, 6, 7, 4], as highlighted in Figure 1.
Dependent parameters (2nd and 3rd column) are parameters that would not impact
the phenotype without specific values taken by parent parameters, as detailed
below.

Figure 1: Parameter search space, total size $4.03\times 10^{8}$. Possible
values for each parameter are between curly brackets, with default value
highlighted in bold green. Parameters not in the $1^{st}$ column are dependent
on others (denoted with arrows from parent to dependent; parent value required
for dependent to affect phenotype is noted in blue, between angled brackets).
Greyed-out parameters are not included in the experiments for this paper (the
default value were used instead). In yellow parameters previously analysed in
literature, with citation.

###  III-A Genetic operators

There are three main genetic operators used by the evolutionary algorithm in
RHEA: crossover, selection and mutation. In our implementation, selection is
only used to select parents for offspring, subsequent generations being formed
directly with the best individuals from the current generation (with no
further selection being applied). These three genetic operators each have
several implementation options, as discussed below. A hyper-parameter controls
which operators should be applied, with options of only using crossover (and
selection), only using mutation, or using all three to first obtain an
offspring from crossover and then mutate it as well. It is worth noting that
the operator type parameters are dependent on the choice of genetic operator:
changing the mutation type parameter would not have any effect on the
phenotype if no mutation is used in the algorithm, and similarly for crossover
and selection.

Selection. Three types of selection are available in the system: tournament,
roulette and rank. Tournament selection picks a percentage of the population
($t=50\%$) randomly and then chooses the best individuals from these to
reproduce. Roulette selection chooses individuals with probabilities equal to
their fitness (therefore, higher fitness individuals have a higher chance of
being selected). Rank selection first assigns inverse-ranks to all individuals
in the population according to their fitness (the lowest fitness individual
would have rank 1, second lowest rank 2 etc.) and then choose individuals with
probabilities equal to their rank (therefore, higher fitness individuals have
a higher chance of being selected, but the selection pressure is reduced by
minimizing the differences in fitness).

Crossover. Two types of crossover are available in the system: uniform and
$n$-point. Uniform crossover selects genes from either of the parents with
equal probability. $n$-point crossover randomly selects $n$ points along the
individuals which would split all individuals in subsections, the offspring
being formed then by alternatively choosing subsections of genes from the
parents; we use $1$ and $2$ as possible values for $n$, leading to three total
values for the crossover parameter.

Mutation. Four types of mutation are available in the system: uniform,
softmax, diversity and $n$-bits. Uniform mutation assigns each gene an equal
probability of mutation ($m=1/L$, where $L$ is the individual length) and
picks a different value for the genes mutating uniformly at random. Softmax
mutation uses the softmax equation (see Equation 3) to bias mutation towards
the beginning of the individual, which causes the largest perturbation in the
action sequence (changing any gene in the individual, in this context, also
changes the meaning of all subsequent genes - therefore changes in the
beginning of the genome have the largest impact in the phenotype). Diversity
mutation keeps track of all values for all genes from all individuals explored
during evolution and chooses to mutate the gene that has currently been
explored the least, to the value for the gene that has been explored the
least. Finally, $n$-bit mutation chooses $n$ genes uniformly at random to
mutate to a new and different random value; we use $1$ and $2$ as possible
values for $n$, leading to a total of five values for the mutation parameter.

$\text{Softmax}(x_{i})=\frac{\exp(x_{i})}{\sum_{j}\exp(x_{j})}$ (3)

###  III-B Fitness assignment

A key part of evaluating individuals, represented as action sequences, is the
fitness assignment resulting from the phenotype interpretation (i.e. a
sequence of game states the AI player traverses through the action sequence).
If all game states traversed are evaluated with a heuristic function $h$ (see
Equation 1), then this array of values $F$ corresponding to each of the game
states can be translated to a fitness value in different ways: keeping only
the value of the last game state reached: $F[L-1]$; keeping the difference
between the value of the last state and the value of the first state, so state
improvement value: $\Delta(F[L-1],F[0])$; keeping the average of all game
state values: $\overline{F}$; keeping the minimum value, a pessimistic model:
$min(F)$; keeping the maximum value, an optimistic model: $max(F)$; or keeping
a discounted sum of all values: $\sum_{i=0}^{L}F[i]\times\gamma^{i}$, where
$\gamma=0.9$, which prioritises immediate rewards.

###  III-C Initialisation

In the vanilla version, the algorithm is initialised with random individuals
(all genes in all individuals are picked uniformly at random from all possible
values). Different initialisation (or seeding) methods have been previously
tested in conjunction with the vanilla algorithm with various success [6].
Both One Step Look Ahead (1SLA) and Monte Carlo Tree Search (MCTS)
initialisation options, which have shown promise in various games in the
previous study by Gaina et. al are included in this system.

1SLA. This algorithm performs an exhaustive search of all possible actions in
a given game state and picks the action which leads to the highest value for
the following game state (evaluated with heuristic $h$ and breaking ties
randomly). To form an individual in the EA, this process is followed for each
gene: the best action is chosen for the first gene, and the game state is
advanced with the chosen action; this process is then repeated again for all
subsequent genes until an action sequence of sufficient length is generated.
If the end of the game is reached during the creation of an individual, the
individual is padded with random actions until it meets the required length.
For initialisation of a RHEA population, the first individual is created with
the 1SLA algorithm and the rest become mutated from the first. Given the
greedy approach, this reduces (and often completely removes) the randomness of
the initial population, in order to begin search from a local optimum.

MCTS. This algorithm iteratively builds a search tree by selecting nodes in
the tree to expand using the UCB1 formula, see Equation 4, where: constant
$C=\sqrt[]{2}$, $a$ is the chosen action from the set of possible actions
$A(s)$, $s$ is the current game state, $Q(s,a)$ is the value of choosing
action $a$ from state $s$, $N(s)$ is the number of times state $s$ has been
visited and $N(s,a)$ is the number of times state $s$ has been visited and
action $a$ was chosen next. It then evaluates nodes with Monte Carlo
simulations (a sequence of random actions up to a maximum tree depth $L$)
starting from the newly expanded node and updates the statistics ($N(s)$,
$N(s,a)$ and $Q(s,a)$ of all nodes traversed during an iteration with the
value given by the heuristic $h$ for the final game state reached after Monte
Carlo simulations. This tree grows asymmetrically as MCTS balances between
exploration of uncertain actions and exploitation of seemingly good actions.
For initialisation of a RHEA population, MCTS is run for half of the entire
thinking budget of the agent (leaving half available for evolution), and the
first individual is selected by greedily traversing the tree created. As the
tree would not be fully expanded, the path through the tree is capped when a
node with less than $3$ visits is reached and actions are added randomly up
until individual length $L$; the rest of the individuals are mutated from the
first.

$a^{*}=\operatorname*{arg\,max}_{a\in A(s)}\left\\{Q(s,a)+C\sqrt{\frac{\ln
N(s)}{N(s,a)}}\right\\}$ (4)

###  III-D Frame skip

Frame skipping has become common practice in several Reinforcenemnt Learning
works, and key in the success of specific applications [30, 31]: grouping $N$
game states when making a decision, to increase the data available and reduce
the frequency of decisions returned to only every $N$ game states. Statistical
forward planning approaches, on the other hand, usually make a new decision at
every game tick, repeating their search process in the very limited time. With
this modification, we test if SFP methods can also benefit from a longer time
for making decision by only returning an action every $N$ game ticks, replying
according to a specific strategy for the game ticks inbetween and using all
the time inbetween decisions for planning the next move. We test $0$ (no frame
skip, decisions at every game tick), $5$ and $10$ as values for $N$ and four
different strategies for actions inbetween decisions: repeat, null, random and
sequence. The repeat strategy simply repeats the previously decided action
until a new action is decided. The null strategy plays ACTION_NIL (does
nothing), which more closely mimics human player gameplay with pauses
inbetween actions. The random strategy plays a random action and the sequence
strategy continues playing the following actions in the best individual
returned with the last decision. The frame skip type parameter is dependant on
the frame skip value: if no frame skip is used (value $0$), then changing the
frame skip type would have no effect on the phenotype.

A form of frame skip using the repeat strategy described above was previously
tested in GVGAI by Perez et al. [32] with notable success in several games.

###  III-E Shift buffer

This is a population management technique which avoids repeating the entire
search process from scratch at every new game tick, which usually loses
information gained in previous iterations of the algorithm; this is meant to
make the algorithm more sample-efficient by retaining previous computation
information. The shift buffer has been employed in several works and tested in
GVGAI by Gaina et al. [7], and it works by keeping the final population
evolved during one game tick to the next. However, as the first action of the
best individual has just been played, all first actions from all individuals
in the population are removed and a new random action is added at the end (a
possible extension to this would keep only the individuals with the same first
action as the one chosen). Additionally, there exists the option in our
implementation to apply a discount to the values of all individuals in the new
population, which can be either $0.9$, $0.99$ or $1.0$ (no discount applied);
this would weaken the values of previously obtained sequences in the new
context. The shift buffer discount parameter is dependent on the shift buffer
toggle: if no shift buffer is used, then changing the shift buffer discount
would have no effect on the phenotype.

###  III-F Dynamic depth

It is often the case that different games benefit from different algorithm
parameters. In particular, the individual length has a high impact in the
performance of the vanilla RHEA, as shown in [3]. This was mainly tied to the
density of rewards in the various games in [4]: games with dense rewards
generally benefit from shorter individuals which would allow for more
generations and more statistics gathered to facilitate quick strategic
reactions; as opposed to games with sparse or no rewards, where longer
individuals are required in order to be able to find those rewards further
ahead. This difference in reward density can also be observed at a more
granular level, during the play-through of only one game: some areas of the
game may contain more rewards, whereas others would require more exploration.
Therefore, the dynamic depth modification presented in [4] is included in the
system, which has the option to change the length of the individuals at every
$5$ game ticks: if the standard deviation of the fitness landscape observed
previously falls below a threshold ($0.04$), decisions are considered to be
uncertain without much variety in rewards observed and the individual length
is increased by $2$; if the opposite happens and the fitness landscape
observed previously raises above a threshold ($0.9$), more generations are
prioritised for more informed decision making in a highly varied environment
and the individual length is decreased by $2$ instead. All parameters for
dynamic length adjustments were set based on [4] and could represent one point
for further increasing the parameter search space in further studies.

###  III-G MC rollouts

Lastly, we consider the hybridisation of the algorithm and its further
combination with MCTS, which has been very successful in many GVGAI games
[22]. We have previously described MCTS initialisation, but concepts from MCTS
can further be borrowed and integrated into RHEA, such as its Monte Carlo (MC)
simulation phase. As described in [7], the evaluation process in RHEA may add
MC rollouts of length {$0.0$ (no rollouts used), $0.5$, $1.0$ or $2.0$}
$\times$ $L$ after advancing through the action sequence of length $L$
represented by the individual; these may be repeated $1$, $5$ or $10$ times
for more statistics gathered. In order for this to be compatible with the
fitness assignment modifications, the values of all game states traversed (or
the average value for a particular game tick if there are repetitions
performed) $R$ are added at the end of the array of state values $F$ obtained
from the individual and all fitness assignment methods are applied to the
combined array of values ($F+R$) instead. The MC rollout repetition parameter
is dependent on the rollout length: if the length is set to $0.0$, then
changing the number of rollout repetitions would have no effect on the
phenotype.

##  IV Experiments

Given the large number of parameter combinations, estimated at $4.03\times
10^{8}$, it would take a significant amount of time to test each combination
exhaustively in several games and with repetitions for statistical
significance. Therefore we choose to analyse the different parameters
indirectly through the evolutionary process described by an N-Tuple Bandit
Evolutionary Algorithm (NTBEA). We ran NTBEA for $1500$ iterations on each of
the $20$ games described in Section II to perform a search through the RHEA
parameter space depicted in Figure 1. Each individual evaluated by NTBEA would
therefore be one parameter combination ($18$ individual length). We seed NTBEA
with the previous state-of-the-art parameter configuration for each game (see
‘SotA’ rows in Table II). To evaluate each individual, we run RHEA with the
specific parameter configuration on the given game, once in each of the $5$
levels of the game and we use the average win rate on the $5$ levels as
individual fitness. To test the final configuration, we run it $100$ times on
the given game ($20$ times per level) and we additionally test the tuned
parameter configuration on the entire set of $20$ games, similarly with $100$
runs per game.

All experiments were run on IBM System X iDataPlex dx360 M3 Server nodes, with
one game per node, having one Intel Xeon E5645 processor core allocated to it
and a maximum of 3GB of RAM of JVM Heap Memory. The runs took between $43$
hours and $6$ days to complete, including NTBEA tuning and final configuration
testing; one run of a game can take up to $2000$ game ticks to complete, with
$1000$ Forward Model calls per tick for AI decision making (plus game engine
computations), the fastest game ending after $50$ game ticks on average. The
budget for all agents was set as $1000$ Forward Model calls instead of time
limits (which averages as the equivalent of $40$ms in our tests), in order for
the experiments to be consistent and replicable across different machines.

In the following sections we aim to analyse not only the performance of the
optimised agents on the different games, but also the parameter space explored
during the evolution and the parameter choices themselves. We hypothesise that
similar games would lead to similar choices in parameters, which would differ
across game types.

The paper presents and discusses the most interesting aspects observed, but
all results, plotting scripts and additional figures are available on
Github111https://github.com/rdgain/ExperimentData/tree/NTBEA-RHEA-2019.

Figure 2: Progression of solution fitness during NTBEA optimisation process in
2 games, Missile Command (left) and Intersection (right). The pink dots
indicate when the solution evaluated becomes the new best (the last pink dot
before or at iteration X is the solution which NTBEA would return if execution
was stopped at iteration X). Trendline in black.

###  IV-A Optimisation Effectiveness

We first discuss the effectiveness of the optimisation. We summarise in Table
II the results obtained on all 20 games used for tuning RHEA parameters with
NTBEA. For each game, we present the parameter configuration of the previous
state of the art (previous highest win rate recorded), its win rate and
standard error; similarly, we present the optimised configuration for each
game.

There are many games in which the win rate remains at or very close to $0\%$.
This set of games (Dig Dug, Lemmings, Roguelike) remains too difficult for
these methods to solve without more game-specific information or better
exploration policies.

There are also several games which see win rates at, or very close to, $100\%$
(Intersection, Aliens, Infection, Chopper and Plaque Attack). We do not see a
decrease in performance in these games after optimisation (but a definite
increase in Plaque Attack to $100\%$ with several modifications in parameter
choices, including using dynamic depth, 1SLA initialisation and random frame
skip).

We do see several games improving performance significantly: the win rate in
Sea Quest increases from $65\%$ to $84\%$ by employing longer individual
lengths, a larger population size, a shift buffer and MC rollouts. Missile
Command sees an increase in win rate from $77.78\%$ to $86\%$ with a shift
buffer, MC rollouts and a discounted fitness assignment. And performance in
Camel Race increases from $11\%$ to $41\%$ by using repetition frame skip, a
shift buffer and MC rollouts, amongst many configuration modifications. These
3 games do not immediately show common features as per Table I, with Sea Quest
standing out due to its stochastic nature and dense environment, while the
other two feature sparser deterministic environments.

We see a decrease in performance in three of the games: Butterflies (from
$96\%$ to $90\%$), Escape (from $46\%$ to $32\%$) and Modality (from $37.5\%$
to $25\%$). As NTBEA was seeded with the previously best solution, we believe
these are cases in which the noisy fitness evaluation was shown to be most
harmful, as the initial solution ended up with a worse fitness than the
solutions returned. However, with more runs of the two configurations on the
game, their rank turns out to be opposite. A similar smaller decrease is also
observed in Lemmings and Bait \- all of these, except for Butterflies, are
games with puzzle elements to them, which appear to be most difficult to
optimize and estimate solution quality for, as they require more precise
action sequences, with one move possibly making the game unsolvable, and
therefore more precise evaluation.

Finally, we highlight NTBEA’s optimisation process progression in two games in
Figure 2, Missile Command and Intersection. Both of these games see an upwards
trend in solution quality, and they represent the games with the slowest and
fastest convergence, respectively. We can observe that the algorithm settles
on the solution for Intersection very quickly, before iteration $100$, whereas
it uses almost all computation budget for Missile Command to find the best
option. This could be an indication of not only game difficulty, but also
strategic depth: most parameter options work well and obtain very good
performance in Intersection, while Missile Command poses a challenge at which
not many options are successful and the finding of those few good
configurations is more difficult.

Overall, the game-specific optimised agents achieve win-rates of below $50\%$
when tested on the entire set of games, which is not surprising in the general
game playing context; the agents do not use any game-specific information. The
best performing tuned agent is that for Sea Quest ($53.4$ average win rate on
all $20$ games), which shares different features with several other games;
this appears to make the specific configuration more generally applicable than
the others.

Figure 3: 1-tuple: rollout length percentage parameter. Color intensity
represents number of occurrences of the data point (the darker the color, the
more occurrences).

###  IV-B 1-tuple Analysis

We further look into the parameter space explored by NTBEA starting with
1-tuples: that is, looking at each parameter in isolation and its preferred
values in the different games tested; we use the term prefer to mean the value
achieves highest win rate. We group together the solutions in which the
parameter had the same value chosen and plot the fitness of these solutions
against parameter values. It is worth noting that it possible the parameter
may have not had a great influence in the fitness obtained. We further exclude
the data points where the parameter had no influence at all, in the case of
dependent parameters (see Figure 1). The resulting heatmaps show the fitness
values observed for each parameter values, as well as how many times each
parameter value was explored by NTBEA. The latter is given by the intensity of
colours in the figures presented; we cap the maximum number of occurrences of
a data point at $100$ and normalize all values in [$0,1$] for visualisation
purposes.

$17$ games prefer the shift buffer turned on and to keep 1 elite between
generations. Additionally, as previously seen in [3], most games prefer long
individual length and large population sizes. $17$ games further prefer the
agent employing Monte Carlo rollouts at the end of its individual evaluation:
Chopper, Sea Quest and Missile Command in particular prefer very long rollouts
($2.0\times L$, see Figure 3); this could be due to these three games
featuring different types of rewards and delays in obtaining rewards. The
other similar game in terms of rewards, Intersection, does not show a
particular preference in this parameter, achieving $1.0$ fitness in all
values. Full plots and results are available on GitHub.

In terms of genetic operators, most games prefer the agent to use both
mutation and crossover in its evolutionary process. However, there are some
exceptions: Chopper and Plaque Attack prefer to use mutation only, whereas
Missile Command prefers options that do include crossover and more disturbance
in its offspring (see Figure 4). Although these games are seen as similar in
[23] and obtain high winning rates, the way the agents achieve their good
performance does differ in these games, suggesting win-rate-based clustering
methods could be improved by taking into account agent-based features.

Figure 4: 1-tuple: genetic operator parameter. 0 - crossover and mutation. 1 -
mutation only. 2 - crossover only.

When looking at the number of offspring (see Figure 5), Survive Zombies,
Missile Command and Chopper prefer more. These games are quite similar in
terms of features (win/lose conditions, level sizes, enemy NPCs) and are
clustered together in [23]. However, in the same cluster, Butterflies and
Plaque Attack don’t show strong preference here - as opposed to the others,
these two games have a smoother reward function and score progression, while
Missile Command and Chopper show more delay in getting rewards, more actions
are required from the player to find particular rewarding scenarios. Sea Quest
is placed in a similar cluster by [21], but it shows opposite preference, for
less offspring instead. In this game we see large discontinuous rewards as
well as many smaller dense rewards - the larger variety in types of rewards
could be what leads to favouring less solutions sampled to increase the number
of generations in the evolutionary process, and to gain better insight into
which reward type is preferable.

Figure 5: 1-tuple: offspring count parameter.

Lastly, we highlight that Intersection and Wait for Breakfast are the only
games that benefit largely from null frame skipping (see Figure 6) - in both
of these games it is essential to wait for specific events to happen (a way in
the road to clear, or the waiter to arrive) and this is highlighted in choice
of method. Plaque Attack prefers sequence frame skipping, as plans evolved are
precise enough in line with the constant stream of rewards. And Camel Race
prefers repeat or sequence frame skipping, with more frames skipped being
better, which are more effective strategies of exploring large sparse
environments. Most other games dislike frame skipping and prefer more fine-
grained search; however, we note that the choice in values for this parameter
is very coarse and it might be that more games could benefit from some or
dynamic frame skipping.

Figure 6: 1-tuple: frame skip type parameter. 0 - repeat. 1 - null. 2 -
random. 3 - sequence. Figure 7: 2-tuple: individual length and population
size. Colors show average fitness for each data point, with blue being highest
($1.0$) and gray being lowest ($0.0$). Each data point is highlighted with a
black circle; the darker the circle, the more number of times that combination
of values was sampled.

###  IV-C 2-tuples Analysis

Similarly as with 1-tuples, we can look at how combinations of parameters
affect overall solution fitness. In this section we group together solutions
which had the same values for each parameter combination, while eliminating
the data points where either one or both of the parameter values did not
impact solution phenotype, in case of dependent parameters (see Figure 1). We
plot each parameter against all others in the different games tested, each
data point representing the average fitness observed in the respective group
of solutions. We further add black circles on each data point to highlight the
number of times each combination was explored by NTBEA during the optimisation
process.

The first thing that stands out in all resulting figures is that NTBEA
explores the best combinations the most, while mostly ignoring less promising
options. This can be seen as a direct confirmation of the effectiveness of the
bandit-based approach, but also as a potential point of improvement: due to
the nature of the very noisy optimisation, it might be beneficial to obtain
more accurate estimates of some data points which do not immediately stand out
as the best: as discussed in a previous section, it was the case in several
games that the optimised solution ended up performing worse than the initial
solution given to the algorithm, which could have been avoided had a more
accurate evaluation of solution quality been done.

In Figure 7 we can observe the combination of individual length $L$ and
population size $P$ parameters. We’ve previously observed that longer
individuals lead to higher fitness values, and similar for larger population
sizes. It is interesting to see that this holds true also for the combination
of $L$ and $P$, although specific combinations achieve better results in some
games (such as $L=20$ and $P=15$ in Chopper).

Another interesting parameter combination to discuss is that of mutation type
and crossover type, shown in Figure 8, which largely decides how offspring are
created at each generation. Although the overall fitness of solutions differs,
games Hungry Birds and Plaque Attack show a similar distribution of good or
bad quality combinations: in particular, 1-point crossover does not agree with
diversity mutation, and 2-point crossover does not agree with bit-mutation.
This could largely be due to the specific modifications n-point crossover
wishes to generate, which are modified unexpectedly by bit-mutation. However,
these two games singled out here do not appear to have much in common
according to our feature descriptions and clustering in Table I; it is thus
interesting to find game similarities beyond those given by traditionally-
employed features.

Figure 8: 2-tuple: mutation type and crossover type.

##  V Conclusion

In this paper we use the N-Tuple Bandit Evolutionary Algorithm (NTBEA) to
optimise the performance of Rolling Horizon Evolutionary Algorithm (RHEA) in
20 GVGAI games, by modifying the configuration of RHEA’s 18 parameters. The
various values possible for all parameters form a large search space of
$4.03\times 10^{8}$, which makes manual optimisation or exhaustive search
difficult with limited compute, thus we choose to use NTBEA to attempt to
improve the win rate of the agent in each of the $20$ games.

As a result of the optimisation, the performance increases in several games.
However, puzzles appeared to be the games where NTBEA struggled to estimate
the quality of different agent configurations and the solution returned was
worse than the state of the art, although NTBEA’s evolutionary process was run
with SotA as the initial solution. The optimisation process differed in the
games tested, NTBEA being able to converge in under $100$ iterations in some
games, while taking most of its $1500$ iteration budget to find good solutions
in others: this strengthens the idea that one specific method is unlikely to
perform well across all games, and that games might require specialised
parameter search spaces to ensure fast optimisation or even the possibility of
a high-performing solution being found.

We further analysed RHEA’s parameters through the evolutionary process, by
looking at some 1-tuples and 2-tuples and the values explored for each.
Several games with similar features in common were found to prefer similar
parameter values, although exceptions do exist of game clusters shown in
parameter values, but not in the traditional game features considered. This
suggests that game clustering methods can be further enhanced by considering
agent-based features.

To further expand on the work carried out in this paper, we propose further
exploring larger and more complex search spaces, with an enhanced NTBEA which
is able to handle tree-structures: we’ve seen several parameters dependent on
others and optimisation would be more sample-efficient if this was taken into
account during the evolutionary process. More enhancements can also be added
into the system, as well as optimising RHEA on a larger set of games
(including multi-player games and games with hidden information), with the
possibility of testing approaches at optimising a generally applicable player.
Lastly, information gathered during optimisation and in-depth analysis can be
used for designing hyper-parameter methods which would be able to identify
game features, relate these to previously seen situations and adapt to new
unknown environments.

## Acknowledgments

This work was funded by the EPSRC CDT in Intelligent Games and Game
Intelligence (IGGI) EP/L015846/1

TABLE II: RHEA best win rate (and standard error) recorded in all games. “opt” rows show NTBEA optimisation results, other rows show previously best recorded (with corresponding citation, highlighted in yellow). Parameters using default values (as per Figure 1) highlighted in green. Enhancements include values for dependants in brackets. Win-rates in bold are the higher values observed, if different. |  | Parameters |
---|---|---|---
Numerical | Nominal |  |
Game | Win Rate | P.Size | I.Len | Offspring | Elite | Init. | Selection | Crossover | Mutation | Fit. | Enhancements |
| 0% $(0.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
0 | 0% $(0.00)$ | 1 | 20 | 15 | 1 | MCTS | Rank | Uniform | 2-bit | Last | S.Buff(0.9); MC(0.5,1); F.Skip(Rep) | opt
| 4% $(1.98)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | DD | [4]
1 | 0% $(0.00)$ | 10 | 10 | 1 | 0 | RND | Tourn. | 1-point | 2-bit | Last |  | S.Buff(0.9); MC(0.5,5); F.Skip(Rep); DD
---
opt
| 0% $(0.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
2 | 0% $(0.00)$ | 1 | 20 | 15 | 1 | MCTS | Rank | Uniform | 2-bit | Last |  | S.Buff(0.9); MC(0.5,1); F.Skip(RND)
---
opt
| 100% $(0.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
3 | 99% $(0.99)$ | 10 | 15 | 20 | 1 | 1SLA | - | - | Uniform | Disc. | S.Buff(0.9); MC(1.0,5); DD | opt
| 10% $(3.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
4 | 10% $(3.00)$ | 20 | 10 | 15 | 0 | 1SLA | - | - | 2-bit | Disc. | S.Buff(0.9); DD | opt
| 13.13% $(3.39)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
5 | 3% $(1.70)$ | 10 | 20 | 20 | 1 | RND | Tourn. | 2-point | - | Average | MC(0.5,1) | opt
| 11.00% $(3.129)$ | 1 | 10 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | MC(0.5,10) | [7]
6 | 41% $(4.918)$ | 15 | 15 | 1 | 1 | MCTS | Tourn. | Uniform | Diversity | Disc. |  | S.Buff(0.99); MC(1.0,5);
---
F.Skip(Rep); Fit.Div(0.5)
opt
| 46% $(4.984)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | MC(0.5,1) | [7]
7 | 32% $(4.665)$ | 20 | 10 | 10 | 0 | RND | - | - | Diversity | Disc. | S.Buff(0.9); Fit.Div(0.5) | opt
| 12% $(3.25)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | S.Buff(0.9); MC(0.5,10) | [7]
8 | 11% $(3.129)$ | 10 | 20 | 15 | 0 | 1SLA | Rank | 2-point | 2-bit | Max | S.Buff(0.99); MC(2.0,5) | opt
| 20% $(4.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | S.Buff(0.9); MC(0.5,10) | [7]
9 | 19% $(3.923)$ | 10 | 20 | 10 | 1 | RND | Tourn. | 1-point | Uniform | Max | S.Buff(0.99); MC(1.0,5) | opt
| 78.33% $(3.76)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
10 | 83% $(3.756)$ | 10 | 20 | 10 | 1 | 1SLA | Tourn. | 1-point | - | Disc. |  | S.Buff(0.99); MC(2.0,1);
---
F.Skip(Null); DD
opt
| 54.55% $(5.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
11 | 56% $(4.968)$ | 20 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Disc. |  | S.Buff(0.99); MC(2.0,5);
---
F.Skip(RND); DD
opt
| 37.5% $(4.42)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
12 | 25% $(4.33)$ | 10 | 20 | 15 | 0 | RND | Tourn. | 1-point | Diversity | Max |  | MC(0.5,10);
---
F.Skip(Seq); DD
opt
| 77.78% $(4.18)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
13 | 86% $(3.47)$ | 15 | 20 | 15 | 1 | RND | Tourn. | 1-point | Softmax | Max | S.Buff(0.9); MC(2.0,1) | opt
| 98.99% $(1.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
14 | 100% $(0.00)$ | 15 | 20 | 1 | 1 | 1SLA | Rank | 1-point | Diversity | Max |  | S.Buff(1.0); MC(2.0,1); F.Skip(RND); DD
---
opt
| 65% $(4.77)$ | 1 | 5 | 1 | 1 | RND | Tourn. | Uniform | Uniform | Last | S.Buffer(0.9) MC(0.5,10) | [7]
15 | 84% $(3.66)$ | 20 | 20 | 1 | 1 | RND | Rank | Uniform | - | Average | S.Buff(0.9); MC(2.0,1) | opt
| 100% $(0.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
16 | 99% $(0.99)$ | 15 | 20 | 1 | 0 | RND | - | - | 2-bit | Last |  | S.Buff(0.99); MC(0.5,10); F.Skip(RND); DD
---
opt
| 100% $(0.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
17 | 100% $(0.00)$ | 15 | 20 | 20 | 0 | RND | - | - | 2-bit | Disc. | S.Buff(0.9); DD | opt
| 96% $(1.92)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
18 | 90% $(3.0)$ | 15 | 5 | 20 | 0 | RND | Roulette | 2-point | - | Disc. | S.Buff(0.99); MC(2.0,5) | opt
| 100% $(0.00)$ | 10 | 15 | 10 | 1 | RND | Tourn. | Uniform | Uniform | Last | - | [3]
19 | 100% $(0.00)$ | 10 | 5 | 1 | 1 | 1SLA | Roulette | 1-point | 2-bit | Disc. | MC(2.0,5); DD | opt

## References

  * [1] H. Baier and P. I. Cowling, “Evolutionary MCTS with Flexible Search Horizon,” in _Fourteenth Artificial Intelligence and Interactive Digital Entertainment Conference_ , 2018.
  * [2] N. Justesen, T. Mahlmann, S. Risi, and J. Togelius, “Playing Multiaction Adversarial Games: Online Evolutionary Planning Versus Tree Search,” _IEEE Transactions on Games_ , vol. 10, no. 3, pp. 281–291, 2017.
  * [3] R. D. Gaina, J. Liu, S. M. Lucas, and D. P. Liébana, “Analysis of Vanilla Rolling Horizon Evolution Parameters in General Video Game Playing,” in _Springer Lecture Notes in Computer Science, Applications of Evolutionary Computation, EvoApplications_ , no. 10199, 2017, pp. 418–434.
  * [4] R. D. Gaina, S. M. Lucas, and D. Perez-Liebana, “Tackling Sparse Rewards in Real-Time Games with Statistical Forward Planning Methods,” in _AAAI Conference on Artificial Intelligence (AAAI-19)_ , vol. 33, 2019, pp. 1691–1698.
  * [5] D. Perez-Liebana, S. Samothrakis, S. M. Lucas, and P. Rolfshagen, “Rolling Horizon Evolution versus Tree Search for Navigation in Single-Player Real-Time Games,” in _Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)_ , 2013, pp. 351–358.
  * [6] R. D. Gaina, S. M. Lucas, and D. P. Liébana, “Population Seeding Techniques for Rolling Horizon Evolution in General Video Game Playing,” in _Proceedings of the Congress on Evolutionary Computation_ , June 2017, pp. 1956–1963.
  * [7] ——, “Rolling Horizon Evolution Enhancements in General Video Game Playing,” in _Proceedings of IEEE Conference on Computational Intelligence and Games_ , Aug 2017, pp. 88–95.
  * [8] B. Santos, H. Bernardino, and E. Hauck, “An Improved Rolling Horizon Evolution Algorithm with Shift Buffer for General Game Playing,” in _2018 17th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames)_. IEEE, 2018, pp. 31–316.
  * [9] X. Tong, W. Liu, and B. Li, “Enhancing Rolling Horizon Evolution with Policy and Value Networks,” in _2019 IEEE Conference on Games (CoG)_. IEEE, 2019, pp. 1–8.
  * [10] M. H. Segler, M. Preuss, and M. P. Waller, “Planning Chemical Syntheses with Deep Neural Networks and Symbolic AI,” _Nature_ , vol. 555, no. 7698, p. 604, 2018.
  * [11] J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel _et al._ , “Mastering atari, go, chess and shogi by planning with a learned model,” _arXiv preprint arXiv:1911.08265_ , 2019.
  * [12] S. M. Lucas, J. Liu, I. Bravi, R. D. Gaina, J. Woodward, V. Volz, and D. Perez-Liebana, “Efficient Evolutionary Methods for Game Agent Optimisation: Model-Based is Best,” _arXiv preprint arXiv:1901.00723_ , 2019\.
  * [13] D. Ashlock, D. Perez-Liebana, and A. Saunders, “General Video Game Playing Escapes the No Free Lunch Theorem,” in _2017 IEEE Conference on Computational Intelligence and Games (CIG)_. IEEE, 2017, pp. 17–24.
  * [14] K. Kunanusont, R. D. Gaina, J. Liu, D. Perez-Liebana, and S. M. Lucas, “The N-Tuple Bandit Evolutionary Algorithm for Automatic Game Improvement,” in _2017 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, 2017, pp. 2201–2208.
  * [15] K. Kunanusont, S. M. Lucas, and D. Perez-Liebana, “Modelling Player Experience with the N-Tuple Bandit Evolutionary Algorithm,” in _Artificial intelligence and Interactive Digital Entertainment (AIIDE)_ , 2018\.
  * [16] S. M. Lucas, J. Liu, and D. Perez-Liebana, “The N-Tuple Bandit Evolutionary Algorithm for Game Agent Optimisation,” in _2018 IEEE Congress on Evolutionary Computation (CEC)_. IEEE, 2018, pp. 1–9.
  * [17] I. Bravi, S. Lucas, D. Perez-Liebana, and J. Liu, “Rinascimento: Optimising Statistical Forward Planning Agents for Playing Splendor,” _arXiv preprint arXiv:1904.01883_ , 2019.
  * [18] R. D. Gaina, S. M. Lucas, and D. Perez-Liebana, “Project Thyia: A Forever Gameplayer,” in _IEEE Conference on Games (COG)_ , 2019, pp. 1–8. [Online]. Available: https://ieeexplore.ieee.org/document/8848047
  * [19] S. Samothrakis, S. A. Roberts, D. Perez, and S. M. Lucas, “Rolling Horizon Methods for Games with Continuous States and Actions,” in _2014 IEEE Conference on Computational Intelligence and Games_. IEEE, 2014, pp. 1–8.
  * [20] J. Liu, D. Perez-Liebana, and S. M. Lucas, “Rolling Horizon Coevolutionary Planning for Two-Player Video Games,” in _Proceedings of the IEEE Conference on Computational intelligence and Games (CIG)_ , 2016.
  * [21] P. Bontrager, A. Khalifa, A. Mendes, and J. Togelius, “Matching Games and Algorithms for General Video Game Playing,” in _Twelfth Artificial Intelligence and Interactive Digital Entertainment Conference_ , 2016, pp. 122–128.
  * [22] M. J. Nelson, “Investigating Vanilla MCTS Scaling on the GVG-AI Game Corpus,” in _2016 IEEE Conference on Computational Intelligence and Games (CIG)_. IEEE, 2016, pp. 1–7.
  * [23] M. Stephenson, D. Anderson, A. Khalifa, J. Levine, J. Renz, J. Togelius, and C. Salge, “A Continuous Information Gain Measure to Find the Most Discriminatory Problems for AI Benchmarking,” _arXiv preprint arXiv:1809.02904_ , 2018.
  * [24] D. Perez-Liebana, S. M. Lucas, R. D. Gaina, J. Togelius, A. Khalifa, and J. Liu, _General Video Game Artificial Intelligence_. Morgan and Claypool Publishers, 2019. [Online]. Available: https://gaigresearch.github.io/gvgaibook/
  * [25] D. Perez-Liebana, J. Liu, A. Khalifa, R. D. Gaina, J. Togelius, and S. M. Lucas, “General Video Game AI: a Multi-Track Framework for Evaluating Agents Games and Content Generation Algorithms,” _IEEE Transactions on Games_ , vol. 11, no. 3, pp. 195–214, Sep 2019. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/8664126
  * [26] D. Perez-Liebana, S. Samothrakis, J. Togelius, S. M. Lucas, and T. Schaul, “General Video Game AI: Competition, Challenges and Opportunities,” in _Thirtieth AAAI Conference on Artificial Intelligence_ , 2016.
  * [27] R. D. Gaina, A. Couëtoux, D. J. Soemers, M. H. Winands, T. Vodopivec, F. Kirchgessner, J. Liu, S. M. Lucas, and D. Perez-Liebana, “The 2016 Two-Player GVGAI Competition,” _IEEE Transactions on Games_ , vol. 10, no. 2, pp. 209–220, June 2018.
  * [28] A. Khalifa, D. Perez-Liebana, S. M. Lucas, and J. Togelius, “General Video Game Level Generation,” in _Proc. of the Genetic and Evolutionary Computation Conference 2016_. ACM, 2016, pp. 253–259.
  * [29] A. Khalifa, M. C. Green, D. Perez-Liebana, and J. Togelius, “General Video Game Rule Generation,” in _2017 IEEE Conference on Computational Intelligence and Games (CIG)_. IEEE, 2017, pp. 170–177.
  * [30] A. Braylan, M. Hollenbeck, E. Meyerson, and R. Miikkulainen, “Frame Skip is a Powerful Parameter for Learning to Play Atari,” in _Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence_ , 2015.
  * [31] M. C. Machado, M. G. Bellemare, E. Talvitie, J. Veness, M. Hausknecht, and M. Bowling, “Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents,” _Journal of Artificial Intelligence Research_ , vol. 61, pp. 523–562, 2018.
  * [32] D. P. Liébana, M. Stephenson, R. D. Gaina, J. Renz, and S. M. Lucas, “Introducing Real World Physics and Macro-Actions to General Video Game AI,” in _Proceedings of IEEE Conference on Computational Intelligence and Games_ , Aug 2017, pp. 248–255.