#  AlphaZero-Inspired Game Learning: Faster Training by Using MCTS Only at
Test Time

Johannes Scheiermann  RWTH Aachen University
Germany
Email<EMAIL_ADDRESS>Wolfgang Konen  TH Köln –
University of Applied Sciences
Germany
Email<EMAIL_ADDRESS>
###### Abstract

Recently, the seminal algorithms AlphaGo and AlphaZero have started a new era
in game learning and deep reinforcement learning. While the achievements of
AlphaGo and AlphaZero – playing Go and other complex games at super human
level – are truly impressive, these architectures have the drawback that they
require high computational resources. Many researchers are looking for methods
that are similar to AlphaZero, but have lower computational demands and are
thus more easily reproducible.
In this paper, we pick an important element of AlphaZero – the Monte Carlo
Tree Search (MCTS) planning stage – and combine it with temporal difference
(TD) learning agents. We wrap MCTS for the first time around TD n-tuple
networks and we use this wrapping only at test time to create versatile agents
that keep at the same time the computational demands low. We apply this new
architecture to several complex games (Othello, ConnectFour, Rubik’s Cube) and
show the advantages achieved with this AlphaZero-inspired MCTS wrapper. In
particular, we present results that this agent is the first one trained on
standard hardware (no GPU or TPU) to beat the very strong Othello program Edax
up to and including level 7 (where most other learning-from-scratch algorithms
could only defeat Edax up to level 2).

##  I Introduction

###  I-A Motivation

In computer science, game learning and game playing are interesting test beds
for strategic decision making done by computers. Games usually have large
state spaces, and they often require complex pattern recognition and strategic
planning capabilities to decide which move is the best in a certain situation.
If an algorithm is able to learn a game (or, even better, a variety of
different games) just by self-play, given no other knowledge than the game
rules, it is likely to perform also well on other problems of strategic
decision making.

With their seminal papers on AlphaGo [1], AlphaGo Zero [2] and AlphaZero [3],
Silver et al. opened a new door in game learning by presenting self-learning
algorithms for the game of Go (which was considered to be unattainable for
computers prior to theses publications). All these algorithms were able to
beat the human Go world champion Lee Sedol.

However, the full algorithms in [1]–[3] require huge computational resources
in order to learn how to play the game of Go at world-master level. It is the
purpose of this work to investigate whether some of the important elements of
AlphaZero can already reach decent advances in game learning with much smaller
computational efforts. For this purpose, we study several games – namely
Othello, ConnectFour and Rubik’s Cube – that have a lower complexity than Go
yet are not easy to master for both humans and game learning algorithms. The
goal is to deliver not only agents with average game playing strength but
agents that learn from scratch and play almost as well as the strongest known
algorithms111e. g. Edax for Othello or AB-DL for ConnectFour as will be
further explained in Sec. IV for these games. We will show that this can be
achieved for Othello and ConnectFour and, to some extent, also for Rubik’s
Cube.

In this work, we pick an element of AlphaZero (here: the MCTS planning stage)
and combine it with reinforcement learning (RL) agents. We wrap MCTS around
TD($\lambda$) n-tuple networks [4, 5, 6], but the same technique could be
applied to all types of RL agents.

The main contributions of this paper are as follows: (i) it shows for the
first time – to the best of our knowledge – a coupling between trainable
TD($\lambda$) n-tuple networks and MCTS planning; (ii) an AlphaZero-inspired
solution, but with largely reduced computational requirements; (iii) a
comparison between MCTS inside and outside of self-play training; (iv) very
good results on Othello, ConnectFour and 2x2x2 Rubik’s Cube. Specifically, we
are able to defeat the strong Othello program Edax at level 7 with an agent
trained from scratch in less than 2 hours on a standard CPU.

The rest of this paper is organized as follows: Sec. II details the
algorithmic building blocks and methods of our approach. Sec. III describes
the experimental setup, the games and the evaluation methods. Sec. IV presents
the results on the three games: quality achieved, interpretation, computation
times. Sec. V shows related work and discusses our results in comparison with
other research. Sec. VI concludes.

##  II Algorithms and Methods

The algorithm presented in this paper is implemented in the General Board Game
(GBG) learning and playing framework [7, 8], which was developed for education
and research in AI. GBG allows applying the new algorithm easily to a variety
of games. GBG is open source and available on
GitHub222https://github.com/WolfgangKonen/GBG.

###  II-A Algorithm Overview

The most important task of a game-playing agent is, given an observation or
game state $s_{t}$ at time $t$, to propose a good next action $a_{t}$ from the
set of actions available in $s_{t}$ (Fig. 1). TD-learning uses the value
function $V(s_{t})$, which is the expected sum of future rewards when being in
state $s_{t}$.

It is the task of the agent to learn the value function $V$ from experience
(by interacting with the environment). In order to do so, it usually performs
multiple self-play training episodes until a certain training budget is
exhausted or a certain game-playing strength is reached.

Our base RL algorithm TD-FARL is described in detail in [9, 10] and is partly
inspired by Jaskowski et al. [11], van der Ree et al. [12] and partly by our
own experience with RL-n-tuple training. The key elements of the new RL-logic
– as opposed to our previous RL algorithms [4, 13] – are n-tuple systems,
temporal coherence learning (TCL) [14] and final adaptation RL (FARL) [9, 10].
All these key elements will be briefly described in Sec. II-C, II-D and II-E.

Despite being successful on a variety of games [9, 10], this base algorithm
shares one disadvantage with other deep learning algorithms that are only
value-based: they base their decision on the value of the current state-action
pairs. They have no planning component, no what-if scenarios to think about
further consequences, like possible counter-actions of the other player(s),
further own actions and so on.

action $a_{t}$environmentobservation $s_{t}$reward $r_{t}$ MCTS wrapper
---
RL agent
Figure 1:  Reinforcement learning with MCTS wrapper: The RL agent with MCTS
wrapper observes a certain state $s_{t}$ and reward $r_{t}$ from the game
environment and predicts the next action $a_{t}$.

This is where AlphaZero’s MCTS-trick comes into play: Silver et al. [1, 2]
combine a deep learning RL agent with an MCTS wrapper (Fig. 1) to introduce
such a planning component. They do this throughout the whole training
procedure, which is better for the overall performance but also very
computationally demanding. In this work, we take a simpler approach: we first
train our RL agent, a TD n-tuple network, and then use the MCTS wrapping only
at test time (i. e. during game play). This usage of MCTS adds a form of
planning at test time.

###  II-B MCTS Wrapper

Our MCTS wrapper is based on the UCT variant of MCTS, where the probability of
predicting an optimal move converges to 100% in the limit of an infinite
number of iterations [15]. If we limit the iterations to a fixed number, we
only approach optimality but have a fixed runtime.

Therefore, with an MCTS, promising results can be expected under reasonable
computational requirements, given the number of MCTS iterations is correctly
balanced.

The iterations of MCTS usually consist of four consecutive steps: selection,
expansion, simulation, and backpropagation [16]. The following child selection
policy, which is the one used by Silver et al. [2] in AlphaGo Zero, is also
the one we implemented in our MCTS wrapper for the same purpose:

$\displaystyle a_{t}$ $\displaystyle=$ $\displaystyle\arg\max_{a\in
A(s_{t})}\left(\frac{W(s_{t},a)}{N(s_{t},a)}+U(s_{t},a)\right)$ (1)
$\displaystyle U(s,a)$ $\displaystyle=$ $\displaystyle
c_{puct}P(s,a)\frac{\sqrt{\varepsilon+\sum_{b\in A(s)}{N(s,b)}}}{1+N(s,a)}$
(2)

Here, $W(s,a)$ is the accumulator for all backpropagated values (as detailed
in Algorithm 1 below) that arrive along with branch $a$ of node r that carries
state $s$. Likewise, $N(s,a)$ is the visit counter and $P(s,a)$ the prior
probability. $A(s)$ is the set of actions available in state $s$.
$\varepsilon$ is a small positive constant for the special case
$\sum_{b}{N(s,b)}=0$: It guarantees that in this special case the maximum of
$U(s,a)$ is given by the maximum of $P(s,a)$. The prior probabilities $P(s,a)$
are obtained by sending the RL agent’s values of all available state-action
pairs $(s,a)$ with $a\in A(s)$ through a softmax function (see Sec.
II-C).333Note that the prior probabilities and the MCTS iteration are only
needed at test time, so that we – different to AlphaZero – do not need MCTS
during self-play training.

According to Silver et al. [2], the above child selection policy is a variant
of the PUCB (”Predictor + UCB”) algorithm presented by Rosin [17].
Furthermore, the latter is a modification of the bandit algorithm UCB1,
extending it with the behavior to also consider the recommendations of a
predictor. UCB1 is also the basis of the previously mentioned algorithm UCT
(UCB applied to trees) by Kocsis and Szepesvári [15].

Algorithm 1 MctsIteration: This recursive algorithm is applicable to 1- or
2-player games. It performs a single iteration of a Monte Carlo tree search,
starting from root node r carrying state $s$.

1:function MctsIteration(Node r)

2: $\kappa=(-1)^{N-1}$ $\triangleright$ $N$: number of players

3: if IsGameOver$(s)$ then

4: return $\kappa*\textsc{FinalGameScore}(s)$

5: if $\textsc{r}.\textsc{expanded}=\textsc{false}$ then

6: $(V,\mathbf{p})\leftarrow f(s)$ $\triangleright$ $f$: approximator network

7: $P(s,\cdot)\leftarrow\mathbf{p}$ $\triangleright$ prior probabilities given
by $f$

8: $\textsc{r}.\textsc{expanded}\leftarrow\textsc{true}$

9: return $\kappa*V$

10:

11: $(a,\textsc{c})\leftarrow\textsc{SelectChild}(\textsc{r})$
$\triangleright$ use Eq. (1) to select

12: $\triangleright$ action $a$ and child  c

13: $V_{child}\leftarrow\textsc{MctsIteration}(\textsc{c})$

14: $W(s,a)\leftarrow W(s,a)+V_{child}$

15: $N(s,a)\leftarrow N(s,a)+1$

16:

17: return $\kappa*V_{child}$

Our implementation of an MCTS iteration is illustrated in Algorithm 1. It
performs a single MCTS iteration for a given node. The numerical return value
approximates how valuable it is to choose an action that leads to this node.
Since this assessment corresponds to the view of the previous player, the
algorithm negates the returned values ($\kappa=-1$) in the case of 2-player
games.

If the node represents a game-over state, then the consequence of choosing
this node is known and does not need to be approximated. In this case, the
final game score is the value to propagate back.

Reaching a non-expanded node is also a termination condition. In this case,
the approximator function $f$ (usually the wrapped RL agent of Fig. 1)
approximates the value $V$ of the corresponding node together with its action
probabilities $\mathbf{p}$ (line 6). Afterward, the node is marked as
expanded, and its approximated value is propagated back.

SelectChild is used to select a child node based on the PUCB variant of Eq.
(1) if no previous termination condition occurred. To determine the selected
child node’s value, it serves as input to another recursive call of the
MctsIteration algorithm. On return from the recursive call, the returned value
$V_{child}$ is added to $W(s,a)$ (line 14), and the visit count $N(s,a)$ is
incremented.

Our MCTS implementation first performs a certain number of iterations starting
from the node corresponding to the current game state in a concrete match.
Then it decides on the action that leads to the most frequently visited child
node.

Furthermore, our tree search adopts another element from AlphaGo which reuses
the previously built search tree whenever possible, i. e., when a node
corresponding to the current game state is already present in the search tree
of the previous move. This optimization avoids performing superfluous MCTS
iterations, which only recalculate already known facts again.

Table I:  N-tuple systems used in this work. Parameters $n$, $m$ and $k$ are explained in the main text. The number of weights is $4^{7}\cdot 200$ (Othello) and $4^{8}\cdot 140$ (ConnectFour). For 2x2x2 Rubik’s Cube, each 7-tuple has either 3 or 7 positional values, depending on the cell location. Thus, the number of weights depends on the cell location. Since not every weight represents a reachable position, the number of active weights is smaller, as given by the percentage in the last column.  game | length $n$ | position $m$ | $k$ | weights | percent active
---|---|---|---|---|---
Othello | 7 | 4 | $2\cdot 100$ | 3,276,800 | 51%
ConnectFour | 8 | 4 | $2\cdot 70$ | 9,175,040 | 8%
2x2x2 Rubik’s | 7 | {3, 7} | 60 | 3,720,780 | 31%
3x3x3 Rubik’s | 7 | {2, 3, 8, 12} | 120 | 46,563,392 | 22%
Figure 2: Example n-tuples: We show 4 random-walk 8-tuples on a 6x7
ConnectFour board. The tuples are selected manually to show that not only
snake-like shapes are possible, but also bifurcations or cross shapes. Tuples
may or may not be symmetric.

