Skip to main content
SpringerLink
Log in

The Many AI Challenges of Hearthstone

  • Technical Contribution
  • Published:
KI - Künstliche Intelligenz Aims and scope Submit manuscript

Abstract

Since the inception of artificial intelligence, games have benchmarked algorithmic advances. Recent success in classic board games such as Chess and Go have left space for video games that pose related yet different sets of challenges. With this shifted focus, the set of AI problems associated with video games has expanded from simply playing these games to win, to include playing games in particular styles, generating game content, modeling players, etc. Different games pose different challenges for AI systems, and several such AI challenges can typically be addressed in the same game. In this article we analyze the popular collectible card game Hearthstone published by Blizzard in 2014, and describe a varied set of interesting AI challenges it poses. Despite their popularity and associated interesting challenges, collectible card games are relatively understudied in the AI community. By analyzing a single game in-depth, we get a glimpse of the entire field of AI and games through the lens of a single game, discovering a few new variations on existing research topics.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. https://hearthsim.info/.

  2. https://github.com/HearthSim/SabberStone.

  3. A subreddit is a sub-forum on the website Reddit. Each subreddit is dedicated to a specific topic.

  4. https://github.com/demilich1/metastone.

  5. https://github.com/hiddenswitch/Spellsource-Server.

  6. https://github.com/fatheroctopus/hdt-deck-predictor.

  7. https://hsreplay.net/downloads/.

  8. https://github.com/HearthSim/archetypes.

  9. https://github.com/rembound/Arena-Helper.

  10. http://thelightforge.com/TierList.

