Abstract
Games pose many interesting questions for the development of artificial intelligence agents. Especially popular are methods that guide the decision-making process of an autonomous agent, which is tasked to play a certain game. In previous studies, the heuristic search method Monte Carlo Tree Search (MCTS) was successfully applied to a wide range of games. Results showed that this method can often reach playing capabilities on par with humans or even better. However, the characteristics of collectible card games such as the online game Hearthstone make it infeasible to apply MCTS directly. Uncertainty in the opponent’s hand cards, the card draw, and random card effects considerably restrict the simulation depth of MCTS. We show that knowledge gathered from a database of human replays help to overcome this problem by predicting multiple card distributions. Those predictions can be used to increase the simulation depth of MCTS. For this purpose, we calculate bigram-rates of frequently co-occurring cards to predict multiple sets of hand cards for our opponent. Those predictions can be used to create an ensemble of MCTS agents, which work under the assumption of differing card distributions and perform simulations according to their assigned distribution. The proposed ensemble approach outperforms other agents on the game Hearthstone, including various types of MCTS. Our case study shows that uncertainty can be handled effectively using predictions of sufficient accuracy, ultimately, improving the MCTS guided decision-making process. The resulting decision-making based on such an MCTS ensemble proved to be less prone to errors by uncertainty and opens up a new class of MCTS algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
“Blizzard Entertainment”: Hearthstone Webpage. https://playhearthstone.com/en-gb/0. Accessed 06 Mar 2017
Browne, C.B., Powley, E., Whitehouse, D., Lucas, S.M., Cowling, P.I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of monte carlo tree search methods. IEEE Trans. Comput. Intelli. AI Games 4(1), 1–43 (2012). https://doi.org/10.1109/TCIAIG.2012.2186810
Bursztein, E.: I am a legend: hacking hearthstone using statistical learning methods. In: 2016 IEEE Conference on Computational Intelligence and Games (CIG), pp. 1–8. IEEE, September 2016. https://doi.org/10.1109/CIG.2016.7860416
“Collect-o-Bot”: Hearthstone Replay Database. http://www.hearthscry.com/CollectOBot. Accessed 06 Mar 2017
“darkfriend77”: Sabberstone Github Repository. https://github.com/HearthSim/SabberStone. Accessed 06 Mar 2018
“demilich1”: Metastone Github Repository. https://github.com/demilich1/metastone. Accessed 06 Mar 2017
Dockhorn, A., Doell, C., Hewelt, M., Kruse, R.: A decision heuristic for Monte Carlo tree search doppelkopf agents. In: 2017 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1–8. IEEE, November 2017. https://doi.org/10.1109/SSCI.2017.8285181
Dockhorn, A., Mostaghim, S.: Hearthstone AI Competition. http://www.is.ovgu.de/Research/HearthstoneAI.html. Accessed 06 Mar 2018
Grad, Ł.: Helping AI to play hearthstone using neural networks. In: Ganzha, M., Maciaszek, L., Paprzycki, M. (eds.) Proceedings of 2017 Federated Conference on Computer Science and Information Systems, vol. 11, pp. 131–134, Sepember 2017. https://doi.org/10.15439/2017F561
HearthSim Project: Hearthsim Webpage Hearthstone Simulation & AI. https://hearthsim.info/. Accessed 06 Mar 2017
Janusz, A., Świechowski, M., Zieniewicz, D., Stencel, K., Puczniewski, J., Mańdziuk, J., Ślęzak, D.: AAIA’17 Data Mining Challenge: Helping AI to Play Hearthstone. https://knowledgepit.fedcsis.org/contest/view.php?id=120. Accessed 06 Mar 2017
Kocsis, L., Szepesvári, C.: Bandit based Monte-Carlo planning. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol. 4212, pp. 282–293. Springer, Heidelberg (2006). https://doi.org/10.1007/11871842_29
Santos, A., Santos, P.A., Melo, F.S.: Monte Carlo tree search experiments in hearthstone. In: 2017 IEEE Conference on Computational Intelligence and Games (CIG), pp. 272–279. IEEE (2017). https://doi.org/10.1109/CIG.2017.8080446
Tzourmpakis, G.: Hearthagent, a Hearthstone Agent, Based on the Metastone Project. http://www.intelligence.tuc.gr/~robots/ARCHIVE/2015w/Projects/LAB51326833/. Accessed 06 Mar 2017
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Dockhorn, A., Frick, M., Akkaya, Ü., Kruse, R. (2018). Predicting Opponent Moves for Improving Hearthstone AI. In: Medina, J., et al. Information Processing and Management of Uncertainty in Knowledge-Based Systems. Theory and Foundations. IPMU 2018. Communications in Computer and Information Science, vol 854. Springer, Cham. https://doi.org/10.1007/978-3-319-91476-3_51
Download citation
DOI: https://doi.org/10.1007/978-3-319-91476-3_51
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-91475-6
Online ISBN: 978-3-319-91476-3
eBook Packages: Computer ScienceComputer Science (R0)