###  II-C N-Tuple Systems

N-tuple systems coupled with TD were first applied to game learning by Lucas
in 2008 [5], although n-tuples were already introduced in 1959 for character
recognition purposes [18]. The remarkable success of n-tuples in learning to
play Othello [5] motivated other authors to benefit from this approach for a
number of other games. The main goal of n-tuple systems is to map a highly
non-linear function in a low dimensional space to a high dimensional space
where it is easier to separate ‘good’ and ‘bad’ regions. This can be compared
to the kernel trick of support-vector machines. An n-tuple is defined as a
sequence of $n$ cells of the board. Each cell can have $m$ positional values
representing the possible states of that cell. Therefore, every n-tuple will
have a (possibly large) look-up table indexed in form of an $n$-digit number
in base $m$. Each entry corresponds to a feature and carries a trainable
weight. An n-tuple system is a system consisting of $k$ n-tuples. Tab. I shows
the n-tuple systems that we use in this work. Each time a new agent is
constructed, all n-tuples are formed by random walk. That is, all cells are
placed randomly with the constraint that each cell must be adjacent444The form
of adjacency (e. g. 4- or 8-point neighborhood) is user-defined. to at least
one other cell in the n-tuple. An example n-tuple system is shown in Fig. 2.

Let $\mathbf{\Theta}$ be the vector of all weights $\theta_{i}$ of the n-tuple
system. The length of this vector may be large, as the fifth column in Tab. I
shows. If all n-tuples have the same $n$ and $m$, $\mathbf{\Theta}$ has length
$m^{n}k$. Let $\mathbf{\Phi}(s)$ be a binary vector of the same length
representing the feature occurences in state $s$. The value function of the
n-tuple network given state $s$ is

$V(s)=\sigma\left(\mathbf{\Phi}(s)\cdot\mathbf{\Theta}\right)$ (3)

with transfer function $\sigma$ which may be a sigmoidal function or simply
the identity function.

An agent using this n-tuple system derives a policy from the value function in
Eq. (3) as follows: Given state $s$ and the set $A(s)$ of available actions in
state $s$, it applies with a forward model $f$ every action $a\in A(s)$ to
state $s$, yielding the next state $s^{\prime}=f(s,a)$. Then it selects the
action that maximizes $V(s^{\prime})$.

The prior probabilities $P(s,a)$ in Eq. (2) are calculated similarly: Given
state $s$ and actions $a\in A(s)$, we compute with Eq. (3) all values
$V(s^{\prime})$ of reachable states $s^{\prime}=f(s,a)$ and send them through
a softmax function to yield $P(s,a)$.

###  II-D TD Learning and FARL

The goal of n-tuple agent training is to learn a value function $V$ that
generates a good policy, i. e. a policy that selects in almost all cases the
best action. In our work, we use the TD learning algorithm TD-FARL [9, 10] for
training, which is briefly described in the following.

Let $s^{\prime}[p]$ be the actual state generated by acting player $p$ and let
$s[p]$ be the previous state that was generated by this acting player. TD(0)
learning [12, 19] adapts the value function with model parameters
$\mathbf{\Theta}$ through

$\mathbf{\Theta}_{t+1}=\mathbf{\Theta}_{t}+\alpha\delta\mathbf{\nabla_{\mathbf{\Theta}}}V(s[p])$
(4)

Here, $\alpha$ is the learning rate and $V$ is in our case the n-tuple value
function of Eq. (3). $\delta$ is the usual TD error [19] after player $p$ has
acted and generated $s^{\prime}[p]$:

$\delta=r[p]+\gamma V(s^{\prime}[p])-V(s[p])$ (5)

where the sum of the first two terms (reward $r[p]$ for player $p$ and the
discounted value $\gamma V(s^{\prime}[p])$) is the desirable target for
$V(s[p])$.

The extra element of FARL is to add a final adaptation step at the end of each
episode: All players $p^{\prime}$ different from the last player take their
reward $r[p^{\prime}]$ and adapt the value function for state $s[p^{\prime}]$
according to Eq. (4), but with error signal

$\delta=r[p^{\prime}]-V(s[p^{\prime}])\quad\forall p^{\prime}\neq p$ (6)

This FARL step was found to be crucial for reaching training success in
$N$-player games with arbitrary $N$ [9].

TD-FARL performs its training purely by $\epsilon$-greedy self-play: The agent
plays against itself and makes random moves with probability $\epsilon$ in
order to explore. No external knowledge or databases are used. More details on
TD-FARL for $N$-player games, including the extension to TD($\lambda$) with
arbitrary $\lambda\in[0,1]$, based on the eligibility mechanism for n-tuple
systems [11], are described in our previous work [10].

###  II-E Temporal Coherence Learning (TCL)

The TCL algorithm developed by Beal and Smith [14] is an extension of TD
learning. It replaces the global learning rate $\alpha$ with the weight-
individual product $\alpha\alpha_{i}$ for every weight $\theta_{i}$. Here, the
adjustable learning rate $\alpha_{i}$ is a free parameter set by a pretty
simple procedure: For each weight $\theta_{i}$, two counters $N_{i}$ and
$A_{i}$ accumulate the sum of weight changes and the sum of absolute weight
changes. If all weight changes have the same sign, then
$\alpha_{i}=|N_{i}|/A_{i}=1$, and the learning rate stays at its upper bound.
If weight changes have alternating signs, then the global learning rate is
probably too large. In this case, $\alpha_{i}=|N_{i}|/A_{i}\rightarrow 0$ for
$t\rightarrow\infty$, and the effective learning rate will be largely reduced
for this weight.

In our previous work [4] we extended TCL to $\alpha_{i}=g(|N_{i}|/A_{i})$
where $g$ is a transfer function being either the identity function (standard
TCL) or an exponential function $g(x)=e^{\beta(x-1)}$. It was shown in [4]
that TCL leads to faster learning and higher win rates for the game
ConnectFour.

##  III Experimental Setup

###  III-A The Games

(a) (b)

Figure 3: (a) Othello game state. The black cell with a red outline marks the
last move of Black. It is White’s turn to choose one of the available actions
marked by cells with a green border. These actions capture one or more black
pieces, which are then flipped to white. (b) ConnectFour game state. It is
Red’s turn, and they have to place their piece in the only free column.
Subsequently, Yellow wins by reaching Four in a Row. Numbers show cell coding:
1 and 2 for players’ pieces, 3: empty and reachable, 0: empty, but not
reachable (in next move).

####  III-A1 Othello

(Reversi) is a well-known board game with quite simple rules yet requiring
complex strategies to play strongly. Fig. 3(a) shows a typical game position.
The regular 8x8 Othello has $10^{28}$ states and an average branching factor
of 10. It is an unsolved game (no perfect winning strategy is known).

In our Othello experiments, we compete against Edax [20], a strong Othello
playing program. We use Edax in the same way as Norelli et al. [21] with
standard settings (alpha-beta search, tabular value functions, no opening
books) and vary only the Edax level (search depth).

####  III-A2 ConnectFour

(Four in a Row) is another board game with quite simple rules. Fig. 3(b) shows
a typical end game position. The regular 6x7 ConnectFour has $10^{12}$ states
and a branching factor $\leq 7$. It is a solved game: The $1^{st}$ player wins
if playing perfectly.

In our ConnectFour experiments, we compete against the strong alpha-beta
search agents AB and AB-DL [22], further described in Sec. IV-B. AB and AB-DL
work with a pre-computed opening book and do not need any evaluation
functions, search depth or time budget parameters.

####  III-A3 Rubik’s Cube

is a famous puzzle of a cube consisting of smaller ’cubies’ where the goal is
to move an arbitrary scrambled cube into the solved position through a
sequence of twists. In the solved position, each cube face consists of 9
(3x3x3 cube) or 4 (2x2x2 cube) cubie faces with the same color. The regular
3x3x3 cube has $4.3\cdot 10^{19}$ states and a branching factor of $18$. The
2x2x2 cube has $3.6\cdot 10^{6}$ states and a branching factor of 9.

###  III-B Common Settings

We use for all our experiments the same RL agent based on n-tuple systems and
TCL. Only its hyperparameters are tuned to the specific game, as shown below.
We refer to this agent as TCL-base whenever it alone is used for game playing.
If we wrap this agent by an MCTS wrapper with a given number of iterations,
then we refer to this as TCL-wrap.

The hyperparameters for each game were found by manual fine-tuning. For
reasons of space we give the exact explanation and the setting of all
parameters as supplementary material in Appendix G of [8]. A short version of
these settings is: The chosen n-tuple configurations are given in Tab. I, and
the main parameters are:

  * •

Othello: learning rate $\alpha=0.2$, TCL activated, eligibility trace factor
$\lambda=0.5$, exploration rate $\epsilon=0.2\rightarrow 0.1$, 250,000
training episodes.

  * •

ConnectFour: learning rate $\alpha=3.7$, TCL activated, eligibility trace
factor $\lambda=0.0$, exploration rate $\epsilon=0.1\rightarrow 0.0$,
6,000,000 training episodes.

  * •

Rubik’s Cube: learning rate $\alpha=0.25$, TCL activated, eligibility trace
factor $\lambda=0.0$, exploration rate $\epsilon=0.0$, 3,000,000 training
episodes.

Figure 4:  Different Othello agents playing against Edax. TCL-wrap: TCL
coupled with MCTS wrapper (10,000 iterations); TCL-base: TCL alone; MCTS-10k:
MCTS alone with 10,000 iterations. Shown are the percentages of won runs from
(a) 20 TCL agents trained with different random n-tuples in the TCL cases and
(b) 20 MCTS agents with different seeds in the MCTS case. Each agent plays in
both roles (1st and 2nd player), yielding 40 competition runs in total.

##  IV Results

###  IV-A Othello

It is not too difficult for game learning algorithms to reach a medium playing
strength in Othello, i. e. a strength where simple heuristic players are
beaten [5, 23]. But it is very difficult to beat the very strong Othello
playing program Edax [20]. Edax has a configurable playing strength (level,
depth) between 0 and 60.

We compare our agents with Edax at different levels. Since all agents (Edax,
TCL-base and TCL-wrap) are deterministic move predictors, repeated evaluation
runs with the same pair of agents always yield the same results and cannot be
used to collect statistics. We use the following procedure to get
statistically sound results: We draw 20 different random n-tuple
configurations (random walk, see Sec. II-C) and train for each configuration a
separate TCL-base agent. All TCL agents compete in both roles against Edax,
yielding 40 competition runs.

Fig. 4 shows the resulting win rates (win count divided by 40 runs): Both MCTS
and TCL-base cannot defeat Edax at level 2 and above (their win rates are
lower than 50% from level 2 on). The situation changes dramatically as soon as
we wrap TCL-base by MCTS: TCL-wrap defeats Edax up to level 7 and has win
rates above 25% for levels 8 and 9. The non-monotonuous trend of TCL-wrap at
Edax level 5 and 6 is surprising and not fully understood: It could be
statistical fluctuations or it could be that Edax plays a little weaker at
level 7 than at level 5 or 6.

(a) (b)

Figure 5: Tactics of Edax in Othello: (a) Move 48 in a game TCL-base (Black)
vs. Edax level 7 (White): It is Black’s turn, and Edax forces Black into
disadvantageous moves that allow White to capture the corners. TCL-wrap will
avoid such disadvantageous positions. (b) Move 57 in a game TCL-wrap (Black)
vs. Edax level 8 (White): Now it is White’s turn, and although Black has the
current majority of pieces, White will eventually win because Black has to
pass and White moves three times in a row.

