chap1.tex

\chapter{引言}
\label{section:Introduction}

《炉石传说：魔兽英雄传》（Hearthstone: Heroes of Warcraft，下简称“炉石传说”）是由暴雪娱乐推出的线上集换式卡牌游戏。
2014~年~3~月~11~日，炉石传说登陆~Microsoft Windows~平台并在全世界发行。
此后，炉石传说相继登陆了OS X、iOS和安卓平台，吸引了大批的忠实玩家。
截止至~2015~年的~11~月，炉石传说已拥有超过~4~千万的注册用户，并为暴雪娱乐带来了每月超过~2~千万美金的利润。
与此同时，暴雪娱乐也为炉石传说举办了世界级的比赛以吸引人气。两届炉石传说世界锦标赛分别在~2014~年和~2015~年的暴雪嘉年华上举行，两届的冠军选手均获得了~10~万美元的奖金，奖金池总额更是达到了~25~万美元。
炉石传说在~2014~年游戏大奖（the Game Awards）上被评选为年度最佳手机游戏，并在~2015~年游戏大奖上被提名为年度电子竞技游戏。

作为卡牌游戏，炉石传说也有着像桥牌那样的随机性和不完全信息性。与桥牌等传统扑克牌游戏不同的是，玩家在炉石传说中使用的卡组不是固定的标准卡组，而是由玩家根据情况自行构建的卡组。炉石传说中的卡牌都能够在不同程度上改变游戏的规则，不同卡牌之间的相互影响更是大大提高了游戏的灵活性。在本论文所讨论的炉石传说构筑模式中，玩家需要从炉石传说的所有可用的卡牌中选取出~30~张卡牌构成自己的卡组。而炉石传说中所有可用的所有卡牌种数已经达到了~743~种，且每年均会有~$200\sim300$~ 张新的卡牌被加入到游戏中。游戏本身有着极高的多样性，不同的卡组可能意味着完全不同的打法，因此要开发一个相对有竞争力的炉石传说人工智能更类似于开发一个普适游戏人工智能（General Game Playing）\cite{cadiaplayer}。本质上，炉石传说的核心规则其实极为简单，其规则的多样性主要来自于卡组的变化。由此，炉石传说十分适合作为不完全信息游戏、随机游戏以及普适游戏的人工智能领域的研究对象。

这篇论文将讨论如何用蒙特卡洛方法搜索炉石传说的最优策略。基于蒙特卡洛方法的炉石传说智能体将与基于规则的智能体进行相互对弈，以判明何种数量的对弈模拟可以使得蒙特卡洛智能体拥有与规则智能体同等的对弈能力。在实验中，蒙特卡洛智能体会先使用较弱的（随机）智能体进行模拟，以验证在模拟数量足够大的情况下，蒙特卡洛智能体是否能打败较强的规则智能体；而后，规则智能体将作为蒙特卡洛智能体的模拟策略，以验证在为蒙特卡洛智能体的模拟策略加入启发知识的情况下，蒙特卡洛智能体的对弈能力是否能有所提高。

\section{研究现状}
\label{section:RelatedWork}

卡牌游戏是典型的不完全信息随机游戏，其中包括了对手手牌的不可见信息以及洗牌后随机的牌堆出牌顺序。信息隐藏与随机性两者相结合，使得卡牌游戏对于人类玩家或是人工智能开发来说都是十分有趣的领域~\cite{bowling2008strategy}。 其中，被大量用于人工智能研究的卡牌游戏包括扑克牌和桥牌~\cite{schaeffer2001gamut}。

作为卡牌游戏，扑克牌（Poker）的一局对弈最多可容纳~8~名玩家。扑克牌的对弈决策包含了概率分析以及对手行为预测等多个方面~\cite{billings2003approximating,billings2002challenge}。
要成为一个扑克牌高手通常需要根据自己现有的手牌来正确估计自己的当前形势，并据此来决定自己跟或不跟。
相关的人工智能研究多数集中在研究如何通过基于现有的手牌进行多次模拟来判断当前有多大几率获胜~\cite{billings2004game}。
除此之外，也有相关研究在探索如何判断对手的决策强度，并以此对智能体进行调整。
研究显示，贝叶斯分析可被用于根据玩家已有的出牌方式来判断他正在使用的策略，甚至判断出他何时会改变自己的策略~\cite{baker2007bayesian,baker2008can}。

