IEEE Computational Intelligence Magazine - August 2020 - 61

achieve an overall better game experience, and to improve the learning process for players, it is imperative to
balance program difficulty accordingly.
In addition to matching the player with an appropr iate opponent,
strength adjustment can also be used
as a player assessment tool. More specifically, given a player of unknown
strength, an equally matched opponent (i.e., playing at about 50% win
rate) can be used as a metric of measuring the player's performance [10],
[11]. Ideally, the goal is to design a
mechanism that is able to provide a
wide-ranging and evenly distributed
set of playing strengths, such that it
would be possible for most human
players to choose the most appropriate strength to play against. Similarly,
any player that falls within the range
of provided strengths can also be measured by this mechanism.
Coming up with a stable and wideranging strength adjustment mechanism
is a non-trivial problem. Using the
AlphaGo Zero algorithm as an example
target, there are two straightforward
tweaks that can be applied to the two
major components of the algorithm:
Monte-Carlo tree search (MCTS) and
deep neural networks (DNNs).
First, we could reduce the superhuman program strength to lower levels
by reducing the total thinking time, or
the total simulation count in MCTS.
However, with this method, the search
tree's relatively smaller size leaves the
program vulnerable to tactical traps. For
example, the ladder problem in Go is
one of the most elementary shapes
taught to human players [5]; however, for
MCTS-based programs, a significant
number of simulations are often required
before the program can handle ladders
properly. It has been shown that when
adjusting program strength through
reduction, simulation count and playing
strength do not form a linear relationship
[12]. In fact, once the number of simulations falls below a certain threshold, the
program playing strength drops catastrophically. In other words, by reducing
the simulation count, we would not be
able to offer an evenly distributed skill

On the low end of the difficulty scale, human players tend
to lose interest when playing against an AI opponent far
weaker than themselves; on the other hand, excessive
difficulty tends to lead to frustration [9].
level, especially towards the lower end
of the playing strength scale.
The second straightforward approach
is to offer different programs for different strength levels. For example, we
could train separate DNNs for each difficulty. A good example of this type of
strength adjustment is Paulsen and
Fürnkranz's work 1 on training chess
evaluation functions for different
strengths [13]. However, this approach
usually requires large amounts of time
and effort to tune and test the programs.
This is especially difficult for games like
Go, where strength levels span a wide
range from 30 kyu to professional 9 dan
[14], corresponding to about a 3,000 Elo
rating [15] difference.
The main contributions of this paper
are as follows:
❏ We improve upon an existing strength
adjustment approach with a threshold
mechanism to filter out low-quality
moves.
❏ We present an in-depth strength
analysis to justify that there is a lower
bound on the move quality.
❏ We introduce three dynamic strength
adjustment methods to predict opponents' expected strengths automatically.
❏ We successfully applied our methods
in real-world cases ranging from professionals to kyu rank amateurs in
terms of strength adjustment and
strength assessment.
The structure of this paper is as follows. First, we review a strength adjustment (SA) approach based on the
softmax policy and propose our modification in Section II. We then apply the
method to two programs: 1) the opensource Go program ELF OpenGo
(abbr. ELF for the remainder of this
paper); 2) the Go program CGI [16].
1
Paulsen and Fürnkranz's method does not use DNNs,
but is similar to our example here in that they create
multiple programs, each offering one static strength.

From these two implementations, we
demonstrate that the modified strength
adjustment method can be easily used
to adjust the strength of a program, covering a range of over 800 Elo ratings. In
Sect ion III, this paper presents a
hypothesis and performs theoretical
analyses to justify the empir ical
strengths shown in Section II. Having
demonstrated that the program strength
can be adjusted with relative ease, we
introduce methods to adjust the
strength dynamically in Section IV. In
Section V, we test our method on realworld scenarios, playing against human
players. Finally, we summarize our contributions in Section VI.
This paper is an extension of our
work, which was published in the
AAAI 2019 conference [17]. The mixed
dynamic strength adjustment (MDSA)
mechanism (Subsection IV-C) and realworld experiments (Section V) contain
new work and data for this version of
the paper.
II. Static Strength Adjustment (SSA)

In this section, we first review past work
on strength adjustment, then present our
modifications to the method. We apply
the modified approach to the Go program ELF and provide empirical data.
A. Past Work

For strength adjustment, Sephton et al.
[12] investigated some selection mechanisms for MCTS-based game-playing
programs. One of these mechanisms uses
a simple softmax policy as follows.
Given strength index z, choose moves i
with probability N zi / / j N zj , where N i
is the number of simulations on move i
in MCTS. For simplicity of discussion in
the rest of this paper, let N i $ N j if
i 1 j, i.e., N 1 is the maximum.
Conceptually, z is the inverse of the
softmax temperature. When z is higher,

AUGUST 2020 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

IEEE Computational Intelligence Magazine - August 2020

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2020