Strength improvement and analysis for an MCTS-based Chinese dark chess program

Chu Hsuan Hsueh, I-Chen Wu*, Wen Jie Tseng, Shi Jim Yen, Jr Chang Chen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

Monte-Carlo tree search (MCTS) has been successfully applied to Chinese dark chess (CDC). In this paper, we study how to improve and analyze the playing strength of an MCTS-based CDC program, named DARKKNIGHT, which won the CDC tournament in the 17th Computer Olympiad. We incorporate the three recent techniques, early playout terminations, implicit minimax backups, and quality-based rewards, into the program. For early playout terminations, playouts end when reaching states with likely outcomes. Implicit minimax backups use heuristic evaluations to help guide selections of MCTS. Quality-based rewards adjust rewards based on online collected information. Our experiments showed that the win rates against the original DARKKNIGHT were 60.75%, 70.90% and 59.00%, respectively for incorporating the three techniques. By incorporating all together, we obtained a win rate of 76.70%.

Original languageEnglish
Title of host publicationAdvances in Computer Games - 14th International Conference, ACG 2015, Revised Selected Papers
EditorsAske Plaat, Jaap van den Herik, Walter Kosters
PublisherSpringer Verlag
Pages29-40
Number of pages12
ISBN (Print)9783319279916
DOIs
StatePublished - 1 Jan 2015
Event14th International Conference on Advances in Computer Games, ACG 2015 - Leiden, Netherlands
Duration: 1 Jul 20153 Jul 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9525
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Advances in Computer Games, ACG 2015
CountryNetherlands
CityLeiden
Period1/07/153/07/15

Fingerprint Dive into the research topics of 'Strength improvement and analysis for an MCTS-based Chinese dark chess program'. Together they form a unique fingerprint.

Cite this