以基因規劃法與蒙地卡羅樹搜尋設計卡牌遊戲策略—以爐石戰記為例

Abstract

收集類卡牌遊戲 (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對戰，以評估本論文所提出之策略的效能。透過分析基因規劃法的染色體結構，我們能了解哪些盤面資訊對爐石戰記的出牌策略是重要的，也能讓爐石戰記玩家快速的了解並參考獲勝的關鍵策略。我們也希望在未來能將此研究方法應用在其它遊戲中。none