An analysis for strength improvement of an MCTS-based program playing Chinese dark chess

作者：Hsueh Chu Hsuan; Wu I Chen^*; Tseng Wen Jie; Yen Shi Jim; Chen Jr Chang

来源：Theoretical Computer Science, 2016, 644: 63-75.

DOI：10.1016/j.tcs.2016.06.025

• Monte Carlo tree search
• Chinese dark chess
• Early playout terminations
• Implicit minimax backups
• Quality-based rewards
• Progressive bias

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.

• 出版日期2016-9-6
• 单位东华大学