Interpretation: What are the reasons for opponents to win or lose in Othello
against Edax? – To investigate this, we analyze specific Othello episodes:
When Edax plays at level 7, it has advanced tactics that narrow the range of
possible actions for the opponent (Fig. 5(a)): If Edax ($2^{nd}$) plays
against opponent TCL-base ($1^{st}$), Edax forces TCL-base towards the end of
the episode to play disadvantageous moves. If we now replace the opponent
($1^{st}$) with TCL-wrap, it avoids these traps: The planning stage of TCL-
wrap helps to foresee the disadvantageous positions when they are some moves
ahead; now TCL-wrap finds other moves to avoid them and is thus not forced
into the disadvantageous positions.

At level 8 or higher, Edax shows sometimes another tactic: It may play in such
a way that the last 2-4 moves are pass moves for the opponent (Fig. 5(b)):
Since the opponent has no available action at its disposal, it is forced to
pass the move right to Edax again. During the very last moves of an episode,
Edax may gain the majority of pieces. Currently, TCL-wrap is not able to avoid
these pass situations, at least not in the majority of the episodes played.

Table II:  Results of a ConnectFour tournament with 4 agents. Shown is the W/T/L (win/tie/loss) count of the $1^{st}$ (row) player when playing 100 episodes against the $2^{nd}$ (column) player. Agents are ranked by their overall rate of games won (last column). The colored and bold numbers show remarkable improvements of TCL-wrap over TCL-base. W/T/L |  $2^{nd}$ player | won games rate
---|---|---
TCL-wrap |  AB-DL | TCL-base |  MCTS
$1^{st}$ | TCL-wrap |  |  99/0/1 | 100/0/0 | 100/0/0 | 66.3%
AB-DL | 100/0/0 |  | 100/0/0 | 100/0/0 | 64.9%
TCL-base | 100/0/0 |  91/2/7 |  | 100/0/0 | 49.0%
MCTS |  1/2/97 | 17/3/80 |  97/2/1 |  | 19.8%

###  IV-B ConnectFour

ConnectFour is a non-trivial game that is not easy to master for humans.
However, its medium-size complexity allows for very strong tree-based
solutions when combined with a pre-computed opening book. These near-perfect
agents are termed AB and AB-DL since they are based on alpha-beta search (AB)
that extends the Minimax algorithm by efficiently pruning the search tree.
Thill et al. [22] were able to implement alpha-beta search for ConnectFour in
such a way that it plays near-perfect: It wins all games as $1^{st}$ player
and wins very often as $2^{nd}$ player when the $1^{st}$ player makes a wrong
move. AB and AB-DL differ in the way they react to losing states: While AB
just takes a random move, AB-DL searches for the move, which postpones the
loss as far (as distant) as possible (DL = distant losses). It is tougher to
win against AB-DL since it will request more correct moves from the opponent
and will very often punish wrong moves.

We perform a tournament with the following 4 agents:

  * •

TCL-wrap: MCTSWrapper[TCL-base] (iter=1,000, $c_{PUCT}$=1.0, unlimited depth),

  * •

TCL-base: TCL alone,

  * •

AB-DL: Alpha Beta with Distant Losses,

  * •

MCTS: MCTS(UCT, random playouts, iter=10,000, treeDepth=40)

Figure 6:  The effect of MCTS wrapping on ConnectFour. Shown are the averages
from 5 runs, where each run consists of 25 competition episodes MCTS
($1^{st}$) vs. agent ($2^{nd}$). The agents are a) TCL-wrap: TCL wrapped by
MCTS wrapper with iterMWrap iterations; b) AB-DL: Alpha-Beta agent with
distant losses; c) TCL-base: TCL without MCTS wrapper. Error bars denote
standard deviations.

The results are shown in Tab. II and can be described as follows: TCL-wrap and
AB-DL win nearly all their games when playing first (ConnectFour is a
theoretical win for the $1^{st}$ player). TCL-base ($1^{st}$) wins against AB-
DL ($2^{nd}$) the majority of its games (91%), but not all. If we enhance TCL-
base by MCTS wrapper, the win rate of TCL-wrap rises to fantastic 99%, so it
avoids 8/9 of the former TCL-base losses or ties.

MCTS, as the weakest agent in the tournament, wins as $1^{st}$ player most of
its games (97%) against TCL-base ($2^{nd}$), but it predominantly loses
against TCL-wrap and AB-DL ($2^{nd}$). TCL-wrap as $2^{nd}$ player is in this
respect significantly stronger than AB-DL (97% vs. 80% win rate, resp.), which
leads for TCL-wrap to a higher total rate of 66.3% won games as compared to
AB-DL (64.9%). Besides that, the total won games rate 66.3% is a big jump
forward when compared to the total won game rate 49% of TCL-base.

Interpretation: MCTS plays differently, perhaps more surprising, than near-
optimal agents. Since TCL-base was trained on a near-optimal agent (itself),
it has never seen the ‘surprising’ moves of MCTS and will probably often react
wrongly on these moves. Thus, TCL-base loses most of its games when playing
$2^{nd}$. If we now add with MCTS wrapper a planning component to TCL-base,
then TCL-wrap can find better responses to the ‘surprising’ moves, and it can
better exploit the occasional wrong moves of MCTS. As a consequence, it wins
most of the episodes.

Fig. 6 shows the results of MCTS wrapping in ConnectFour as a function of MCTS
wrapper iterations. Even a small amount of iterations (50-100) already leads
to a TCL-wrap win rate of $>80\%$. With 500 iterations or more, TCL-wrap
achieves a win rate near 100%.

Additionally, we made an experiment comparing our agents AlphaBeta-DL and TCL-
wrap with ConnectZero from Dawson [24]: We performed 10 episodes with
ConnectZero starting (which is a theoretical win), but found instead that
AlphaBeta playing second won 80% of the episodes and TCL-wrap playing second
won all episodes.

(a) (b)

Figure 7:  The effect of MCTS wrapping on Rubik’s Cube. Shown are the averages
from 4 runs, where each run evaluates the ability of the agents to solve a
large set of scrambled cubes (a) as a function of MCTS iterations: 2x2x2: 600
cubes scrambled with either 11, 12 or 13 twists; 3x3x3: 600 cubes scrambled
with either 7, 8 or 9 twists; (b) as a function of scrambling twists where
iterMWrap=0 corresponds to TCL-base and iterMWrap$>$0 to different variants of
TCL-wrap. We average over 200 scrambled cubes for each twist number. Error
bars denote standard deviations.

###  IV-C Rubik’s Cube

We investigate two variants of Rubik’s Cube: 2x2x2 and 3x3x3. We trained TCL
agents by presenting them cubes scrambled with up to $p_{max}$ twists where
$p_{max}=13$ for 2x2x2 and $p_{max}=9$ for 3x3x3555We limit ourselves to up to
9 twists here, because our network has not enough capacity to learn all states
of 3x3x3 Rubik’s Cube. Experiments with higher twist numbers during training
did not improve the solved-rates., both in half-turn metric. This covers the
complete cube space for 2x2x2, but only a small subset for 3x3x3, where God’s
number [25] is known to be 20. We evaluate the trained agents on 200 scrambled
cubes that are created by applying a given number $p$ of scrambling twists to
a solved cube. The agent now tries to solve each scrambled cube. A cube is
said to be unsolved if the agent cannot reach the solved cube in $e_{E}=20$
steps. More details on our method are found in [26].

Here we are interested in the relative strength of agents with and without
MCTS wrapping. The results are shown in Fig. 7: While TCL-base could only
solve 75% (2x2x2) or 25% (3x3x3) of the scrambled cubes, resp., the MCTS-
wrapped agent TCL-wrap could either fully solve the problem (2x2x2) or at
least double or triple the percentage of solved cubes (3x3x3).

Interpretation 2x2x2: Since the solved-rate of TCL-base is only 75%, the value
function $V(s)$ does not predict the right action for every state $s$
(resulting in a short path to the solved cube). However, if we add the
planning stage of MCTS-wrapper, then the action with the highest $V(s)$ after
a few ‘what-if’ steps is selected. This is sufficient to boost the solved-rate
to 100% after 200 or more MCTS-iterations.

Interpretation 3x3x3: The agent has seen during training only a small subset
of cubes with up to 9 scrambling twists. Therefore, the solved-rates for
$p\in{8,9}$ are much lower for TCL-base because it is very likely that the
cube ‘escapes’ with a wrong move into the unknown area of $p=10$ or higher. It
is interesting to see that the MCTS planning stage can double or triple the
solved-rate. However, it can not cure everything since the high branching
factor of 18 together with slight inaccuracies of the value function
approximator makes it likely that even 1000 iterations of MCTS-wrapper do not
explore enough to find the right path.

Table III: Training times to train $n_{ag}$ agents without and with MCTS wrapping (hypothetical) for all games.  game | $n_{ag}$ |  base${}^{\vphantom{R}}$ training time${}_{\vphantom{M}}$ | $i_{MCTS}$ | factor |  hypothetical${}^{\vphantom{R}}$ wrapped training time${}_{\vphantom{M}}$
---|---|---|---|---|---
Othello | 20 | 1.5 d | 10,000 | 2,575 | 10.6 years
ConnectFour | 10 | 1.4 d | 1,000 | 850 | 3.3 years
RubiksCube | 5 | 2.2 h | 1,000 | 770 | 71 days

###  IV-D Computation times

The MCTS wrapper for RL agents, as proposed in this paper, has the advantage
that it does not cost any additional training time since it is an enhancement
added after agent training.

The extra computational resources needed during game play or evaluation are
moderate. This is because we usually only need a few evaluation episodes
(compared to the huge number of training episodes) and for these few episodes
the 10,000 iterations are not a large computational burden, as shown in Tab.
IV (note the unit milliseconds).

Table IV:  Move times of TCL-base, TCL-wrap, and MCTS, where TCL-wrap [$i$] and MCTS [$i$] refer to the respective agents using $i$ iterations. Shown are average times and standard deviations in milliseconds. For the games Othello and ConnectFour, the values were averaged over 50 games. For RubiksCube, the values are based on 25 cubes, each initially scrambled with 8 twists.  game | TCL-base |  TCL-wrap [100] |  TCL-wrap [1000] |  TCL-wrap [10000] |  MCTS [10000]
---|---|---|---|---|---
Othello | $0.4\pm 0.5$ | $10\pm 6$ | $100\pm 80$ |  1,300 $\pm$ 700 |  551 $\pm$ 371
ConnectFour | $0.05\pm 0.02$ | $3\pm 2$ | $30\pm 20$ | $300\pm 200$ |  66 $\pm$ 20
3x3x3 Rubik’s | $0.6\pm 0.7$ | $10\pm 6$ | $100\pm 70$ |  1,800 $\pm$ 1,000 |  783 $\pm$ 49

The above advantage becomes more apparent if we compare the actual TCL-base
training times with the would-be training times if the MCTS planning stage
were also used during training, as shown in Tab. III: The base training time
is the time actually needed to train $n_{ag}$ agents without MCTS wrapper. All
computations were done on a single CPU Intel i7-9850H @ 2.60GHz.666To get a
single-agent training time, the base training time has to be divided by
$n_{ag}$ which results for example in 1.8 hours training time for one Othello
agent.

The wrapped training times are estimated by multiplying the base training time
with factor which is established by running a few episodes without and with
MCTS wrapper doing $i_{MCTS}$ iterations. This estimate assumes that a wrapped
agent needs as many training episodes as a base agent. This assumption needs
not to be true, a wrapped agent could reach similar performance in fewer
episodes. We experimentally investigate and discuss this point further in Sec.
IV-E. If this assumption were true, the hypothetical training times would be
astronomical: We see from Tab. III that with the same hardware, many years or
at least near 100 days of computation time would be necessary. Of course,
large speed-ups are possible with dedicated hardware or parallel execution on
many cores, but often this hardware is just not available.

###  IV-E MCTS Inside Self-Play Training

MCTS inside self‐play training can improve the quality of the experience
generated. It might be that substantially fewer episodes are necessary to
learn the same (or a better) function.

In order to investigate this, we conducted several experiments for the Othello
case: We cannot afford 10,000 MCTS iterations in the training loop for 250,000
episodes, as Tab. III shows, but we can approach it from several directions.

