- 學位論文
以基因規劃法與蒙地卡羅樹搜尋設計卡牌遊戲策略—以爐石戰記為例
Designing Card Game Strategies with Genetic Programming and Monte-Carlo Tree Search — A Case Study of Hearthstone
摘要
收集類卡牌遊戲 (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.