桥牌（Bridge）同属卡牌游戏，一局对弈包含~4~名被分为两队的玩家。在考虑到应用蒙特卡洛搜索算法可能可以使桥牌人工智能拥有更强的决策强度后，Ginsberg~运用了包含蒙特卡洛搜索算法、分部搜索~\cite{ginsberg1996partition}~以及各类优化算法在内的相关技术开发出了一款名为~GIB~的桥牌人工智能。GIB~也是首款在决策强度上能与人类桥牌大师相提并论的桥牌人工智能。

事实证明，部分传统最小最大搜索算法所不能应付的游戏，使用蒙特卡洛搜索算法时可以有不错的效果。围棋本身属于完全信息游戏，
但它与国际象棋~\cite{campbell2002deep}~等不同的地方在于，其过大的分支系数使得运用暴力搜索的人工智能难以获得良好的表现。
在无法使用简单的搜索算法来开发围棋人工智能的情况下，人们提出使用蒙特卡洛方法~\cite{brugmann1993monte}。
自此，各种不同的基于蒙特卡洛方法的搜索算法被相继提出~\cite{chaslot2006monte}，
其中包括了将蒙特卡洛方法与策略搜索相结合的搜索算法~\cite{cazenave2005combining}以及后来的蒙特卡洛树搜索算法~\cite{chaslot2007progressive}。
所有的这些算法都基于蒙特卡洛方法的基本思想：与其在决策时考虑未来每一步所有可能的走法（进而产生一棵巨大的对弈树），倒不如只考虑当前所有可能的走法，
然后使用一个随机或启发式的模拟策略将当前对弈模拟到终止状态，并根据模拟的对弈结果来更新该走法的收益值。
这背后的本质在于，当我们无法验证未来所有可能的对弈状态变化时，足够数量的随机模拟对弈的结果可以近似反映走法的期望收益。

除此之外，研究人员还提出了一种名为赌博机决策（Bandit Based Planning）的方法~\cite{kocsis2006bandit}。方法的名称来源于概率论中著名的多臂赌博机问题（Multi-armed Bandit Problem）。
该问题的内容大致如下：给定一排若干数量的赌博机，所有的这些赌博机都有着各自不同的出奖几率，那么为了获取最高的期望收益，参与者应该以何种顺序去尝试这些不同的赌博机呢？
Kocsis et al~\cite{kocsis2006bandit}~将一个可用于在多次尝试赌博机后获取最大收益的算法利用于对弈树搜索中，以找到当前的最优策略。
由此，一个名为~UCT（Upper Conficence Bounds for Trees）的算法被提出。
算法首先会对当前所有可用的策略进行一次采样，然后在一个概率模型的指导下再在所有这些策略中选取某个策略来再次采样。
如此一来，算法便能很好地在穷尽某个策略（exploitation）和探索其他策略（exploration）之间获得良好的平衡，
因为拥有高收益的策略将会被更多地采样，其他收益相对较低的策略也不会被完全抛弃，也会被不时地进行采样。
而该决策方法已在围棋上获得了巨大的成功~\cite{wang2007modifications,lee2009computational}。

与此同时，UCT~算法还被应用于普适游戏领域并获得了不错的成果~\cite{finnsson2008simulation}。
一款游戏人工智能的核心在于搜索和估价，其中搜索功能可用于预测游戏未来的走向而估价功能则可被运用于评估搜索功能发现的策略的收益。在普适游戏中，人工智能无法使用任何先验的与游戏有关的特定知识来对对弈状态进行估价，所有可用的知识只可以通过对弈的过程自行推断~\cite{clune2007heuristic}。
由于蒙特卡洛搜索算法和~UCT~算法均无需依赖于任何启发式的估价函数，它们最终都能够在普适游戏领域获得巨大的成功~\cite{sharma2008knowledge}。