Figure 8:  MCTS inside training under the same training time budget (2h) as
TCL-base. The label W$*$ stands for MCTS with $*$ = 0, 100, 1,000, 10,000
iterations inside self-play training. This allows for 250,000, 12,000, 1,200
and 120 episodes, resp. W0 is identical to TCL-wrap. Shown are the win rates
vs. Edax from 20 competition runs (40 for W0) conducted in the same way as in
Fig. 4. Each agent uses 10,000 iterations during Edax evaluation.

Figure 9:  MCTS inside training with the same small number of training
episodes (12,000). The labels W$*$ have the same meaning as in Fig. 8. Note
that W0 is now different from TCL-wrap (only 12,000 training episodes). Shown
are the win rates from 20 competition runs (16 in the case of W10000).

Figure 10:  MCTS inside training with the same number of training episodes as
TCL-wrap (250,000). The labels W$*$ have the same meaning as in Fig. 8. W0 is
identical to TCL-wrap. Shown are the win rates vs. Edax from 40 competition
runs.

First, we present in Fig. 8 several runs with the same computational training
budget (2 hours) as TCL-base. All agents, regardless of their MCTS iterations
during training, use the same number of 10,000 MCTS iterations during Edax
evaluation (the standard for TCL-wrap in Othello). It is not surprising that
W1000 and W10000 cannot compete with Edax on any level, since the number of
training episodes is too small to explore a significant portion of the state
space.

The next experiment requires a higher computational budget: We take for all
agents the same number of 12,000 training episodes and allow for different
numbers of MCTS iterations during training (Fig. 9). This leads to single-
agent training times of 1.2 days for W1000 and 11.5 days for W10000, which is
16$\times$ and 153$\times$ the training time of TCL-wrap, resp. Nevertheless,
the win rates against Edax level 5–9 are considerably lower than for TCL-wrap.
Surprisingly, the win rates for W1000 and W10000 are for some levels lower
than for W100. It might be that the agents with higher iteration counts become
too deterministic and explore too little during self-play.777We used
$\epsilon$-greedy exploration during self-play and tuned $\epsilon$ on the
W100 agent, where we found a very small $\epsilon$ (compatible with 0) to give
the best results.

The third experiment tests MCTS iterations during training when we choose the
same number of training episodes (250,000) as TCL-wrap. 100 iterations are the
maximum possible here, since the training time for a single agent is already
2.5 days. The results in Fig. 10 show that W100 is mostly better than W0 (TCL-
wrap), with the largest increase for Edax level 8 (from 34% to 66%).

In summary, these experiments show that MCTS inside self-play training cannot
reach the same results as TCL-wrap under (a) the same computational budget (2
hours) or (b) a small number (12,000) of training episodes. But if we use the
same number of 250,000 training episodes as TCL-wrap, we see a small positive
effect of using MCTS in the training loop. However, this requires 30 times
more computing time.

##  V Discussion

###  V-A Related work

Self-play RL has a long tradition in game learning, with Tesauro’s TD-Gammon
[27] being a very early TD-learning application to Backgammon. The seminal
papers of Silver et al. on AlphaGo and AlphaZero [1, 3] lifted this for the
games Go, chess and shogi to a new complexity and performance level. They have
stirred the interest of many researchers to achieve similar things with
smaller hardware requirements and/or fewer training cycles. Thakoor et al.
[28] provided in 2017 a general AlphaZero implementation in Python with less
computational demands than the original. But even their architecture requires
for 6x6 Othello 3 days of training on a specialized cloud computing service
(Google Compute Engine with GPU support). Several works of Wang et al. [29,
30, 23] focus on different aspects of the AlphaZero architecture: alternative
loss functions, hyperparameter tuning and warm-start enhancements. They test
these aspects on smaller games like 6x6 Othello or 5x5 ConnectFour. The work
of Chang et al. [31] covered several AlphaZero improvements applied to 6x6
Othello. van der Ree and Wiering [12] investigate TD-, Q- and Sarsa-learning
for 8x8 Othello with a simple neural network (one hidden layer with 50
neurons).

Dawson [24] introduces a CNN-based and AlphaZero-inspired RL agent named
ConnectZero for ConnectFour, which can be played online and which reaches a
good playing strength against MCTS1000. Young et al. [32] report on an
AlphaZero implementation applied to ConnectFour. Here, training took between
21 and 77 hours of GPU time.

Recently in 2022, Norelli and Panconesi [21] presented an approach that is
close to our work: They as well pursue the goal to set up an AlphaZero-
inspired algorithm at much lower cost than the original AlphaZero [3]. The
agent in [21] is based on a residual DNN and is trained solely by self-play.
It is able to play 8x8 Othello and to defeat the strong Othello program Edax
[20] up to level 10. Although much less computationally demanding than the
original AlphaZero [3], their training time took roughly one month on
Colaboratory, a free Google cloud computing service offering GPUs and TPUs.
See Sec. V-C for a direct comparison between Norelli and Panconesi [21] and
our work.

Apart from Norelli and Panconesi [21], there are only few works on Othello
game learning that actually benchmark against Edax: Liskowski et al. [33]
presented in 2018 an agent obtained by training a convolutional neural network
(CNN) with the help of a database of expert moves. Their agent could defeat
Edax up to and including level 2.

Our work presented here is based on an earlier Bachelor thesis [34] published
in 2020 (but only in German); it presents an n-tuple RL agent for Othello
trained in 1.8 hours on standard hardware (no GPU) that can defeat Edax up to
and including level 7.

For the puzzle Rubik’s Cube, the pioneering work of McAleer [35] and
Agostinelli [36] in 2018 and 2019 shows that the 3x3x3 cube can be solved
without putting human knowledge or positional-pattern databases into the
agent. They solve arbitrary scrambled cubes with a method that is partly
inspired by AlphaZero but also contains special tricks for Rubik’s Cube.

A work related to GBG [7, 8] is the general game system Ludii [37]. Ludii is
an efficient general game system based on a ludeme library implemented in
Java, allowing to play as well as to generate a large variety of strategy
games. Currently, all AI agents implemented in Ludii are tree-based agents
(MCTS variants or AlphaBeta). GBG, on the other hand, offers the possibility
to train RL-based algorithms on several games.

Soemers et al. [38] describe a bridge between Ludii [37] and Polygames [39],
the latter providing DNN algorithms for strategy games. Similar to our work,
they couple approximator networks (DNNs) with MCTS, but for different games.
With 20 hours of training time, 8 GPUs, 80 CPU cores, and 475 GB of memory
allocation per training job, their resource usage is in a different dimension
than our training process.

###  V-B Related Work in N-Tuple Research

N-tuple networks, which are an important building block of our approach, have
shown to work well in many games, e. g., in ConnectFour [4, 22], Othello [5],
EinStein würfelt nicht (EWN) [40], 2048 [6], SZ-Tetris [41], etc. Other
function approximation networks (DNN or other) could be used as well in
AlphaZero-inspired RL, but n-tuple networks have the advantage that they can
be trained very fast on off-the-shelf hardware.

There are two papers in the game learning literature that combine n-tuple
networks with MCTS: Sironi et al. [42] use the n-tuple bandit EA to
automatically tune a self-adaptive MCTS. This is an interesting approach but
for a completely different goal and not related to AlphaZero.

Chu et al. [40] use an n-tuple network as a guidance for MCTS in the game EWN.
They train an n-tuple network via Monte-Carlo RL and incorporate the trained
heuristic with three different approaches into MCTS. Monte Carlo is a special
form of temporal difference (TD) learning, namely TD(1). To the best of our
knowledge, our work is the first to couple n-tuple networks with MCTS using
TD($\lambda$)-training with arbitrary $\lambda$.

Neither Chu et al. [40] nor we use MCTS in the training loop for the main
results. However, we compare in Sec. IV-E – at least for some viable settings
– MCTS within and outside of self-play training. Finally, we use our approach
for other games than those studied in [40].

###  V-C Comparison with Other RL Research

In this section, we compare our results with other RL approaches from the
literature.

Concerning the game ConnectFour, it was shown in Sec. IV-B that Dawson’s
ConnectZero lost most or all of its episodes when starting against AlphaBeta-
DL or TCL-wrap. This is in contrast to our TCL-base and TCL-wrap, which win
nearly all episodes when starting against AlphaBeta-DL (see Tab. II).

Concerning the game Othello, there are a number of other researchers that do
RL-based game learning: van der Ree and Wiering [12] reached in 2013 with
their Q-learning agent against the heuristic player Bench (positional player)
a win rate of 87%. We reach with both TCL-base and TCL-wrap a win rate of 100%
against Bench. Liskowski et al. [33] show in Table IX that their agent wins
against Edax up to and including Edax level 2. We win up to and including Edax
level 7.

In 2022, Norelli and Panconesi [21] obtained with their system Olivaw the best
Othello results up-to-date: It defeats Edax up to and including Edax level 10.
This is a truly impressive result, but it also took considerable computational
resources to achieve it: Although much cheaper than DeepMind’s original
AlphaZero, they needed an informal crowd computing project with 19 people for
game generation and then about 30 days to train a single agent on Google
Colaboratory using GPU and TPU hardware (50,000 training episodes with 100-400
MCTS iterations). Due to the large training time, fine-tuning of
hyperparameters or ablation studies could not be undertaken.

In our work presented here, we defeat Edax only up to level 7, but with a much
simpler architecture that is trainable in less than 2 hours on a single
standard CPU.888level 8 with MCTS in the training loop (Fig. 10) and 60 hours
training It is, on the one hand, interesting that our architecture, which
keeps the costly MCTS completely out of the training process, can get so far.

On the other hand, there is of course a performance gap to [21], and it would
be interesting to investigate which element of the more complex architecture
in [21] is responsible for the performance gain. We see here two hypothetical
candidates: First, including MCTS in the training phase leads to better
positional material in the replay buffer. Second, the network architecture of
Olivaw uses a Residual Network, a somewhat reduced version of the original
AlphaZero Residual Network, but still a deeper architecture than our n-tuple
network.

Concerning the puzzle Rubik’s Cube, the deep network used by McAleer [35] and
Agostinelli [36] had over 12 million weights and was trained for 44 hours on a
32-core server with 3 GPUs. Our approach with much less computational effort
can solve the 2x2x2 cube completely, but the 3x3x3 cube only partly.

##  VI Conclusion and Future Work

We have shown on the three challenging games, Othello, ConnectFour, and
Rubik’s Cube, that an AlphaZero-inspired MCTS planning stage boosts the
performance of TD-n-tuple networks. Interestingly, this performance boost is
even reached when MCTS is not part of the training stage, which leads to very
large reductions in training times and computational resources.

The new architecture was evaluated on the three games without any game-
specific changes. We reach near-perfect play for ConnectFour and 2x2x2 Rubik’s
Cube. For the games Othello and 3x3x3 Rubik’s Cube, we observe good results
and increased performance compared to our version without MCTS planning stage,
but we do not reach the high-quality results of Norelli and Panconesi [21] on
Othello (beats Edax level 10 where we reach only level 7) and of Agostinelli,
McAleer et al. [35, 36] on 3x3x3 Rubik’s Cube (they solve all scrambled cubes
while we solve only cubes with up to 9 twists). Both high-performing
approaches require considerably more computational resources.

We compared the effects of using MCTS within or outside of self-play training.
For Othello and n-tuple networks, we have found that large increases in
computation time are accompanied by no or only small increases in performance.

It is an interesting topic of future research to investigate which element of
the more complex architecture (MCTS in the training phase or deep residual
network for the approximator) is more relevant to reach the impressive high-
quality results of others. However, for moderately complex games, our smaller
architecture has the advantage of allowing faster training and more parameter
tuning with simpler hardware that is accessible to anyone.

We also plan to extend our MCTS wrapper concept to non-deterministic games (e.
g., EWN, 2048, Blackjack, Poker) where previous research [43] has shown that
plain MCTS is not sufficient and has to be extended by the Expectimax
approach.

## Acknowledgment

The authors would like to thank the anonymous reviewers for their insightful
comments that helped a lot to shape and improve this work.