References

  1. Abrakam (2017) Faeria, Angleur

  2. Agrawal R, Srikant R (1994) Fast algorithms for mining association rules. In: Proceedings of the 20th international conference on very large data bases, VLDB, vol 1215, pp 487–499

  3. Aponte M-V, Levieux G, Natkin S (2009) Scaling the level of difficulty in single player video games. In: Natkin S, Dupire J (eds) Entertainment computing – ICEC 2009. ICEC 2009. Lecture notes in computer science, vol 5709. Springer, Berlin, pp 24–35

  4. Bellemare MG, Naddaf Y, Veness J, Bowling M (2013) The arcade learning environment: an evaluation platform for general agents. J Artif Intell Res 47:253–279

    Article  Google Scholar 

  5. Bethesda Softworks (2017) The elder scrolls: legends

  6. Bhatt A, Lee S, de Mesentier Silva F, Watson CW, Togelius J, Hoover AK (2018) Exploring the Hearthstone deck space. In: Proceedings of the 13th international conference on the foundations of digital games (FDG). ACM, pp 18:1–18:10

  7. Blizzard Entertainment (2014) Hearthstone, Irvine, CA

  8. Browne C (2011) Evolutionary game design. SpringerBriefs in computer science, Springer, London, pp 75–85

  9. Bursztein E (2016) I am a legend: hacking Hearthstone using statistical learning methods. In: Proceedings of the 2016 IEEE Conference on Computational Intelligence and Games (CIG), pp 1–8

  10. Cai X, Wunsch DC (2007) Computer go: a grand challenge to AI. In: Challenges for computational intelligence. Springer, Berlin, pp 443–465

  11. CD Projekt and CD Projekt RED (2019) Gwent: the witcher card game

  12. Coulom R (2006) Efficient selectivity and backup operators in Monte-Carlo tree search. In: Proceedings of the international conference on computers and games. Springer, pp 72–83

  13. Cully A, Clune J, Tarapore D, Mouret J-B (2015) Robots that can adapt like animals. Nature 521(7553):503

    Article  Google Scholar 

  14. de Mesentier Silva F, Canaan R, Lee S, Togelius J, Hoover AK (2019) Evolving the hearthstone meta. In: Proceedings of the First IEEE Conference on Games (CoG)

  15. de Mesentier Silva F, Isaksen A, Togelius J, Nealen A (2016) Generating heuristics for novice players. In: Proceedings of the 2016 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, pp 1–8

  16. de Mesentier Silva F, Togelius J, Lantz F, Nealen A (2018) Generating beginner heuristics for simple Texas Hold’em. In: Proceedings of the 2018 genetic and evolutionary computation conference (GECCO). ACM, pp 181–188

  17. de Mesentier Silva F, Togelius J, Lantz F, Nealen A (2018) Generating novice heuristics for post-flop poker. In: Proceedings of the 2018 IEEE conference on computational intelligence and games (CIG). IEEE, pp 1–8

  18. Dockhorn A, Frick M, Akkaya Ü, Kruse R (2018) Predicting opponent moves for improving Hearthstone AI. In: Proceedings of the 18th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems. Springer, pp 621–632

  19. Dire Wolf Digital LLC (2016) Eternal

  20. Drachen A, Sifa R, Bauckhage C, Thurau C (2012) Guns, swords and data: Clustering of player behavior in computer games in the wild. In: Proceedings of the 2012 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, pp 163–170

  21. Ecoffet A, Huizinga J, Lehman J, Stanley KO, Clune J (2019) Go-explore: a new approach for hard-exploration problems. arXiv preprint arXiv:1901.10995

  22. Elias GS, Garfield R, Gutschera KR (2012) Characteristics of games. MIT Press, Cambridge

    Google Scholar 

  23. Ensmenger N (2012) Is chess the drosophila of artificial intelligence? A social history of an algorithm. Soc Stud Sci 42(1):5–30

    Article  Google Scholar 

  24. Fontaine MC, Lee S, Soros LB, Silva FDM, Togelius J, Hoover AK (2019) Mapping Hearthstone deck spaces through MAP-Elites with sliding boundaries. In: Proceedings of the 2019 Genetic and Evolutionary Computation Conference (GECCO). ACM

  25. García-Sánchez P, Tonda A, Squillero G, Mora A, Merelo JJ (2016) Evolutionary deckbuilding in Hearthstone. In: Proceedings of the 2016 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, pp 1–8

  26. García-Sánchez P, Tonda A, Mora AM, Squillero G, Merelo JJ (2018) Automated playtesting in collectible card games using evolutionary algorithms: a case study in Hearthstone. Knowl Based Syst 153:133–146

    Article  Google Scholar 

  27. Gobet F, Simon HA (1996) The roles of recognition processes and look-ahead search in time-constrained expert problem solving: evidence from grand-master-level chess. Psychol Sci 7(1):52–55

    Article  Google Scholar 

  28. Góes LFW, Da Silva AR, Saffran J, Amorim A, França C, Zaidan T, Olímpio BMP, Alves LRO, Morais H, Luana S et al (2017) Honingstone: building creative combos with honing theory for a digital card game. IEEE Trans Comput Intell AI Games 9(2):204–209

    Article  Google Scholar 

  29. Green MC, Khalifa A, Barros GAB, Machado T, Nealen A, Togelius J (2018) AtDELFI: automatically designing legible, full instructions for games. In: Proceedings of the 13th international conference on the foundations of digital games (FDG). ACM, p 17

  30. Guzdial M, Liao N, Riedl M (2018) Co-creative level design via machine learning. Fifth Experimental AI in Games Workshop (EXAG). arXiv preprint arXiv:1809.09420

  31. Hodge V, Sephton N, Devlin S, Cowling P, Goumagias N, Shao J, Purvis K, Cabras I, Fernandes K, Li F (2019) How the business model of customisable card games influences player engagement. IEEE Trans Games. https://doi.org/10.1109/tg.2018.2803843

  32. Holmgard C, Green MC, Liapis A, Togelius J (2018) Automated playtesting with procedural personas with evolved heuristics. IEEE Trans Games. https://doi.org/10.1109/TG.2018.2808198

  33. Holmgård C, Liapis A, Togelius J, Yannakakis GN (2014) Evolving personas for player decision modeling. In: Proceedings of the 2014 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, pp 1–8

  34. Hoover AK, Szerlip PA, Stanley KO (2014) Functional scaffolding for composing additional musical voices. Comput Music J 38(4):80–99

    Article  Google Scholar 

  35. Jakubik J (2018) A neural network approach to Hearthstone win rate prediction. In: Proceedings of the 2018 federated conference on computer science and information systems (FedCSIS). IEEE, pp 185–188

  36. Janusz A, Świechowski M, Tajmajer T (2017) Helping AI to play Hearthstone: AAIA’17 data mining challenge. arXiv preprint arXiv:1708.00730

  37. Janusz A, Tajmajer T, Świechowski M, Grad Ł, Puczniewski J, Ślȩzak D (2018) Toward an intelligent HS deck advisor: lessons learned from AAIA’18 data mining competition. In: Proceedings of the 2018 federated conference on computer science and information systems (FedCSIS). IEEE, pp 189–192

  38. Kasparov G (2017) Deep thinking: where machine intelligence ends and human creativity begins. Public Affairs

  39. Liapis A, Yannakakis GN, Togelius J (2013) Sentient sketchbook: computer-aided game level authoring. In: Proceedings of the 8th Conference on the Foundations of Digital Games (FDG), pp 213–220

  40. Ling W, Grefenstette E, Hermann KM, Kočiskỳ T, Senior A, Wang F, Blunsom P (2016) Latent predictor networks for code generation. arXiv preprint arXiv:1603.06744

  41. Lucas SM (2009) Computational intelligence and AI in games: a new IEEE transactions. IEEE Trans Comput Intell AI Games 1(1):1–3

    Article  Google Scholar 

  42. Machado T, Bravi I, Wang Z, Nealen A, Togelius J (2016) Shopping for game mechanics. In: Proceedings of the 7th workshop on procedural content generation the first joint conference of the joint international conference of DiGRA and FDG

  43. Mahlmann T, Togelius J, Yannakakis GN (2012) Evolving card sets towards balancing dominion. In: Proceeding of the 2012 IEEE congress on evolutionary computation (CEC). IEEE, pp 1–8

  44. Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, Riedmiller M, Fidjeland AK, Ostrovski G et al (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529

    Article  Google Scholar 

  45. Mouret J-B, Clune J (2015) Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909

  46. OpenAI (2018) OpenAI Five. https://blog.openai.com/openai-five/. Accessed 10 June 2019

  47. Santos A, Santos PA, Melo FS (2017) Monte carlo tree search experiments in Hearthstone. In: Proceedings of the 2017 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, pp 272–279

  48. Shaker N, Shaker M, Togelius J (2013) Ropossum: an authoring tool for designing, optimizing and solving cut the rope levels. In: Proceedings of the ninth AAAI conference on artificial intelligence and interactive digital entertainment

  49. Shannon CE (1950) XXII. Programming a computer for playing chess. Lond Edinb Dublin Philos Mag J Sci 41(314):256–275

    Article  Google Scholar 

  50. Silver D, Huang A, Maddison CJ, Guez A, Sifre L, Van Den Driessche G, Schrittwieser J, Antonoglou I, Panneershelvam V, Lanctot M et al (2016) Mastering the game of Go with deep neural networks and tree search. Nature 529(7587):484

    Google Scholar 

  51. Smith G, Whitehead J, Mateas M (2011) Tanagra: Reactive planning and constraint solving for mixed-initiative level design. IEEE Trans Comput Intell AI Games 3(3):201–215

    Article  Google Scholar 

  52. Spronck P, Sprinkhuizen-Kuyper I, Postma E (2004) Difficulty scaling of game AI. In: Proceedings of the 5th International Conference on Intelligent Games and Simulation (GAME-ON 2004), pp 33–37

  53. Stiegler A, Dahal K, Maucher J, Livingstone D (2017) Symbolic reasoning for Hearthstone. IEEE Trans Comput Intell AI Games 10(2):113-127

    Article  Google Scholar 

  54. Stiegler A, Messerschmidt C, Maucher J, Dahal K (2016) Hearthstone deck-construction with a Utility System. In: Proceedings of the 2016 10th international conference on software, knowledge, information management & applications (SKIMA). IEEE, pp 21–28

  55. Summerville AJ, Mateas M (2016) Mystical tutor: a magic: the gathering design assistant via denoising sequence-to-sequence learning. In: Twelfth artificial intelligence and interactive digital entertainment conference

  56. Supercell (2012) Clash of clans

  57. Świechowski M, Tajmajer T, Janusz A (2018) Improving Hearthstone AI by combining MCTS and supervised learning algorithms. arXiv preprint arXiv:1808.04794

  58. Turing AM (1953) Digital computers applied to games. Faster than Thought, Pitman

  59. van Lankveld G, Spronck P, Rauterberg M (2008) Difficulty scaling through incongruity. In: Proceedings of the Fourth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment

  60. Vinyals O, Babuschkin I, Chung J, Mathieu M, Jaderberg M, Czarnecki WM, Dudzik A, Huang A, Georgiev P, Powell R, Ewalds T, Horgan D, Kroiss M, Danihelka I, Agapiou J, Oh J, Dalibard V, Choi D, Sifre L, Sulsky Y, Vezhnevets S, Molloy J, Cai T, Budden D, Paine T, Gulcehre C, Wang Z, Pfaff T, Pohlen T, Wu Y, Yogatama D, Cohen J, McKinney K, Smith O, Schaul T, Lillicrap T, Apps C, Kavukcuoglu K, Hassabis D, Silver D (2019) AlphaStar: mastering the real-time strategy game StarCraft II. https://deepmind.com/blog/alphastar-mastering-real-time-strategy-game-starcraft-ii/. Accessed 20 Apr 2019

  61. Ward CD, Cowling PI (2009) Monte carlo search applied to card selection in magic: the gathering. In: 2009 IEEE symposium on computational intelligence and games (CIG). IEEE, pp 9–16

  62. Wizards of the Coast (1993) Magic: the gathering, Renton, Washington

  63. Yannakakis GN, Liapis A, Alexopoulos C (2014) Mixed-initiative co-creativity. In: Proceedings of the 9th Conference on the Foundations of Digital Games (FDG)

  64. Yannakakis GN, Togelius J (2018) Artificial intelligence and games. Springer, Berlin

    Book  Google Scholar 

  65. Yee N (2006) Motivations for play in online games. CyberPsychol Behav 9(6):772–775

    Article  Google Scholar 

  66. Zhang S, Buro M (2017) Improving Hearthstone AI by learning high-level rollout policies and bucketing chance node events. In: Proceedings of the 2017 IEEE conference on computational intelligence and games (CIG). IEEE, pp 309–316

  67. Zopf M (2015) A comparison between the usage of flat and structured game trees for move evaluation in Hearthstone. Master, Technische Universität Darmstadt, Darmstadt, Germany

Download references

Acknowledgements

Thanks to Matthew Fontaine, Rodrigo Canaan, Aditya Bhatt, Connor Watson, Param Trivedi for their contributions to research that has informed this paper. Additionally, we thank Andy Nealen and Alex Zook for useful discussions. Finally, we are happy that all the hours we spent playing the game could contribute to something useful, or at least publishable.

Author information

Authors and Affiliations

  1. New Jersey Institute of Technology, 323 Dr Martin Luther King Jr Blvd, Newark, NJ, 07102, USA

    Amy K. Hoover

  2. New York University, 6 MetroTech Center, Brooklyn, NY, 11201, USA

    Julian Togelius

  3. Irvine, USA

    Scott Lee

  4. Rio de Janeiro, Brazil

    Fernando de Mesentier Silva

Authors
  1. Amy K. Hoover
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Julian Togelius
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Scott Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Fernando de Mesentier Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amy K. Hoover.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hoover, A.K., Togelius, J., Lee, S. et al. The Many AI Challenges of Hearthstone. Künstl Intell 34, 33–43 (2020). https://doi.org/10.1007/s13218-019-00615-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13218-019-00615-z

Keywords

Search

Navigation