# Autonomous Quadrotor Flight despite Rotor Failure
with Onboard Vision Sensors: Frames vs. Events

Sihao Sun1, Giovanni Cioffi1, Coen de Visser2, Davide Scaramuzza1 1S.Sun, G.
Cioffi and D. Scaramuzza are with the Robotics and Perception Group,
University of Zurich, Switzerland (http://rpg.ifi.uzh.ch).2C. de Visser is
with Faculty of Aerospace Engineering, Delft University of Technology, 2629 HS
Delft, The Netherlands.

###### Abstract

Fault-tolerant control is crucial for safety-critical systems, such as
quadrotors. State-of-art flight controllers can stabilize and control a
quadrotor even when subjected to the complete loss of a rotor. However, these
methods rely on external sensors, such as GPS or motion capture systems, for
state estimation. To the best of our knowledge, this has not yet been achieved
with only onboard sensors. In this paper, we propose the first algorithm that
combines fault-tolerant control and onboard vision-based state estimation to
achieve position control of a quadrotor subjected to complete failure of one
rotor. Experimental validations show that our approach is able to accurately
control the position of a quadrotor during a motor failure scenario, without
the aid of any external sensors. The primary challenge to vision-based state
estimation stems from the inevitable high-speed yaw rotation (over 20 rad/s)
of the damaged quadrotor, causing motion blur to cameras, which is detrimental
to visual inertial odometry (VIO). We compare two types of visual inputs to
the vision-based state estimation algorithm: standard frames and events.
Experimental results show the advantage of using an event camera especially in
low light environments due to its inherent high dynamic range and high
temporal resolution. We believe that our approach will render autonomous
quadrotors safer in both GPS denied or degraded environments. We release both
our controller and VIO algorithm open source.

###### Index Terms:

Aerial Systems: Perception and Autonomy, Robot Safety, Sensor-based Control,
Event Camera.

## Source code and video

The source code of both our controller and VIO algorithm is available at:
https://github.com/uzh-rpg/fault_tolerant_control

A video of the experiments is available at: https://youtu.be/Ww8u0KH7Ugs

##  I Introduction

Multi-rotor drones have been widely used in many applications, such as
inspection, delivery, surveillance, agriculture, and entertainment. Among
different types of multi-rotor drones, quadrotors are the most popular by
virtue of their simple structure and relatively high aerodynamic efficiency.
However, due to less rotor redundancy, quadrotors are also more vulnerable to
motor failures.

Because safety is always a major concern, which restricts the expansion of the
drone industry, it is crucial to develop methods to prevent quadrotors from
crashing after motor failures. Fault-tolerant flight control of quadrotors is
a feasible solution since only software adaptation is required, which is an
obvious advantage over adding rotor redundancy or parachutes.

Previous works have achieved autonomous flight of a quadrotor subjected to
complete failure of a single rotor [1, 2], and even in high-speed flight
conditions where aerodynamic disturbances are apparent [3, 4]. However, these
methods rely on external sensors, such as GPS or motion capture systems, for
position tracking, which completely eliminate or alleviate the effects of
state estimation errors. To improve quadrotor safety in GPS denied or degraded
environments, we need to resort to fully onboard solutions, such as vision-
based state estimation.

Figure 1: Controlling a quadrotor with complete failure of a rotor causes fast
yaw rotation, over 20 rad/s (top figure). Bottom figures show a standard frame
and events captured by an onboard event camera. Bottom Left: standard frame
with motion blur. Bottom Center: Events only (blue: positive events, red:
negative events). Bottom Right: Event frame generated from events. Blue
circles are detected features, green dots indicate tracked features.

Complete failure of a rotor results in a fast spinning motion ($>20$ rad/s) of
the quadrotor [5]. This high-speed motion brings a significant challenge to
onboard state-estimation methods. First, in vision-based estimators, it causes
motion blur (bottom left plot in Fig. 1). Such motion blur deteriorates
feature detection and tracking and subsequently degrades visual-inertial
odometry (VIO) performance, especially in low-light environments. Secondly, a
large centrifugal acceleration read by the inertial measurement unit (IMU)
often causes large errors in commonly-used attitude estimators. These problems
need to be resolved to achieve autonomous quadrotor flight despite rotor
failure, using only onboard sensors.

###  I-A Contributions

To address the aforementioned problems, we make the following contributions:

  1. 1.

We achieve and demonstrate the first closed-loop flight of a quadrotor
subjected to complete failure of a rotor, using only onboard sensors and
computation. We demonstrate that a damaged quadrotor can both hover as well as
follow a sequence of setpoints.

  2. 2.

We propose a novel state-estimation algorithm combining measurements from an
IMU, a range sensor, and a vision sensor that can be either a standard camera
or an event camera [6]. We show that an event camera becomes advantageous in
low-light environments because the sensor does not suffer from motion blur and
has a very high dynamic range.

  3. 3.

We improve the complementary filter, commonly used for attitude estimation, to
account for the measurement error (up to $1g$) induced by the fast spinning
motion on the accelerometer. We show that this yields significant improvements
in pitch and roll estimates in this high-speed spinning flight condition.

###  I-B Related Work

####  I-B1 Quadrotor Fault-Tolerant control

The first flight controller resilience to complete failure of a single rotor
was proposed by [5] using a feedback linearization approach. The authors
demonstrated that sacrificing the stability in the yaw direction becomes
inevitable in order to keep the full control of pitch, roll, and thrust. As a
consequence, the drone fast spins due to the imbalanced drag torques from
remaining rotors. Following this idea, different approaches were proposed for
this problem, such as PID [7], backstepping [8], robust feedback linearization
[9], and incremental nonlinear dynamic inversion (INDI) [10]. However, these
works were only validated in simulation environments.

The first real-world flight test of a quadrotor with a complete failure of a
rotor was achieved by [11], where a linear quadratic regulator (LQR) was
applied. The authors also proposed the relaxed-hovering solution as a quasi-
equilibrium, where the quadrotor spins about a fixed point in the 3-D space,
with constant body rates, pitch, and roll angles [1]. The authors of [2]
considered the initial spinning phase with varying yaw rate, using a linear
parameter varying controller. As the above controllers did not consider
aerodynamic effects, the INDI approach was applied in [3] and [4] to render
the controller resilient to significant aerodynamic disturbances in high-speed
wind-tunnel flight tests.

####  I-B2 Visual Inertial Odometry

VIO [12, 13] fuses visual and inertial measurements to estimate the 6-DoF pose
of the sensor rig. Recent progress has made VIO algorithms computationally
efficient to be deployed on resource constrained platforms such as quadrotors
[14]. In this work, we are interested in sliding-window optimization-based,
also known as fixed-lag smoothing, VIO estimators. Such methods estimate a
sliding-window of the most recent system states in a nonlinear least-squares
optimization problem. They are normally more accurate than filter-based
methods [15, 16]. Two successful sliding-window optimization-based estimators
are [17, 18]. These estimators minimize a cost function containing visual,
inertial, and marginalization residuals. A limited number of the most recent
system states is kept in the sliding window. Old states are marginalized
together with part of the measurements. In this work, we use a sliding-window
optimization-based approach by virtue of its favorable trade-off between
computational efficiency and estimate accuracy.

Recent works [19, 20] showed that event cameras allow to deploy VIO-based
state estimators in scenarios where standard cameras are not reliable, such as
high dynamic range scenes and high speed motions, which cause large motion
blur. In [19], an event-based algorithm was presented, which is able to
estimate the pose of the camera and build a semi-dense 3D map when the camera
undergoes fast motion and operates in challenging illumination conditions. In
[20], both standard and event cameras were combined into a sliding-window-
based VIO pipeline. The authors showed that leveraging the complementary
properties of the standard and event cameras leads to large accuracy
improvements with respect to the standard frame-only or event-only algorithms.

###  I-C Notation

Throughout the paper, we use bold lowercase letter to represent vector
variables and bold capital letters for matrices; otherwise, they are scalars.
Superscript $B$ indicates that the vector is in the body frame, and $C$ stands
for the camera frame. By default, a vector without superscript is represented
in the inertial frame. A 3-D vector with subscript ’$\times$’ means its skew-
symmetric matrix for cross product, such that
$\boldsymbol{a}_{\times}\boldsymbol{b}=\boldsymbol{a}\times\boldsymbol{b}$ for
any $\boldsymbol{a}\in\mathbb{R}^{3}$. $\mathrm{diag}(a,~{}b)$ represents
diagonal matrix with $a$ and $b$ as diagonal elements.

###  I-D Organization

This paper is organized as follows: We first introduce the fault-tolerant
flight controller in Section II. Then Section III details the state estimator,
including the VIO algorithm and the improved complementary filter. The
evaluation and closed-loop flight results are given in Section IV. Afterwards
the conclusions are drawn in Section V.

##  II Flight Controller Design

###  II-A Quadrotor Model

####  II-A1 Quadrotor Dynamic Model

The translational and rotation dynamic equations of a quadrotor are:

$m\ddot{\boldsymbol{\xi}}=m\boldsymbol{g}+\boldsymbol{R}_{\mathrm{IB}}\boldsymbol{f}^{B},$
(1)
$\boldsymbol{I}_{v}^{B}\dot{\boldsymbol{\omega}}^{B}+\boldsymbol{\omega}^{B}\times\boldsymbol{I}_{v}^{B}\boldsymbol{\omega}^{B}=\boldsymbol{m}^{B}+\boldsymbol{m}_{g}^{B},$
(2)

where $\boldsymbol{\xi}=[x,~{}y,~{}z]^{T}$ indicates the center of gravity
(c.g.) location of the drone in the inertial frame.
$\boldsymbol{R}_{\mathrm{IB}}\in$ SO(3) is the rotational matrix representing
the quadrotor attitude. The angular velocity of the body frame w.r.t the
inertial frame is expressed as
$\boldsymbol{\omega}^{B}=[\omega_{x},~{}\omega_{y},~{}\omega_{z}]^{T}$. The
vehicle mass and inertia are denoted by $m$ and $\boldsymbol{I}_{v}^{B}$
respectively, and $\boldsymbol{g}=[0,~{}0,~{}g]^{T}$ denotes the gravity
vector, where $g$ is the local gravitational constant.
$\boldsymbol{m}_{g}^{B}$ is the propeller gyroscopic moments.
$\boldsymbol{f}^{B}=[0,~{}0,~{}T]^{T}$ is the external force vector projecting
on the body frame.

The collective thrust $T$ and control torques
$\boldsymbol{m}^{B}=[\tau_{x},~{}\tau_{y},~{}\tau_{z}]^{T}$ are generated by
rotors from the control allocation model:

$\left[T,~{}\tau_{x},~{}\tau_{y},~{}\tau_{z}\right]^{T}=\boldsymbol{G}\boldsymbol{u},$
(3)

where $\boldsymbol{u}\in\mathbb{R}^{4}$ is the control input vector containing
thrusts generated by each rotor. $\boldsymbol{G}\in\mathbb{R}^{4\times 4}$ is
the control effective matrix projecting individual thrust of each rotor to the
collective thrust and torques.

####  II-A2 Reduced Control Allocation Model

After the occurrence of the complete failure of the $i$-th rotor, where
$i\in\\{1,~{}2,~{}3,~{}4\\}$, a quadrotor cannot maintain a stationary
condition [5]. It is a common strategy to stop controlling quadrotor heading
angle leading to high-speed yaw rotation. In this case, we remove the last row
and the $i$-th column of $\boldsymbol{G}$, and obtain a reduced control
effective matrix $\tilde{\boldsymbol{G}}\in\mathbb{R}^{3\times 3}$. The
control input $\boldsymbol{u}$ is also reduced to
$\tilde{\boldsymbol{u}}\in\mathbb{R}^{3}$ where the $i$-th element is removed.
Then, we obtain the reduced control allocation model

$\left[T,~{}\tau_{x},~{}\tau_{y}\right]^{T}=\tilde{\boldsymbol{G}}\tilde{\boldsymbol{u}}.$
(4)

####  II-A3 Reduced Attitude Kinematic Model

Since the heading is not being controlled, instead of a full attitude
kinematic model, we use a reduced attitude kinematic model [3] to design the
flight controller:

$\dot{\boldsymbol{n}}^{B}=\boldsymbol{n}^{B}_{\times}\boldsymbol{\omega}^{B}+\boldsymbol{R}_{\mathrm{IB}}^{T}\dot{\boldsymbol{n}},$
(5)

where $\boldsymbol{n}$ is an arbitrary unit vector and
$\boldsymbol{n}^{B}=[n_{x},~{}n_{y},~{}n_{z}]^{T}$.

###  II-B Fault Tolerant Controller

Given $\boldsymbol{a}_{\mathrm{des}}$ the reference acceleration from a PD
position controller [11], we can obtain the desired thrust orientation as
$\boldsymbol{n}=(\boldsymbol{a}_{\mathrm{des}}-\boldsymbol{g})/||(\boldsymbol{a}_{\mathrm{des}}-\boldsymbol{g})||$.
The reduced attitude controller aims at aligning $\boldsymbol{n}$ with a body
frame fixed vector
$\boldsymbol{n}_{\mathrm{fix}}^{B}=[\bar{n}_{x},~{}\bar{n}_{y},~{}\bar{n}_{z}]^{T}$,
where $\bar{n}_{x},~{}\bar{n}_{y},~{}\bar{n}_{z}$ are constants [21]. A
straightforward option is to select
$\boldsymbol{n}_{\mathrm{fix}}^{B}=[0,~{}0,~{}1]^{T}$, namely the thrust
direction, to align with $\boldsymbol{n}$. However, we keep a slight angle
(around 15 deg) between $\boldsymbol{n}_{\mathrm{fix}}^{B}$ and
$\boldsymbol{n}$. This reduces the spinning rate and causes wobbling motion of
the drone. We refer the reader to [11] for more details.

To align $\boldsymbol{n}_{\mathrm{fix}}$ with $\boldsymbol{n}$, we use a
nonlinear dynamic inversion (NDI) approach [22]. We define the control
variable as

$\boldsymbol{y}=\left[\begin{array}[]{c}n_{x}-\bar{n}_{x}\\\
n_{y}-\bar{n}_{y}\end{array}\right]=\left[\begin{array}[]{c}y_{1}\\\
y_{2}\end{array}\right].$ (6)

Then we need to design the control input $\tilde{\boldsymbol{u}}$ leading to a
stable second-order closed-loop dynamic of $\boldsymbol{y}$:

$\ddot{\boldsymbol{y}}(\tilde{\boldsymbol{u}})=-\mathrm{diag}(k_{p},~{}k_{p})\boldsymbol{y}-\mathrm{diag}(k_{d},~{}k_{d})\dot{\boldsymbol{y}},$
(7)

where $k_{p}$ and $k_{d}$ are proportional and derivative gains. An integral
term may be added to (7) as well to address slight model mismatch. To simplify
the derivation of $\tilde{\boldsymbol{u}}$, we assume that $\omega_{z}$ and
$n_{z}$ are constant after rotor failure. Similarly to [11], we assume a
slowly changing $\boldsymbol{n}$ and $\dot{\boldsymbol{n}}=\boldsymbol{0}$.
The quadrotor inertia matrix $\boldsymbol{I}_{v}^{B}$ is approximated by
$\mathrm{diag}(I_{x},~{}I_{y},~{}I_{z})$. Propeller gyroscopic moment
$\boldsymbol{m}_{g}^{B}$ is also negligible compared with rotor thrust
generated torques, thus we omit it in the controller design. We validate these
assumptions in the real flights. Then, we substitute (2)(5)(6) into (7),
yielding expressions of roll and pitch torque commands:

$\begin{array}[]{l}\left[\tau_{x,\mathrm{cmd}},~{}\tau_{y,\mathrm{cmd}}\right]^{T}=\\\
\\\
\left[\begin{array}[]{c}\begin{array}[]{l}\left[k_{p}y_{2}+k_{d}(n_{x}\omega_{z}-n_{z}\omega_{x})+(n_{y}\omega_{z}-n_{z}\omega_{x})\omega_{z}\right]I_{x}/n_{z}\\\
+I_{z}\omega_{y}\omega_{z}-I_{x}\omega_{y}\omega_{z}\end{array}\\\
\begin{array}[]{l}-\left[k_{p}y_{1}+k_{d}(n_{z}\omega_{y}-n_{y}\omega_{z})+(n_{x}\omega_{z}-n_{z}\omega_{y})\omega_{z}\right]I_{y}/n_{z}\\\
+I_{x}\omega_{x}\omega_{z}-I_{z}\omega_{x}\omega_{z}\end{array}\\\
\end{array}\right]\end{array}.$ (8)

The thrust command $T_{\mathrm{cmd}}$ can be obtained from the desired
vertical acceleration $\boldsymbol{a}_{z,\mathrm{des}}$ and (1), yielding

$T_{\mathrm{cmd}}=m(\boldsymbol{a}_{z,\mathrm{des}}+g)/\cos{\phi}\cos{\theta},$
(9)

where $\theta$ and $\phi$ are pitch and roll angles of the quadrotor.

Finally, substituting (8) and (9) into (4), we can get the control input
$\tilde{\boldsymbol{u}}$, namely thrust commands of the three remaining rotors

$\tilde{\boldsymbol{u}}=\tilde{\boldsymbol{G}}^{-1}\left[T_{\mathrm{cmd}},~{}\tau_{x,\mathrm{cmd}},~{}\tau_{y,\mathrm{cmd}}\right]^{T}.$
(10)

Note that this controller is modified from that in [4] to avoid using motor
speed measurements unobtainable for some platforms. As a consequence, this
controller is less robust against model mismatch caused by, e.g., high-speed
induced aerodynamic effects. If the rotor speeds are measurable, we refer
readers to use the controller proposed in [4] to improve the resilience
against aerodynamic disturbances.

The proposed method also assumes that the motor failure is already known by
the controller, which can be easily detected by methods such as monitoring the
motor current [23], or using a Kalman filter [24].

##  III Onboard State Estimation

Figure 2: General diagram of the onboard state estimator and the fault-
tolerant controller.

To achieve autonomous flight with rotor failure, the state estimator provides
orientation and position information using only onboard sensors, including an
IMU, a downward looking range sensor, and a downward looking camera. The
camera can be either a standard camera or an event camera. The block diagram
of our system is given in Fig. 2. A range-sensor-aided monocular VIO algorithm
provides pose estimates of the camera at 50 Hz. These estimates are fused with
the IMU from a low-level flight control board located at the center of
gravity, using a Kalman filter and a complementary filter, to provide
position, velocity, and orientation estimates at 200 Hz for the fault-tolerant
flight controller. A rotation compensated complementary filter is proposed for
orientation estimation instead of directly using the orientation from the VIO.
This can improve the robustness of the algorithm in case of loss of feature
tracks.

###  III-A Visual Inertial Odometry

Figure 3: Diagram of the visual-inertial odometry (either event based or frame
based).

The proposed VIO provides position and yaw estimations. It can use either
standard frames or events as visual inputs. A block diagram of the algorithm
is given in Fig. 3.

####  III-A1 Front-end

If events are selected as visual input, we first of all generate synthetic
event frames [25]. Each event frame $I_{k}(\boldsymbol{x})$ is aggregated from
events from a spatio-temporal window $W_{k}$:

$I_{k}(\boldsymbol{x})=\sum_{e_{j}\in
W_{k}}p_{j}\delta(\boldsymbol{x}-\boldsymbol{x}{{}^{\prime}}_{j}),$ (11)

where function $\delta(\cdot)$ is the Kronecker delta, $p_{j}$ is the polarity
of a certain event represented by $e_{j}$, $\boldsymbol{x}^{\prime}_{j}$ is
the corrected event position considering the motion of the camera:

$\boldsymbol{x}{{}^{\prime}}_{j}=\pi\left(T_{t_{k},t_{j}}\left(Z(\boldsymbol{x}_{i})\pi^{-1}(\boldsymbol{x}_{i})\right)\right).$
(12)

where $\pi(\cdot)$ is the camera projection model, $T_{t_{k},t_{j}}$ is the
transformation of camera pose between $t_{k}$ and $t_{j}$,
$Z(\boldsymbol{x}_{i})$ is the scene depth approximated by the range sensor.

As the rotation of the damaged quadrotor in this time window is more dominant
than the linear motion, we use a pure rotation transformation to approximate
$T_{t_{k},t_{k-1}}$, which is generated by integrating angular rate
measurements from the gyroscope. Then $T_{t_{k},t_{j}}$ is approximated by a
linear interpolation
$T_{t_{k},t_{j}}=T_{t_{k},t_{k-1}}(t_{j}-t_{k-1})/(t_{k}-t_{k-1})$.

Then we use a FAST feature detector [26] and Lucas-Kanade tracker [27] to
detect and track features. If a feature has been tracked over 3 consecutive
frames, it is determined as persistent and is triangulated. The corresponding
landmark is added to the map. These settings are the same as applied in [20]
and [25].

If standard frames are selected as visual input, we simply replace the
synthetic event frames in the above procedure.

####  III-A2 Range-Based Landmark Triangulation

Since the damaged quadrotor motion is mostly rotation, triangulating landmarks
based on the disparity is inaccurate. For this reason, we use a downward range
sensor to detect the range of the camera to the ground, where most features
are detected. We also assume that all landmarks lie within the ground plane.
For the $j$-th landmark whose position in the inertial coordinate frame is
defined as $\boldsymbol{p}_{j}$ we have

$\begin{split}\lambda\left[\begin{array}[]{c}u\\\ v\\\
1\end{array}\right]=\boldsymbol{K}\boldsymbol{R}_{\mathrm{CI}}\left(\boldsymbol{p}_{j}-\boldsymbol{p}_{c}\right),\\\
{p}_{c,z}-{p}_{j,z}=\hat{h}=r\cos\theta\cos\phi,\\\ \end{split}$ (13)

where $u$, $v$ are observations of the landmark in the last (event) frame,
$\boldsymbol{p}_{c}$ is the position of the camera in the inertial coordinate
frame, $\boldsymbol{K}$ is the camera calibration matrix,
$\boldsymbol{R}_{\mathrm{CI}}$ is the rotation matrix from camera frame to the
inertial frame, $\hat{h}$ is the height estimate, $r$ is the range measurement
from the range sensor.

As $\boldsymbol{R}_{\mathrm{CI}}$ and $\boldsymbol{p}_{c}$ are obtained from
the backend optimization, $\phi$ and $\theta$ are estimated from the
complementary filter, we can subsequently solve $\boldsymbol{p}_{j}$ from
(13). The position estimates of triangulated landmarks are then used as
initial guess for the nonlinear optimization problem in the backend.

####  III-A3 Back-end

We use a keyframe-based fixed-lag smoother inspired by [17] to estimate the
pose of the camera. The optimization cost function is formulated as

$\begin{split}J(\boldsymbol{X})&=\sum^{K}_{k=1}\sum_{j\in
J(k)}||\boldsymbol{e}^{j,k}_{v}||^{2}_{\boldsymbol{W}_{v}^{j,k}}+\sum^{K-1}_{k=1}||\boldsymbol{e}^{k}_{i}||^{2}_{\boldsymbol{W}_{i}^{k}}\\\
&+\sum^{K}_{k=1}\sum_{j\in
J(k)}w_{h}^{j,k}({p}_{c,z}-\hat{h}-{p}_{j,z})^{2},\end{split}$ (14)

where $k$ is the frame index, $K$ denotes number of frame in the sliding
window, $j$ is the landmark index, $J(k)$ is the set containing all the
visible landmarks from the frame $k$. The first and second term in (14)
represent reprojection error and inertial error respectively. The optimization
variables are the states of the $K$ frames in the sliding window, which are
represented by $\boldsymbol{X}$ and include position, velocity, orientation,
and IMU biases.

Differently from the optimization-based back-end in [17], we add the third
term in the cost function (14), where $w_{h}^{j,k}$ is the weight. It forces
the vertical differences between the position of the camera and the observed
landmark to be equal to the height estimate $\hat{h}$ from the range sensor.
By this means we add additional scale information from the range sensor while
the IMU based scale information becomes less reliable in this fast rotational
motion dominated task.

The optimization is run when a new (event) frame is generated. To improve
computation efficiency, we do not perform marginalization and discard the
states and measurements outside the sliding window. We use the Google Ceres
Solver [28] to solve this nonlinear least square problem.

###  III-B Rotation Corrected Complementary Filter

The complementary filter is widely used to provide attitude estimates of a
quadrotor. It has a major advantage that the pitch and roll are estimated only
from IMU measurements, thus it is robust to failure of other sensors. The
accelerometer measurement is expressed as:

$\boldsymbol{a}_{\mathrm{IMU}}=\boldsymbol{a}^{B}-\boldsymbol{g}^{B}+\boldsymbol{\omega}^{B}\times(\boldsymbol{\omega}^{B}\times\boldsymbol{d}_{\mathrm{ba}}^{B})+\dot{\boldsymbol{\omega}}^{B}\times\boldsymbol{d}_{\mathrm{ba}}^{B}+\boldsymbol{w}_{\mathrm{acc}}+\boldsymbol{b}_{\mathrm{acc}}~{},$
(15)

where $\boldsymbol{a}^{B}$ is the acceleration of the center of gravity,
$\boldsymbol{w}_{\mathrm{acc}}$ and $\boldsymbol{b}_{\mathrm{acc}}$ are the
measurement noise and bias respectively. $\boldsymbol{d}_{\mathrm{ba}}^{B}$ is
the displacement from the center of gravity to the accelerometer.

A standard complementary filter assumes that the accelerometer measures the
negative gravitational vector expressed the body frame in a long-term period.
In other words, it neglects other terms in (15) except $\boldsymbol{g}^{B}$.
This works well when a quadrotor spends significant periods of time in hover
or slow forward flight [29]. However, when the quadrotor fast spins at a near
constant body rate $\boldsymbol{\omega}^{B}$ and enter the relaxed-hovering
condition [1], $\boldsymbol{a}^{B}$ becomes a constant non-zero centripetal
acceleration, and the displacement induced term
$\boldsymbol{\omega}^{B}\times(\boldsymbol{\omega}^{B}\times\boldsymbol{d}_{\mathrm{ba}}^{B})$
also becomes non-negligible. These two terms need to be considered in the
filter, yielding the rotation corrected complementary filter.

We estimate acceleration $\boldsymbol{a}^{B}$ by assuming the quadrotor stays
in the relaxed-hovering condition in a long-term period. According to Fig. 4,
we can obtain the estimated $\boldsymbol{a}^{B}$ as

$\hat{\boldsymbol{a}}^{B}=\left[-\frac{\omega_{x}}{||\boldsymbol{\omega}||}g,~{}-\frac{\omega_{y}}{||\boldsymbol{\omega}||}g,~{}g\tan{\alpha}\sin{\alpha}\right]^{T},$
(16)

where $\alpha=\arccos(\cos{\theta}\cos{\phi})$. Note that (16) is valid only
at relaxed-hovering condition where quadrotor fast spins. Therefore, we still
assume a zero $\hat{\boldsymbol{a}}^{B}$ vector when
$|\omega_{z}|<\bar{\omega}$, where $\bar{\omega}$ is a positive threshold. We
use $\bar{\omega}=10$ rad/s in our experiments. Knowing $\boldsymbol{a}^{B}$,
we can subsequently estimate the displacement $\boldsymbol{d}_{\mathrm{ba}}$
from (15) by a least-square estimator, using real flight data.

Fig. 5 presents the diagram of the proposed complementary filter, where the
rotation compensation block is marked in yellow. Since there is no
magnetometer used in our platform, we adopt the yaw angle from the VIO to fuse
the gyroscope measurement and to obtain the yaw estimate. Finally, we can
estimate the full attitude from this rotation corrected complementary filter.

Figure 4: In the relaxed-hovering condition, the acceleration projection on
the body frame ($\boldsymbol{a}^{B}$) is constant. Figure 5: Diagram of the
rotation corrected complementary filter.

##  IV Experiments

###  IV-A Hardware Descriptions

Figure 6: Photo of a quadrotor flying with three rotors, where an event camera
is used for state estimation.

As Fig. 6 shows, the tested quadrotor is built with a carbon fiber frame and
3D printed parts. It is powered by four 2306-2400KV motors with 5-inch
propellers. The state estimation and the control algorithm are run on a Nvidia
Jetson TX2, which contains a quad-core 2.0 Hz CPU and a dual-core 2.5 Hz CPU
running Ubuntu 18.04 and ROS [30]. The motor thrust commands from the control
algorithm are sent to motors through a Radix FC flight control board, which
runs a self-built firmware that also sends the IMU measurements to the TX2 at
200 Hz. We used TeraRanger One, a LED time-of-flight range sensor, to measure
the distance to the ground. Both standard and event cameras are facing
downward. They both use a 110∘ field-of-view lens. For the event camera, we
use an Inivation DAVIS-346 with a resolution of $346\times 240$ pixels. For
the standard camera, we use a mvBlueFox-220w [31] with a resolution of
$376\times 240$ pixels, chosen intentionally to be close to that of the event
camera to enable a fair comparison. It is worth noting that the maximum gain
(12 dB) of the mvBlueFox-200w camera is used to minimize the required exposure
time, which is found essential in reducing the motion blur in the standard
frames.

###  IV-B Validation of the Rotation Corrected Complementary Filter

We use the flight data to evaluate the performance of the proposed
complementary filter, against the one without rotation motion considered. Fig.
7 shows that the roll error of the standard complementary filter became large
as the quadrotor started spinning at around 5 s. By contrast, the rotation
corrected complementary filter could well estimate the pitch and roll angles
despite the over 20 rad/s spinning rate. Bottom plot of Fig. 7 explains the
large error of the roll estimates. As standard complementary filter assumes
that the accelerometer measures the negative gravitational vector,
$\boldsymbol{g}^{B}$ should align with $\boldsymbol{a}_{\mathrm{IMU},x}$.
However, this assumption becomes invalid when considerable centripetal
acceleration appears, which leads to significant bias of the accelerometer
measurement.

Figure 7: Top two plots: Pitch and roll angle estimates of the proposed
rotation corrected complementary filter and a standard complementary filter,
compared with the ground truth measured by the motion capture system. Bottom
plot: comparison between the gravity projection on the body frame and the
accelerometer measurement.

###  IV-C Closed-loop Flight Validation

(a) Closed-loop flight trajectory using standard frames.

(b) Closed-loop flight trajectory using events.

Figure 8: Top view of the closed-loop flight trajectories. Ground-truth from
the motion capture system (blue), estimated trajectory (green), and the
reference trajectory (red) including 9 setpoints.

We conducted setpoint tracking tasks in the closed-loop flight experiment to
validate the entire algorithm, including the vision-based state estimator and
the fault-tolerant flight controller. During the test, the quadrotor took off
with four rotors. The VIO was initialized while the drone was in hovering.
Then, we switched off one rotor and the fault-tolerant flight controller
started controlling the quadrotor. As shown in Fig. 8(a), nine setpoints
formed into a square were given to the flight controller in steps of 5
seconds. The damaged quadrotor then flew a square trajectory by tracking these
setpoints.

Two different tests were performed where standard frames and events were
respectively used as visual input to the state estimator. Fig. 8(a) shows the
closed-loop flight result using standard frames, where the estimated
trajectory from the VIO in the inertial frame, the ground truth trajectory
measured by the motion capture system, and the reference trajectory are
presented. The difference between the real trajectory and the reference is
caused by the position estimation error and the controller tracking error.
Although the tracking performance is not perfect, it is sufficient for
controlling a damaged quadrotor to a safe area for landing. Similarly, Fig.
8(b) shows another test where events are used as visual input to the state
estimator. Both tests were conducted in a well-illuminated environment (500
lux), which is a bright indoor office lighting condition [32].

###  IV-D Comparison between Frames and Events

TABLE I: Position tracking accuracy (RMSE) with state estimators using
standard frames or events in different light conditions. For standard frames,
gains of the camera are set as 12 dB. Env lux: environment illuminance. Cam
lux: illuminance at the camera lens. The left column shows photos of the test
environment.

In this section, we test the algorithm in different environment’s lighting
conditions, and compare between using frames and events as visual input. In
these tests, we let the damaged quadrotor track a single setpoint (i.e.,
hovering). Then, we measure the root mean square error (RMSE) of the closed-
loop position tracking to evaluate the performance of the entire algorithm.
The exposure times of the standard camera are changed according to the
environment brightness to capture frames with sufficient intensity for
detecting and tracking features. For the event camera, we observe that the
number of events generated in a fixed time window is smaller in a darker
environment. Hence, we accordingly reduce the number of events needed to
construct an event frame in low-light conditions.

Table LABEL:tab:illuminance_comparison reports the position tracking RMSE when
using standard frames or events in different lighting conditions. As can be
observed, when the environment illuminance is around 500 lux, both frames and
events can accomplish the task with similar tracking error. However, with
standard frames as visual input, the tracking error doubles as the illuminance
drops to 100 lux, and the damaged quadrotor crashes immediately when the
illuminance gets lower than 100 lux. By contrast, with events as visual input,
the damaged quadrotor can even fly when the illuminance is decreased to 10
lux. These comparisons clearly show the advantage of using an event camera for
state estimation in low-light conditions.

Fig. 9 presents the standard frames and the event frames in a bright (500 lux)
and a dark (50 lux) indoor environment, respectively. When the environment
illuminance is 50 lux, a relatively long exposure time (12 ms) of the standard
camera is required. Hence, the standard frames experience significant motion
blur (Fig. 9c) owning to the quadrotor fast rotational motion caused by the
motor failure. Although more than 20 features are detected from this blurry
image, few of them are successfully tracked (i.e., persistent features) and
added to the map, causing failure of the standard frame-based VIO. By
contrast, the event frames are sharp enough for feature detection and tracking
in both bright and dark conditions.

Figure 9: Standard and event frames, including features (light blue circle are
detected features, green dots are persistent features), in a bright (500 lux)
and a dark (50 lux) environment. (a) Standard frame in the bright environment
with 2 ms exposure time. (b) Event frame in the bright environment. (c)
Standard frame in the dark environment with 12 ms exposure time. (d) Event
frame in the dark environment.

###  IV-E Outdoor Flight Test

Figure 10: Outdoor flight to validate the proposed fault-tolerant flight
solution. Left: snapshot of the qudarotor flying with only three propeller.
Right: top view of the forward-backward flight trajectory given by the state
estimator.

Finally, we validate the proposed algorithm in an outdoor environment with
natural light and textures. Fig. 10 shows the snapshot of the flying
quadrotor, and the top view of the flight trajectory from the state estimator.
The quadrotor was commanded to conduct forward flight for 4 meters, and then
return to the origin. The entire flight can be found in the supplementary
video. In this flight, the environment illuminance was 2000 lux. According to
Table LABEL:tab:illuminance_comparison, both standard frames and events are
reliable in such bright conditions. Hence, a standard camera was used in this
flight.

##  V Conclusions

In this work, to the best of our knowledge we achieved the first autonomous
flight of a quadrotor despite loss of a single rotor, using only onboard
sensors. A new state estimation pipeline was proposed, including a rotation
corrected complementary filter and a VIO algorithm aided by a range sensor.
Despite the fast spinning motion of the damaged quadrotor, we demonstrated
that the proposed method can provide reliable state estimates to perform
hovering flights and setpoint-tracking tasks with only onboard sensors.

Comparisons were made between different visual inputs to the proposed
algorithm: standard frames and events. In a well-illuminated environment, we
demonstrated that the algorithms using both forms of visual input can provide
sufficiently accurate state estimates. However, in a relatively low-light
environment with illuminance lower than 100 lux, the standard frames were
affected by significant motion blur due to the fast rotation and the long
exposure time required. By contrast, the event-based algorithm could stand
closed-loop tests in a much darker environment (10 lux).

Finally, we conducted outdoor flight tests to validate the proposed method in
realistic conditions, with natural light and texture.

We believe that the this work can significantly improve quadrotor flight
safety in both GPS denied or degraded environments.

## ACKNOWLEDGMENT

We appreciate valuable discussions and suggestions from Zichao Zhang, Henri
Rebecq, and Philipp Föhn. We also appreciate the help from Thomas Längle,
Manuel Sutter, Roberto Tazzari, Tobias Büchli, Yunlong Song, Daniel Gehrig,
and Elia Kaufmann.

## References

  * [1] M. W. Mueller and R. D’Andrea, “Relaxed hover solutions for multicopters: Application to algorithmic redundancy and novel vehicles,” Int. J. Robot. Research, vol. 35, no. 8, pp. 873–889, 2016.
  * [2] J. Stephan, L. Schmitt, and W. Fichter, “Linear parameter-varying control for quadrotors in case of complete actuator loss,” Journal of Guidance, Control, and Dynamics, vol. 41, no. 10, pp. 2232–2246, 2018.
  * [3] S. Sun, L. Sijbers, X. Wang, and C. de Visser, “High-Speed Flight of Quadrotor Despite Loss of Single Rotor,” IEEE Robot. Autom. Lett. (RA-L), vol. 3, no. 4, pp. 3201–3207, 2018.
  * [4] S. Sun, X. Wang, Q. Chu, and C. d. Visser, “Incremental nonlinear fault-tolerant control of a quadrotor with complete loss of two opposing rotors,” IEEE Trans. Robot., pp. 1–15, 2020.
  * [5] A. Freddi, A. Lanzon, and S. Longhi, “A feedback linearization approach to fault tolerance in quadrotor vehicles,” IFAC proceedings volumes, vol. 44, no. 1, pp. 5413–5418, 2011.
  * [6] G. Gallego, T. Delbruck, G. M. Orchard, C. Bartolozzi, B. Taba, A. Censi, S. Leutenegger, A. Davison, J. Conradt, K. Daniilidis, and D. Scaramuzza, “Event-based vision: A survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1–1, 2020.
  * [7] V. Lippiello, F. Ruggiero, and D. Serra, “Emergency landing for a quadrotor in case of a propeller failure: A backstepping approach,” in IEEE/RSJ Int. Conf. Intell. Robot. Syst. (IROS), pp. 4782–4788, 2014.
  * [8] V. Lippiello, F. Ruggiero, and D. Serra, “Emergency landing for a quadrotor in case of a propeller failure: A PID Based Approach,” in IEEE Intern. Symp. on Safety, Security, and Rescue Robot., pp. 4782–4788, 2014.
  * [9] A. Lanzon, A. Freddi, and S. Longhi, “Flight Control of a Quadrotor Vehicle Subsequent to a Rotor Failure,” Journal of Guidance, Control, and Dynamics, vol. 37, no. 2, pp. 580–591, 2014.
  * [10] P. Lu and E.-J. van Kampen, “Active Fault-Tolerant Control for Quadrotors subjected to a Complete Rotor Failure,” in IEEE/RSJ Int. Conf. Intell. Robot. Syst. (IROS), 2015.
  * [11] M. W. Mueller and R. D’Andrea, “Stability and control of a quadrocopter despite the complete loss of one, two, or three propellers,” in IEEE Int. Conf. Robot. Autom. (ICRA), 2014.
  * [12] G. Huang, “Visual-inertial navigation: A concise review,” in IEEE Int. Conf. Robot. Autom. (ICRA), 2019.
  * [13] D. Scaramuzza and Z. Zhang, “Visual-inertial odometry of aerial robots,” Encyclopedia of Robotics, 2019.
  * [14] J. Delmerico and D. Scaramuzza, “A benchmark comparison of monocular visual-inertial odometry algorithms for flying robots,” in IEEE Int. Conf. Robot. Autom. (ICRA), 2018.
  * [15] H. Strasdat, J. M. Montiel, and A. J. Davison, “Visual slam: why filter?,” Image and Vision Computing, vol. 30, no. 2, pp. 65–77, 2012.
  * [16] J. Delmerico and D. Scaramuzza, “A benchmark comparison of monocular visual-inertial odometry algorithms for flying robots,” in IEEE Int. Conf. Robot. Autom. (ICRA), pp. 2502–2509, 2018.
  * [17] S. Leutenegger, S. Lynen, M. Bosse, R. Siegwart, and P. Furgale, “Keyframe-based visual-inertial odometry using nonlinear optimization,” Int. J. Robot. Research, vol. 34, no. 3, pp. 314–334, 2015.
  * [18] T. Qin, P. Li, and S. Shen, “Vins-mono: A robust and versatile monocular visual-inertial state estimator,” IEEE Trans. Robot., vol. 34, no. 4, pp. 1004–1020, 2018.
  * [19] H. Rebecq, T. Horstschäfer, G. Gallego, and D. Scaramuzza, “Evo: A geometric approach to event-based 6-dof parallel tracking and mapping in real time,” IEEE Robot. Autom. Lett. (RA-L), vol. 2, no. 2, pp. 593–600, 2016\.
  * [20] A. R. Vidal, H. Rebecq, T. Horstschäfer, and D. Scaramuzza, “Ultimate slam? combining events, images, and imu for robust visual slam in hdr and high-speed scenarios,” IEEE Robot. Autom. Lett. (RA-L), vol. 3, no. 2, pp. 994–1001, 2018.
  * [21] N. A. Chaturvedi, A. K. Sanyal, and N. H. McClamroch, “Rigid-body attitude control,” IEEE Control Systems Magazine, vol. 31, no. 3, pp. 30–51, 2011\.
  * [22] R. Da Costa, Q. Chu, and J. Mulder, “Reentry flight controller design using nonlinear dynamic inversion,” Journal of Spacecraft and Rockets, vol. 40, no. 1, pp. 64–71, 2003.
  * [23] O. Moseler and R. Isermann, “Application of model-based fault detection to a brushless dc motor,” IEEE Transactions on Industrial Electronics, vol. 47, no. 5, pp. 1015–1020, 2000.
  * [24] M. H. Amoozgar, A. Chamseddine, and Y. Zhang, “Experimental test of a two-stage kalman filter for actuator fault detection and diagnosis of an unmanned quadrotor helicopter,” Journal of Intelligent & Robotic Systems, vol. 70, no. 1-4, pp. 107–117, 2013.
  * [25] H. Rebecq, T. Horstschaefer, and D. Scaramuzza, “Real-time visual-inertial odometry for event cameras using keyframe-based nonlinear optimization,” British Machine Vision Conf. (BMVC), 2017.
  * [26] E. Rosten and T. Drummond, “Machine learning for high-speed corner detection,” in European Conf. on Comp. Vis. (ECCV), pp. 430–443, Springer, 2006.
  * [27] B. D. Lucas, T. Kanade, et al., “An iterative image registration technique with an application to stereo vision,” 1981.
  * [28] N. S. S. Agarwal, “Ceres solver.” http://ceres-solver.org/.  Accessed: 2020-10-14.
  * [29] R. Mahony, V. Kumar, and P. Corke, “Multirotor aerial vehicles: Modeling, estimation, and control of quadrotor,” IEEE Robotics and Automation magazine, vol. 19, no. 3, pp. 20–32, 2012.
  * [30] M. Quigley, K. Conley, B. Gerkey, J. Faust, T. Foote, J. Leibs, R. Wheeler, and A. Y. Ng, “Ros: an open-source robot operating system,” in ICRA workshop on open source software, vol. 3, p. 5, Kobe, Japan, 2009.
  * [31] “Matrix vision mvbluefox camera.” https://www.matrix-vision.com/USB2.0-industrial-camera-mvbluefox.html.  Accessed: 2020-12-19.
  * [32] “Lux-wikipedia.” https://en.wikipedia.org/wiki/Lux.  Accessed: 2020-10-14.


# Batch Monte Carlo Tree Search
††thanks: Warm thanks to Rémi Coulom who told me he was simulating sequential
PUCT in his implementation of Batch PUCT. This work was supported in part by
the French government under management of Agence Nationale de la Recherche as
part of the “Investissements d’avenir” program, reference ANR19-P3IA-0001
(PRAIRIE 3IA Institute).

Tristan Cazenave  LAMSADE
Université Paris-Dauphine, PSL, CNRS
Paris, France
<EMAIL_ADDRESS>
###### Abstract

Making inferences with a deep neural network on a batch of states is much
faster with a GPU than making inferences on one state after another. We build
on this property to propose Monte Carlo Tree Search algorithms using batched
inferences. Instead of using either a search tree or a transposition table we
propose to use both in the same algorithm. The transposition table contains
the results of the inferences while the search tree contains the statistics of
Monte Carlo Tree Search. We also propose to analyze multiple heuristics that
improve the search: the $\mu$ FPU, the Virtual Mean, the Last Iteration and
the Second Move heuristics. They are evaluated for the game of Go using a
MobileNet neural network.

###### Index Terms:

Monte Carlo Tree Search, Deep Learning, Computer Games

##  I Introduction

Monte Carlo Tree Search (MCTS) using a combined policy and value network is
the state of the art for complex two-player perfect information games such as
the game of Go [1]. MCTS is also the state of the art for many other games and
problems [2]. We propose multiple optimizations of MCTS in the context of its
combination with deep neural networks. With current hardware such as GPU or
TPU it is much faster to batch the inferences of a deep neural network rather
than to perform them sequentially. We give in this paper MCTS algorithms that
make inferences in batches and some heuristics to improve them. We evaluate
the search algorithms for the game of Go.

The second section deals with existing work on MCTS for games. The third
section presents our algorithms. The fourth section details experimental
results.

##  II Monte Carlo Tree Search

MCTS has its roots in computer Go [3]. A theoretically well founded algorithm
is UCT [4]. Dealing with transpositions in UCT was addressed with the UCD
algorithm [5]. The authors tested various ways to deal with transpositions and
gave results for multiple games in the context of General Game Playing (GGP).

The GRAVE algorithm [6] is the state of the art in GGP. It uses a
transposition table as the core of the tree search algorithm. Entries of the
transposition table contain various kind of information such as the statistics
on the moves as well as the generalized AMAF statistics. It does not use the
UCB bandit anymore but an improvement of RAVE [7].

When combined with neural networks the state of the art MCTS algorithm is PUCT
[8]. It is the current best algorithm for games such as Go [9] and Shogi [1].
It was used in the AlphaGo program [8] as well as in its descendants AlphaGo
Zero [9] and Alpha Zero [1].

The PUCT bandit is:

$V(s,a)=Q(s,a)+c\times P(s,a)\times\frac{\sqrt{N(s)}}{1+N(s,a)}$

Where $P(s,a)$ is the probability of move $a$ to be the best moves in state
$s$ given by the policy head of the neural network, $N(s)$ is the total number
of descents performed in state $s$ and $N(s,a)$ is the number of descents for
move $a$ in state $s$.

Many researchers have replicated the Alpha Zero experiments and also use the
PUCT algorithm [10, 11, 12, 13, 14].

###  II-A Parallelization of MCTS

Three different ways to parallelize UCT were first proposed in 2007 [15]. They
were further renamed Root Parallelization, Leaf Parallelization and Tree
Parallelization [16, 17].

Other optimizations of Tree Parallelization such as lock free parallelization
were also proposed [18] as well as scalability studies [19].

###  II-B Virtual Loss

A virtual loss enables to make multiple descents of the tree in parallel when
the results of the evaluations at the leaves are not yet known and the tree
has not yet been updated with these results. It is standard in Tree
Parallelization [16, 17]. The principle is very simple since it consists in
adding a predefined number of visits to the moves that are played during the
tree descent.

Virtual loss is used in most of the Go programs including AlphaGo [8] and ELF
[10].

###  II-C Batched Inferences

Using batch forwards of the neural network to evaluate leaves of the search
tree and find the associated priors given by the policy head is current
practice in many game programs [10, 11, 12, 13, 14]. Usually a set of leaves
is generated with search then the neural network is run on a single batch of
leaves and the results are incorporated into the search tree.

###  II-D First Play Urgency

Vanilla UCT begins by exploring each arm once before using UCB. This behavior
was improved with the First Play Urgency (FPU) [20]. A large FPU value ensures
the exploration of each move once before further exploitation of any
previously visited move. A small FPU ensures earlier exploitation if the first
simulations lead to an urgency larger than the FPU.

In more recent MCTS programs using playouts, FPU was replaced by RAVE [7]
which uses the All Moves As First heuristic so as to order moves before
switching gradually to UCT. RAVE was later improved with GRAVE [6] which has
good results in GGP [21, 22].

In AlphaGo [8], the FPU was revived and is set to zero when the evaluations
are between -1 and 1. We name this kind of FPU the constant FPU. It has
deficiencies. When the FPU is too high, all possible moves are tried at a node
before going further below in the state space and this slows down the search
and makes it shallow. When the FPU is too low, the moves after the best move
are only tried after many simulations and the search does not explore enough.
When the constant is in the middle of the range of values as in AlphaGo, both
deficiencies can occur, either when the average of the evaluations is below
the constant or is greater than the constant.

In other programs such as ELF [10] the FPU is set to the best mean of the
already explored moves. This is better than using a constant FPU since the
best mean is related to the mean of the other moves. It encourages
exploration.

Yet another way to deal with the FPU is to set it to the average mean of the
node (using the statistics of all the explored moves). We name this kind of
FPU the $\mu$ FPU.

##  III The Batch PUCT Algorithm

In this section we describe our algorithm and its refinements. We first
explain how we deal with trees and transposition table. We then detail our
heuristics: the Virtual Mean, the Last Iteration and the Second Move.

###  III-A Trees and Transposition Table

The principle of Batch MCTS is to simulate a sequential MCTS using batched
evaluations. In order to do so it separates the states that have been
evaluated from the search tree. The transposition table contains the states
that have been evaluated. The search tree is developed as in usual sequential
MCTS and when it reaches a leaf it looks up the state in the transposition
table. If it is present then it sends back the corresponding evaluation. If it
is not in the transposition table it sends back the Unknown value and adds the
state to the next batch of states.

At the beginning of Monte Carlo Tree Search (MCTS) were random playouts and
poor initial selection of moves to try. It changed a lot with Deep
Reinforcement Learning (DRL) which brought strong policies and evaluations.
The PUCT algorithm strongly biases the moves to try with the learned policy
and performs accurate evaluations at the leaves of the MCTS instead of random
playouts.

In early MCTS program it was found very useful to use a transposition table in
the search tree in order to reuse the information on the moves to try from
previous tree descents that took another path in the tree such as in UCD [5].
However reusing this information from different descents and starting a
playout at a deeper leaf biases the statistics of the upper part of the tree
and does not preserve equity between root moves. It was not a problem in
playout based MCTS since the tree policy was much stronger than the playout
policy. On the contrary biasing the moves in the context of PUCT can be
misleading for the evaluation of the root moves.

MCTS algorithms were designed when finding the interesting moves was difficult
and when the descent of the tree cost approximately as much as making a
playout. With deep neural networks trained using Deep Reinforcement Learning
the evaluation at a leaf is now more costly than the descent of the tree.
Moreover the policy provides accurate probabilities for the moves to try. In
this context it is interesting to reuse the neural network evaluation as much
as possible and we do not have anymore to make many playouts to have a good
policy in the tree. The algorithm we propose does reuse more than the standard
MCTS the evaluations already made and it is less detrimental than in playout
based MCTS since we already have a good policy provided by the neural network.

Bath MCTS increases the number of tree descents for a given budget of
inferences compared to usual PUCD with a transposition table and it makes the
average evaluations of the moves not biased by the developments from different
paths of already developed states.

In our implementation of Batch PUCT we use one transposition table and two
trees. The transposition table records for each state that has been given to
the neural network the evaluation of the state and the priors for the moves of
the state. The first tree records the statistics required to calculate the
PUCT bandit and the address of the children that have already been explored.
The second tree is a copy of the first tree used to build the next batch of
states that will be then given to the neural network.

Algorithm 1 give the main PUCT search algorithm using a transposition table
and the two trees. The GetBatch boolean is used to make the distinction
between the first tree and the second tree. The first tree is the main search
tree while the second tree is only used to build the batches.

Algorithm 2 gives the usual way of updating the statistics used for the main
tree. Algorithm 3 gives the update of the statistics for the second tree.

The main algorithm is the GetMove algorithm (algorithm 6). It calls the
GetBatch algorithm (algorithm 4) that descends the second tree many times in
order to fill the batch. It then makes inferences on the built batch and calls
the PutBatch algorithm (algorithm 5) that put the results of the inferences in
the transposition table and then upadtes the main tree. GetBatch, forward and
PutBatch are called $B$ times. In the end the GetMove algorithm returns the
most simulated move of the main tree.

###  III-B The Virtual Mean

The standard approach in parallel MCTS is to use a virtual loss to avoid
exploring again and again the same moves when no new evaluation is available.
We propose the Virtual Mean as an alternative to the virtual loss. The Virtual
Mean increases the number of simulation of the move as in the virtual loss but
it also adds the mean of the move to the sum of its evaluations in order to
have more realistic statistics for the next descent.

1: Function BatchPUCT ($s,GetBatch$)

2: if isTerminal ($s$) then

3: return Evaluation ($s$)

4: end if

5: if $GetBatch$ then

6: $t\leftarrow treeBatch$

7: else

8: $t\leftarrow tree$

9: end if

10: if $s\notin t$ then

11: if $s\notin$ transposition table then

12: if $GetBatch$ then

13: add $s$ to the batch

14: end if

15: return Unknown

16: else

17: add $s$ to $t$

18: return value ($s$)

19: end if

20: end if

21: $bestScore=-\infty$

22: for $m\in$ legal moves of $s$ do

23: $\mu=FPU$

24: if $t.p(s,m)>0$ then

25: $\mu=\frac{t.sum(s,m)}{t.p(s,m)}$

26: end if

27: $bandit=\mu+c\times t.prior(s,m)\times\frac{\sqrt{t.p(s)}}{1+t.p(s,m)}$

28: if $bandit>bestScore$ then

29: $bestScore\leftarrow bandit$

30: $bestMove\leftarrow m$

31: end if

32: end for

33: $s_{1}$ = play ($s,bestMove$)

34: $res$ = BatchPUCT ($s_{1}$, $GetBatch$)

35: if $GetBatch$ then

36: UpdateStatisticsGet ($res,bestMove,s,t$)

37: else

38: UpdateStatistics ($res,bestMove,s,t$)

39: end if

40: return $res$

Algorithm 1 The BatchPUCT algorithm

1: Function UpdateStatistics ($res,m,s,t$)

2: if $res\neq Unknown$ then

3: $t.p(s,m)=t.p(s,m)+1$

4: $t.sum(s,m)=t.sum(s,m)+res$

5: $t.p(s)=t.p(s)+1$

6: $t.sum(s)=t.sum(s)+res$

7: end if

Algorithm 2 The UpdateStatistics algorithm for the main tree

Algorithm 3 gives the different ways of updating the statistics of a node. The
$vl$ variable is the number of virtual losses that are added to a move when it
leads to an unknown leaf. A value greater than one will encourage more
exploration and will avoid resampling again and again the same unknown leaf.
The value is related to the maximum number of samples allowed in the GetBatch
algorithm (the variable $N$ in algorithm 4). A low value of $N$ will miss
evaluations and will not completely fill the batch. A large value of $N$ will
better fill the batch but will take more time to do it. Increasing $vl$
enables to fill the batch with more states for the same value of $N$. However
a too large value of $vl$ can overlook some states and decrease the number of
visited nodes in the main search tree. The $res$ value is the evaluation
returned by the tree descent, $m$ is the move that has been tried in the
descent, $s$ is the state and $t$ is the second tree.

1: Function UpdateStatisticsGet ($res,m,s,t$)

2: if $res=Unknown$ then

3: $\mu=\frac{t.sum(s,m)}{t.p(s,m)}$

4: if VirtualLoss then

5: $t.p(s,m)=t.p(s,m)+vl$

6: $t.p(s)=t.p(s)+vl$

7: else if VirtualMean then

8: $t.p(s,m)=t.p(s,m)+vl$

9: $t.sum(s,m)=t.sum(s,m)+vl\times\mu$

10: $t.p(s)=t.p(s)+vl$

11: $t.sum(s)=t.sum(s)+vl\times\mu$

12: end if

13: else

14: $t.p(s,m)=t.p(s,m)+1$

15: $t.sum(s,m)=t.sum(s,m)+res$

16: $t.p(s)=t.p(s)+1$

17: $t.sum(s)=t.sum(s)+res$

18: end if

Algorithm 3 The UpdateStatisticsGet algorithm

1: Function GetBatch ($s$)

2: $treeBatch\leftarrow tree$

3: $i\leftarrow 0$

4: while batch is not filled and $i<N$ do

5: BatchPUCT ($s,True$)

6: $i\leftarrow i+1$

7: end while

Algorithm 4 The GetBatch algorithm

Algorithm 4 give the main algorithm to build the batch. In order to present
the algorithm simply we assume a copy of the main tree to treeBatch which is
then used and modified in order to build the batch. A more elaborate
implementation is to separate inside a node the statistics of the main tree
and the statistics made during the building of the batch. A global stamp can
be used to perform a lazy reinitialization of the batch statistics at each new
batch build.

1: Function PutBatch ($s,out$)

2: for $o\in out$ do

3: add $o$ to the Transposition Table

4: end for

5: $res\leftarrow$ BatchPUCT ($s,False$)

6: while $res\neq Unknown$ do

7: $res\leftarrow$ BatchPUCT ($s,False$)

8: end while

Algorithm 5 The PutBatch algorithm

1: Function GetMove ($s,B$)

2: for $i\leftarrow 1$ to $B$ do

3: GetBatch($s$)

4: $out\leftarrow$ Forward ($batch$)

5: PutBatch ($s,out$)

6: end for

7: $t\leftarrow tree.node(s)$

8: return $argmax_{m}(t.p(s,m))$

Algorithm 6 The GetMove algorithm

###  III-C The Last Iteration

At the end of the GetMove algorithm, many states are evaluated in the
transposition table but have not been used in the tree. In order to gain more
information it is possible to continue searching for unused state evaluations
at the price of small inacurracies.

The principle is to call the BatchPUCT algorithm with GetBatch as True as long
as the number of Unknown values sent back does not reach a threshold.

The descents that end with a state which is not in the transposition table do
not change the statistics of the moves since they add the mean of the move
using the Virtual Mean. The descents that end with an unused state of the
transposition table modify the statistics of the moves and improve them as
they include statistics on more states.

The Last Iteration algorithm is given in algorithm 7. The $U$ variable is the
number of visited unknown states before the algorithm stops.

1: Function GetMoveLastIteration ($s,B$)

2: for $i\leftarrow 1$ to $B$ do

3: GetBatch($s$)

4: $out\leftarrow$ Forward ($batch$)

5: PutBatch ($s,out$)

6: end for

7: $nbUnknown\leftarrow 0$

8: $treeBatch\leftarrow tree$

9: while $nbUnknown<U$ do

10: $res\leftarrow$ BatchPUCT ($s,True$)

11: if $res=Unknown$ then

12: $nbUnknown\leftarrow nbUnknown+1$

13: end if

14: end while

15: $t\leftarrow treeBatch.node(s)$

16: return $argmax_{m}(t.p(s,m))$

Algorithm 7 The GetMoveLastIteration algorithm

###  III-D The Second Move Heuristic

Let $n_{1}$ be the number of playouts of the most simulated move at the root,
$n_{2}$ the number of playouts of the second most simulated move, $b$ the
total budget and $rb$ the remaining budget. If $n_{1}>n_{2}+rb$, it is useless
to perform more playouts beginning with the most simulated move since the most
simulated move cannot change with the remaining budget. When the most
simulated move reaches this threshold it is more useful to completely allocate
$rb$ to the second most simulated move and to take as the best move the move
with the best mean when all simulations are finished.

The modifications of the search algorithm that implement the Second Move
heuristic are given in algorithm 8. Lines 33-39 modify the best move to try at
the root when the most simulated move is unreachable. In this case the second
most simulated move is preferred.

Algorithm 9 gives the modifications of the GetMove algorithm for using the
Second Move heuristic. Lines 8-17 choose between the most simulated move and
the second most simulated move according to their means.

1: Function BatchSecond ($s,GetBatch,budget,i,root$)

2: if isTerminal ($s$) then

3: return Evaluation ($s$)

4: end if

5: if $GetBatch$ then

6: $t\leftarrow treeBatch$

7: else

8: $t\leftarrow tree$

9: end if

10: if $s\notin t$ then

11: if $s\notin$ transposition table then

12: if $GetBatch$ then

13: add $s$ to the batch

14: end if

15: return Unknown

16: else

17: add $s$ to $t$

18: return value ($s$)

19: end if

20: end if

21: $bestScore=-\infty$

22: for $m\in$ legal moves of $s$ do

23: $\mu=FPU$

24: if $t.p(s,m)>0$ then

25: $\mu=\frac{t.sum(s,m)}{t.p(s,m)}$

26: end if

27: $bandit=\mu+c\times t.prior(s,m)\times\frac{\sqrt{1+t.p(s)}}{1+t.p(s,m)}$

28: if $bandit>bestScore$ then

29: $bestScore\leftarrow bandit$

30: $bestMove\leftarrow m$

31: end if

32: end for

33: if root then

34: $b\leftarrow highestValue_{m}(t.p(s,m))$

35: $b_{1}\leftarrow secondHighestValue_{m}(t.p(s,m))$

36: if $b\geq b_{1}+budget-i$ then

37: $bestMove\leftarrow secondBestMove_{m}(t.p(s,m))$

38: end if

39: end if

40: $s_{1}$ = play ($s,bestMove$)

41: $res$ = BatchSecond ($s_{1},GetBatch,budget,i,False$)

42: if $GetBatch$ then

43: UpdateStatisticsGet ($res,bestMove,s,t$)

44: else

45: UpdateStatistics ($res,bestMove,s,t$)

46: end if

47: return $res$

Algorithm 8 The BatchSecond algorithm

1: Function GetMoveSecondHeuristic ($s,B$)

2: $b\leftarrow size(batch)$

3: for $i\leftarrow 0$ to $B$ do

4: GetBatchSecond ($s,B\times b,i\times b$)

5: $out\leftarrow$ Forward ($batch$)

6: PutBatchSecond ($out,B\times b,i\times b$)

7: end for

8: $t\leftarrow tree$

9: $best\leftarrow bestMove_{m}(t.p(s,m))$

10: $\mu=\frac{t.sum(s,best)}{t.p(s,best)}$

11: $secondBest\leftarrow secondBestMove_{m}(t.p(s,m))$

12: $\mu_{1}=\frac{t.sum(s,secondBest)}{t.p(s,secondBest)}$

13: if $\mu_{1}>\mu$ then

14: return $secondBest$

15: else

16: return $best$

17: end if

Algorithm 9 The GetMoveSecondHeuristic algorithm

##  IV Experimental Results

Experiments are performed using a MobileNet neural network which is an
architecture well fitted for the game of Go [23, 24]. The network has 16
blocks, a trunk of 64 and 384 planes in the inverted residual. It has been
trained on the Katago dataset containing games played at a superhuman level.

###  IV-A FPU

We test the constant FPU and the best mean FPU against the $\mu$ FPU. Table I
gives the average winrate over 400 games of the different FPU for different
numbers of playouts. For example, the first cell means that the constant FPU
wins 13.00% of its games against the $\mu$ FPU when the search algorithms both
use 32 playouts per move.

TABLE I: Playing 400 games with different FPU and different numbers of evaluations against the $\mu$ FPU, $\frac{\sigma}{\sqrt{n}}<0.0250$. FPU | 32 | 64 | 128 | 256 | 512
---|---|---|---|---|---
constant | 0.1300 | 0.1300 | 0.0475 | 0.0175 |
best mean | 0.3775 | 0.3450 | 0.3275 | 0.3150 | 0.2725

It is clear that the $\mu$ FPU is the best option. In the remainder of the
experiments we use the $\mu$ FPU.

###  IV-B Trees and Transposition Table

We now experiment with using a plain tree associated to a transposition table.
An entry in the transposition table only contains the evaluation and the
prior. A node in the tree contains the children and the statistics of the
state. We compare it to PUCD, i.e. the PUCT algorithm with a transposition
table that stores both the statistics, the evaluation and the priors. PUCD
searches with a Directed Acyclic Graph while its opponent develops a plain
tree with transpositions only used to initialize leaves.

Table II gives the budget used by each algorithm (the number of forward of the
neural network), the number of descents of the plain tree algorithm using this
budget and the ratio of the number of descents divided by the number of
forwards and the win rate of the plain tree algorithm. Both PUCD and the plain
tree algorithm are called with a batch of size one. The PUCD algorithm makes
exactly as many descents as forwards when the plain tree algorithm makes more
descents than forwards. The ratio of the number of descents divided by the
number of forwards increases with the budget. We can see that both algorithms
have close performances with the plain tree algorithm getting slightly better
with an increased budget.

TABLE II: Playing 400 games with a tree, a transposition table and a batch of size 1 against PUCD with a batch of size 1, $\frac{\sigma}{\sqrt{n}}<0.0250$ Budget | Descents | Ratio | Winrate
---|---|---|---
256 | 273.08 | 1.067 | 0.4800
1024 | 1 172.21 | 1.145 | 0.4875
4096 | 5 234.01 | 1.278 | 0.5275

###  IV-C The Virtual Mean

In order to compare the virtual loss and the Virtual Mean we make them play
against the sequential algorithm. They both use batch MCTS. The results are
given in table III. The first column is the penalty used, the second column is
the value of $vl$ the number of visits to add for the penalty used. The third
column is the number of batches and the fourth column the size of the batches.
The fifth column is the average number of nodes of the tree. The sixth column
is the average of the number of useful inferences made per batch. The number
of inferences made can be smaller than the batch size since the batch is not
always fully filled at each call of the GetBatch algorithm. The last column is
the win rate against the sequential algorithm using 64 batches of size 1. All
experiments are made with the maximum number of descents $N=500$. It is normal
that the number of inferences per batch is smaller than the batch size since
for example the first batch only contains one state because the priors of the
root are not yet known.

The best result for the Virtual Loss is with $vl=3$ when using 8 batches. It
scores 20.75% against sequential PUCT with 64 state evaluations. The Virtual
Mean with 8 batches has better results as it scores 31.00% with $vl=3$ against
the same opponent.

We also tested the virtual loss and the Virtual Mean for a greater number of
batches. For 32 batches of size 32 (i.e. inferences on a little less than 1024
states) the best result for the virtual loss is with $vl=2$ with an average of
157.69 nodes in the tree and a percentage of 79.00% of wins against sequential
PUCT with 64 state evaluations. The Virtual Mean with $vl=1$ and the same
number of batches is much better: it has on average 612.02 nodes in the tree
and a percentage of wins of 97.00% of its games.

In the remaining experiments we use the Virtual Mean.

TABLE III: Playing 400 games with the different penalties against sequential PUCT with 64 state evaluations. $\frac{\sigma}{\sqrt{n}}<0.0250$ Penalty | $vl$ | B | Batch | Nodes | Inference | Winrate
---|---|---|---|---|---|---
Virtual Loss | 1 | 8 | 32 | 24.47 | 23.17 | 0.1300
Virtual Loss | 2 | 8 | 32 | 24.37 | 24.46 | 0.1525
Virtual Loss | 3 | 8 | 32 | 24.11 | 25.16 | 0.2075
Virtual Loss | 4 | 8 | 32 | 23.87 | 25.53 | 0.2025
Virtual Loss | 5 | 8 | 32 | 23.91 | 25.72 | 0.1600
Virtual Loss | 1 | 32 | 32 | 166.09 | 28.08 | 0.7725
Virtual Loss | 2 | 32 | 32 | 157.69 | 28.25 | 0.7900
Virtual Loss | 3 | 32 | 32 | 151.02 | 28.30 | 0.7800
Virtual Loss | 4 | 32 | 32 | 144.45 | 28.19 | 0.7550
Virtual Mean | 1 | 8 | 32 | 46.45 | 20.22 | 0.2625
Virtual Mean | 2 | 8 | 32 | 43.75 | 21.64 | 0.3025
Virtual Mean | 3 | 8 | 32 | 41.63 | 22.10 | 0.3100
Virtual Mean | 4 | 8 | 32 | 40.41 | 22.53 | 0.2400
Virtual Mean | 1 | 32 | 32 | 612.02 | 26.63 | 0.9700
Virtual Mean | 2 | 32 | 32 | 619.07 | 27.83 | 0.9675
Virtual Mean | 3 | 32 | 32 | 593.91 | 28.20 | 0.9500

###  IV-D The Last Iteration

Table IV gives the result of using the Last Iteration heuristic with different
values for U. The column $vll$ contains the value of $vl$ used for the Last
Iteration. We can see that the win rates are much better when using 8 batches
than for table III even for a small U. A large virtual loss ($vll$) of 3 makes
more descents but it is less accurate. Using a virtual loss of 1 is safer and
gives similar results.

When using 32 batches against 512 states evaluations the win rate increases
from 62.75% for $U=0$ to 68.00% for $U=40$.

TABLE IV: Playing 400 games with the Last Iteration algorithm against sequential PUCT with $P$ state evaluations. $\frac{\sigma}{\sqrt{n}}<0.0250$. U | vl | vll | B | Batch | P | Nodes | Inference | Winrate
---|---|---|---|---|---|---|---|---
10 | 3 | 3 | 8 | 32 | 64 | 109.02 | 21.90 | 0.4975
10 | 3 | 1 | 8 | 32 | 64 | 75.09 | 22.04 | 0.4450
40 | 3 | 3 | 8 | 32 | 64 | 232.09 | 22.17 | 0.5100
40 | 3 | 1 | 8 | 32 | 64 | 129.90 | 22.02 | 0.5275
0 | 1 | 1 | 32 | 32 | 512 | 729.41 | 28.88 | 0.6275
40 | 1 | 3 | 32 | 32 | 512 | 962.84 | 28.81 | 0.6650
40 | 1 | 1 | 32 | 32 | 512 | 835.07 | 28.86 | 0.6800

###  IV-E The Second Move Heuristic

Table V gives the winrate for different budgets when playing PUCT with the
second move heuristic against vanilla PUCT. We can see that the Second Move
heuristic consistently improves sequential PUCT.

TABLE V: Playing 400 games with the second move heuristic used at the root of sequential PUCT against sequential PUCT. $\frac{\sigma}{\sqrt{n}}<0.0250$. Budget | Winrate
---|---
32 | 0.5925
64 | 0.6350
128 | 0.6425
256 | 0.5925
512 | 0.6250
1024 | 0.5600

###  IV-F Ablation Study

The PUCT constant $c=0.2$ that we used in the previous experiments was fit to
the sequential PUCT on a DAG with 512 inferences. In order to test the various
improvements we propose to fit again the $c$ constant with all improvements
set on. The results of games against sequential PUCT for different constants
is given in table VI. The $c=0.5$ constant seems best and will be used in the
ablation study.

TABLE VI: Result of different constants for 32 batches of size 32 against sequential PUCT with 256 state evaluations and a constant of 0.2. $\frac{\sigma}{\sqrt{n}}<0.0250$. $c$ | Winrate
---|---
0.2 | 0.7575
0.3 | 0.7925
0.4 | 0.8100
0.5 | 0.8275
0.6 | 0.7975
0.7 | 0.7700
0.8 | 0.7550
1.6 | 0.5900

Table VII is an ablation study. It gives the scores against sequential PUCT
with 512 evaluations of the different algorithms using 32 batches with some
heuristics removed.

Removing the Virtual Mean heuristic is done by replacing it with the virtual
loss heuristic. However the virtual loss combined with the Last Iteration is
catastrophic. So we also removed both the Virtual Mean and the Last Iteration
heuristics in order to evaluate removing the Virtual Mean.

Removing the $\mu$ FPU was done replacing it by the best mean FPU. The Last
Iteration uses $vll=1$ and $U=40$.

We can observe in Table VII that all the heuristics contribute significantly
to the strength of the algorithm. The Virtual Mean has the best increase in
win rate, going from 29.50% for the virtual loss to 68.00% when replacing the
virtual loss by the Virtual Mean. The Second Move heuristic also contributes
to the strength of Batch MCTS.

TABLE VII: Playing 400 games with the different heuristics using 32 batches of size 32 against sequential PUCT with 512 state evaluations. $\frac{\sigma}{\sqrt{n}}<0.0250$. $\mu$ FPU | Virtual Mean | Last Iteration | Second Move | Winrate
---|---|---|---|---
y | y | y | y | 0.6800
n | y | y | y | 0.4775
y | n | y | y | 0.0475
y | n | n | y | 0.2950
y | y | n | y | 0.6275
y | y | y | n | 0.5750

###  IV-G Inference Speed

Table VIII gives the number of batches per second and the number of inferences
per second for each batch size. Choosing batches of size 32 enables to make 26
times more inferences than batches of size 1 while keeping the number of
useful inferences per batch high enough.

TABLE VIII: Number of batches per second according to the size of the batch with Tensorflow and a RTX 2080 Ti. Size | Batches per second | Inferences per second
---|---|---
1 | 38.20 | 38
2 | 36.60 | 73
4 | 36.44 | 146
8 | 33.31 | 267
16 | 32.92 | 527
32 | 31.10 | 995
64 | 26.00 | 1 664
128 | 18.32 | 2 345

##  V Conclusion

We have proposed to use a tree for the statistics and a transposition table
for the results of the inferences in the context of batched inferences for
Monte Carlo Tree Search. We found that using the $\mu$ FPU is what works best
in our framework. We also proposed the Virtual Mean instead of the Virtual
Loss and found that it improves much Batch MCTS. The Last Iteration heuristic
also improves the level of play when combined with the Virtual Mean. Finally
the Second Move heuristic makes a good use of the remaining budget of
inferences when the most simulated move cannot be replaced by other moves.

## References

  * [1] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis, “A general reinforcement learning algorithm that masters chess, shogi, and go through self-play,” _Science_ , vol. 362, no. 6419, pp. 1140–1144, 2018.
  * [2] C. Browne, E. Powley, D. Whitehouse, S. Lucas, P. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton, “A survey of Monte Carlo tree search methods,” _Computational Intelligence and AI in Games, IEEE Transactions on_ , vol. 4, no. 1, pp. 1–43, Mar. 2012.
  * [3] R. Coulom, “Efficient selectivity and backup operators in monte-carlo tree search,” in _Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers_ , 2006, pp. 72–83.
  * [4] L. Kocsis and C. Szepesvári, “Bandit based monte-carlo planning,” in _Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18-22, 2006, Proceedings_ , 2006, pp. 282–293.
  * [5] A. Saffidine, T. Cazenave, and J. Méhat, “UCD: Upper Confidence bound for rooted Directed acyclic graphs,” _Knowledge-Based Systems_ , vol. 34, pp. 26–33, Dec. 2011.
  * [6] T. Cazenave, “Generalized rapid action value estimation,” in _24th International Joint Conference on Artificial Intelligence_ , 2015, pp. 754–760.
  * [7] S. Gelly and D. Silver, “Monte-Carlo tree search and rapid action value estimation in computer Go,” _Artif. Intell._ , vol. 175, no. 11, pp. 1856–1875, 2011.
  * [8] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, “Mastering the game of Go with deep neural networks and tree search,” _Nature_ , vol. 529, no. 7587, pp. 484–489, jan 2016.
  * [9] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. P. Lillicrap, K. Simonyan, and D. Hassabis, “Mastering the game of go without human knowledge,” _nature_ , vol. 550, no. 7676, pp. 354–359, 2017.
  * [10] Y. Tian, J. Ma, Q. Gong, S. Sengupta, Z. Chen, J. Pinkerton, and C. L. Zitnick, “Elf opengo: An analysis and open reimplementation of alphazero,” _CoRR_ , vol. abs/1902.04522, 2019.
  * [11] G.-C. Pascutto, “Leela zero,” https://github.com/leela-zero/leela-zero, 2017\.
  * [12] R. Emslie, “Galvanise zero,” https://github.com/richemslie/galvanise_zero, 2019.
  * [13] D. J. Wu, “Accelerating self-play learning in go,” _CoRR_ , vol. abs/1902.10565, 2019.
  * [14] T. Cazenave, Y.-C. Chen, G.-W. Chen, S.-Y. Chen, X.-D. Chiu, J. Dehos, M. Elsa, Q. Gong, H. Hu, V. Khalidov, L. Cheng-Ling, H.-I. Lin, Y.-J. Lin, X. Martinet, V. Mella, J. Rapin, B. Roziere, G. Synnaeve, F. Teytaud, O. Teytaud, S.-C. Ye, Y.-J. Ye, S.-J. Yen, and S. Zagoruyko, “Polygames: Improved zero learning,” _ICGA Journal_ , vol. 42, no. 4, pp. 244–256, December 2020.
  * [15] T. Cazenave and N. Jouandeau, “On the parallelization of UCT,” in _proceedings of the Computer Games Workshop_ , 2007, pp. 93–101.
  * [16] G. M.-B. Chaslot, M. H. Winands, and H. J. van Den Herik, “Parallel monte-carlo tree search,” in _International Conference on Computers and Games_. Springer, 2008, pp. 60–71.
  * [17] T. Cazenave and N. Jouandeau, “A parallel monte-carlo tree search algorithm,” in _International Conference on Computers and Games_. Springer, 2008, pp. 72–80.
  * [18] M. Enzenberger and M. Müller, “A lock-free multithreaded monte-carlo tree search algorithm,” in _Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11-13, 2009. Revised Papers_ , ser. Lecture Notes in Computer Science, H. J. van den Herik and P. Spronck, Eds., vol. 6048. Springer, 2009, pp. 14–20.
  * [19] R. B. Segal, “On the scalability of parallel UCT,” in _International Conference on Computers and Games_. Springer, 2010, pp. 36–47.
  * [20] Y. Wang and S. Gelly, “Modifications of uct and sequence-like simulations for monte-carlo go,” in _2007 IEEE Symposium on Computational Intelligence and Games_. IEEE, 2007, pp. 175–182.
  * [21] C. Browne, M. Stephenson, É. Piette, and D. J. Soemers, “A practical introduction to the ludii general game system,” in _Advances in Computer Games_. Springer, 2019.
  * [22] C. F. Sironi, “Monte-carlo tree search for artificial general intelligence in games,” Ph.D. dissertation, Maastricht University, 2019.
  * [23] T. Cazenave, “Mobile networks for computer Go,” _IEEE Transactions on Games_ , 2021.
  * [24] ——, “Improving model and search for computer Go,” _Arxiv_ , 2021.