Multi-Agent Monte Carlo Go
Leandro Soriano Marcolino
Matsubara Laboratory – Intelligence Information
Science Department
Future University of Hakodate
Hakodate, Japan
g2209001@fun.ac.jp
Hitoshi Matsubara
Matsubara Laboratory – Intelligence Information
Science Department
Future University of Hakodate
Hakodate, Japan
matsubar@fun.ac.jp
ABSTRACT
In this paper we propose a Multi-Agent version of UCT
Monte Carlo Go. We use the emergent behavior of a great
number of simple agents to increase the quality of the Monte
Carlo simulations, increasing the strength of the artificial
player as a whole. Instead of one agent playing against it-
self, different agents play in the simulation phase of the al-
gorithm, leading to a better exploration of the search space.
We could significantly overcome Fuego, a top Computer Go
software. Emergent behavior seems to be the next step of
Computer Go development.
Categories and Subject Descriptors
I.2.1 [Artificial Intelligence]: Applications and Expert
Systems—Games
General Terms
Algorithms, Experimentation
Keywords
Emergent Behaviour, Collective Intelligence
1. INTRODUCTION
Go is a two-player turn-based strategy board game, that
is famous for being one of the main challenges in Artificial
Intelligence. A small set of simple rules
1
leads to a game
amazingly complex for a human being and a search tree
that is unbearably large for a computer. There are many
reasons for this difficulty of developing a strong artificial
player. First, Go is played in a large board, 19x19, with
361 intersections, creating difficulties for tree search based
algorithms. Second, generally most of the intersections are
valid movements, increasing the number of possible states
from a given state of the board. Third, the stones interact
in complex ways during the game; one stone may influence
a distant group, for example in situations where there is a
1
Available at many places, for example:
http://www.pandanet.co.jp/English
Cite as: Multi-Agent Monte Carlo Go, Leandro Soriano Marcol-
ino, and Hitoshi Matsubara, Proc. of 10th Int. Conf. on Au-
tonomous Agents and Multiagent Systems (AAMAS 2011),
Tumer, Yolum, Sonenberg and Stone (eds.), May, 2–6, 2011, Taipei, Tai-
wan, pp. 21-28.
Copyright
c
2011, International Foundation for Autonomous Agents and
Multiagent Systems (www.ifaamas.org). All rights reserved.
ladder. Besides, building an evaluation function is not triv-
ial. Even end of game situations, that intuitively should be
simpler, were proved to be PSPACE-hard [31]. According
to [1], compared to the complexity of Chess (10
50
), the com-
plexity of Go (10
160
) is bigger by a factor of 10
110
. We can
see, therefore, how challenging it is to create an artificial
player of Go.
However, recently, with the development of evaluations
of the board state based on simulations (known as Monte
Carlo techniques), the strength of Computer Go players im-
proved significantly. Thanks to artificial players like MoGo,
Crazy Stone, Fuego, Many Faces of Go, and Zen, the best Go
programs are now considered amateur level 2 dan. Further
improvement was achieved by parallelization, as it increases
the computational power, allowing a deeper exploration of
the possible movements. In February 2009, Many Faces of
Go, running on a 32-core Xeon cluster, beat the professional
player James Kerwin, in a 19x19 board with a handicap of
7 stones. Many recent works are now investing in the par-
allelization of Monte Carlo techniques. However, there is
always a limit in the amount of speed-up that can be gained
in a parallelization design.
Generally, there are two ways to increase the strength
of an artificial player: advances in computational power,
which can be achieved by parallelization, and advances in
the theory, which can be achieved by new algorithms and
methods. Nowadays, the research in Monte Carlo techniques
seems to be focused on the parallelization of the current
approaches. However, it is always desirable to advance the
theory with the creation of better algorithms, that lead to
stronger players even when the computational power has not
necessarily increased. We believe that the next theoretical
step lies in the investigation of Multi-Agent methodologies.
Multi-Agent systems have been used to solve a great range
of problems in Artificial Intelligence. The emergent behavior
of a great number of simple agents have been applied in al-
gorithms like Ant Colony Optimization [11], Particle Swarm
Optimization [20], etc, in order to solve difficult optimiza-
tion problems. It is also notable how emergence can lead to
complex and intricate group behavior [21, 22, 23, 28].
Emergence is a powerful concept, not only in Computer
Science, but also in a variety of disciplines, like philosophy,
systems theory and art. The stock market and the Internet
are important systems to modern life that arise thanks to
the emergence of simple components. Emergence is also fun-
damental in biological systems. A notable example is an ant
colony. It is known that the queen does not order directly
the ants. Each ant is always reacting to stimuli generated