## References

  * [1] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot _et al._ , “Mastering the game of Go with deep neural networks and tree search,” _Nature_ , vol. 529, no. 7587, pp. 484–489, 2016.
  * [2] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton _et al._ , “Mastering the game of Go without human knowledge,” _Nature_ , vol. 550, no. 7676, pp. 354–359, 2017.
  * [3] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel _et al._ , “Mastering chess and shogi by self-play with a general reinforcement learning algorithm,” _arXiv preprint arXiv:1712.01815_ , 2017.
  * [4] S. Bagheri, M. Thill, P. Koch, and W. Konen, “Online adaptable learning rates for the game Connect-4,” _IEEE Transactions on Computational Intelligence and AI in Games_ , vol. 8, no. 1, pp. 33–42, 2015.
  * [5] S. M. Lucas, “Learning to play Othello with n-tuple systems,” _Australian Journal of Intelligent Information Processing_ , vol. 4, pp. 1–20, 2008.
  * [6] M. Szubert and W. Jaśkowski, “Temporal difference learning of n-tuple networks for the game 2048,” in _Computational Intelligence and Games (CIG), 2014 IEEE Conference on_. IEEE, 2014, pp. 1–8.
  * [7] W. Konen, “General board game playing for education and research in generic AI game learning,” in _Conference on Games (London)_ , D. Perez, S. Mostaghim, and S. Lucas, Eds., 2019, pp. 1–8. [Online]. Available: https://arxiv.org/pdf/1907.06508
  * [8] ——, “The GBG class interface tutorial V2.3: General board game playing and learning,” TH Köln, Tech. Rep., 2022, retrieved Dec-29-2021. [Online]. Available: http://www.gm.fh-koeln.de/ciopwebpub/Konen22a.d/TR-GBG.pdf
  * [9] W. Konen and S. Bagheri, “Reinforcement learning for n-player games: The importance of final adaptation,” in _International Conference on Bioinspired Methods and Their Applications_. Springer, 2020, pp. 84–96.
  * [10] ——, “Final adaptation reinforcement learning for n-player games,” _arXiv preprint arXiv:2111.14375_ , 2021. [Online]. Available: https://arxiv.org/abs/2111.14375
  * [11] W. Jaśkowski, “Mastering 2048 with delayed temporal coherence learning, multistage weight promotion, redundant encoding, and carousel shaping,” _IEEE Trans. on Games_ , vol. 10, pp. 3–14, 2018.
  * [12] M. van der Ree and M. Wiering, “Reinforcement learning in the game of Othello: Learning against a fixed opponent and learning from self-play.” in _Adaptive Dynamic Programming and Reinforcement Learning (ADPRL)_ , 2013, pp. 108–115.
  * [13] W. Konen, “Reinforcement learning for board games: The temporal difference algorithm,” TH Köln, Tech. Rep., 2015. [Online]. Available: http://www.gm.fh-koeln.de/ciopwebpub/Kone15c.d/TR-TDgame_EN.pdf
  * [14] D. F. Beal and M. C. Smith, “Temporal coherence and prediction decay in TD learning,” in _Int. Joint Conf. on Artificial Intelligence (IJCAI)_ , T. Dean, Ed. Morgan Kaufmann, 1999, pp. 564–569.
  * [15] L. Kocsis and C. Szepesvári, “Bandit based Monte-Carlo planning,” in _Proceedings of the 17th European Conference on Machine Learning_ , ser. ECML’06. Berlin, Heidelberg: Springer-Verlag, 2006, p. 282–293. [Online]. Available: https://doi.org/10.1007/11871842_29
  * [16] C. B. Browne, E. Powley _et al._ , “A survey of Monte Carlo tree search methods,” _IEEE Transactions on Computational Intelligence and AI in Games_ , vol. 4, no. 1, pp. 1–43, 2012.
  * [17] C. D. Rosin, “Multi-armed bandits with episode context,” _Annals of Mathematics and Artificial Intelligence_ , vol. 61, no. 3, pp. 203–230, Mar. 2011. [Online]. Available: http://link.springer.com/10.1007/s10472-011-9258-6
  * [18] W. W. Bledsoe and I. Browning, “Pattern recognition and reading by machine,” in _Proceedings of the Eastern Joint Computer Conference_ , 1959, pp. 225–232.
  * [19] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_. Cambridge, MA: MIT Press, 1998.
  * [20] R. Delorme, “Edax, version 4.4,” 2019, retrieved Dec-29-2021. [Online]. Available: https://github.com/abulmo/edax-reversi
  * [21] A. Norelli and A. Panconesi, “OLIVAW: Mastering Othello without human knowledge, nor a penny,” _IEEE Transactions on Games_ , 2022.
  * [22] M. Thill, S. Bagheri, P. Koch, and W. Konen, “Temporal difference learning with eligibility traces for the game Connect-4,” in _International Conf on Computational Intelligence in Games (CIG), Dortmund_ , M. Preuss and G. Rudolph, Eds., 2014, pp. 1–8.
  * [23] H. Wang, M. Preuss, and A. Plaat, “Warm-start AlphaZero self-play search enhancements,” in _International Conference on Parallel Problem Solving from Nature_. Springer, 2020, pp. 528–542.
  * [24] R. Dawson, “Learning to play Connect-4 with deep reinforcement learning,” 2020, retrieved Dec-29-2021. [Online]. Available: https://codebox.net/pages/connect4
  * [25] T. Rokicki, H. Kociemba, M. Davidson, and J. Dethridge, “The diameter of the Rubik’s Cube group is twenty,” _SIAM Review_ , vol. 56, no. 4, pp. 645–670, 2014.
  * [26] W. Konen, “Towards learning Rubik’s Cube with n-tuple-based reinforcement learning,” TH Köln (in preparation), Tech. Rep., 2022.
  * [27] G. Tesauro, “TD-Gammon, a self-teaching backgammon program, achieves master-level play,” _Neural computation_ , vol. 6, no. 2, pp. 215–219, 1994\.
  * [28] S. Thakoor, S. Nair, and M. Jhunjhunwala, “Learning to play Othello without human knowledge,” 2017, retrieved Dec-28-2021. [Online]. Available: https://github.com/suragnair/alpha-zero-general
  * [29] H. Wang, M. Emmerich, M. Preuss, and A. Plaat, “Alternative loss functions in AlphaZero-like self-play,” in _2019 IEEE Symposium Series on Computational Intelligence (SSCI)_. IEEE, 2019, pp. 155–162.
  * [30] ——, “Hyper-parameter sweep on AlphaZero general,” _arXiv preprint arXiv:1903.08129_ , 2019. [Online]. Available: https://arxiv.org/pdf/1903.08129
  * [31] N.-Y. Chang, C.-H. Chen, S.-S. Lin, and S. Nair, “The big win strategy on multi-value network: An improvement over AlphaZero approach for 6x6 Othello,” in _Proceedings of the 2018 International Conference on Machine Learning and Machine Intelligence_ , 2018, pp. 78–81.
  * [32] A. Young, A. Prasad, and I. Abrams, “Lessons from implementing AlphaZero, part 6,” 2018, retrieved Dec-29-2021. [Online]. Available: https://link.medium.com/ylGDD6F7V9
  * [33] P. Liskowski, W. Jaśkowski, and K. Krawiec, “Learning to play Othello with deep neural networks,” _IEEE Transactions on Games_ , vol. 10, no. 4, pp. 354–364, 2018.
  * [34] J. Scheiermann, “AlphaZero-inspirierte KI-Agenten im General Board Game Playing,” 2020, Bachelor thesis, TH Köln – University of Applied Sciences. [Online]. Available: http://www.gm.fh-koeln.de/ciopwebpub/Scheier20a.d/Scheier2020.pdf
  * [35] S. McAleer, F. Agostinelli, A. Shmakov, and P. Baldi, “Solving the Rubik’s Cube with approximate policy iteration,” in _International Conference on Learning Representations_ , 2019.
  * [36] F. Agostinelli, S. McAleer, A. Shmakov, and P. Baldi, “Solving the Rubik’s Cube with deep reinforcement learning and search,” _Nature Machine Intelligence_ , vol. 1, no. 8, pp. 356–363, 2019.
  * [37] É. Piette, D. J. N. J. Soemers, M. Stephenson, C. F. Sironi, M. H. M. Winands, and C. Browne, “Ludii - the ludemic general game system,” _CoRR_ , vol. abs/1905.05013, 2019. [Online]. Available: http://arxiv.org/abs/1905.05013
  * [38] D. J. Soemers, V. Mella, C. Browne, and O. Teytaud, “Deep learning for general game playing with Ludii and Polygames,” _arXiv preprint arXiv:2101.09562_ , 2021. [Online]. Available: https://arxiv.org/pdf/2101.09562
  * [39] T. Cazenave, Y.-C. Chen, G.-W. Chen, S.-Y. Chen, X.-D. Chiu, J. Dehos, M. Elsa, Q. Gong, H. Hu, V. Khalidov _et al._ , “Polygames: Improved zero learning,” _ICGA Journal_ , vol. 42, no. 4, pp. 244–256, 2020.
  * [40] Y. R. Chu, Y. Chen, C. Hsueh, and I. Wu, “An agent for EinStein Würfelt Nicht! using n-tuple networks,” in _Conf. on Technologies and Applications of AI (TAAI)_ , Dec 2017, pp. 184–189.
  * [41] W. Jaśkowski, M. Szubert, P. Liskowski, and K. Krawiec, “High-dimensional function approximation for knowledge-free reinforcement learning: A case study in SZ-Tetris,” in _Conf. on Genetic and Evolutionary Computation_ , 2015, pp. 567–573.
  * [42] C. F. Sironi, J. Liu, D. Perez-Liebana, R. D. Gaina, I. Bravi, S. M. Lucas, and M. H. Winands, “Self-adaptive MCTS for general video game playing,” in _International Conference on the Applications of Evolutionary Computation_. Springer, 2018, pp. 358–375.
  * [43] J. Kutsch, “KI-Agenten für das Spiel 2048: Untersuchung von Lernalgorithmen für nichtdeterministische Spiele,” 2017, Bachelor thesis, TH Köln – University of Applied Sciences. [Online]. Available: http://www.gm.fh-koeln.de/ciopwebpub/Kutsch17.d/Kutsch17.pdf


# Electron energy loss and angular asymmetry induced by elastic scattering in
helium droplets

Jakob D. Asmussen  Department of Physics and Astronomy, Aarhus University,
Denmark  Keshav Sishodia  Department of Physics, Indian Institute of
Technology Madras, India  Björn Bastian  Department of Physics and Astronomy,
Aarhus University, Denmark  Abdul R. Abid  Department of Physics and
Astronomy, Aarhus University, Denmark  Ltaief Ben Ltaief  Department of
Physics and Astronomy, Aarhus University, Denmark  Henrik B. Pedersen
Department of Physics and Astronomy, Aarhus University, Denmark  Subhendu De
Department of Physics, Indian Institute of Technology Madras, India  Christian
Medina  Institute of Physics, University of Freiburg, Germany  Nitish Pal
Elettra Sincrotrone, Trieste, Italy  Robert Richter  Elettra Sincrotrone,
Trieste, Italy  Thomas Fennel  Institut für Physik, Universität Rostock,
Germany  Sivarama Krishnan  Department of Physics, Indian Institute of
Technology Madras, India  Marcel Mudrich<EMAIL_ADDRESS>Department of
Physics and Astronomy, Aarhus University, Denmark

###### Abstract

Helium nanodroplets are ideal model systems to unravel the complex interaction
of condensed matter with ionizing radiation. Here we study the effect of
purely elastic electron scattering on angular and energy distributions of
photoelectrons emitted from He nanodroplets of variable size ($10$-$10^{9}$
atoms per droplets). For large droplets, photoelectrons develop a pronounced
anisotropy along the incident light beam due to a shadowing effect within the
droplets. In contrast, the detected photoelectron spectra are only weakly
perturbed. This opens up possibilities for photoelectron spectroscopy of
dopants embedded in droplets provided they are smaller than the penetration
depth of the light and the trapping range of emitted electrons.

††preprint: APS/123-QED

Irradiation of condensed matter with ionizing radiation induces various
secondary processes in addition to the primary photoionization event. In
biological matter, secondary processes such as electron-impact ionization,
radical reactions and dissociative attachment of low-energy electrons (LEEs)
to biomolecules are the main causes for radiation damage leading to mutations
or cell death [1, 2]. Deciphering the mechanisms of radiation damage is
crucial for devising improved schemes for radiotherapy for cancer [3, 4, 5,
6]. LEEs are mainly produced by scattering of the primary and secondary
electrons in the medium [7]. In bulk molecular systems, complex interactions
of electrons with intra- and intermolecular degrees of freedom make it hard to
unravel the various elastic and inelastic scattering channels. Furthermore,
the tendency of slow electrons to remain trapped in the material hinders their
detection. Therefore, solid or liquid nanoparticles (NPs) have been used to
study the dynamics of electron scattering [8] and other properties making NPs
relevant for atmospheric, astrophysical, and technical sciences [9, 10, 11,
12, 13].

