Visualisations of Candidate Moves
in Game Tree Search
Most recent update from April 2019
Interactive (human + computer) game play has achieved
impressive successes in the last few decades. In
"teams" the computers are used to generate sets of
moves and to present them in such a way that
boss finds it easy to select his or her
Several good screen layouts have been realized.
examples below: first a series for Monte-Carlo
searches in Go, Hex, and Havannah; in the second part
some k-best visualisations
for alpha-beta search with
Valkyria is a private go program,
In October 2010, Persson designed
a very informative
visualisation of Valkyria's Monte
Carlo search process:
in one diagram he put the expected
(like in Fuego, see below)
often each candidate move was visited in
Concerning territory, green means ownership for White and
blue for Black.
Red circles of different sizes indicate the
visits. The radii of circles are proportional to
logarithm(visits) / logarithm(max-visits). Persson first used
but then only the moves searched a lot
became visible. In the example,
the largest circle is 1578
visits and the smallest is 9 visits. The
medium sized are
about 150-700 visits. In the position, Black is
Persson did not include win rates in the diagram
win rates tend to be either unreliable (move was not
much) and because all top candidates tend to have
This picture belongs to a Hex program, based on UCT
(author Cameron Browne, Summer 2010).
The screen shot
shows the different aspects of the
visualisation. There is one
obviously good move (at square E4).
The large circle there means
that UCT has correctly focussed
most of its search time on that
cell. The fact that the big
red pie slice covers more than 50%
of the circle means that
the algorithm is reasonably confident
of this move (pie area
is based on reward percentage).
The red pie slices are positive (winning) estimates and the
pie slices are negative (losing) estimates, hence the
very confident that all but the four red moves
are almost certainly
moves. If the algorithm searched for longer on the cells
three small red pie slices, the red slices would shrink then
become blue as their true negative value is realised.
Circle radius is based on the number of times that each node (move)
has been visited. This is
an exponential scale, so
visited only a few times have inflated radii
and are still visible.
As the number of visits to a node approaches 1,000,000 then
will approach the standard piece size.
This way to visualize a UCT search may be applicable to
(including Go) where a move consists of
a piece being placed on a free
cell of the board.
Ring of Fire was a program for the game
In October 2010, RoF-author Johannes
Waldmann from Leipzig
chose the following way
(somewhat different from Cameron Browne's)
the candidates of Monte-Carlo tree search:
The Havannah board is hexagonal, size 6 in this example.
Black and White
are stones, already placed by the two players.
In the diagram Black is
Candidate moves are shown by blobs with different colors
and red) and different sizes.
The color of a blob is the move value
(green = good, red = bad),
and the size of a blob indicates the number
of visits (large = many).
Colors are normalized (the best value is
always pure green,
no matter how bad it actually is), and visit counts
When Johannes Waldmann presented this solution in the
forum of www.littlegolem.net, he gave a promise:
"Yes, I will make the blobs click-able
(to allow the user to walk
in the search tree)."
Go program Many Faces of Go, version 12.013
2009 (author David Fotland).
This was the first realisation of
a multi-best mode for a
game playing program that is based on
Monte Carlo Tree Search.
The program shows a variable number of "popular" moves.
The numbers in
the board indicate the candidate moves.
The values are the Monte Carlo
scores for these moves,
rounded to full percent.
In the lower left part
of the window the principal variation
for the best move (k5 in the example)
is shown. Typically,
only the first 3-5 moves of this line can be
Fuego is a go program, using Monte-Carlo tree search.
The initial version of the code was released by the
Go Group at the University of Alberta. Fuego
under the terms of the GNU Lesser General
Members of the Fuego team were
(in October 2010):
Martin Müller, Broderick Arneson,
Gerald Tesauro, Arpad Rimmel.
In certain periods also David Silver and Aya Huang the Go-programming
heros of DeepMind ("Alpha-Go") in 2015 and 2016 were also
in this group.
Fuego has a routine that does not show values of moves
how often a square will finally end in the territory
and White, respectively.
The size of the white and dark grey
squares represents the percentage
of playouts that ended up
with that point being territory for that
color. For example,
a large white square means that white almost
this point, while a small grey square means that black
it only slightly more often than white. The exact values are
scaled from -1 (always white) to +1 (always black).
Jonathan Chetwynd used the Fuego routine to generate
another type of colourful pictures showing "expected territory"
The data describe the probability that either player
may gain each point of territory. Reddish color means
probability for becoming white territory. Green
probability for becoming black territory.
(This may be a problem
for color-blind people.)
The data were normalised and converted to two dimensional gradients
using linear interpolation or lerp.
Scaleable Vector Graphics (SVG)
is used to display the combined
image in the browser.
Solutions from before the ages of Monte Carlo game tree search
K-best search in game trees gives the user not only
single best move, but a list with the k best move
Here "best" is always meant with respect to
function of the program in use.
From the mid 1990's on, several
good screen layouts for k-best
game tree search have been realized.
See the seven examples
Chess program Shredder in 4-best analysis mode,
version Shredder-3 from 1998 (author Stefan Meyer-Kahlen).
this site for
more information on Shredder.
Program for game Blobs, running under Morphling
in 5-best analysis mode,
version from Summer 2002 (author of
Morphling: Thomas Rolle).
Program Connect-It for Shannon's Switching game,
in 4-best analysis mode, version from Summer 2002
(author Jörg Sameith).
Amazons program Amazong in 3-best analysis mode,
version 2.5 from Summer
2002 (author Jens Lieberum).
Amazons program 8QP in 2-best analysis mode,
1.05 from Summer 2002 (author Johan de Koning).
Intermediate candidate moves are not deleted but remain on
Top candidates are shown in lighter colours.
A report on the k-best-visualisations was published in the
ICGA Journal, Volume 26 (2003), pp. 182-189.
(Title: "Five visualisations of the k-best mode";
Ingo Althöfer, Johan de Koning, Jens
Stefan Meyer-Kahlen, Thomas Rolle, Jörg Sameith.)
A low quality copy of this report can be found online here:
Keep in mind that this report was written before the
upcoming of Monte Carlo game tree search.
Feel free to contact Ingo Althöfer when you know about other nice
realizations of k-best game tree search.
Back to the main site of Ingo Althöfer