Monte-Carlo Tree Reductions for Stochastic Games - Technologies and Applications of Artificial Intelligence - page 236

In the third experiment, we evaluate the contribution of chance-nodes by
gradually introducing random moves. The figure 2 shows the performance of
chance-nodes-mm against himself. The second player is weakened with a ran-
dom move during X first turns. Players are evaluated in 500 games, with 1[sec]
per move, from 0 to 35 random moves. It shows that performances are equal
when chance-nodes-mm plays randomly during its 10 first moves. After 10 first
random moves, losts increase and draws decrease. It shows chance-nodes contri-
bution while some unrevealed pieces remain. After 20 turns, the game has more
chance to be fully revealed. It shows that similar gain is achieved in the perfect
information part of the game. As there are 32 unrevealed positions at the begin-
ning of the game, chance-nodes contributes effectively at least in managing 12
unrevealed pieces.

5Con lu on

Monte-Carlo Tree Search (MCTS) is a powerful paradigm for perfect informa-
tion games. When considering stochastic games, the tree model that represents
the game has to take chance and a huge branching factor into account. We have
presented 3 ways to regroup nodes and their consequences to

algorithm
and the descent function. We have compared different regrouping policies and
different generating policies in

MCTS

games. Experiments show
that without heuristic function evaluation, chance-nodes regrouping policy is the
best for the stochastic part of the game and that adding minimax search in the
perfect information part of the game improves all players.

Chinese Dark Chess

References

1. Yen, S.-J., Chou, C.-W., Chen, J.-C., Wu, I.-C., Kao, K.-Y.: The Art of the Chinese
Dark Chess Program DIABLE. In: Chang, R.-S., Jain, L.C., Peng, S.-L. (eds.) Ad-
vances in Intelligent Systems & Applications. SIST, vol. 20, pp. 231-242. Springer,
Heidelberg (2013)
2. Chen, B.-N., Hsu, T.-S.: Automatic Generation of Chinese Dark Chess Opening
Books. In: 8th Int. Conf. on Computers and Games (CG 2013) (2013)
3. Chen, J.-C., Lin, T.-Y., Hsu, S.-C., Hsu, T.-S.: Design and Implementation of
Computer Chinese Dark Chess Endgame Database. In: TCGA Computer Game
Workshop (TCGA 2012) (2012)
4. Sadine, A., Jouandeau, N., Buron, C., Cazenave, T.: Material Symmetry to Par-
tition Endgame Tables. In: 8th Int. Conf. on Computers and Games (CG 2013)
(2013)
5. Chen, J.-C., Lin, T.-Y., Chen, B.-N., Hsu, T.-S.: Equivalence Classes in Chinese
Dark Chess Endgames. IEEE Trans. on Computational Intelligence and AI in
Games (TCIAIG-2014) (2014)
6. Chang, H.-J., Hsu, T.-S.: A quantitative study of 2 × 4 chinese dark chess. In: van
den Herik, H.J., Iida, H., Plaat, A. (eds.) CG 2013. LNCS, vol. 8427, pp. 151-162.
Springer, Heidelberg (2014)
7. Chen, B.-N., Shen, B.-J., Hsu, T.-S.: Chinese Dark Chess. ICGA Journal 33(2), 93
(2010)