As atoms or molecules condense into clusters and NPs, photoelectron angular
distributions (PADs) tend to become more isotropic because emitted electrons
scatter on the cluster constituents and thereby change their emission
direction. A reduction of the detected electron kinetic energy for increasing
NP size is typically ascribed to inelastic scattering; energy transfer is
small in elastic electron-molecule collisions due to the large mass mismatch
($<1/1836$). Nevertheless, elastic scattering can lead to diffusion-like,
damped electron motion in extended media, as we show in this work. At particle
sizes $\gtrsim 100$ nm, electron distributions are additionally altered by
optical confinement effects such as nanofocusing and shadowing [13]. The
latter occurs when the particle size exceeds both the penetration depth of the
radiation and the mean path traveled by an emitted electron before it is
trapped in the droplet (‘trapping range’). Electrons are then preferentially
emitted from that side of the particle facing toward the incident light [14,
12]. In electron imaging experiments, the degree of shadowing is often
specified by the anisotropy parameter $\alpha=I_{f}/I_{b}\leq 1$, where
$I_{f/b}$ is the electron intensity in the forward/backward half plane of the
electron image with respect to the incoming light. So far, the various
phenomena related to electron scattering have been studied separately for
different types of NPs [13]. The continuous evolution of photoelectron
distributions from individual atoms up to large NPs has not been reported. In
particular, the effect of elastic scattering on electron distributions has not
been demonstrated explicitly.

In this work, we present a comprehensive study of photoemission spectra (PES)
and PAD of large superfluid helium nanodroplets (HNDs). HNDs are particularly
well suited model systems to study electron scattering as they feature an
extraordinarily wide gap in their excitation spectrum reaching from $\sim 1$
eV (phonons) up to 20 eV (excitons) [15]. This gives us the unique opportunity
to investigate purely elastic electron-atom scattering in a condensed-phase
system in a wide energy range. Additional complications due to nano-focusing
effects [13] are negligible as the refractive index of He only weakly deviates
from 1 by $<0.02$ [16, 17]. Due to their superfluid nature, HNDs are
homogeneous, spherically symmetric particles featuring a flat, nearly size-
independent density distribution [18, 19]. The droplet size can be varied
continuously in a wide range from a few nm up to $\gtrsim 10~{}\mu$m [20, 21].
HNDs are widely used as cold, inert and transparent cryo-matrices to form
tailored molecular complexes, metal clusters and NPs which can be probed by
spectroscopy and mass spectrometry [15, 22]. Extending the HND technique to
extreme-ultraviolet or X-ray photoelectron spectroscopy (UPS, XPS) of embedded
(‘dopant’) species is an intriguing prospect, in particular for probing novel
types of nano-aggregates formed in HNDs [23, 24, 25, 26, 22]. However, it has
remained an open question to what extent PES from dopants are distorted by the
interaction of emitted electrons with the He matrix. Previous PES measurements
of dopants using ns and fs multi-photon laser-ionization schemes appeared to
be largely unperturbed by the surrounding He [27, 28, 29, 30, 31, 32, 33],
while Penning ionization electron spectra are notoriously broad and structure-
less [34, 35, 36, 31]. Likewise, recent experiments investigating above-
threshold ionization of atoms and molecules in HNDs indicated that electron-He
scattering substantially impacts PES and PAD [37, 38, 39, 40, 41]. The
relaxation of hot electrons at energies $>1$ eV in HNDs has been described by
electron-atom binary collisions [28]. Below $1$ eV, electrons localize in void
bubbles [42, 43, 44] which then scatter at elementary modes of the HND
(phonons and rotons) before emerging to the droplet surface where electrons
are eventually released into the vacuum [44, 45]. Here we show experimentally
and using classical scattering simulations that electron-He elastic scattering
is an important mechanism leading to substantial electron-energy loss (EEL)
and drastically altered PADs of emitted electrons. Large HNDs with radii
$R\gtrsim 20$ nm containing $\langle N\rangle\gtrsim 10^{6}$ He atoms feature
a pronounced anisotropy of the electron PAD along the light propagation axis,
but the PES of detected electrons are only weakly perturbed.

Figure 1: a) VMIs of photoelectrons detected in coincidence with He+ from He
gas. Arrows show the light propagation direction ($h\nu$), polarization
($\epsilon$) and the droplet beam direction (HNDs). $\theta$ is the angle of
photoemission with respect to the polarization of the light. b)-d) VMIs of all
electrons emitted from a beam of HNDs of various sizes. All VMIs are measured
at $h\nu=26$ eV. In d) the dotted line separates the forward ($I_{f}$) and
backward ($I_{b}$) half-planes of the image with respect to the incident
light. The grid pattern visible in c) and d) is a detector artifact.

HNDs were formed by continuous expansion of He at high pressure (30-50 bar)
into vacuum through a cryogenically cooled (7-32 K) nozzle of diameter
$5~{}\mu$m. By controlling the expansion pressure and temperature, the droplet
mean radius $R$ was varied in the range 1-190 nm ($\langle
N\rangle=10$-$10^{9}$). The droplet size was determined by titration
measurements [20] and by comparison to literature values [15]. The XENIA (XUV
electron-ion spectrometer for nanodroplets in Aarhus) endstation [46] located
at the AMOLine of the ASTRID2 synchrotron at Aarhus University, Denmark [47],
was used to record velocity-map images (VMIs) of photoelectrons. PES and PAD
were inferred from the VMIs by Abel inversion using the MEVELER reconstruction
method [48]. Additionally, high resolution PES were measured using a
hemispherical analyzer (VG-220i) mounted under the magic angle at the GasPhase
beamline at the synchrotron Elettra in Trieste, Italy [49].

Figure 2: a) Anisotropy parameter $\beta$ inferred from VMIs as a function of
mean droplet size at different photon energies for all electrons and b) for
electrons detected in coincidence with He+ and He${}_{2}^{+}$. c) Shadowing
parameter $\alpha$ as function of droplet size. Note the different $x$-axis
range. The dotted lines show the corresponding results of the scattering
simulations.

Fig. 1 shows VMIs recorded at a photon energy $h\nu=26$ eV for various HND
sizes. Photoelectrons emitted from free He atoms [Fig. 1 a)] by absorption of
one photon are emitted according to the PAD $I(\theta)\propto\cos^{2}(\theta)$
corresponding to the asymmetry parameter $\beta=2$, as conventionally defined
by the angular intensity distribution $I(\theta)\propto
1+\beta(3\cos^{2}\theta-1)/2$ [50]. Here, $\theta$ is the angle between the
light polarization and the emission direction. For increasing HND size, the
angular distribution becomes more isotropic ($\beta\rightarrow 0$) due to the
increasing number of elastic collisions the electrons undergo on their way out
of the droplet [Fig. 1 b) & c)]. Fig. 1 d) shows the VMI in the case where the
HNDs are on average larger than the penetration depth of the incident light.
At $h\nu=26$ eV, the photoionization cross-section of He is 6.79 Mb [51]
corresponding to a penetration depth of $67.6$ nm into liquid helium. For
large HNDs, the PAD is dominated by the shadowing effect and Abel inversion is
ill-defined due to breaking of the cylindrical symmetry about the polarization
of the light meaning that we cannot define $\beta$ from the VMI. Additional
VMIs recorded for different droplet sizes and photon energies are shown in
Suppl. Fig. 1 in the Supplementary Information (SI) [52].

Fig. 2 a) shows $\beta$ for all emitted electrons as a function of the HND
size in the range $\langle N\rangle=10$-$10^{5}$ atoms where the shadowing
effect is absent. $\beta$ is constant up to $\langle N\rangle\sim 200$.
Thereafter, it drops to 0.5 for $\langle N\rangle\sim 10^{4}$. However,
$\beta$ does not significantly depend on the photon energy, as previously
observed [53]. Fig. 2 b) shows $\beta$ as a function of HND size for electrons
detected in coincidence with He+ and He${}_{2}^{+}$ ions, respectively.
Electrons coincident with He+ feature nearly constant anisotropy with
$\beta\approx 2$ for all droplet sizes; These electrons and He+ ions stem from
free He atoms accompanying the droplet beam even under expansion conditions
(low nozzle temperature $\lesssim 12$ K) when large HNDs are formed. In
contrast, for electrons detected in coincidence with He${}_{2}^{+}$, $\beta$
decreases from 2 for $\langle N\rangle\lesssim 30$ to 0.5 for $\langle
N\rangle\approx 10^{4}$. As He${}_{2}^{+}$ are formed by fragmentation of He
clusters and HNDs, the electrons’ PADs recorded in coincidence with
He${}_{2}^{+}$ are indicative for HND photoionization. Note that for these
electrons, $\beta$ drops below 2 for droplet sizes $\langle N\rangle>20$
whereas for all electrons [Fig. 2 a)], $\beta\approx 2$ up to $\langle
N\rangle\approx 200$. This shows that in the regime of small droplets,
$\langle N\rangle\lesssim 200$, free He atoms are more abundant in the
supersonic jet than He droplets. The electron mean-free path (EMFP) for
elastic scattering calculated from the total electron scattering cross-section
[54] and the number density of bulk liquid He [18] is 8 Å for an electron
kinetic energy of 1 eV and it is 16 Å at 10 eV. This value is consistent with
the He droplet radius $R\approx 1.2$ nm up to which $\beta\approx 2$ [Fig. 2
b)].

For larger He droplets, the $\alpha$-anisotropy due to the shadowing effect
dominates the PADs. Fig. 2 c) shows that $\alpha$ decreases (increasing
shadowing effect) as the droplets grow larger than $\langle N\rangle\approx
10^{6}$ ($R\approx 20$ nm). The size-dependence of $\alpha$ for electrons
detected in coincidence with He${}_{2}^{+}$ (correlated with HNDs) closely
follows the one for all electrons because the abundance of free He atoms in
the jet is small under these conditions (see Suppl. Fig. 3 [52]).

To investigate the energy loss of the photoelectrons for large HNDs, we
recorded high-resolution PESs using a hemispherical analyzer. Fig. 3 a) shows
an EEL spectrum recorded at $h\nu=44$ eV (see electron spectra for other
droplet sizes in Suppl. Fig. 11 [52]). As the droplet size increases, the
photoemission line develops a tail toward higher EEL (lower electron energy).
Similar asymmetric line broadening was previously reported for small HNDs
($R=2$-$6$ nm) doped with aniline molecules [28]. While the line shape was
described by an exponentially decaying function $\propto\exp[-E_{e}/a]$, here
we find empirically the best fit with the function
$\propto\exp[-(E_{e}/a)^{b}]$ (see dotted lines in Fig. 3 a) and details in
the SI [52]). From these fits we infer the mean relative EEL (see Suppl. Fig.
11 [52]), which is shown in Fig. 3 b) as function of HND size. Note that the
EEL only pertains to the electrons emitted from the droplets. The total EEL is
in fact higher if all electrons trapped in the droplets are taken into
account. For a droplet of $R\sim 50$ nm, $\sim 15$% of the electron energy is
lost on average due to elastic scattering. This corresponds to $\sim 300$
binary collisions according to simple estimates of the kinematics assuming
head-on collisions (see SI [52]).

To obtain a better understanding of the electron-He interaction leading to
changes in the PAD, the experimental results are compared with classical
electron–He elastic scattering simulations based on differential (energy,
scattering angle) scattering cross sections. See the SI [52] for a detailed
description. In the simulation, an electron recombines with its parent ion
when it turns around and binds to the ion with a binding energy exceeding its
kinetic energy. A simulated electron trajectory for this case is displayed in
Fig. 3 c) as an inset. The corresponding time evolution of the kinetic energy
is shown as a red line. For comparison, a trajectory where the electron
escapes the droplet is included (blue line). Large HNDs, which have similar
properties as bulk superfluid He, feature a potential energy barrier of
$\sim$1.1 eV below which electrons localize in bubbles [black dashed line in
Fig. 3 c] [55, 56, 34]. Thus, in the simulated PAD we exclude those LEEs with
kinetic energy $<1.1~{}$eV. Obviously, this leads to an inconsistency between
the simulation and the experiment at $h\nu<25.7$ eV indicating that not all
low-energy electrons are actually trapped, e. g. those formed near the
surface. We do not have a direct measure of the number of photoelectrons
evading detection due to trapping in the HNDs, but can only make a rough
estimate based on the He flux measured by the pressure increase in the HND
beam dump (see Suppl. Fig. 6 [52]).