在炉石传说中进行决策，最大的难点仍然在于隐藏的信息（对手的手牌不可见）以及随机性（对手和自己抽到的下一张牌不可知）。
我们需要考虑到对手的手牌可能是炉石传说~743~种卡牌中的任何一张，所有暴力的枚举算法最终都必须应对无比巨大的分支系数（考虑到巨大的分支系数正是无法为围棋开发基于暴力搜索算法的人工智能的主要原因）。
除此之外，在没有将对弈模拟至游戏结束的情况下，我们也难以开发出一个完备的效用函数对炉石传说的某个中间状态进行估价。

实际上，炉石传说并不是第一种这种类型的卡牌游戏。早在炉石传说之前，同为集换式卡牌游戏的万智牌就已经风靡全球。尽管在规则上存在着不同点，人们看到更多的是万智牌和炉石传说之间的相似之处：无论是英雄角色的定位、
卡牌种类的差异还是生物对战，万智牌和炉石传说可谓是一脉相承。最关键的是，两款游戏同样有着极大的随机性和分支系数。在~2009~年，~Cowling~和~Ward~将蒙特卡洛搜索应用于万智牌的手牌决策，
通过与随机或基于规则的生物攻击和防御智能体进行相互组合构建出了~9~种不同的智能体，并进行相互对弈~\cite{ward2009monte}。对弈的结果显示，比起使用随机或是预定义规则进行决策的智能体，
使用蒙特卡洛搜索进行手牌决策的智能体都有着相对较高的胜率，胜率的提高在~$4\%\sim7\%$~之间。到了~2012~年，他们和~Powley~一起深入研究，进而将蒙特卡洛树搜索算法应用于万智牌的手牌决策~\cite{cowling2012ensemble}。
在论文中，他们使用了确定化（Determinization）的方法来处理万智牌中带有随机效果的操作，并对比了对蒙特卡洛树搜索智能体的各项参数调整所带来的效果。结果显示，各项调整都能使智能体在胜率上提升~$5\%\sim20\%$。

实际上，确定化的思想并不新鲜，早前，该方法便已被用于处理一些概率决策问题~\cite{yoon2007ff}~以及同为卡牌游戏的斗地主~\cite{powley2011determinization}。除此之外，在上述的研究中，蒙特卡洛方法只被应用于了万智牌的手牌决策。
万智牌和炉石传说的区别在于，万智牌的玩家回合分为多个阶段，包括出牌阶段以及生物攻击阶段。玩家只能在回合的出牌阶段打出手牌，而在生物攻击阶段则只能对进行攻击的生物进行指派。上述的研究中并未将蒙特卡洛方法应用于生物的攻击和防御决策，
因此其对万智牌决策的应用是不完全的。炉石传说的玩家回合并不包含多个阶段，手牌的使用和随从的攻击可以以任意顺序进行，进行的顺序不同会导致不同的结果。这也就导致了炉石传说智能体无法将手牌决策与攻击决策相互割裂。

最近，已有相关的研究团队开始将机器学习算法应用于炉石传说~\cite{taralla2016decision}。尽管实验的结果并不理想，机器学习智能体在面对规则智能体时只能获得~$10\%$~的胜率，但随着游戏进行次数的提升，智能体的胜率也有了上升的趋势，
可见智能体已具备一定的学习能力。除此之外，也有研究团队在进行炉石传说卡组自动构建的研究~\cite{goeshoningstone}。可见，作为一款新兴的卡牌游戏，炉石传说已经引起了研究人员的注意。

本文将在~Cowling~和~Ward~的研究的基础上，将蒙特卡洛搜索和蒙特卡洛树搜索分别应用于炉石传说，并对智能体进行部分的配置调优以测试各种不同的优化能在何种程度上提高智能体的决策强度。

\section{论文结构}
\label{section:structure}

本文余下部分结构如下：第~2~章将用于讲述本文将使用的蒙特卡洛方法的基本概念；第~3~章讲述炉石传说的基本规则并给出形式化定义；第~4~章将详细描述本文实验所使用的规则智能体的组成；第~5~章则描述本文所使用的蒙特卡洛智能体；第~6~章为实验结果部分，并在第~7~章给出本文结论以及未来可能的工作方向。