Title: An analysis for strength improvement of an MCTS-based program playing Chinese dark chess
Authors: Hsueh, Chu-Hsuan
Wu, I-Chen
Tseng, Wen-Jie
Yen, Shi-Jim
Chen, Jr-Chang
Department of Computer Science
Keywords: Monte Carlo tree search;Chinese dark chess;Early playout terminations;Implicit minimax backups;Quality-based rewards;Progressive bias
Issue Date: 6-Sep-2016
Abstract: Monte Carlo tree search (MCTS) has been successfully applied to many games recently. Since then, many techniques are used to improve the strength of MCTS-based programs. This paper investigates four recent techniques: early playout terminations, implicit minimax backups, quality-based rewards and progressive bias. The strength improvements are analyzed by incorporating the techniques into an MCTS-based program, named DARKKNIGHT, for Chinese Dark Chess. Experimental results showed that the win rates against the original DARKKNIGHT were 60.75%, 71.85%, 59.00%, and 82.10%, respectively for incorporating the four techniques. The results indicated that the improvement by progressive bias was most significant. By incorporating all together, a better win rate of 84.75% was obtained. (C) 2016 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.tcs.2016.06.025
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2016.06.025
Volume: 644
Begin Page: 63
End Page: 75
Appears in Collections:Articles