The results of the simulations including the 1.1 eV cutoff are shown as dotted
lines in Fig. 2. For reference, the results of the simulation without energy
cutoff are shown in the Suppl. Fig 10 [52]. The simulated $\beta$ values
follow a similar size-dependence as those inferred from electrons detected in
coincidence with He${}_{2}^{+}$ in the experiment. The PAD becomes more
isotropic as $\langle N\rangle>30$ due to elastic electron-He scattering.
Deviations from atomic PAD have been observed for inner-valence ionization of
the clusters of heavier rare-gas atoms in a size range from $\langle
N\rangle=70$-$7000$ [57, 58, 59, 60]. The conclusion was that PAD are
significantly changed when the cluster size reaches the magnitude of the EMFP
for elastic scattering [57], which is consistent with our findings for HNDs.
The shadowing effect for large HNDs is also well reproduced by the scattering
simulations, see Fig. 2 c). The corresponding drop of $\alpha$ for $\langle
N\rangle\gtrsim 10^{6}$ is more pronounced near the He ionization threshold
(24.59 eV) where both the absorption cross-section (7.40 Mb [51]) and the
electron-He scattering cross-section (600 Mb [54]) are highest. Note that at
higher photon energies $>45~{}$eV additional features appear in the electron
VMIs due to inelastic scattering of photoelectrons on He atoms in the
droplets, see Suppl Fig. 2 [52]. Different $\alpha$ values for these features
inform about the mechanisms of generating these electrons.

The value $\alpha=0.6$ measured for $R=100$ nm at $h\nu=25$ eV is close to
that reported for solid salt NPs (NaCl [12], KCl [61]) of similar size.

Figure 3:  a) Experimental and simulated EEL spectra for large HNDs
($R=57.6~{}$nm) recorded at $h\nu=44$ eV. The colored dotted lines are best
fits to the experimental and simulated data. b) Mean relative energy loss as
function of HND size determined from the fits of the electron spectra. c)
Classical simulations of electron scattering in a HND at a photon energy of 26
eV. The inset shows an electron trajectory for the case where the electron
loses all its energy and returns to its parent ion where it recombines. The
electron energy is encoded in the line color. The evolution of the electron
energy is shown as red line in the main panel. The blue line indicates a
trajectory where the electron escapes from the droplet. The black dashed line
shows the potential barrier for electron localization in the bulk of large
HNDs.

The fact that shadowing becomes the dominant effect when the HND size
approaches the photon penetration depth ($\sim 70$ nm) implies that the latter
is the upper bound for the electron trapping range. A conservative estimate of
the lower bound is the EMFP for elastic scattering ($\sim 1$ nm). Thus, the
trapping range is in order of 10 nm, which is consistent with the rise in
electrons evading detection which we observe in the size range $R=10$-$40$ nm
(see the Suppl. Fig 6 [52]). From the simulations we determine the trapping
range by evaluating the maximum distance travelled by an electron from the
cation in bulk liquid He, see Suppl. Fig. 7-9 [52]. For $h\nu<27$ eV, the
trapping range is smaller than the photon penetration depth and it becomes
similar in magnitude for $h\nu\gtrsim 27$ eV.

When excluding the droplet barrier for electron trapping, the simulated values
of the $\alpha$-parameter closely follow those found when the 1.1 eV-barrier
is taken into account, but the trapping range is largely overestimated. As the
the trapping range and the potential barrier are closely correlated, an
alternative condition for LEE trapping in He droplets could be a finite escape
depth at the droplet surface, see Suppl. Fig. 9 [52]. The higher efficiency of
electron-He elastic scattering observed in experiments as compared to the
classical scattering simulations is likely due to quantum effects becoming
important at low energies $\lesssim 10~{}$eV where the de Broglie wavelength
of the electron reaches the average distance between He atoms in a HND (3.6 Å)
or even the size of the whole HND ($\lesssim 1$ eV). However, performing
quantum-scattering simulations goes beyond the scope of this work.

The experimental and simulated electron spectra show a similar tail extending
from the photoline toward higher EEL [see Fig. 3 a)]. However, given that the
resulting average relative EEL is only 15 % and the peak of the photoemission
line remains nearly unshifted, we conclude that photoelectron spectroscopy is
possible even for large droplets ($\langle N\rangle>10^{7}$) provided the
electron energy well exceeds 1.1 eV. The larger EEL found in the experiment
with aniline-doped HNDs [28] is likely due to the low energy of emitted
electrons ($\sim 0.8$ eV), at which scattering should be treated quantum
mechanically and electron localization by formation of bubbles can no longer
be neglected.

In summary, we have demonstrated the effect of elastic scattering on the
energy and angular distributions of photoelectrons emitted from HNDs in wide
ranges of droplet size and electron energy. We identify two regimes of
anisotropic electron emission. For small droplets ($\langle N\rangle<10^{6}$),
the cylindrical symmetry with respect to the polarization of the light is
retained. However, electron emission becomes more isotropic compared to free
He atoms when the HND radius $R\gtrsim 1.2$ nm exceeds the EMFP for elastic
scattering. Large droplets ($\langle N\rangle>10^{6}$) exhibit a pronounced
shadowing effect and the PAD becomes anisotropic along the light propagation
direction. For typical experimental conditions ($\langle N\rangle\sim 10^{4}$)
used in spectroscopy experiments, the average EEL is only $<1$ %; for large
droplets ($\langle N\rangle\sim 10^{7}$) the average EEL of the detected
photoelectrons rises but stays below $15\,$%. This makes HNDs a suitable
matrix for UPS and XPS of embedded species, but a significant loss of electron
angular information should be expected. Likewise, a large number of electrons
remain undetected as multiple elastic scattering leads to trapping of the
electrons in the droplets where they recombine with their parent ions. In
molecular systems such as water, electron scattering is affected by the higher
mass of the molecular constituents and by their internal (ro-vibrational)
degrees of freedom which open up additional inelastic scattering channels.
Nevertheless, scattering of electrons on molecules where no internal modes are
excited will contribute to EEL and should be taken into account as a mechanism
generating highly reactive LEEs.

##  I Acknowledgements

J.D.A. and M.M. acknowledge financial support by the Carlsberg Foundation. We
thank the Danish Agency for Science, Technology, and Innovation for funding
the instrument center DanScatt. T.F. acknowledges support by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) via SFB 1477
“light–matter interactions at interfaces” (project number 441234705) and via
the Heisenberg program (project number 436382461). S.R.K. thanks Dept. of
Science and Technology, Govt. of India, for support through the DST-DAAD
scheme and Science and Eng. Research Board. S.R.K., K.S. and S.D. acknowledge
the support of the Scheme for Promotion of Academic Research Collaboration,
Min. of Edu., Govt. of India, and the Institute of Excellence programme at
IIT-Madras via the Quantum Center for Diamond and Emergent Materials. S.R.K.
gratefully acknowledges support of the Max Planck Society’s Partner group
programme. M.M. and S.R.K. gratefully acknowledge funding from the SPARC
Programme, MHRD, India. A.R.A. acknowledges with gratitude for the support
from the Marie Skłodowska-Curie Postdoctoral Fellowship project Photochem-RS-
RP (Grant Agreement No. 101068805) provided by the European Union’s Horizon
2020 Research and Innovation Programme. The research leading to this result
has been supported by the project CALIPSOplus under grant agreement 730872
from the EU Framework Programme for Research and Innovation HORIZON 2020 and
by the COST Action CA21101 “Confined Molecular Systems: From a New Generation
of Materials to the Stars (COSY)”.

