56
Fifth International Students Conference on Informatics
–
ICDD 2015
May 21-23, 2015, Sibiu, Romania
References
[1] Philips's Hue reference, accessed February 2015
http://www.usa.philips.com/e/hue/hue.html
[2] The Belkin WeMo Switch + Motion reference , accessed February 2015 http://www.belkin.com/us/p/P-
F5Z0340/
[3] SmartThings reference, February 2015
http://www.smartthings.com/
[4] Smart Room Control Solution by Distech Controls reference, accessed February 2015
http://www.distech-controls.com/en/csa/products/smart-room-control-solution/
[5] Control4 from Exzel Smart Home reference, accessed February 2015
http://www.exzelsmarthome.com/products/homecontrol/index.html
[6] MySql refference manual http://dev.mysql.com/doc/refman/5.7/en/ accessed June 2014
[7] Windows 8 User manual , accessed June 2014, http://www.microsoft.com/en-
us/download/details.aspx?id=39055
[8] Intel Galieo online manual, accessed June 2014, http://www.intel.com/content/www/us/en/do-it-
yourself/galileo-maker-quark-board.html
[9] Yocto Linux documentation, accessed June 2014 https://www.yoctoproject.org/documentation
[10] Apache Tomcat Server documentation http://tomcat.apache.org/tomcat-7.0-doc/
[11] Android Developer Manual http://developer.android.com/ , accessed June 2014
[12] Schneier on Security: Cryptanalysis of SHA-1, accessrd June 2014
https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html
[13] Unified Modeling Language User Guide, The (2 ed.). Addison-Wesley. 2005. p. 496. ISBN
0321267974.
[14] Ian F. Darwin : Java Cookbook, 3rd Edition, ISBN 978-1-4493-3704-9, publisher O'Reilly Media,
2014
[15] Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. 2001.Introduction to
Algorithms (2nd ed.). McGraw-Hill Higher Education.
[16] Leonard Richardson, Sam Ruby: RESTful Web Services Web services for the real world, ISBN: 978-
0-596-52926-
0, publisher O’Reilly Media, 2007
Mitrica Alexandru
University of Craiova
Department of computers and
information technology
Blvd. Decebal nr. 107, Craiova
Romania
E-mail: alexmitrica@yahoo.com
Sperila Alecsandru
University of Craiova
Department of computers and
information technology
Blvd. Decebal nr. 107, Craiova
Romania
E-mail:sperila.alecsandru@gmail.com
Sorin Ilie
University of Craiova
Department of computers and
information technology
Blvd. Decebal nr. 107, Craiova
Romania
E-mail:ilieviorelsorin@gmail.com
124
How to C#: Special Effects Erase. Set the image to current background color, the background color can be set by:ImageProcess.BackgroundColor = Color.Red. Encipher.
delete text from pdf file; how to delete text in a pdf acrobat
37
Fifth International Students Conference on Informatics
Imagination, Creativity, Design, Development
ICDD 2015, May 21-23
Sibiu, Romania
Playing Hex with Monte Carlo simulation
Nikola Radovic, Ljubomir Raicevic
Teacher Coordinator: Milan Tuba
Abstract
The goal of this paper is to show that Monte Carlo simulation can be used to play zero-sum board
games, with application to Hex. Additionally, we wish to measure two properties of this approach:
what is the minimum number of Monte Carlo repetitions after which benefits are negligible, and
second, does making a game tree with Monte Carlo simulation as evaluation function perform better
than the naive approach, and if it does, by how much.
1 Introduction
In section 1.1 we discuss the motivation for using Monte Carlo simulation in the game of Hex. In
section 1.2 rules of the game and some history are presented. In section 1.3 we give an overview
of Monte Carlo in general. Section 2 explains some of the choices we made during
implementation and experimental phases. Section 3 and the sub-sections present the quality of the
Monte Carlo Hex player, reasonable values for Monte Carlo repetitions and benefits of using a
game tree, through experimental data. Section 4 discusses limitations of this approach and future
work.
1.1 Motivation
Monte Carlo has been used with great success in many applications. The main advantage of using
Monte Carlo in this setting is that besides the basic dynamics of the game (i.e. players take turns,
only one tile can be marked per move etc) basically no domain knowledge about the game is
necessary, and therefore it could easily be implemented for other similar games, or any decision
making process which can be modeled in a similar fashion.
1.2 About Hex Board Game
Hex is a zero-sum board game, in which two players take turns in making moves. It was invented
in 1942 by Piet Hein and it was independently reinvented and studied in 1947 by John Nash. [2]
Board on which the game is played is rhomboid in shape and is composed of hexagonal tiles with
the same number of rows and columns. Traditionally, Hex is played on boards of size 11x11,
13x13 or larger.
At each turn, player marks a single empty tile by placing a mark, or more traditionally a stone,
making the tile occupied. After a tile gets occupied, the mark cannot be removed and no
additional marks can be put on the tile. This limits the maximum number of moves in a game to
125
35
Fifth International Students Conference on Informatics
–
ICDD 2015
May 21-23, 2015, Sibiu, Romania
the number of tiles on the board. First player’s goal is to connect the two vertical edges of the
board by a path of tiles marked with his marks. The second player has the same goal with the two
horizontal edges. When one of the players achieves this, the game ends.`
Figure 1. Game won by the second player.
Since the first player has great advantage to the second player [2], pie rule is used. According to
the pie rule, the second player can choose to switch positions after the first move has been played.
This removes the first player’s advantage.
One of the properties of the game of Hex is that there are no ties [1]. The game can end before the
maximum number of moves has been played if one of the players connects their respective board
edges by a path of marks. The alternative is to play the maximum number of moves, in which case
a single winning path - from the top to the bottom, or from the left to the right - is formed. More
generally, any random permutation with appropriate proportion of marks for the first and the
second player that covers the entire board will result in a winning path. This property will be
important in the implementation of Monte Carlo simulation Hex player, since it greatly simplifies
the process of evaluation of potential moves.
1.3 Monte Carlo Simulation Method
Monte Carlo simulation method is model evaluation (simulation) method based on random sets of
inputs. Two main aspects of usage are: simulation of models dependent on random factors and
simulation of complex mathematical problems not dependent on random factors, but that could be
simplified via probabilistic estimation. One of most famous usage example is estimating area of
figure A within unit square, by randomly selecting N points, as ratio number of points within A to
N.
Idea of using randomness in deterministic models first appeared in 18th century, as part of
“Buffon's needle” method for evaluating PI number. [3] Officially, Monte Carlo Simulation
method is developed in 1940s by John von Neumann and Stanislav Ulam in Manhattan project.
Appearance of computers led to large usage in variety of fields such as risk evaluation,
weathercast prediction, random walk prediction, fluid dynamics and thermodynamics [5].
Monte Carlo simulation has three steps: create random input sets, evaluate model for each set and
compute statistic of interest. Providing uniform distribution of input sets is essential part of
simulation and often most challenging for implementation. Main advantages of this approach are
126
48
Fifth International Students Conference on Informatics
–
ICDD 2015
May 21-23, 2015, Sibiu, Romania
its simplicity and speed as creating large number of pseudo random input sets is easily done by
computers, and evaluating function is trivial in most cases.
In two player deterministic games Monte Carlo Simulation can be as follows: find all possible
moves for player, evaluate all of them using Monte Carlo simulation method and choose best
evaluated. This approach can be extended with optimal move “search tree” where Monte Carlo
simulation is used for evaluation of leaves. This version of algorithm is called Monte Carlo
Search algorithm and is successfully used in games such as GO, Backgammon and Scrabble. [4]
2 Implementation Choices and Simplifications
The main simplification that was made was not implementing the pie rule. Rationale behind this
decision was that the pie rule only applies to the first move, and this decision - to switch or not -
is a completely different problem from the rest of the game, and the two should be analyzed
separately. Pie rule could be implemented easily, but it would add complexity that is not
necessary for the purposes of this paper.
Naive Monte Carlo approach for deciding the best move for the player is given by the following
simple algorithm:
procedure MonteCarloNaive
For each empty tile on the board do
Place a temporary mark on the tile
For i := 1 to N do
Fill the rest of the board randomly
If current player won then
wins = wins + 1;
Remove the random marks
Remove the temporary mark from the tile
end
return tile with the highest number of wins
This algorithm uses the fact that a completely filled board has exactly one winner. [1] It checks
each of the next possible moves by generating N random outcomes of the game for each of them
and chooses the one with the highest number of winning positions for the given player. Although
these outcomes are random, and unlike games with real players, are not produced by intelligent
decision making, they are a sufficient approximation of player’s chances of winning on a given
board.
Finally, all experimental data presented in this paper was gathered on 7x7 boards. This was done
for simplicity and easy comparison, as well as shorter execution times, since execution time is
superlinear with regard to board size.
3 Experimental results
3.1 Quality of Monte Carlo Simulation Hex Player
The quality of the player was tested in two ways: by playing games against human players, and by
playing games with other Monte Carlo players, with varying number of repetitions for the
opponents.
When playing against human players, if the number of repetitions is set to 2500 or more, Monte
Carlo player always wins. It is worth mentioning that none of the human players are expert Hex
players, but this is definitely indicative of the quality of the Monte Carlo player.
127
72
Fifth International Students Conference on Informatics
–
ICDD 2015
May 21-23, 2015, Sibiu, Romania
Games involving two Monte Carlo players also show expected behaviour. Since pie rule was not
implemented, first player has the advantage. Figure 2 shows the results of games played between
different Monte Carlo players.
first player
second player
# of games
1st player won
ratio
500
500
200
152
0.76
1000
1000
200
165
0.825
3000
3000
200
185
0.925
5000
5000
200
194
0.97
7000
7000
200
195
0.975
10000
10000
200
199
0.995
13000
13000
200
199
0.995
Figure 2. Results of games between two Monte Carlo players
It is apparent that as the number of Monte Carlo repetitions increases, so does the ratio of first
player’s wins to the total number of games played.
Also, inspecting games move by move shows reasonable choices from both Monte Carlo players.
3.2 Diminishing Returns in Monte Carlo Simulation Repetitions
Naive Monte Carlo search algorithm described in Section 2 will perform better when N, the
number of repetitions, is higher. This is due to the fact that adding more repetitions is equivalent
to sampling more future moves of both players. If every possible permutation could be explored,
the algorithm would be completely deterministic. Of course, this is prohibitively expensive in
terms of CPU time, and therefore the number of possible outcomes per move that gets sampled by
the algorithm is much smaller than the number of all possible outcomes. However, the previous
section shows that even this very limited sampling yields good results, and the following question
can be posed: how many Monte Carlo repetitions are necessary so that increasing their number
produces negligible benefits in terms of decision quality?
Previous section shows that increasing the number of repetitions after 10000 does not improve
player’s performance. Also choosing a number of repetitions below 500 leads to poor quality of
moves chosen by Monte Carlo.
When determining optimal number of Monte Carlo repetitions, the following procedure was used.
Number of Monte Carlo simulation repetitions started from 500 and at each step was increased by
5 percent. There were 62 such steps, and the greatest number of repetitions observed was 9813. In
each step one hundred randomly generated boards were evaluated. These boards are chosen
randomly for given number of moves played i.e. how many first and second player’s marks are
there on the board. Same boards are evaluated at each step. Boards are evaluated as probability
that player that made last move on board wins game.
128
158
Fifth International Students Conference on Informatics
–
ICDD 2015
May 21-23, 2015, Sibiu, Romania
Figure 3. Single board evaluated by different Monte Carlo players
Figure 3. shows chart for a typical board. Even with number of repetitions below 1000 all
probabilities are within 0.5% range. As number of repetitions grows variance of results decreases.
For number of repetitions 3000 and greater probabilities are within range of 0.02%.
# of Monte Carlo repetitions
1000
3000
5000
# of move
goal prob
min
prob
max prob
stdev
mean
ratio
stdev
mean
ratio
stdev
mean
ratio
3
0.56902
0.56624
0.57270
0.00116
0.56988
0.15150
0.00077
0.56942
0.07051
0.00061
0.56892
0.01740
3
0.60952
0.60531
0.61216
0.00105
0.60774
0.29325
0.00078
0.60916
0.05991
0.00072
0.60928
0.04054
5
0.56644
0.56357
0.56864
0.00083
0.56632
0.02110
0.00059
0.56640
0.00742
0.00047
0.56589
0.09761
5
0.56086
0.55797
0.56455
0.00110
0.56045
0.07284
0.00090
0.56212
0.22362
0.00082
0.56013
0.12981
13
0.47075
0.46773
0.47198
0.00089
0.47065
0.02085
0.00083
0.46983
0.19503
0.00049
0.47058
0.03586
13
0.50621
0.50377
0.51005
0.00107
0.50656
0.07046
0.00081
0.50666
0.09014
0.00044
0.50687
0.13196
17
0.51385
0.50940
0.51741
0.00087
0.51378
0.01288
0.00070
0.51405
0.03982
0.00072
0.51350
0.06722
23
0.40901
0.40467
0.41204
0.00083
0.40814
0.21161
0.00057
0.40896
0.01281
0.00057
0.40882
0.04499
29
0.69701
0.69438
0.70005
0.00105
0.69745
0.06284
0.00077
0.69739
0.05508
0.00045
0.69679
0.03118
29
0.37759
0.37337
0.38058
0.00076
0.37568
0.50538
0.00063
0.37737
0.05775
0.00033
0.37692
0.17744
Figure 4. Statistical parameters for different Monte Carlo players
129
Documents you may be interested
Documents you may be interested
