收集類卡牌遊戲 (Collectible Card Games, CCG) 的AI研究在近年來逐漸火熱，而爐石戰記 (Hearthstone) 是目前全世界最熱門的線上卡牌遊戲 ，在2018年底已經超過一億名玩家。本論文將透過基因規劃法 (Genetic Programming, GP) 產生爐石戰記的出牌策略，目的是希望僅使用基本的爐石戰記領域知識 (domain knowledge) 就能自動化地演化出不錯的出牌策略。並進一步將此策略套用在蒙地卡羅樹搜尋 (Monte-Carlo Tree Search, MCTS) 的模擬策略中，以提升MCTS之效能。此外，為了改善本論文基因規劃法評估時間過長的問題，我們使用昂貴優化中的適應值近似法減少了10% - 20% 的實驗時間。最後，我們將與COG 2019 爐石比賽第 1 名以及CIG 2018爐石比賽第10名的AI對戰，以評估本論文所提出之策略的效能。透過分析基因規劃法的染色體結構，我們能了解哪些盤面資訊對爐石戰記的出牌策略是重要的，也能讓爐石戰記玩家快速的了解並參考獲勝的關鍵策略。我們也希望在未來能將此研究方法應用在其它遊戲中。

[1]遊戲王 - 怪獸之決鬥 (Yu-Gi-Oh! Duel Monsters) https://en.wikipedia.org/wiki/ Yu-Gi-Oh!_Duel_Monsters
[2]魔法風雲會 (Magic: The Gathering) https://magic.wizards.com/zh-hant
[3]爐石戰記 (Hearthstone) https://playhearthstone.com/zh-tw/
[4]J. R. Koza,“Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems,”Report No. STANCS-90-1314, Stanford University, Stanford, CA, 1990.
[5]J. R. Koza,“Genetic programming: on the programming of computers by means of natural selection,”MIT Press, Cambridge, MA, 1992.
[6]M. Bhattacharya,“Evolutionary approaches to expensive optimisation,”International Journal of Advanced Research in Artificial Intelligence, vol. 2, no. 3, pp. 53–59, 2013.
[7]A. Esparcia-Alcazar and J. Moravec,“Fitness approximation for bot evolution in genetic programming,”Soft Computing, vol. 17, no. 8, pp. 1479–1487, 2013.
[8]Unreal Tournament 2004 (UT2004) https://en.wikipedia.org/wiki/Unreal_Tournament_2004
[9]R. Coulom,“Efficient selectivity and backup operators in Monte-Carlo tree search,”International Conference on Computers and Games, pp. 29–31, 2006.
[10]C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton,“A survey of Monte-Carlo tree search methods,”IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 1, pp. 1–43, 2012.
[11]P. Auer, N. Cesa-Bianchi, and P.Fischer,“Finite-time analysis of the multiarmed bandit problem,”Machine Learning, vol. 47, no. 2, pp. 235–256, 2002.
[12]L. Kocsis and C. Szepesvári, “Bandit based Monte-Carlo planning,” European Conference on Machine Learning, pp. 282–293, 2006.
[13]A. Dockhorn, M. Frick, U. Akkaya, and R. Kruse, “Predicting opponent moves for improving hearthstone AI,” International Conference on Information Processing and Management of Uncertainty in KnowledgeBased Systems, pp. 621–632, 2018.
[14]A. Saffidine, T. Cazenave, and J. Méhat,“UCD: Upper confidence bound for rooted directed acyclic graphs,”Knowledge-Based Systems, vol. 34, pp. 26–33, 2012.
[15]J. S. B. Choe and J. Kim,“Enhancing monte carlo tree search for playing hearthstone,”IEEE Conference on Games, pp. 1–7, 2019.
[16]M. Kearns, Y. Mansour, and A. Y. Ng, “A sparse sampling algorithm for near-optimal planning in large Markov decision processes,”International Joint Conference on Artificial Intelligence, pp. 1224–1231, 1999.
[17]S. Zhang and M. Buro,“Improving hearthstone AI by learning high-level rollout policies and bucketing chance node events,”IEEE Conference on Computational Intelligence and Games, pp. 309–316, 2017.
[18]M. Swiechowski, T. Tajmajer, and A. Janusz,“Improving hearthstone AI by combining mcts and supervised learning algorithms,”IEEE Conference on Computational Intelligence and Games, pp. 1–8, 2018.
[19]A. Santos, P. A. Santos, and F. S. Melo, “Monte-Carlo tree search experiments in hearthstone,”IEEE Conference on Computational Intelligence and Games, pp. 272–279, 2017.
[20]P. García-Sánchez, A. Tonda, A. J. Fernández-Leiva, and C. Cotta,“Optimizing Hearthstone agents using an evolutionary algorithm,”Knowledge-Based Systems, 2019.
[21]M. A. Potter and K. A. De Jong,“Cooperative coevolution: An architecture for evolving coadapted subcomponents,”Evolutionary Computation, vol. 8, no. 1, pp. 1–29, 2000.
[22]CIG Hearthstone 2018, COG Hearthstone 2019, and 2020. https://dockhorn.antares.uberspace.de/wordpress/
[23]C. D. Ward and P. I. Cowling, “Monte-Carlo search applied to card selection in magic: the gathering,”IEEE Symposium on Computational Intelligence in Games, pp. 9–16, 2009.
[24]P. I. Cowling, C. D. Ward, and E. J. Powley, Ensemble determinization in monte carlo tree search for the imperfect information card game magic: The gathering,”IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 4, pp. 241–257, 2012.
[25]B. E. Childs, J. H. Brodeur, and L. Kocsis,“Transpositions and move groups in Monte-Carlo tree search,”IEEE Symposium on Computational Intelligence and Games, Perth, Australia, pp. 389–395, 2008.
[26]P. García-Sánchez, A. Tonda, G. Squillero, A. Mora, and J. Merelo,“Evolutionary deckbuilding in hearthstone,”IEEE Conference on Computational Intelligence and Games, pp. 1–8, 2016.
[27]P. García-Sánchez, A. Tonda, A. M. Mora, G. Squillero, and J. J. Merelo,“Automated playtesting in collectible card games using evolutionary algorithms: A case study in hearthstone,”Knowledge-Based Systems, vol. 153, pp. 133–146, 2018.
[28]SabberStone, https://github.com/HearthSim/SabberStone
[29]L. Piotrowski , S. Mittenentzwei , and T. Heimbrodt, https://dockhorn.antares.uberspace.de/wordpress/bot-downloads/
[30]E. Håkonsen, 2018, Available: https://www.reddit.com/r/hearthstone/comments/7l1ob0/i_wrote_a_masters_thesis_on_effective_hearthstone/
[31]A. M. Alhejali and S. M. Lucas,“Using genetic programming to evolve heuristics for a Monte-Carlo tree search Ms Pac-Man agent,”IEEE Conference on Computational Intelligence and Games, pp. 65–72, 2013.
[32]D.E. Knuth and R.W. Moore,“An analysis of alpha-beta pruning.”Artificial Intelligence, vol. 6, no. 4, pp. 293–326, 1975.
[33]A. Benbassat and M. Sipper,“EvoMCTS: Enhancing MCTSbased Players Through Genetic Programming.”IEEE Conference on Computational Intelligence and Games, pp. 57–64, 2013.