## References

  * Gómez-Tejedor and Fuss [2012] G. G. Gómez-Tejedor and M. C. Fuss,  _Radiation damage in biomolecular systems_ (Springer Science & Business Media, 2012).
  * Alizadeh  _et al._ [2015] E. Alizadeh, T. M. Orlando, and L. Sanche, Biomolecular damage induced by ionizing radiation: the direct and indirect effects of low-energy electrons on DNA, Ann. Rev. Phys. Chem. 66, 379 (2015).
  * Hanel  _et al._ [2003] G. Hanel, B. Gstir, S. Denifl, P. Scheier, M. Probst, B. Farizon, M. Farizon, E. Illenberger, and T. Märk, Electron attachment to uracil: Effective destruction at subexcitation energies, Phys. Rev. Lett. 90, 188104 (2003).
  * Martin  _et al._ [2004] F. Martin, P. D. Burrow, Z. Cai, P. Cloutier, D. Hunting, and L. Sanche, DNA strand breaks induced by 0–4 eV electrons: The role of shape resonances, Phys. Rev. Lett. 93, 068101 (2004).
  * Gokhberg  _et al._ [2014] K. Gokhberg, P. Kolorenč, A. I. Kuleff, and L. S. Cederbaum, Site-and energy-selective slow-electron production through intermolecular coulombic decay, Nature 505, 661 (2014).
  * Stumpf  _et al._ [2016] V. Stumpf, K. Gokhberg, and L. S. Cederbaum, The role of metal ions in X-ray-induced photochemistry, Nat. Chem. 8, 237 (2016).
  * Bass and Sanche [1998] A. D. Bass and L. Sanche, Absolute and effective cross-sections for low-energy electron-scattering processes within condensed matter, Radiation and Environmental Biophysics 37, 243 (1998).
  * Ban  _et al._ [2020] L. Ban, B. L. Yoder, and R. Signorell, Photoemission from free particles and droplets, Annu. Rev. Phys. Chem. 71, 315 (2020).
  * Niessner  _et al._ [1989] R. Niessner, W. Robers, and P. Wilbring, Laboratory experiments on the determination of polycyclic aromatic hydrocarbon coverage of submicrometer particles by laser-induced aerosol photoemission, Analytical Chemistry 61, 320 (1989).
  * Ziemann and McMurry [1998] P. J. Ziemann and P. H. McMurry, Secondary electron yield measurements as a means for probing organic films on aerosol particles, Aerosol Science and Technology 28, 77 (1998).
  * Wilson  _et al._ [2006] K. R. Wilson, D. S. Peterka, M. Jimenez-Cruz, S. R. Leone, and M. Ahmed, VUV photoelectron imaging of biological nanoparticles: Ionization energy determination of nanophase glycine and phenylalanine-glycine-glycine, Phys. Chem. Chem. Phys. 8, 1884 (2006).
  * Wilson  _et al._ [2007] K. R. Wilson, S. Zou, J. Shu, E. Rühl, S. R. Leone, G. C. Schatz, and M. Ahmed, Size-dependent angular distributions of low-energy photoelectrons emitted from NaCl nanoparticles, Nano Letters 7, 2014 (2007).
  * Signorell  _et al._ [2016] R. Signorell, M. Goldmann, B. L. Yoder, A. Bodi, E. Chasovskikh, L. Lang, and D. Luckhaus, Nanofocusing, shadowing, and electron mean free path in the photoemission from aerosol droplets, Chem. Phys. Lett. 658, 1 (2016).
  * Watson [1973] W. D. Watson, Photoelectron emission from small spherical particles, JOSA 63, 164 (1973).
  * Toennies and Vilesov [2004] J. P. Toennies and A. F. Vilesov, Superfluid helium droplets: A uniquely cold nanomatrix for molecules and molecular complexes, Angewandte Chemie International Edition 43, 2622 (2004).
  * Henke  _et al._ [1993] B. L. Henke, E. M. Gullikson, and J. C. Davis, X-ray interactions: Photoabsorption, scattering, transmission, and reflection at E= 50-30,000 eV, z= 1-92, Atomic Data and Nuclear Data Tables 54, 181 (1993).
  * Chantler [1995] C. T. Chantler, Theoretical form factor, attenuation, and scattering tabulation for Z= 1–92 from E= 1–10 eV to E= 0.4–1.0 MeV, Journal of Physical and Chemical Reference Data 24, 71 (1995).
  * Harms  _et al._ [1998] J. Harms, J. P. Toennies, and F. Dalfovo, Density of superfluid helium droplets, Phys. Rev. B 58, 3341 (1998).
  * Gomez  _et al._ [2014] L. F. Gomez, K. R. Ferguson, J. P. Cryan, C. Bacellar, R. M. P. Tanyag, C. Jones, S. Schorb, D. Anielski, A. Belkacem, C. Bernando, _et al._ , Shapes and vorticities of superfluid helium nanodroplets, Science 345, 906 (2014).
  * Gomez  _et al._ [2011] L. F. Gomez, E. Loginov, R. Sliter, and A. F. Vilesov, Sizes of large He droplets, J. Chem. Phys. 135, 154201 (2011).
  * Kolatzki  _et al._ [2022] K. Kolatzki, M. L. Schubert, A. Ulmer, T. Möller, D. Rupp, and R. M. P. Tanyag, Micrometer-sized droplets from liquid helium jets at low stagnation pressures, Physics of Fluids 34, 012002 (2022).
  * Slenczka and Toennies [2022] A. Slenczka and J. P. Toennies,  _Molecules in Superfluid Helium Nanodroplets: Spectroscopy, Structure, and Dynamics_ (Springer Nature, 2022).
  * Boatwright  _et al._ [2013] A. Boatwright, C. Feng, D. Spence, E. Latimer, C. Binns, A. M. Ellis, and S. Yang, Helium droplets: a new route to nanoparticles, Faraday discussions 162, 113 (2013).
  * Haberfehlner  _et al._ [2015] G. Haberfehlner, P. Thaler, D. Knez, A. Volk, F. Hofer, W. E. Ernst, and G. Kothleitner, Formation of bimetallic clusters in superfluid helium nanodroplets analysed by atomic resolution electron tomography, Nat. Commun. 6, 8779 (2015).
  * Schiffmann  _et al._ [2020] A. Schiffmann, T. Jauk, D. Knez, H. Fitzek, F. Hofer, F. Lackner, and W. E. Ernst, Helium droplet assisted synthesis of plasmonic Ag@ZnO core@shell nanoparticles, Nano Research 13, 2979 (2020).
  * Messner  _et al._ [2020] R. Messner, W. E. Ernst, and F. Lackner, Shell-isolated Au nanoparticles functionalized with Rhodamine B fluorophores in helium nanodroplets, J. Phys. Chem. Lett. 12, 145 (2020).
  * Radcliffe  _et al._ [2004] P. Radcliffe, A. Przystawik, T. Diederich, T. Döppner, J. Tiggesbäumker, and K.-H. Meiwes-Broer, Excited-state relaxation of Ag8 clusters embedded in helium droplets, Phys. Rev. Lett. 92, 173403 (2004).
  * Loginov  _et al._ [2005] E. Loginov, D. Rossi, and M. Drabbels, Photoelectron spectroscopy of doped helium nanodroplets, Phys. Rev. Lett. 95, 163401 (2005).
  * Kazak  _et al._ [2019] L. Kazak, S. Göde, K.-H. Meiwes-Broer, and J. Tiggesbäumker, Photoelectron spectroscopy on magnesium ensembles in helium nanodroplets, J. Phys. Chem. A 123, 5951 (2019).
  * Ltaief  _et al._ [2020] L. B. Ltaief, M. Shcherbinin, S. Mandal, S. R. Krishnan, R. Richter, T. Pfeifer, and M. Mudrich, Direct inner-shell photoionization of Xe atoms embedded in helium nanodroplets, Journal of Physics B: Atomic, Molecular and Optical Physics 53, 204001 (2020).
  * Ltaief  _et al._ [2021] L. B. Ltaief, M. Shcherbinin, S. Mandal, S. Krishnan, R. Richter, S. Turchini, N. Zema, and M. Mudrich, Photoelectron spectroscopy of coronene molecules embedded in helium nanodroplets, J. Low Temp. Phys. 202, 444 (2021).
  * Dozmorov  _et al._ [2018] N. Dozmorov, A. Baklanov, J. Von Vangerow, F. Stienkemeier, J. Fordyce, and M. Mudrich, Quantum dynamics of Rb atoms desorbing off the surface of He nanodroplets, Phys. Rev. A 98, 043403 (2018).
  * Thaler  _et al._ [2018] B. Thaler, S. Ranftl, P. Heim, S. Cesnik, L. Treiber, R. Meyer, A. W. Hauser, W. E. Ernst, and M. Koch, Femtosecond photoexcitation dynamics inside a quantum solvent, Nat. Commun. 9, 1 (2018).
  * Wang  _et al._ [2008] C. C. Wang, O. Kornilov, O. Gessner, J. H. Kim, D. S. Peterka, and D. M. Neumark, Photoelectron imaging of helium droplets doped with Xe and Kr atoms, J. Phys. Chem. A 112, 9356 (2008).
  * Shcherbinin  _et al._ [2018] M. Shcherbinin, A. LaForge, M. Hanif, R. Richter, and M. Mudrich, Penning ionization of acene molecules by helium nanodroplets, J. Phys. Chem. A 122, 1855 (2018).
  * Mandal  _et al._ [2020] S. Mandal, R. Gopal, M. Shcherbinin, A. D’Elia, H. Srinivas, R. Richter, M. Coreno, B. Bapat, M. Mudrich, S. Krishnan, _et al._ , Penning spectroscopy and structure of acetylene oligomers in He nanodroplets, Phys. Chem. Chem. Phys. 22, 10149 (2020).
  * Treiber  _et al._ [2021] L. Treiber, B. Thaler, P. Heim, M. Stadlhofer, R. Kanya, M. Kitzler-Zeiler, and M. Koch, Observation of laser-assisted electron scattering in superfluid helium, Nat. Commun. 12, 1 (2021).
  * Michiels  _et al._ [2021] R. Michiels, M. Abu-Samha, L. Madsen, M. Binz, U. Bangert, L. Bruder, R. Duim, A. Wituschek, A. LaForge, R. Squibb, _et al._ , Enhancement of above threshold ionization in resonantly excited helium nanodroplets, Physical Review Letters 127, 093201 (2021).
  * Krebs  _et al._ [2022] B. S. Krebs, V. Tulsky, L. Kazak, M. Zabel, D. Bauer, and J. Tiggesbäumker, Phase-of-the-phase electron momentum spectroscopy on single metal atoms in helium nanodroplets, J. Phys. Chem. Lett. 13, 1526 (2022).
  * Treiber  _et al._ [2022] L. Treiber, R. Kanya, M. Kitzler-Zeiler, and M. Koch, Dynamics of above-threshold ionization and laser-assisted electron scattering inside helium nanodroplets, The Journal of Physical Chemistry A 126, 8380 (2022).
  * Zhou  _et al._ [2023] L. Zhou, X. Hu, Y. Peng, J. Qiang, P. Lu, K. Lin, S. Pan, X. Gong, W. Jiang, Z. Jiang, _et al._ , Enhancing strong-field dissociation of H2+ in helium nanodroplets, Phys. Rev. Lett. 130, 033201 (2023).
  * Onn and Silver [1969] D. G. Onn and M. Silver, Attenuation and lifetime of hot electrons injected into liquid helium, Physical Review 183, 295 (1969).
  * Onn and Silver [1971] D. G. Onn and M. Silver, Injection and thermalization of hot electrons in solid, liquid, and gaseous helium at low temperatures, Phys. Rev. A 3, 1773 (1971).
  * Sethumadhavan  _et al._ [2004] B. Sethumadhavan, W. Yao, H. Eguchi, Y. Huang, Y. Kim, R. Lanou, H. Maris, A. Mocharnuk-Macchia, and G. Seidel, Detection of a single electron produced inside bulk superfluid helium, Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 520, 142 (2004).
  * Aitken  _et al._ [2017] F. Aitken, F. Volino, L. G. Mendoza-Luna, K. von Haeften, and J. Eloranta, A thermodynamic model to predict electron mobility in superfluid helium, Physical Chemistry Chemical Physics 19, 15821 (2017).
  * Bastian  _et al._ [2022] B. Bastian, J. D. Asmussen, L. Ben Ltaief, A. Czasch, N. C. Jones, S. V. Hoffmann, H. B. Pedersen, and M. Mudrich, A new endstation for extreme-ultraviolet spectroscopy of free clusters and nanodroplets, Rev. Sci. Instrum. 93, 075110 (2022).
  * Hertel and Hoffmann [2011] N. Hertel and S. V. Hoffmann, Astrid2: A new Danish low-emittance SR source, Synchrotron Radiation News 24, 19 (2011).
  * Dick [2014] B. Dick, Inverting ion images without Abel inversion: maximum entropy reconstruction of velocity maps, Phys. Chem. Chem. Phys. 16, 570 (2014).
  * Blyth  _et al._ [1999] R. Blyth, R. Delaunay, M. Zitnik, J. Krempasky, R. Krempaska, J. Slezak, K. Prince, R. Richter, M. Vondracek, R. Camilloni, _et al._ , The high resolution gas phase photoemission beamline, Elettra, J Electron Spectros Relat Phenomena 101, 959 (1999).
  * Cooper and Zare [1968] J. Cooper and R. N. Zare, Angular distribution of photoelectrons, J. Chem. Phys. 48, 942 (1968).
  * Samson and Stolte [2002] J. Samson and W. C. Stolte, Precision measurements of the total photoionization cross-sections of He, Ne, Ar, Kr, and Xe, Journal of Electron Spectroscopy and Related Phenomena 123, 265 (2002).
  * [52] See supplemental material at [url will be inserted by publisher] for additional information.
  * Buchta  _et al._ [2013] D. Buchta, S. R. Krishnan, N. B. Brauer, M. Drabbels, P. O’Keeffe, M. Devetta, M. Di Fraia, C. Callegari, R. Richter, M. Coreno, _et al._ , Extreme ultraviolet ionization of pure he nanodroplets: Mass-correlated photoelectron imaging, Penning ionization, and electron energy-loss spectra, J. Chem. Phys. 139, 084301 (2013).
  * Adibzadeh and Theodosiou [2005] M. Adibzadeh and C. E. Theodosiou, Elastic electron scattering from inert-gas atoms, Atomic Data and Nuclear Data Tables 91, 8 (2005).
  * Broomall  _et al._ [1976] J. R. Broomall, W. D. Johnson, and D. G. Onn, Density dependence of the electron surface barrier for fluid He3 and He4, Physical Review B 14, 2819 (1976).
  * Henne and Toennies [1998] U. Henne and J. P. Toennies, Electron capture by large helium droplets, J. Chem. Phys. 108, 9327 (1998).
  * Zhang  _et al._ [2008] H. Zhang, D. Rolles, Z. Pešić, J. Bozek, and N. Berrah, Angular distributions of inner-shell photoelectrons from rare-gas clusters, Phys. Rev. A 78, 063201 (2008).
  * Pflüger  _et al._ [2011] T. Pflüger, A. Senftleben, X. Ren, A. Dorn, and J. Ullrich, Observation of multiple scattering in (e, 2 e) experiments on small argon clusters, Phys. Rev. Lett. 107, 223201 (2011).
  * Öhrwall  _et al._ [2003] G. Öhrwall, M. Tchaplyguine, M. Gisselbrecht, M. Lundwall, R. Feifel, T. Rander, J. Schulz, R. Marinho, A. Lindgren, S. Sorensen, _et al._ , Observation of elastic scattering effects on photoelectron angular distributions in free Xe clusters, J. Phys. B: At., Mol. Opt. Phys. 36, 3937 (2003).
  * Rolles  _et al._ [2007] D. Rolles, H. Zhang, Z. Pešić, R. Bilodeau, A. Wills, E. Kukk, B. Rude, G. Ackerman, J. Bozek, R. D. Muiño, _et al._ , Size effects in angle-resolved photoelectron spectroscopy of free rare-gas clusters, Phys. Rev. A 75, 031201 (2007).
  * Goldmann  _et al._ [2015] M. Goldmann, J. Miguel-Sánchez, A. H. West, B. L. Yoder, and R. Signorell, Electron mean free path from angle-dependent photoelectron spectroscopy of aerosol particles, J. Chem. Phys. 142, 224304 (2015).